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

Содержание

Содержание тестирование микропроцессоров тестовые ситуации постановка задачи предлагаемый метод оценка метода

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

/ кафедра СП ВМК МГУ

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

Слайд 2Содержание
тестирование микропроцессоров
тестовые ситуации
постановка задачи
предлагаемый метод
оценка метода

Слайд 3Место задачи в разработке аппаратного обеспечения
...
output sm_out;
reg [1:0] c, next_state;
always

@ (posedge sm_cl) begin    if (reset == 1'b1) c <= 2'b00;    else c <= next_state; end
...




проектные документы

design на Verilog

микропроцессор

тестирование design’а

Слайд 4Системное тестирование
генерация тестовых программ
эмулятор
микропроцессора
(эталон)
( на Си )
cравнение трасс
Возникла ошибка
Успешный прогон
cимуляция design’а (на Verilog)
lui

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

проводится «сравнением с эталоном»

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

Слайд 6Ситуации в MMU
классификация поведения в виде ситуаций
ситуации для отдельных инструкций:
возникновение исключительных

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

«длинные» цепочки инструкций (~10 инстр-й)

Слайд 7Ошибки в MMU
ошибки обработки управляющих битов
ошибки сопоставления тэгов
конфликты использования ресурсов


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

Слайд 8Построение нацеленных тестов
нацеленные на ситуации тесты
пример ситуации: в 1-й инструкции происходит

«деление на ноль», во 2-й – происходит кэш-промах

DIV x, y, z «деление на 0»
LOAD y, x, c «промах в L1»

ситуация в виде шаблона программы

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
DIV x,y,z
LOAD y,x,1

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

Слайд 9Задача
дан шаблон программы – (I, a1, …, an, С)*
I – инструкция

(название)
a1, …, an – параметры инструкции
С – вариант инструкции I (название отдельного пути выполнения инструкции I)
построить программу, соответствующую шаблону (I, a1, …, an)*
отношение соответствия: программа оканчивается той же цепочкой инструкций с параметрами, их исполнение в программе соответствует вариантам в шаблоне

Слайд 10Задача





s1 = f1(so)
P1(so)
s2 = f2(s1)
P2(s1)
…
(I, a1,

…, an, С)* - шаблон программы
si – состояние микропроцессора
Pi – предикат, определяющий вариант инструкции
fi – функция изменения состояния
So – множество допустимых начальных состояний

so ∈ So = ?


I(1) a1(1) … an(1)
C(1)

I(2) a1(2) … an(2)

C(2)



I(-m) a… …
I(-1) a…

= ?

специфика MMU: fi содержат функции поиска типа lookup(k,s)

Слайд 11Существующие методы построения нацеленных тестов
прямое конструирование программ (MicroTESK)
только для ситуаций из

2-3 инструкций

сведение к системам уравнений (RAVEN, Genesys-Pro)
нет информации в открытых публикациях (проприетарное ПО)

Слайд 12Схема предлагаемого подхода
ситуация
(шаблон
программы)
модель варианта инструкции1
...
модель блока1 MMU
...



1. формализовать микропроцессор
система уравнений (constraints)
начальные значения регистров
инициализ-я блока1
...
тестовая программа

2. построение уравнений

3. решение уравнений

4. составление текста тестовой

программы

ручная работа

автоматизированная

DIV x, y, z «деление на 0»
LOAD y, x, c «промах в L1»

Слайд 13Схема предлагаемого подхода
ситуация
(шаблон
программы)
модель варианта инструкции1
...
модель блока1 MMU
...



1. формализовать микропроцессор
система уравнений (constraints)
начальные значения регистров
инициализ-я блока1
...
тестовая программа

2. построение уравнений

3. решение уравнений

4. составление текста тестовой

программы

ручная работа

автоматизированная

Слайд 14Модель блока MMU
пример:
какие блоки MMU нужны для ситуации (кэш, таблица страниц,

TLB)
блок моделируется ассоциативным массивом
модель блока – значения заданных характеристик:
структурные характеристики
поведение строк блока

L1 {
policy=LRU; lines=4;
regbits=7;
key(tag:24);
data(d:32); keyMatch(k:30) {
k[29:6] = tag
};
}

Слайд 15Схема предлагаемого подхода
ситуация
(шаблон
программы)
модель варианта инструкции1
...
модель блока1 MMU
...



1. формализовать микропроцессор
система уравнений
начальные значения регистров
инициализ-я блока1
...
тестовая программа

2. построение уравнений

3. решение уравнений

4. составление текста тестовой

программы

ручная работа

автоматизированная

Слайд 16Модель варианта инструкции
пример:
отдельный путь выполнения инструкции
в виде утверждений о свойствах битовых

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

LOAD (y,x,c)
«промах в L1»
[var y:64; var x:64; const c:16;]

phys <- x + (64)c; assume: phys[1:0]=0^2
miss(phys) {replace(y)};
hit(phys)
{load(y)};

Слайд 17Схема предлагаемого подхода
ситуация
(шаблон
программы)
модель варианта инструкции1
...
модель блока1 MMU
...



1. формализовать микропроцессор
система уравнений
начальные значения регистров
инициализ-я блока1
...
тестовая программа

2. построение уравнений

3. решение уравнений

4. составление текста тестовой

программы

ручная работа

автоматизированная

Слайд 18Построение уравнений: этап 1
ситуация
hit(miss) pi
hit(miss) pi+1
. . .

цепочка промахов/ попаданий в блок1
load(store) qi,di
load(store) qi+1,di+1
.

. .


цепочка загрузки/ сохранения данных в блоке1

. . .

. . .


phys = x + (64)c

phys[1:0] = 0^2

. . .

условия на значения регистров, адресов, других промежуточных значений

модели вариантов инструкций

модели блоков MMU


Слайд 19Построение уравнений: этап 2
hit(miss) pi
load(store) qi,di
phys[1:0] = 0^2
(свойства битовых строк)
система уравнений

(битовая и целочисленная арифметика)

Hit [pi] = pi ∈{p1,…,pi-1} Λ ¬Ev(p1,…,pi-1; pi)

Miss [pi] = pi ∈{p1,…,pi-1} Λ Ev(p1,…,pi-1; pi)

равенство данных при равных адресах

phys[1:0] = 0^2 (без изменений)

это новые методы

модели блоков MMU






Слайд 20Схема предлагаемого подхода
ситуация
(шаблон
программы)
модель варианта инструкции1
...
модель блока1 MMU
...



1. формализовать микропроцессор
система уравнений
начальные значения регистров
инициализ-я блока1
...
тестовая программа

2. построение уравнений

3. решение уравнений

4. составление текста тестовой

программы

ручная работа

автоматизированная

DIV x, y, z «деление на 0»
LOAD y, x, c «промах в L1»

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


Слайд 21Теоремы корректности и полноты методов построения уравнений
доказана корректность: если предлагаемые методы

построят систему уравнений для шаблона, которая будет совместной, то ее решение будет удовлетворять шаблону

доказана полнота: если для шаблона существует тест, то предлагаемые методы строят систему уравнений, среди решений которой есть этот тест (если она несовместна, то шаблону не соответствует ни один тест)

Слайд 22Новизна
ситуация
(шаблон
программы)
модель варианта инструкции1
...
модель блока1 MMU
...


система уравнений
начальные значения регистров
инициализ-я блока1
...
тестовая программа
I. модели вариантов инструкций и блоков MMU
II. методы построения уравнений
III.

написана программа, строящая уравнения

Слайд 23Особенности предлагаемых методов
блоки инициализируются цепочкой обращений в них по адресам –

адреса вычисляет решатель уравнений
единая система уравнений
компактность уравнений (в них выражается не изменение состояния, а зависимости адресов)


Слайд 24Где предлагаемые методы работают
многоуровневая кэш-память
обращение в память с / без

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

Слайд 25Направления развития
псевдослучайное вытеснение
псевдослучайный выбор блоков MMU в инструкции
временные ограничения (длительности,

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

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

Слайд 26Реализация

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

Слайд 27Практическое использование
микропроцессор архитектуры MIPS
блоки MMU в микропроцессоре:
кэш L1 16кБ
кэш L2 256кБ
TLB

48 строк (по 2 страницы в строке)
microTLB 4 строки

Слайд 28Эксперименты
увеличение допустимого размера шаблонов (было 2-3, стало 9-12)
среднее время построения одного теста –

1-30с.

Слайд 29Публикации
1. статья в «Программировании» [из списка ВАК]
2. статья в «Вычислительных методах

и программировании»
3-4. статьи на SYRCoSE-2008 и 2009
5. статья на EWDTS-2009
6-7. статьи в сборниках трудов ИСП РАН (тт.15, 17)

Слайд 30Апробация
конференции:
SYRCoSE-2008
SYRCoSE-2009
EWDTS-2009
Микроэлектроника и информатика-2009
The Ph.D. Summer School on Scientific Computing 2009
Ломоносов-2009, 2010
Тихоновские

чтения-2009
Ломоносовские чтения-2010
семинары:
семинар отдела Технологий программирования ИСП РАН
научно-исследовательский семинар им. М.Р.Шура-Бура

Слайд 31Результаты
модель блока MMU, описывающая его характеристики
модель инструкции в виде совокупности отдельных

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

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

status="readonly" />                     rs            
rs    
 
    
            rt
            
rt
    
 
    
                
rs
                    
rs
                
                
                     rt
                     
rt 
                

    
            temp

            temp

    

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

Слайд 33Уравнения (constraints)

Слайд 34Уравнения (constraints)

Слайд 35Теоремы о количестве адресов, инициализирующих блок
общий случай: m ≤ n ·

(n + 2w)

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

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

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

Слайд 37Схема предлагаемого подхода
ситуация S
(шаблон
программы)
модель инструкции1 в ситуации S
...
модель блока1 MMU
...



1. формализовать микропроцессор
система уравнений
начальные значения регистров
инициализ-я блока1
...
тестовая программа

2. построение уравнений

3. решение

уравнений


4. составление текста тестовой программы

ручная работа

автоматизированная

Слайд 38Шаблоны и их связь с моделями инструкций и моделями блоков MMU
DIV

x, y, z «деление на 0»
LOAD y, x, c «промах в L1»

ситуация в виде
шаблона программы

DIV (x,y,z) «деление на 0» {
…
}

LOAD (y,x,c) «промах в L1» {
…
... L1 ...
}


модели инструкций


модели блоков MMU

L1 {
…
}

модели инструкций формализуют, как должны работать инструкции
модели блоков MMU формализуют кэши, таблицы страниц, ...

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

Похожие презентации

Элитная вилла 116,30 кв.м, трехэтажная, каменная. Состоит в основном из дома, состоящим из одной спальни, 1 кухни, 1 столовой, 1 гостиной с камином, 1 ванной комнаты, 1 WC, 2 веранды, и автономной гостевой. Имеются подвальный гараж, бассейн, частный и 158
Активизация предпринимательской деятельности в университете 213
первое задание 167
Ц у н а м и 207
Развитие жилищно-коммунального комплекса и энергетики в Ханты-Мансийском автономном округе – Югре в 2013 году 173
Настройка DHCP с использованием назначения на основе Microsoft Windows Server 475

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

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

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

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

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

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

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