Оптимальное планирование инструкций для процессоров семейства IA-64 с использованием алгоритма A* Дипломная работа студента 545 группы Галанова Сергей Евгеньевича Научный руководитель: Булычев Дмитрий Юрьевич Рецензент: Фоминых Николай Федорович презентация

A*

Дипломная работа студента 545 группы
Галанова Сергей Евгеньевича

Научный руководитель: Булычев Дмитрий Юрьевич
Рецензент: Фоминых Николай Федорович

регистров
В ходе планирования происходит построение плана исполнения программы - переупорядочение инструкций и их распределение по вычислительным устройствам
Целью является построение оптимального плана, то есть плана с минимальным временем исполнения
Задача оптимального планирования NP-трудна

дает субоптимальные результаты
Целочисленное линейное программирование
Программирование ограничений
Метод ветвей и границ

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

являющийся усовершенствованием класса VLIW (Very Long Instruction Word)‏
Информация о параллелизме инструкций и распределении их по устройствам рассчитывается компилятором статически
Требуется обеспечить совместимость кода между разными представителями архитектуры, поэтому должны накладываться специальные ограничения на кодирование инструкций

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

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

r5, r6 // => M1
add r7 = r8, r9 // => I0
}
{ m.mi
add r9 = r2, r5 ;; // => M2
ld4 r2 = [r1] // => M0
add r8 = r9, r10 // => I0
}
{ mfi.
sub r6 = r7, r4 // => M1
fadd f3 = f4, f5 // => F0
add r12 = r1, r4 // => I1 }

каждом блоке и построение дэга зависимостей
Планирование плана для каждого блока
Построение результирующего ассемблерного кода

можно применять элементарные операции issueOp и endGroup
В вершинах графа поиска находятся частичные планы
Два плана соединены дугой, если второй получен из первого применением элементарной операции
Есть дополнительная конечная вершина, в которую входят дуги из полных планов
Расстояние между двумя планами равно разности их длин (в тактах)‏

пройденного пути, а оцениваемая длина оптимального пути, которая складывается из известной длины текущего пути и эвристической оценки длины оптимального пути из текущей точки до концевой
Если эвристика не переоценивает длину, получится оптимальный путь

поиска
Необходимо найти хорошую эвристику, оценивающую расстояние (в тактах) от заданной точки до конечной

меньше длины критического пути в дэге зависимостей
Можно взять в качестве эвристики эту длину
Она хорошо работает для «густых» дэгов
Плохо работает для блоков, в которых мало зависимостей

число тактов, требуемое для выполнения соответствующего набора инструкций
Выбирается максимум

определяется нижняя граница номеров тактов, в которых она может быть запущена (на основе критических путей в дэге)‏
Для каждой нижней границы определяется минимальное число дополнительных тактов, требуемое для запуска остальных инструкций (на основе эвристики доступных ресурсов)‏
Выбирается максимум

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

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

компиляторами open64 и gcc.

архитектуру