'

Исследование и разработка методов построения тестовых программ для тестирования 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


Слайд 4

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


Слайд 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

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

Итак, второй результат диссертации набор эвристик построения ограничений для кэш-попаданий и кэш-промахов совместная эвристика - если есть обращения к нескольким связанным буферам x \in L0 \inter T0 /\ x не вытеснен   \/   ... зеркальная эвристика - у каждого адреса есть "зеркало" x \in {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) вытеснение - это всегда некая экстремальная ситуация, некая функция в момент вытеснения достигает своего экстремума этой функцией является количество инструкций, способствующих вытеснению (если их достаточно, происходит вытеснение) для выражения этой идеи достаточно для стратегии вытеснения определить понятие способствующей к вытеснению инструкции --- и тогда вытеснение опишется ограничением \Sigma_{i}  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 минут Слайды должны отражать суть диссертации, показывать ее результаты


Слайд 31

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


Слайд 32

История вопроса конец 1970-х начало 1980-х - автоматизация проектирования микропроцессоров


×

HTML:





Ссылка: