Лекция 6.а. WCET 1 (Лекции 2015-2016), страница 2

Кэш-памятьиерархичнаОсновная памятьБольшеобъём37Анализ влияния кэш-памятиКакие команды приведутк промахам в кэш?Промахи в кэш приводят кзначительно большимзадержкам, чем попаданияCPUКэшпамятьОсновная память Анализируется двоичный код В данном примере – только кэшс прямым отображением(каждому адресу в основнойпамяти соответствуетединственный адрес в кэшпамяти)38Анализ влияния кэш-памятиРазмеркомандыНачальный адрес• Информациядля анализавлияния кэшакоманд39Анализ влияния кэш-памяти• Отображение вкэш команд40Анализ влияния кэш-памяти41Анализ влияния кэш-памятиПерваяитерацияциклаОстальныеитерации42Учет совместного влияния кэша иконвейера• Анализ влияния конвейера долженбрать на вход результаты анализавлияния кэш-памятиo Команды помечаютсяпопаданием/промахом в кэшo Попадания/промахи влияют назадержки в конвейере• Сложная аппаратура требуетсовместного анализа влияния кэшаи конвейера43ПрограммаАнализ потоковНизкоуровневый анализВычисление WCET• Вычислить верхнюю оценкуWCET программы– Исходные данные: информация озадержках и потоковаяинформация• Примеры подходов:ВычислениеОценкаWCET– Расчёт по синтаксическомудереву– Расчёт по путям выполнения– Неявный перебор путей (IPET)44Расчёт WCET по деревуАнализируетсясинтаксическоедерево программыОбход дерева снизувверхциклзаголовок45Расчёт WCET по дереву Фиксированныевремена выполненияузлов Времена выполнениялистьев известны Времена выполнениявнутренних узловрассчитываются поформулам для типовузловцикл: 100заголовок46Правило для оператора ветвления• Ветвление:• берем максимум иззначений дляузлов-потомков• добавляем времяна проверкуцикл: 100условиязаголовок47Правило для оператора цикла•Цикл:1.

Суммируем оценкидля узлов-потомков2. Умножаем наоценку числаитерацийцикл: 100заголовок48Результат расчёта по дереву• WCET функции foo() равен3800 тактамцикл: 100заголовок49Расчёт WCET по путям• Найти самый длинный путь• Рассматриваем итерации цикла поодной• Подготовить цикл• Убрать обратные дуги• Перенаправить их на50специальные узлы «continue»Расчёт WCET по путям• Самый длинный путь:–A-B-C-E-F-G–7 + 5 + 12 + 4 + 8 + 2 =38 тактов• Суммарное время:– 100 итераций– 38 тактов на итерацию– Итого: 3800 тактов51Расчёт WCET по путямC и F никогда невыполняютсясовместно• Недопустимый путь:• A-B-C-E-F-G• Отбрасываем, ищем следующийпо длине52Расчёт WCET по путямC и F никогда невыполняютсясовместно• Недопустимый путь:• A-B-C-E-F-G• Отбрасываем, ищем следующийпо длине• Новый самый длинный путь:• A-B-C-E-G• 30 тактов• Итого: 3000 тактов53Расчёт WCET по путям:учёт конвейера• Упорядочиваем допустимые путипо убыванию грубой оценки WCET(сумма оценок WCET для участковпутей)• для х из {допустимые_пути}– Вычислить WCETPL(x) с учётом«экономии» δXY от конвейерноговыполнения последовательныхучастков– Если WCETPL(x) больше, чемнаибольшая из грубых оценокWCET для оставшихся путей, илиесли других путей не осталось, тоx – самый длинный (наихудший)путь; стопиначе продолжить цикл54Неявный перебор путей• Implicit path enumerationtechnique (IPET)– Пути выполнения необрабатываются в явном виде• Представление программы– Информация о задержках( )• Значения в узлах: выполнениеучастков• Значение на дугах: экономия засчёт конвейера– Число выполнений ( )55Неявный перебор путейгде совокупность удовлетворяетограничениям:• начальные и конечные условия• структура программы• ограничения на число итераций• прочая потоковая информация56Неявный перебор путей• Методы решения системыограничений:• Целочисленное линейноепрограммирование• Разрешение ограничений(constraint satisfaction)• Результат• Число выполнений дляузлов и дуг• Оценка WCET57Спасибо за внимание!58.