Сжатие кода
Сжатие кода (Code Compaction) – стадия работы компилятора, направленная на формирование микроинструкций из команд, которые могут быть выполнены параллельно. При этом планирование команд должно проводиться с учетом зависимостей по данным и ограничений на использование ресурсов. Учет зависимостей по данным гарантирует, что никакая команда не будет выполнена до тех пор, пока все команды, от которых она зависит, не будут выполнены полностью. Ограничения на ресурсы гарантируют, что построенное расписание не затребует ресурсов (функциональных модулей) больше, чем позволяет архитектура. Целью сжатия кода является получение минимального количества микроинструкций.
Известно, что задача сжатия кода NP-полная. Поэтому был разработан целый ряд эвристических алгоритмов планирования. Перечислим такие как first-come-first-served, critical path и list scheduling. Каждая из этих эвристик приводит к близким к оптимуму результатам в большинстве случаев, отличаясь в свою очередь скоростью и простотой. Детальное описание этих алгоритмов (сложности O(n2)) может быть найдено в [3]. В этом обзоре мы остановимся подробнее на алгоритме list scheduling.
Приоритетное списочное планирование (list scheduling) относится к разряду алгоритмов, решающих задачу локального сжатия кода, т.е. планирования команд внутри базового блока. Стоит отметить, что в этом случае зависимости по данным представляются в виде ориентированного ациклического направленного графа (DAG – direct acyclic graph). Алгоритм планирует команды с нулевого момента времени, начиная с входной команды базового блока. В каждый момент времени t поддерживается список готовых команд (ReadyList), т.е. команд, чьи предшественники уже были спланированы и произведут результат в выходном регистре к моменту времени t. List scheduling является жадной эвристикой и всегда планирует в текущий момент времени готовую инструкцию в случае отсутствия конфликтов по ресурсам. Требования по ресурсам для спланированных команд поддерживаются в глобальной таблице резервирования (GRT – global reservation table)
Если есть несколько готовых команд, то выбирается команда с наивысшим приоритетом. Приоритеты назначаются в соответствии с различными эвристиками. Различные виды алгоритма list scheduling отличаются способами задания приоритетов для команд. Отметим, что назначение приоритета может быть как статическим (приоритет назначается один раз и не меняется больше в течение планирования), так и динамическим (меняться в течение планирования) и таким образом требовать пересчета приоритетов готовых команд после каждой спланированной команды. Мы рассмотрим вариант алгоритма со статическими приоритетами.
Когда все команды из ReadyList, не приводящие к конфликту по ресурсам, спланированы, то момент времени увеличивается на единицу, и ReadyList пополняется новыми готовыми командами. Затем ReadyList сортируется в порядке убывания приоритета. Процесс планирования продолжается до тех пор, пока все команды не будут спланированы. В общем виде алгоритм list scheduling можно записать следующим образом: Вход: DAG Выход: Instruction Schedule AssignPriority(DAG);/*каждой команде присваивается приоритет в соответствии с выбранной эвристикой */ ReadyList = source node in the DAG; timestep = 0; while (DAG содержит неспланированные команды) do { Сортировать ReadyList в порядке убывания приоритета; while (не испробованы все команды из ReadyList) do { Выбрать следующую команду i из ReadyList; Проверить на конфликт по ресурсам; if (команду можно спланировать) { update GRT (i, timestep); Удалить команду из ReadyList; } } timestep++; Добавить команды, которые стали готовыми, в ReadyList }
Рассмотрим эвристики, используемые для назначения приоритета готовым командам. Обычно используется эвристика, основанная на максимальном расстоянии от узла до фиктивного узла стока. Максимальное расстояние узла стока до себя принимается за ноль. Максимальное расстояние узла u определяется как:
MaxDistance(u) = max(MaxDistance(vi) + weight(u, vi))
где максимум берется по всем vi – потомкам узла u.
MaxDistance вычисляется с помощью обратного прохода графа зависимости и является статическим приоритетом.
Приоритет отдается узлам с наибольшим
MaxDistance.
Часто более высокий приоритет отдается командам, которые имеют наименьшее значение Estart. Для входного узла графа Estart принимается равным нулю. Значение Estart команды v определяется как:
Estart(v) = max(Estart(ui) + weight(ui, v))
где максимум берется по всем ui – предкам v. Похожим образом можно отдать приоритет командам с наименьшим значением параметра Lstart, который определяется как:
Lstart(u) = min(Lstart(vi) - weight(u, vi))
где минимум берется по всем vi – потомкам узла u. Значение Lstart для узла стока принимается равным Estart. Разность между Lstart(u) и Estart(u) называется резервом времени или мобильностью и также может быть использована для назначения приоритета. Команды с меньшим резервом времени получают больший приоритет. Команды, лежащие на критическом пути, могут иметь нулевой резерв времени и поэтому иметь больший приоритет над командами, лежащими вне критического пути.
Мы уже упоминали, что задача сжатия кода является NP-полной. Для нахождения
оптимального расписания команд можно воспользоваться методом целочисленного линейного программирования. Сформулируем задачу для случая планирования базового блока при наличии ограничений на ресурсы. Предполагается простая модель ресурсов с полностью конвейеризированными функциональными модулями. Рассмотрим архитектуру с функциональными модулями различного типа (например, АЛУ, устройство записи/чтения, умножитель/делитель), где задержка выполнения команд может быть разной в различных модулях. Также, будем считать, что существует Rr экземпляров для типа r функционального модуля.
Пусть si – момент времени, для которого спланирована команда i, и d(i, j) – вес ребра (i, j). Чтобы не нарушить зависимостей по данным для каждого ребра (i, j) в DAG должно выполняться:
(1) sj ? si + d(i, j)
Рассмотрим матрицу K размера n x T, где n – количество команд или узлов в DAG, и T оценка для наихудшего времени выполнения всего расписания. Обычно T – это сумма времен выполнения всех команд, входящих в базовый блок.
Отметим, что T – константа и может быть получено из DAG. Элемент матрицы К[i,t] равен единице если команда i спланирована для момента времени t и ноль в противном случае. Время планирования si для команды i можно выразить с помощью
К в следующем виде:
si = ki,0 * 0 + ki,1 * 1 + … + ki,T-1
Для всех si это может быть выражено в матричной форме:
(2) s = K * N
где столбец s = {s0, s1, … , sn-1} и столбец N = {0, 1, …, T-1}.
Тот факт, что каждая команда может быть спланирована в точности один раз, выражается условием:
(3) ? ki,t = 1 , ?i
Наконец, ограничения на ресурсы задаются неравенством:
(4) ? ki,t ? Rr , ?t, ?r, i ? F(r)
где F(r) представляет собой набор команд, которые могут выполняться на функциональном модуле типа r.
Целевой функцией является минимизация длины расписания, что можно выразить как: minimize (max (si + d(i,j)))
Чтобы выразить это в линейной форме введем:
(5) z ? si + d(i, j)
Таким образом, решение задачи состоит в минимизации z при условиях (1) – (5).
Стоит отметить, что важным фактором для реализации любого из алгоритмов сжатия кода является описание имеющихся в наличии параллельных функциональных модулей и подходящих для этого инструкций с учётом нерегулярности кодирования.
