Презентация на тему Построение тестовых программ для проверки подсистем управления памяти микропроцессоров

Презентация на тему Построение тестовых программ для проверки подсистем управления памяти микропроцессоров, предмет презентации: Разное. Этот материал содержит 33 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

Построение тестовых программ для проверки подсистем управления памяти микропроцессоров

Корныхин Евгений Валерьевич

научный руководитель: д.ф.-м.н. Петренко Александр Константинович


Слайд 2
Текст слайда:

Актуальность: подсистемы управления памяти (MMU)


Слайд 3
Текст слайда:

Системное тестирование Задача

эмулятор
микропроцессора
(эталон)
( на Си )

cравнение трасс

Возникла ошибка

Успешный прогон

программная модель




(на Verilog)

lui s1,0x27
ori s1,s1,0xc8
lui s3,0x4e
ori s3,s3,0xf7 ...

тестовые программы

Задача – построение тестовых программ


Слайд 4
Текст слайда:





Тестовые шаблоны и тестовые программы

STORE x, y, z «page fault»
LOAD y, x, c «промах в кэше»

тестовый шаблон

MOV x,0 MOV y,0
STORE y,x,3
STORE y,x,9 STORE y,x,7 STORE y,x,5
MOV z,0
STORE x,y,z
LOAD y,x,1

тестовая программа


инициализирующая цепочка инструкций


цепочка инструкций тестового шаблона


Слайд 5
Текст слайда:

Сложность построения тестовых программ по тестовым шаблонам

переборная задача сводится к решению систем уравнений и неравенств («ограничений»)


Слайд 6
Текст слайда:

Предлагаемая схема автоматической генерации тестовых программ


генератор системы ограничений

конструктор текста программы

решатель ограничений

тестовый шаблон

тестовая программа

описания вариантов исполнения инструкций

описания устройств

ограничения для промахов и попаданий

ограничения для всего шаблона


Слайд 7
Текст слайда:

Эксперименты

увеличение допустимого размера шаблонов (было 2-3, стало 11-12)


Слайд 8
Текст слайда:

Основные результаты

Предложен подход к построению тестовых программ, позволяющий понизить трудоемкость построения некоторых классов тестовых программ
Предложен метод формализации механизма вытеснения при помощи ограничений, эффективно разрешаемых современным инструментарием
Создан прототип генератора тестовых программ, при помощи которого исследована эффективность предложенных решений


Слайд 9

Слайд 10
Текст слайда:

Основные результаты

Создан язык для описания вариантов исполнения инструкций ПУП широкого класса современных микропроцессоров, для которого разработаны формальные определения синтаксиса и семантики.
Построена математическая модель последовательной ПУП, в рамках которой сформулирован алгоритм формирования системы ограничений на значения аргументов инструкций тестовой программы. Свойства корректности и полноты этого алгоритма доказаны.
Предложен метод полезных обращений, позволяющий сократить число ограничений на значения аргументов инструкций тестовой программы для случаев вытеснения элемента из кэш-памяти. Получены оценки минимально необходимой длины инициализирующей последовательности инструкций для основных стратегий замещения в кэш-памяти (LRU, Pseudo-LRU, FIFO).
На основе предложенных моделей и методов создан прототип системы построения тестовых программ для проверки ПУП микропроцессоров архитектуры MIPS64 и экспериментально показана его эффективность.


Слайд 11
Текст слайда:

Где предлагаемые методы работают

многоуровневая кэш-память
обращение в память с / без виртуальной памяти
сквозная запись / отложенная запись
доп.условия на строки кэш-памяти
virtually indexed кэш-память
virtually tagged кэш-память


Слайд 12
Текст слайда:

Направления развития

псевдослучайное вытеснение
псевдослучайный выбор блоков MMU в инструкции
временные ограничения (длительности, зависимости от скорости выполнения)
циклические действия (итеративная реализация sqrt)
кэш-память инструкций
многоядерные микропроцессоры

 
тестирование, нацеленное на эти особенности, надо проводить иначе


Слайд 13
Текст слайда:

Реализация


существующий генератор
шаблонов

описания вариантов инструкций
(xml)

конструктор текстов asm (Java)

~100стр. на вариант исполнения инструкции

~2000стр.

~1000стр.

ограничения (smt) 100-500стр.

генератор ограничений (ruby)

описания устройств MMU (xml)

~10стр. на блок

шаблон теста

решение ограничений

тесты
(asm)


Слайд 14
Текст слайда:

Примеры описаний инструкций

                            rs            
rs
   

 
    
            rt
            
rt

    

 
    
                
rs
                    
rs

                

                
                     rt
                     
rt
 
                

    
            temp

            temp

    

арифметическое переполнение
ADD rd, rs, rt


Слайд 15
Текст слайда:

Уравнения (constraints)


Слайд 16
Текст слайда:

Уравнения (constraints)


Слайд 17
Текст слайда:

Теоремы о длине инициализирующей цепочки

общий случай: m ≤ n · (n + 2w)

для LRU: m ≤ n · w + M

n – количество промахов/попаданий (~ длина шаблона)
M – количество промахов
w – ассоциативность блока


Слайд 18
Текст слайда:

Метод построения уравнений для стратегий вытеснения

Ev(x1,…,xi;x) = ( ux(x1) + … + ux(xi) > C )
C – константа (значение зависит от стратегии вытеснения)
ux(xk) = 1, если xk «способствует вытеснению» x; 0, иначе
для LRU: ux(xk) = ( x∉{xk,…,xi} Λ xk∉{xk+1,…,xi} )


Слайд 19
Текст слайда:

Основные определения

Адрес – вектор целых неотрицательных чисел
Данные – вектор целых неотрицательных чисел
Состояние устройства S : A → D, A – конечное множество адресов, D – конечное множество данных, |def(S)| = const
Строка – пара (x, S(x)), x ∈ def(S)
Обращение к устройству – это адрес («обращение по адресу»)


Слайд 20
Текст слайда:

Основные определения

Данные по адресу x присутствуют (или, находятся) в устройстве : x ∈ def(S)
Данные по адресу x не присутствуют (или, не находятся) в устройстве : x ∉ def(S)
Попадание – обращение по адресу x к устройству, если x ∈ def(S)
Промах – обращение по адресу x к устройству, если x ∉ def(S)


Слайд 21
Текст слайда:

Основные определения

Стратегия вытеснения – это пара функций (Policy, Ev), Policy: S x A → S, Ev: S → A :





x – вытесняемая строка, если x = Ev(S)


Слайд 22
Текст слайда:

Направления исследований стратегий вытеснения

эффективность стратегий вытесн.
способы определения стратегий вытесн.
⬄ после обращения x1. затем x2, …, затем xn данные по адресу x не присутствуют в устройстве
x1, x2 , … , xn таковы, что ∀ S’, S’’ Policy(Policy(…Policy(S’, x1), x2), … , xn) = Policy(Policy(…Policy(S’’, x1), x2), … , xn) ≡ P(x1, x2 , … , xn)
D(x1, x2 , … , xn; x) ≡ x ∉ def(P(x1, x2 , … , xn))


Слайд 23
Текст слайда:

Метод полезных обращений

подобрать функцию a: A* x A → N такую, что
∃ a’, a’’: a’ ≤ a’’
¬ D(x1 , x2 , … , xn ; x) ⬄ a’ ≤ a(x1 , x2 , … , xn ; x) ≤ a’’
a(x1 , x2 , … , xn , x ; x) = a’
∃ f: a(x1 , x2 , … , xn+1 ; x) = f(a(x1 , x2 , … , xn ; x), x1 , x2 , … , xn+1 , x)

f(a, x1 , x2 , … , xn , x) = f(a, xn , x )
∃! x’: a(x1 , x2 , … , xn ; x’) = a’’
a(x1 , x2 , … , xn ; Ev(x1 , x2 , … , xn )) = a’’
(xi = x /\ x∉{xi+1 , xi+2 , … , xn} /\ Ev(x1 , x2 , … , xn) = x) ⇒ (ai ≤ ai+1 ≤ … ≤ an /\ ∀k=i+1..n |ak- ak-1|≤1)


Слайд 24
Текст слайда:

Метод полезных обращений

подобрать функцию a: A* x A → N


C = a’’ - a’
пусть ai = a(x1, x2 , … , xi ; x)
до i* ux(x1, x2 , … , xi) ≡ 0
после i* ux(x1, x2 , … , xi) ≡ (ai > ai-1)


Слайд 25
Текст слайда:

Ситуации в MMU

ситуации для отдельных инструкций:
возникновение исключительных ситуаций
промахи/попадания в кэшах разных уровней, в TLB
кэшируемые/некэшируемые обращения в память
отображаемые/неотображаемые вирт.адреса
ситуации для цепочек инструкций:
чтение регистра после записи в него
обращения по одинаковым/разным физическим/виртуальным адресам
чтение после записи ячейки памяти
одинаковые/разные страницы вирт.памяти
одинаковые/разные строки кэш-памяти
запись/чтение совместно с исключит.ситуациями


Слайд 26
Текст слайда:

Ошибки в MMU

ошибки обработки управляющих битов
ошибки сопоставления тэгов
конфликты использования ресурсов
ошибки обновления/вытеснения данных
ошибки синхронизации данных
ошибки планирования обработки запросов
ошибки, вызванные исключениями


Слайд 27
Текст слайда:

Теорема корректности алгоритма генерации ограничений


Слайд 28
Текст слайда:

Теорема полноты алгоритма генерации ограничений


Слайд 29
Текст слайда:

Теоремы о существенной вытесняе-мости ряда стратегий вытеснения


Слайд 30
Текст слайда:

Теорема корректности метода полезных обращений для LRU


Слайд 31
Текст слайда:

Теорема корректности метода полезных обращений для PseudoLRU


Слайд 32
Текст слайда:

Теорема корректности метода полезных обращений для PseudoLRU


Слайд 33
Текст слайда:

Теорема корректности метода полезных обращений для PseudoLRU


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика