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

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

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

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

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

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

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

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

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

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

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

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

12 Последовательности обращений к «таблицам» в 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]

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

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

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

16 Совместное обращение в MIPS vpn pfn tag virtual = φ(y, c) LOAD x, y, c x := mem[y+c] tag L 0 vpn V 0 vpnpfn pfn P 0 tag = pfn[..] tag L 0[P 0 ]

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

18 Стратегия вытеснения x = displaced(L) hit(x) = x L 0 /\ x {x 1, …, x n } \/ (x = x i /\ x {x i+1,…, x n })_i hit(x) = x L 0 /\ x еще не вытеснен \/ (x = x i /\ x не вытеснен)_i miss(x) = x L 0 /\ x {x 1, …, x n } \/ (x = x i /\ x {x i+1, …, x n })_i miss(x) = x L 0 /\ x {x 1, …, x n } \/ (xL 0{x 1, …, x n } /\ x уже вытеснен)

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

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

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

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

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

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

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

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

27 Совместная генерация W = 4W = 8 N = 2 КПД = 34% макс.время = 14.0 с средн.время = 1.6 с КПД = 39% макс.время = 10.2 с средн.время = 2.2 с N = 3 КПД = 29% макс.время = 51.3 с средн.время = 3.0 с КПД = 30% макс.время = 47.0 с средн.время = 3.8 с N = 4 КПД = 22% макс.время = 59.7 с средн.время = 3.3 с КПД = 21% макс.время = 57.7 с средн.время = 4.6 с

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