'

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

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





Слайд 0

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


Слайд 1

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


Слайд 2

Системное функциональное тестирование стимулы реакции оракул покрытие


Слайд 3

Генерация стимулов стимулы абстрактные стимулы последовательность имен инструкций зависимости аргументов разных инструкций зависимости аргументов одной инструкции события в MMU при исполнении инструкций


Слайд 4

Определения Тестовый шаблон Тестовая программа (инициализ.) Отношение соответствия LW x, y, c1 @ miss SB y, x, c2 @ hit MOV x, 0 MOV y, 25 LW 0, 25, 0 LW x, y, 0 SB z, u, 10 инициали зация тестовое воздействие


Слайд 5

Шаблон c большим количеством зависимостей ADD x, y, z @ overflow LD u, x, c1 @ miss /\ pagecross SB y, u, c2 @ hit /\ tagequals(2) DIV u, y, z @ normal


Слайд 6

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


Слайд 7

Простые шаблоны: комбинаторные методы ADD x, y, z LD u, x, c1 SB y, u, c2 DIV u, y, z x, y, z, u, c1, c2 ? {0, 1}


Слайд 8

Genesys-Pro: трудоемкое построение генератора программ Пользователь задает ограничения, инструмент собирает из них системы ограничений и разрешает их ADD x, y, z @ overflow LD u, x, c1 @ miss /\ pagecross y != z /\ … c1[1] = 0 /\ … Miss(x, c1) …


Слайд 9

Трудности генерации стимулов большое количество зависимостей выразительность шаблонов трудоемкость подготовки генератора стимулов


Слайд 10

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


Слайд 11

Последовательности обращений к «таблицам» в MMU Тестовый шаблон = битовые и арифметические отношения на переменных + последовательность обращений к внутренним «таблицам», для которых известны события LW x, y, c: virt := y + c; AddrTrans(virt, phys); phys[2:0] := 8 – phys[2:0] LoadMemory(phys,data); x := data[virt[2:0]:0]


Слайд 12

«совместная» эвристика: уменьшать множества констант x f(x) T L x?T f(x)?L ? x?T’ x?T?T’ f(x)?L[T’]


Слайд 13

«зеркальная» эвристика: вообще избавиться от множеств констант hit/miss hit/miss hit/miss hit x hit/miss hit/miss hit/miss miss x нет зависимости от множества констант перед первой инструкцией!


Слайд 14

Кэш-попадания/промахи hit(x) ? x ? L miss(x) ? x ? L, x’ = displaced(L), L’ = L\{x’} ? {x} L = L0 \ {x’1, …, x’n} ? X hit(x) = x ? L0 /\ x ? {x’1, …, x’n} \/ (x = xi /\ x ? {x’i+1,…, x’n})_i miss(x) = x ? L0 /\ x ? {x1, …, xn} \/ (x = x’i /\ x ? {xi+1, …, xn})_i


Слайд 15

Совместное обращение в MIPS vpn pfn tag virtual = ?(y, c) LOAD x, y, c x := mem[y+c] tag ? L0 vpn ? V0 vpn pfn ? pfn ? P0 tag = pfn[..] ? tag ? L0?[P0]


Слайд 16

Зеркальная генерация добавляем несколько «инициализирующих тегов» перед тестовым шаблоном hit(x) ? (x = xi /\ с момента этого обращения х не вытеснен)_i miss(x) ? (x = xi /\ с момента этого обращения х вытеснен)_i количество инициализирующих ? n*w + M (для LRU)


Слайд 17

Стратегия вытеснения x’ = displaced(L) hit(x) = x ? L0 /\ x ? {x’1, …, x’n} \/ (x = xi /\ x ? {x’i+1,…, x’n})_i hit(x) = x ? L0 /\ x еще не вытеснен \/ (x = xi /\ x не вытеснен)_i miss(x) = x ? L0 /\ x ? {x1, …, xn} \/ (x = x’i /\ x ? {xi+1, …, xn})_i miss(x) = x ? L0 /\ x ? {x1, …, xn} \/ (x?L0?{x1, …, xn} /\ x уже вытеснен)


Слайд 18

Стратегия вытеснения метрика вытеснения miss max


Слайд 19

Монотонная, немонотонная метрика вытеснения LRU, FIFO PseudoLRU


Слайд 20

Перебор диапазонов вытеснения «Диапазон вытеснения» - отрезок тестового шаблона, непосредственно влияющий на вытеснение Перебираем всевозможные диапазоны вытеснения и формируем ограничения на них


Слайд 21

Пример диапазона вытеснения … hit/miss xi hit/miss xi+1 … hit/miss xn miss x x’ = xi {xi+1,…,xn} = L\{x’} LRU


Слайд 22

Функции полезности инструкций Инструкция полезная для вытеснения (или просто полезная), если она способствует вытеснению некоторого тега Вытеснение происходит, когда количество полезных инструкций превышает некоторую границу Функция полезности полезной инструкции = 1, неполезной = 0


Слайд 23

Фактически методы основываются на представлении стратегии вытеснения, как замены некоторого элемента, расположенного в специальном месте («в конце») LRU, FIFO, PseudoLRU являются такими


Слайд 24

Пример функции полезности x x xi xi x x xi xi 1 2 … w 1 2 … w бесполезное обращение полезное обращение LRU x = ad не вытеснен : ? u(xi) ? w-d u(xi) = xi?{x1,…,xi-1} /\ xi?{ad+1,…,aw}, xi:hit u(xi) = 1, xi:miss


Слайд 25

Полнота Совместная генерация не является полной Зеркальная генерация является полной для важных стратегий вытеснения (LRU, FIFO, PseudoLRU)


Слайд 26

Совместная генерация


Слайд 27

Модели MMU MIPS Alpha Pentium 6 PowerPC


×

HTML:





Ссылка: