'

Исследование и разработка методов построения тестовых программ для тестирования MMU

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





Слайд 0

Исследование и разработка методов построения тестовых программ для тестирования MMU  


Слайд 1

Актуальность Качественное тестирование - актуальная проблема Тестирование микропроцессора тестами-программами часто применяется на практике Построение тестов для качественного тестирования - актуальная проблема Нацеленная генерация программ - генерация программ с особым исполнением (особыми происходящими событиями) и особой структурой, например, чтобы произошло переполнение Для программ из 1-2 инструкций построить программу для заданной цели несложно, а для 10-15 инструкций сложно В одной инструкции может происходить несколько событий, поскольку в исполнении инструкций участвует много подсистем микропроцессора Для сложных целей случайная генерация плохо работает Существующие инструменты - закрытые или работают лишь для небольших тестов


Слайд 2

Задача Тестовый шаблон - отражает особенности исполнения и структуры программы, он задан (какие инструкции, что происходит в микропроцессоре при их исполнении)   Задача: построить программу (на языке ассемблера), удовлетворяющую тестовому шаблону объект исследования - особые тестовые шаблоны (а значит и особые способы построения программ)


Слайд 3

Иллюстрация задачи (1) тестовый шаблон:   MOV x, y    @ y > 10     ;; x := y   and y > 10 тестовая программа: MOV y, 11 MOV x, y ;; здесь y > 10


Слайд 4

Иллюстрация задачи (2) тестовый шаблон: ADD x, y, z    @ overflow     ;; x := y + z with overflow тестовая программа: MOV y, 2147483648 MOV z, 2147483650 ADD x, y, z ;; x = 2 : overflow


Слайд 5

Иллюстрация задачи (3) тестовый шаблон: LOAD x, y, c    @ l1Hit  ;; загрузка в x данных из ;; памяти по виртуальному  ;; адресу (y+c)   ;; при этом должно  ;; произойти l1Hit тестовая программа: MOV y, 123 LOAD u, y, 0 LOAD x, y, 0 может быть и другая:   MOV y, 2041 LOAD x, y, 5


Слайд 6

Перспективный алгоритмический аппарат: ограничения (constraints) разрешение ограничений / задача ВЫПОЛНИМОСТЬ (SAT, CSP) - поиск значений переменных предиката, на которых он истинен один из фундаментальных способов решения поисковых задач (поиск объектов, для к-х выполнены отношения) SAT -- алгоритмически сложная задача для предикатов общего вида SMT - SAT для предикатов над битовыми строками, термами, линейная арифметика - перспективный аппарат  


Слайд 7

Что нужно для построения программ тестовый шаблон содержит особенности нужной программы, но этого мало - нужна модель микропроцессора   модель микропроцессора - семантика инструкций, структурные особенности микропроцессора формулы, диссертация – способы построения формул какие формулы? как их строить?


Слайд 8

Тестовый шаблон - это отношения на переменных  


Слайд 9

Новизна - где здесь нерешенная задача? для оперирования с регистрами-битовыми строками ничего нового придумывать не надо – формулы (ограничения) в явном виде записаны в тестовом шаблоне или модели микропроцессора: ADD @ overflow(x,y) :   t <- x[31]||x + y[31]||y;   t[32] != t[31] LOAD @ l1Hit(x,y) : ???  что такое l1Hit ? l2Miss ? что вообще возможно на его месте в тестовом шаблоне?


Слайд 10

Первый результат диссертации При работе с памятью задействованы разные подсистемы микропроцессора -- в них могут происходить разные события... НО зачастую эти подсистемы можно разделить на 2 класса: кэширующие буферы таблицы (в диссертации проанализированы архитектуры Pentium, PowerPC, MIPS, Alpha) а что это?


Слайд 11

Кэширующие буферы и таблицы (1) множество пар «(ключ,значение)» происходят обращения по ключу ситуация «попадания» - наличие ключа ситуация «промаха» - отсутствие ключа Отличие кэш.буферов от таблиц: промах в кэш.буфере устраняется микропроцессором автоматически (стратегия вытеснения), а в таблице нет


Слайд 12

Кэширующие буферы и таблицы (2) примеры - хранение последних [обращений в память/осуществленных трансляций адресов] изменение содержимого таблицы выполняется специальными подпрограммами, они пишутся вручную, это часть операционной системы (пример - подгрузка страницы виртуальной памяти из свопа) - поэтому внутри тестовых шаблонов изменение таблиц не производится!


Слайд 13

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


Слайд 14

Изменение содержимого кэш.буфера как множества для инструкции с попаданием - в ней происходит обращение в буфер по ключу x - составляем ограничение x ? L L - текущее содержимое кэш.буфера после инструкции L не меняется для инструкции с промахом: x ? L в следующей инструкции вместо L будет (L\{x`}  ? {x}) Итого x ?/? L0 \ {x'1,x'2,...,x'n} ? F(x1,x'1,x2,x'2,...,xn,x'n)


Слайд 15

Другие результаты диссертации x ?/? L0 \ {x'1,x'2,...,x'n} ? F(x1,x'1,x2,x'2,...,xn,x'n)   в диссертации решаются                  проблема 1:                                           проблема 2:    L0 имеет большой размер               как определить x'i ?        (ограничения     большого размера     крайне долго    разрешаются)             второй результат дисс.         третий результат дисс.


Слайд 16

Результат: уменьшить множество констант если в инструкции задействованы несколько буферов (L0 и T0), то можно использовать лишь L0 ? T0. (пример: буфер, хранящий последние странслированные страницы виртуальной памяти, и кэш-память: нужно оставить лишь ту часть кэш-памяти, которая может быть получена в результате трансляции виртуального адреса в физический)


Слайд 17

Результат: или совсем избавиться от множества констант! вводим дополнительные адреса t1, t2, ...,tm, по ним надо сделать обращения, чтобы подготовить кэш.буфер попадание по ключу x будет тогда, когда по нему было обращение и после этого он не вытеснен промах по ключу x будет тогда, когда по нему было обращение и после этого он вытеснен получаются ограничения без констант (у них и размер небольшой), например:    x ? { t1, t2, ..., tm, x1, x2, ..., xn }    х не вытеснен                         --  как это записать ?


Слайд 18

Итак, второй результат диссертации набор эвристик построения ограничений для кэш-попаданий и кэш-промахов совместная эвристика - если есть обращения к нескольким связанным буферам x ? L0 ? T0 /\ x не вытеснен   \/   ... зеркальная эвристика - у каждого адреса есть "зеркало" x ? {t1,...,xn} /\ x не вытеснен (для эвристик доказана корректность и условная полнота) как выразить это свойство?


Слайд 19

Что известно для решения новой задачи?         1. стратегия вытеснения для каждого кэширующего буфера (LRU, FIFO, PseudoLRU) LRU: вытесняется то,к чему дольше остального не было обращения FIFO: вытесняется то,что было добавлено в буфер раньше остального             2. для выражения ограничений можно использовать лишь переменные x, L0, x1, ..., xn


Слайд 20

Есть способ моделирования стратегии вытеснения на "перестановках" каждый элемент кэш.буфера попадает в свой вектор и остается в нем до вытеснения каждая инструкция переставляет элементы вектора, возможно с заменой вытесняемого элемента вытесняющим стратегия вытеснения задается матрицей "перестановок" (policy table [Grund,Reineke-2008])


Слайд 21

"Жизнь" элемента в векторе   если посмотреть на перестановки с точки зрения одного, выделенного, элемента вектора, то его "жизнь" заключается в перемещении от момента помещения в вектор до момента вытеснения


Слайд 22

Было замечено, что (1) с некоторого момента в перемещениях выделенного элемента начинается монотонное стремление к позиции вытеснения (диапазон вытеснения) предлагается такое рассуждение: некоторая часть тестового шаблона образует "диапазон вытеснения" - выделить эту часть и записать ее в виде ограничений диапазон вытеснения для LRU: "в нем встречаются обращения ко всем остальным элементам вектора": {xi, xi+1, ..., xn} = L \ {x}


Слайд 23

Было замечено, что (2) вытеснение - это всегда некая экстремальная ситуация, некая функция в момент вытеснения достигает своего экстремума этой функцией является количество инструкций, способствующих вытеснению (если их достаточно, происходит вытеснение) для выражения этой идеи достаточно для стратегии вытеснения определить понятие способствующей к вытеснению инструкции --- и тогда вытеснение опишется ограничением ?i=1,2,..,n  u(xi) ? C u : адрес -> {0,1} - функция полезности инструкции


Слайд 24

Тем самым третий результат диссертации методы построения ограничений, описывающих стратегии вытеснения метод диапазонов вытеснения метод функций полезности   для обоих методов в диссертации представлены ограничения для стратегий вытеснения LRU, FIFO, PseudoLRU - самых частых в микропроцессорах (для ограничений доказана эквивалентность определениям на перестановках) Для PseudoLRU предложено определение "на бинарном дереве", помогающее построить диапазоны вытеснения и функции полезности


Слайд 25

Эксперименты время генерации, КПД


Слайд 26

Публикации Kornikhin E. Test Data Generation for Arithmetic Subsystem of CPUs MIPS64 // Proceedings of SYRCoSE'08, 2008 Корныхин Е.В. Генерация тестовых данных для тестирования арифметических операций центральных процессоров // Труды ИСП: том 15, 2008 Корныхин Е.В. Система генерации тестовых программ с использованием ограничений ТЕСЛА // "Ломоносов-2009", 2009 Корныхин Е.В. Система генерации тестовых данных для системного функционального тестирования микропроцессоров ТЕСЛА // "Микроэлектроника и информатика-2009", 2009 Корныхин Е.В. Генерация тестовых данных для системного функционального тестирования FIFO-кэш-памяти микропроцессоров // журнал "Вычислительные методы и программирование", вып.10, 2009 Kornikhin E. Test Data Generation for LRU Cache-Memory testing // SYRCoSE'09 Kornikhin E. SMT-based Test Program Generation for Cache-memory Testing // East and West-2009 Корныхин Е.В. Генерация тестовых данных для системного функционального тестирования микропроцессоров с учетом кэширования и трансляции адресов // Труды ИСП: том 17, 2009. Корныхин Е.В. Генерация тестовых данных для тестирования механизмов кэширования и трансляции адресов микропроцессоров // Программирование, 36(1), 2010


Слайд 27

Выступления на конференциях SYRCoSE'2008 Ломоносов-2009 Микроэлектроника и информатика-2009 SYRCoSE'2009 East and West-2009 The Ph.D. Summer School on Scientific Computing 2009 Тихоновские чтения-2009


Слайд 28

Результаты Модель MMU (как условие применимости методов) Методы генерации ограничений для тестовых ситуаций в кэширующих буферах Методы генерации ограничений для описания стратегий вытеснения


Слайд 29

конец


Слайд 30

Требования к этим слайдам! Слайды должны читаться без докладчика Слайды должны быть понятны постороннему человеку Весь рассказ не должен превышать по времени 30 минут Слайды должны отражать суть диссертации, показывать ее результаты


×

HTML:





Ссылка: