'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

Подсистемы управления памяти (MMU)


Слайд 2

Системное тестирование эмулятор микропроцессора (эталон) ( на Си ) cравнение трасс Возникла ошибка Успешный прогон программная модель (на Verilog) lui s1,0x27 ori s1,s1,0xc8 lui s3,0x4e ori s3,s3,0xf7 ... проводится «сравнением с эталоном» тестовые программы


Слайд 3

Тестовые шаблоны 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 тестовая программа инициализирующая цепочка инструкций цепочка инструкций тестового шаблона


Слайд 4

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


Слайд 5

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


Слайд 6

Эксперименты УБРАТЬ КРАСНУЮ ЛИНИЮ !!! увеличение допустимого размера шаблонов (было 2-3, стало 11-12) среднее время построения одного теста – 1-30с.


Слайд 7

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


Слайд 8


Слайд 9

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


Слайд 10

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


Слайд 11

12 Реализация существующий генератор шаблонов описания вариантов инструкций (xml) конструктор текстов asm (Java) ~100стр. на вариант исполнения инструкции ~2000стр. ~1000стр. ограничения (smt) 100-500стр. генератор ограничений (ruby) описания устройств MMU (xml) ~10стр. на блок шаблон теста решение ограничений тесты (asm)


Слайд 12

Примеры описаний инструкций <situation>     <argument name="rd" length="64" status="readonly" />     <argument name="rs" length="64" status="readonly" />     <argument name="rt" length="64" status="readonly" />     <assume><eq>             <bits end="63" start="32"><var>rs</var></bits>             <power index="32"><bit index="31"> <var>rs</var></bit></power>     </eq></assume>       <assume><eq>             <bits end="63" start="32"><var>rt</var></bits>             <power index="32"><bit index="31"> <var>rt</var></bit></power>     </eq></assume>       <let name="temp"><sum>                 <concat> <bit index="31"><var>rs</var></bit>                     <bits end="31" start="0"> <var>rs</var></bits>                 </concat>                 <concat>                      <bit index="31"><var>rt</var></bit>                      <bits end="31" start="0"> <var>rt</var></bits>                  </concat></sum></let>     <assume><neq>             <bit index="32"><var>temp </var></bit>             <bit index="31"><var>temp </var></bit>     </neq></assume> </situation> арифметическое переполнение ADD rd, rs, rt


Слайд 13

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


Слайд 14

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


Слайд 15

Теоремы о длине инициализирующей цепочки общий случай: m ? n · (n + 2w) для LRU: m ? n · w + M n – количество промахов/попаданий (~ длина шаблона) M – количество промахов w – ассоциативность блока


Слайд 16

Метод построения уравнений для стратегий вытеснения 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} )


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

Направления исследований стратегий вытеснения эффективность стратегий вытесн. способы определения стратегий вытесн. ? после обращения 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))


Слайд 21

Метод полезных обращений подобрать функцию 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)


Слайд 22

Метод полезных обращений подобрать функцию 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)


Слайд 23

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


Слайд 24

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


×

HTML:





Ссылка: