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

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

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

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

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

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

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

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

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

Новизна - где здесь нерешенная задача? для оперирования с регистрами-битовыми строками ничего нового придумывать не надо - ограничения уже записаны в нужном виде в тестовом шаблоне или модели микропроцессора overflow(x,y) : t

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

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

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

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

Изменение содержимого кэш.буфера как множества для инструкции с попаданием - в ней происходит обращение в буфер по ключу 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)

Другие результаты диссертации 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' ? (ограничения большого размера крайне долго разрешаются) второй результат дисс. третий результат дисс.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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