Генерация эффективного кода для процессорных архитектур с явным параллелизмом

Вид материала

Реферат

Содержание Для всех Vi, i=1,...,n выполнять следующее. Если Si уже имеется в множестве построенных наборов, то это означает, что мы нашли другой путь из Sbegin в Si. В этом случае Tcomp / Tass 3 | move d1.s,x:(r4)+ ;запись результата (d1) в T[j][i]

Подобный материал:

• Лекция: Моделирование информационного обеспечения: Моделирование данных. Метод idefi., 352.76kb.
• Низкоуровневое программирование, 108.99kb.
• Программа, написанная непосредственно в процессорных кодах, представляет собой последовательность, 302.67kb.
• Петербургский Государственный Университет Математико-механический факультет Кафедра, 358.16kb.
• Программа вступительных испытаний (собеседования) для поступающих в магистратуру, 41.05kb.
• Ю энергию, поставляемую филиалом ОАО «Квадра» «Курская региональная генерация» потребителям, 487.98kb.
• В. Решетов Отделяя плевелы от семян, 273.07kb.
• Вопросы для Государственного экзамена, 72.4kb.
• Тема: Классификация вычислительных систем, 73.02kb.
• Кафедра Вычислительной Техники Расчётно-пояснительная записка, 484.99kb.

Генерация эффективного кода для процессорных архитектур с явным параллелизмом


Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М.

НИИ системных исследований РАН


В статье анализируются проблемы генерации кода, специфичные для процессорных архитектур с явным параллелизмом, и предлагаются методы их решения, главный из которых - постпроцессор, действующий на уровне ассемблерных инструкций.


Содержание


1. Постановка задачи


2. Три направления повышения эффективности генерируемого кода

2.1. Расширение исходного языка

2.2. Роль базового компилятора в генерации эффективного параллельного кода

2.2.1. Функциональные устройства

2.2.2. Распределение регистров


3. Постпроцессирование кода

3.1 Неформальное введение

3.2 Комбинирование команд

3.2.1 Основные понятия

3.2.2 Аппаратная совместимость

3.2.3 Эквивалентность входной и выходной VLIW-последовательностей

3.2.4 Постановка задачи комбинирования

3.2.5 Алгоритм комбинирования

3.2.6 Учет аппаратных задержек

3.2.7 Сокращение перебора

3.3 Другие оптимизации, реализованные в постпроцессоре

3.3.1 Подбор вариантов команд

3.3.2 Модификация команд


4. Результаты измерений и их интерпретация

4.1. Цели и методика измерений

4.2. Результаты измерений

4.3. Прокрутка и раскатка циклов

4.4. Замена адресации со смещением на адресацию с постинкрементацией адресного регистра

4.5. Перестановки обращений к памяти

4.6. Оценка эффективности оптимизаций

4.7. Распределение регистров


5. Заключение


6. Благодарности


7. Литература

1. Постановка задачи


Введение явного параллелизма в (микро)процессорные архитектуры - одно из основных направлений повышения быстродействия компьютеров. В статье будет рассмотрена генерация кода с языков высокого уровня для процессоров, обладающих двумя свойствами:


- имеется несколько функциональных устройств, способных рабо тать одновременно;


- поддерживается очень длинное командное слово (Very Large Instruction Word, VLIW), позволяющее комбинировать в одной инструкции несколько элементарных команд.


В архитектуре с явным параллелизмом уже довольно давно строятся цифровые сигнальные процессоры (Digital Signal Processor, DSP); из более поздних разработок укажем на Itanium и E2K. Два последних примера, очевидно, свидетельствуют об исключительной важности и актуальности проблемы генерации эффективного кода для подобных архитектур.


Чтобы показать различие "естественного" генерируемого кода и команд, эффективно выполняемых в архитектурах с явным параллелизмом, приведем пример программы для микропроцессора 96002 корпорации Motorola [1, 2] (этот цифровой сигнальный процессор будет использован для иллюстраций на протяжении всей статьи). Это программа внешнего умножения вещественных векторов T = S x P.


Реализация на языке С:


for (j = 0; j < M; j++) {

sj = S [j];

for (i = 0; i < N; i++) {

T [j] [i] = P [i] * sj; /* Внутренний цикл */

}

}


Наивная ассемблерная реализация внутреннего цикла (1):


; sj находится в регистре d4, r1 содержит адрес вектора P,

; r4 содержит адрес T[j][0],

; r1 содержит адрес массива P.

do N,_enddo

move x:(r1)+,d5.s ;Чтение P[i] из памяти в регистр d5.

fmpy.s d4,d5,d1 ;Умножение sj на P[i], результат

;заносится в регистр d1.

move d1.s,x:(r4)+ ;Запись результата (d1) в T[j][i].

_enddo:


Эффективная ассемблерная реализация внутреннего цикла (2):


;Пролог цикла:

move x:(r1)+,d5.s ;Чтение P[0] из памяти в регистр d5.

fmpy.s d4,d5,d1 ;Умножение sj на P[0], результат в d1.

move x:(r1)+,d5.s ;Чтение P[1] из памяти в регистр d5.

;для следующего умножения

;Цикл (одно командное слово вместо трех):

do N-2,_enddo

fmpy.s d4,d5,d1 x:(r1)+,d5.s d1.s,y:(r4)+

_enddo:

;Эпилог цикла:

move d1.s,y:(r4)+ ;Запись результата в T[j][N-2].

fmpy.s d4,d5,d1 ;Умножение sj на P[N-1], результат в d1.

move d1.s,y:(r4)+ ;Запись результата в T[j][N-1].


Трудность генерации эффективного кода проистекает в первую очередь из того, что нередко в длинное слово желательно комбинировать операции, относящиеся к разным операторам исходного языка и даже к разным итерациям цикла. Например, в теле цикла (2) совмещены действия из трех последовательных итераций внутреннего цикла исходной C-программы, что позволяет упаковать три команды в одно командное слово, так что они будут выполняться параллельно. Команды из тела цикла (1) нельзя выполнить параллельно, потому что каждая последующая использует результат предыдущей. Более подробно этот пример обсуждается в п. 4.3.


Некоторые подходы к генерации эффективного кода для архитектур такого типа рассматриваются в работах [3, 4].


В НИИСИ РАН, на базе известного свободно распространяемого продукта gcc, разработан C-компилятор, настраиваемый на различные целевые архитектуры и способный использовать явный параллелизм, комбинируя операции для разных функциональных устройств. Опыт, накопленный в процессе этой разработки, и лег в основу данной статьи.


2. Три направления повышения эффективности генерируемого кода


Можно представить себе три способа повышения эффективности кода, генерируемого для архитектур с явным параллелизмом:


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


- совершенствование компилятора, развитие средств описания архитектур с явным параллелизмом, способствующих генерации эффективного кода;


- постпроцессирование сгенерированного кода с целью его улучшения.


В данном разделе мы рассмотрим первые два способа; постпроцессированию посвящен следующий раздел.


2.1. Расширение исходного языка


В различных реализациях компиляторов с языка C для архитектур с явным параллелизмом предпринимаются попытки отразить на уровне исходного языка специфику этих процессоров и особенности программирования для них [5, 6]. Операции над комплексными, векторными, матричными данными, явно выраженные в терминах исходного языка, могут быть непосредственно отображены в эффективные связки команд целевых процессоров с явным параллелизмом.


Комплексный тип данных зафиксирован в последнем стандарте языка C [7]. Пример:


#include


complex float x, y = 1.0 + 3.0 * I;


Для комплексного типа определен набор обычных операций и библиотечных функций.


Gcc, используемый в рассматриваемом проекте в качестве базового компилятора, поддерживает комплексный тип данных. Его применение дает более эффективный код по сравнению с реализациями, основанными на использовании структур. Компилятор, опираясь на известную семантику комплексных данных, обеспечивает более глубокую оптимизацию программы и генерирует код со значительно меньшим числом пересылок.


Векторные и матричные операции, привлекательные с точки зрения возможности напрямую использовать явный параллелизм, к сожалению, плохо "встраиваются" в синтаксис языка C, поскольку имена массивов в выражениях интерпретируется как указатели. Поэтому, например, в стандарте ANSI Numerical C, разработанном группой NCEG (Numerical C Extension Group) [5] для численных приложений, введены понятия итератора и оператора суммирования, отражающие семантику матричных операций.


Пример описания и использования итератора:


iter I = N;

A[I] = sin(2 * PI * I / N);


Этот фрагмент программы эквивалентен следующему тексту на стандартном C:


int i;

for (i = 0; i

{

A[i] = sin(2 * PI * i / N);

}


Пример вычисления произведения матриц с использованием итераторов и оператора суммирования:


iter I=N, J=N, K=N;


A[I][J] = sum (B[I][K] * C[K][J]);


Суммирование здесь проводится по итератору K. В общем случае суммирование выполняется по всем свободным итераторам, то есть итераторам, которые не встречаются в том же выражении вне оператора суммирования.


Упомянем также работу [6], где предлагаются языковые расширения, соответствующие понятиям пространств памяти и аппаратных циклических буферов.


Положительные стороны такого рода языковых расширений - краткость и естественность исходных текстов программ, возможность отобразить высокоуровневые операции в оптимальный для заданной целевой платформы код. В то же время, из-за ограниченности "зоны оптимизации" этот подход вряд ли можно рассматривать как самодостаточный; на наш взгляд, его целесообразно применять в сочетании с другими методами повышения эффективности программирования и компиляции.


2.2. Роль базового компилятора в генерации эффективного параллельного кода


В данном проекте базовому компилятору (gcc) отведена роль инструмента для генерации промежуточного (последовательного) ассемблерного кода, который затем подвергается постпроцессированию. Задача постпроцессора - скомбинировать команды последовательной программы в длинные командные слова с учетом возможностей и ограничений процессора и сгенерировать параллельный код, эквивалентный исходному.


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


Во-первых, базовый компилятор должен обладать развитыми общеоптимизирующими средствами, порождая пусть и чисто последовательный, но, тем не менее, достаточно экономный код. Компилятор gcc удовлетворяет этому требованию, в нем реализован общепринятый набор методов оптимизации: алгоритмы оптимизации циклов и переходов, раскатка циклов, понижение мощности операций, выделение общих подвыражений, свертка констант и др.


Во-вторых, можно усилить возможности постпроцессора (или ускорить его работу), если встроить в промежуточный код дополнительную информацию, которую компилятор накапливает во время обработки программы. Например, зная, что некоторое значение не используется за пределами линейного участка, постпроцессор может более свободно переупорядочивать (и, следовательно, комбинировать) команды на этом участке; зная точки начала и конца циклов, постпроцессор может применить более дорогостоящие средства анализа и оптимизации к телам внутренних циклов. В модуль генерации кода компилятора gcc были добавлены средства для вывода подобной информации в выходной ассемблерный код в виде комментариев.


В-третьих, очень важно, чтобы генерируемые компилятором команды допускали эффективное комбинирование в длинные командные слова. Для этого необходимо, например, учитывать ограничения на форматы параллельных команд и генерировать преимущественно те варианты последовательных команд, которые могут быть скомбинированы с другими командами. Полезно также располагать потенциально комбинируемые команды по возможности ближе друг к другу. Рассмотрим более подробно, как эти требования обеспечиваются средствами настройки базового компилятора.


2.2.1. Функциональные устройства


В ответ на развитие архитектур с неявным параллелизмом, в компилятор gcc были введены средства для описания функциональных устройств. Неявный параллелизм, так же как и явный, подразумевает наличие нескольких функциональных устройств, которые могут работать параллельно. Различие заключается в том, что команды не упаковываются в длинное командное слово. Очередная команда выполняется параллельно с предыдущими, если функциональные единицы, которые нужны для ее выполнения, свободны.


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


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


Пример: функциональные единицы процессора Motorola 96002. Процессор Motorola 96002 позволяет упаковывать в одно командное слово и параллельно выполнять до 4 элементарных команд: умножение, сложение и две пересылки данных. Вместо умножения и сложения в командном слове может фигурировать другая арифметическая команда. Некоторые вычислительные команды не комбинируются с пересылками данных. Кроме того, при некоторых форматах адресации в командное слово умещается только одна пересылка данных, а не две. Комбинирование команд в общее командное слово ограничено также размещением операндов по регистрам.

В соответствии с описанными выше возможностями параллельного выполнения, для этого процессора разумно описать 4 функциональных устройства:


- умножитель;

- сложитель;

- первое устройство пересылки данных;

- второе устройство пересылки данных.

Каждому виду команд в описании целевой архитектуры приписываются атрибуты, определяющие устройства, которые участвуют в ее выполнении. В данном случае в описание атрибутов была заложена следующая информация:


- умножение занимает умножитель;

- сложение занимает сложитель;

- другие арифметические команды занимают и сложитель, и умножитель;

- некомбинируемые команды занимают все 4 устройства;

- пересылки данных занимают первое, второе или оба устройства пересылки данных.


Необходимо отметить ограниченность средств планирования в gcc, поскольку оно применяется не к последовательности машинных команд, а к промежуточному представлению программы. Промежуточное представление - это список абстрактных инструкций, семантика которых задается в терминах лиспоподобного языка RTL (Register Transfer Language). Одной абстрактной инструкции может соответствовать несколько команд целевого процессора, что затрудняет описание атрибутов и снижает точность планирования.


2.2.2. Распределение регистров


Из-за ограниченной длины командного слова возможны ограничения на форматы адресации и использование регистров в параллельных командах. Так, из 800 комбинаций регистров возможных в команде умножения процессора Motorola 96002:


FMPY.S Di,Dj,Dk ;; Dk=Di*Dj, i,k=0, ..., 9; j=0, ..., 7


допустимы только 16, если умножение выполняется параллельно со сложением.


Соответственно, в описании целевой платформы распределение регистров задано таким образом, чтобы в командах умножения использовались преимущественно эти 16 комбинаций. Таким образом, постпроцессор получает относительно широкие возможности для комбинирования умножения со сложением.


Некоторые виды ограничений на использование регистров в параллельных командах учесть довольно сложно. Например, две пересылки данных в память или из памяти в процессоре Motorola 96002 могут выполняться параллельно только при условии, что в них используются адресные регистры из двух разных банков: r0-r3 и r4-r7. В ходе компиляции на этапе распределения регистров сложно предсказать, какие из пересылок в дальнейшем могут быть скомбинированы, чтобы назначить подходящие адресные регистры. Единственное, что удается довольно легко обеспечить при настройке компилятора, - это равномерное использование адресных регистров из обоих банков; для этого достаточно указать соответствующий порядок выделения регистров, например: r0, r4, r1, r5, r2, r6, r3, r7.


3. Постпроцессирование кода


3.1 Неформальное введение


В этой главе рассматривается постпроцессирование кода, сгенерированного базовым C-компилятором. Основная цель постпроцессирования заключается в том, чтобы объединить (скомбинировать) команды исходной программы в длинные командные слова и таким образом обеспечить их параллельное выполнение.


Постпроцессор также способен выполнять другие оптимизирующие преобразования: подбор вариантов команд (п. 3.3.1), модификация команд (п. 3.3.2), удаление избыточного кода и др.


Пример 3.1. Последовательный код для DSP96002 и эквивалентный код, обеспечивающий одновременное выполнение нескольких элементарных действий.


Последовательный код:


Номера Команды Комментарии

команд

1| move x:(r0)+,d4.s ; пересылка данных из памяти в регистр d4.

| ; Запись "x:(r0)+" означает обращение по шине x

| ; к слову, адрес которого находится в регистре

| ; r0. Символ "+" означает, что после вычисления

| ; адреса значение r0 увеличится на 1.

2| fadd.s d0,d1 ; d1:=d1+d2

3| fmpy.s d4,d7,d0 ; d0:=d4*d7

4| fsub.s d3,d2 ; d2:=d2-d3

5| fmpy.s d5,d6,d3 ; d3:=d5*d6

6| move d3.s,x:(r4)+ ; Запись в память значения d3.


Параллельный код:


Номера

команд

1,4,5| fmpy d5,d6,d3 fsub.s d3,d2 x:(r0)+,d4.s

2,3,6| fmpy d4,d7,d0 fadd.s d0,d1 d3.s,x:(r4)+


(В записи параллельной команды имя команды move опускается.)


3.2 Комбинирование команд


3.2.1 Основные понятия


В этом разделе определяются понятия, используемые при описании процедуры комбинирования команд, называемой далее для краткости процедурой комбинирования.


Элементарная команда - это команда, рассматриваемая постпроцессором как неделимое действие.


VLIW-строкой назовем неупорядоченный набор элементарных команд, исполняющихся параллельно и независимо. Разумеется, в записи выходного ассемблерного кода элементарные команды VLIW-строк упорядочиваются согласно синтаксическим правилам ассемблера. В частном случае VLIW-строка может соответствовать одной элементарной команде.


Комбинирование - это объединение элементарных команд во VLIW-строки.


VLIW-последовательность - это последовательность VLIW-строк.


Линейный участок - это VLIW-последовательность, не содержащая меток, и содержащая не более одной команды передачи управления, которая располагается в конце последовательности.


Постпроцессор воспринимает в качестве входных данных VLIW-последовательность, распознает содержащиеся в ней элементарные команды, разбивает ее на линейные участки и комбинирует в пределах этих участков элементарные команды, формируя выходную VLIW-последовательность.


В следующих двух разделах описываются ограничения, которым должна удовлетворять выходная VLIW-последовательность.


3.2.2 Аппаратная совместимость


При комбинировании необходимо соблюдать ограничения аппаратной совместимости, которые определяют, может ли данное множество элементарных команд выполняться параллельно. Описание этих ограничений должно обеспечивать простой способ проверки корректности результирующих VLIW-строк. Для некоторых архитектур (например, DSP96002) составление такого описания - весьма непростая задача.


Общее ограничение алгоритма комбинирования заключается в том, что параллельно исполняемые команды не должны записывать значения в один и тот же регистр. Многократное чтение считается допустимым. Более того, регистр может быть входным для одной элементарной команды и выходным для другой команды из той же VLIW-строки: читающая команда использует прежнее значение регистра до того, как оно будет изменено пишущей командой.


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


Этого простого подхода, к сожалению, оказывается недостаточно. Таким способом невозможно учесть многочисленные специфические ограничения процессора (например, запрет на параллельное исполнение операций разной точности в DSP96002). Для решения этой проблемы вводятся описания запрещенных комбинаций. Так, чтобы исключить комбинации команд разной точности, достаточно каждой элементарной команде сопоставить ресурс sngl или dbl и запретить комбинировать (sngl, dbl). Аналогично, комбинация (int, flt, rm, rm) запрещает комбинировать пересылки

регистр <-> память

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


Описанный подход оказался чрезвычайно удобен как для компактного описания корректных VLIW-строк, так и для рекурсивного их порождения из заданного множества элементарных команд.


В дальнейшем изложении при упоминании VLIW-строк или VLIW-последовательностей везде подразумевается, что речь идет об аппаратно корректных VLIW-строках или их последовательностях.


3.2.3 Эквивалентность входной и выходной VLIW-последовательностей


В общем случае в результате комбинирования элементарные команды могут оказаться переупорядоченными в пределах линейных участков. Так, в примере 3.1 команда 4 выполняется раньше команд 2 и 3 и одновременно с командой 1. Переупорядочение допустимо при условии, что вычисления, производимые входной и выходной VLIW-последовательностями, эквивалентны.


Две VLIW-последовательности V1 и V2, реализующие линейный участок L программы P, эквивалентны, если в результате выполнения V1 и V2 вычисляются одни и те же значения всех объектов, которые могут использоваться в программе P за пределами линейного участка L (при одинаковых исходных значениях всех объектов программы P).


При комбинировании команд для обеспечения эквивалентности выходной и входной VLIW-последовательностей используется подход, основанный на сохранении зависимостей по данным между элементарными командами. Далее приводятся определения, относящиеся к понятию зависимости по данным, и формулируется достаточное условие эквивалентности вычислений.


У элементарной команды есть входные объекты, которые она читает, и выходные, в которые она пишет. Значения выходных объектов команды полностью определяются значениями ее входных объектов.


Если команда записывает значение в зависимости от некоторого условия или записывает только часть выходного объекта, то считается, что этот объект является также входным для нее (иначе можно было бы посчитать, что она отменяет действие предыдущих команд, в которых были переписаны другие части объекта). Оперативная память в этом отношении трактуется как объект, переписываемый частично. Таким образом, если команда осуществляет запись в память, то объект "память" трактуется как входной и выходной для нее.


Чтобы исключить переупорядочение команд, производящих побочные эффекты (например, ввод-вывод), определяется фиктивный объект, который считается входным и выходным для всех команд с побочными эффектами.


Для соблюдения связей по данным между линейными участками, в начало и в конец линейного участка добавляются фиктивные команды START и STOP. Считается, что START ничего не читает и записывает значения всех регистров, а STOP считывает те регистры, значения которых могут потребляться за пределами данного линейного участка.


Будем говорить, что команда B зависит от команды A по объекту O, если A пишет значение O, а B использует его.


Алгоритм комбинирования команд опирается на тот факт, что для эквивалентности двух VLIW-последовательностей V1 и V2 достаточно выполнения следующих двух условий:


1. V2 состоит из тех же элементарных команд, что и V1;


2. каждая элементарная команда последовательности V2 по всем своим входным объектам зависит от тех же команд, что и в V1.


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


T = {O, A, {B1,...,Bn}}


где O - объект, A - команда, которая пишет в него, {B1,...,Bn} - множество команд, читающих значение O, записанное командой A.


Такое представление обеспечивает эффективную проверку достаточных условий эквивалентности VLIW-последовательностей в процедуре комбинирования команд.


На рис. 1 показан пример линейного участка и представление зависимостей по данным для него, а также приведена VLIW-последовательность, эквивалентная исходной.


----------------------------------------------------------------

VLIW-последовательность (линейный участок):


0| START

1| move x:(r0)+,d4.s

2| fadd.s d0,d1

3| fmpy.s d4,d7,d0

4| fsub.s d3,d2

5| fmpy.s d5,d6,d3

6| move d3.s,x:(r4)

7| STOP


Зависимости по данным


T1 ={память, 0, {1,6}} T9 ={d5, 0, {5} }

T2 ={r0, 0, {1} } T10={d4, 1, {3,7}}

T3 ={d0, 0, {2} } T11={r0, 1, {7} }

T4 ={d1, 0, {2} } T12={d6, 2, {7} }

T5 ={d7, 0, {3} } T13={d0, 3, {7} }

T6 ={d3, 0, {4} } T14={d2, 4, {7} }

T7 ={d2, 0, {4} } T15={d3, 5, {6,7}}

T8 ={d6, 0, {5} } T16={память, 6, {7} }


Эквивалентная VLIW-последовательность:


Номера

команд

0 | START (не выводится в результирующий ассемблерный код)

1,4,5 | fmpy d5,d6,d3 fsub.s d3,d2 x:(r0)+,d4.s

2,3,6 | fmpy d4,d7,d0 fadd.s d0,d1 d3.s,x:(r4)

7 | STOP (не выводится в результирующий ассемблерный код)

----------------------------------------------------------------

Рис. 1. Пример линейного участка и соответствующие ему зависимости по данным. Показан пример эквивалентной VLIW-последовательности.


3.2.4 Постановка задачи комбинирования


Цель процедуры комбинирования заключается в том, чтобы построить линейный участок с минимальным временем выполнения и эквивалентного исходному линейному участку. Время выполнения линейного участка определяется как сумма времен выполнения составляющих его VLIW-строк.


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


3.2.5 Алгоритм комбинирования


Обработка линейного участка начинается с выделения элементарных команд и построения зависимостей по данным.


Чтобы объяснить понятия, используемые далее в описании процедуры комбинирования, представим ее сначала упрощенно в виде недетерминированного процесса:


"Выбрать в исходном линейном участке группу элементарных команд, сгенерировать из них VLIW-строку и вывести ее в выходной линейный участок. Выбранные команды пометить как обработанные. Продолжать, пока не будут обработаны все элементарные команды входного линейного участка."


Поскольку требуется получить линейный участок, эквивалентный исходному, то при генерации очередной VLIW-строки из элементарных команд K1, ..., Kn необходимо соблюдать по крайней мере следующие условия.


1. Условие готовности. Все команды, от которых K1,...,Kn зависят по данным, обработаны ранее.


2. Условие неразрушения данных. Пусть объект O является выходным для команды Ki. Если среди ранее обработанных команд есть команда P, которая пишет в O, и имеется необработанная команда N, которая зависит от P по O, то Ki можно обработать на данном шаге только совместно с N.


Смысл этого требования в том, что команда, которую мы собираемся обработать, не должна разрушать значение объекта, пока не обработаны все команды, которые его используют.


---------------------------------------------------------------

Номер Команда Комментарий Обработана? Может быть обработана в данном

состоянии?

0 | START (фиктивная) +

1 | move x:(r0),d1.s; d1:=x:(r0) +

2 | move y:(r1),d2.s; d2:=y:(r1) - только вместе с 7.

3 | fadd.s d1,d2 ; d2:=d2+d1 - нет

4 | fmpy.s d6,d7,d0 ; d0:=d6*d7 - да

5 | move d2.s,x:(r4); x:(r4):=d2 - нет

6 | fmpy.s d4,d4,d2 ; d2:=d4*d4 +

7 | fadd.s d2,d3 ; d3:=d2+d3 - да

8 | move (r5)+ ; r5:=r5+1 - да

---------------------------------------------------------------

Рис. 2. Пример возможного состояния обработки линейного участка. Обработанные команды отмечены символом "+". Справа показано, какие команды могут быть обработаны в этом состоянии.


Рис. 2 иллюстрирует применение условий готовности и неразрушения данных. Если команды 0, 1 и 6 уже обработаны, то на очередном шаге


* безусловно можно обработать команды 4, 7, 8;


* команду 2 можно обработать только совместно с командой 7 (обработав 2 раньше чем 7, мы разрушим значение регистра d2, установленное командой 6 и используемое командой 7, которая еще не обработана);


* команду 3 нельзя обработать, потому что не соблюдается условие готовности данных - не вычислено входное значение d2 (команду 3 можно обработать только после 2);


* команду 5 нельзя обработать также из-за нарушения условия готовности по d2 (команду 5 можно обработать только после 3).


Составим все возможные VLIW-строки из элементарных команд 2, 4, 7, 8, соблюдая ограничения аппаратной совместимости:


Номера

команд VLIW-строка


2 | move y:(r1),d2.s

4 | fmpy.s d6,d7,d0

7 | fadd.s d2,d3

8 | move (r5)+

2,4 | fmpy d6,d7,d0 y:(r1),d2.s

2,7 | fadd.s d2,d3 y:(r1),d2.s

4,7 | fmpy d6,d7,d0 fadd.s d2,d3

4,8 | fmpy.s d6,d7,d0 (r5)+

2,4,7 | fmpy d6,d7,d0 fadd.s d2,d3 y:(r1),d2.s

4,7,8 | fmpy d6,d7,d0 fadd.s d2,d3 (r5)+


Отбросим теперь комбинации, в которых присутствует команда 2, но отсутствует 7. Получается, что, с учетом требований аппаратной совместимости, готовности и неразрушения данных, в данном состоянии можно сгенерировать любую из перечисленных выше VLIW-строк, кроме (2) и (2,4).


Таким образом, при формировании возможных VLIW-последовательностей мы располагаем большой свободой. Чтобы получить оптимальную выходную последовательность, необходимо организовать перебор возможных VLIW-последовательностей и выбор наилучшей из них в смысле определения, сформулированного в п. 3.2.4.


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


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


Дуга проводится из набора S1 в набор S2, если S2 = S1 U {K1,...Kn} где K1,...Kn - группа команд, удовлетворяющая относительно S1 условиям аппаратной совместимости, готовности данных и неразрушения данных. Дуга соответствует выполнению одного шага описанного выше недетерминированного процесса, т.е. генерации одной VLIW-строки.


Рис. 3 показывает набор S0, соответствующий состоянию обработки линейного участка, которое изображено на рис. 2. На рис. 3 представлены также наборы, непосредственно достижимые из S0.

---------------------------------------------------------------



S1={0,1,6,4} S2={0,1,6,7} S3={0,1,6,8} S4={0,1,6,2,7}



--------- S0={0,1,6} ----------------



S5={0,1,6,4,7} S6={0,1,6,4,8} S7={0,1,6,2,4,7} S8={0,1,6,4,7,8}

---------------------------------------------------------------

Рис. 3. Фрагмент графа наборов. Показан набор S0, соответствующий состоянию, которое изображено на рис. 2, а также все наборы, непосредственно достижимые из него.


Длина дуги определяется как время выполнения VLIW-строки, составленной из команд K1,...Kn. Например, длина дуги из S0 в S4 на рис. 3 равна времени выполнения VLIW-строки, составленной из элементарных команд 2, 7, т.е. строки


fadd.s d2,d3 y:(r1),d2.s


(см. рис. 2).


Из одного набора в другой может вести несколько путей. Например, из S0 в S4 (рис. 3) можно попасть непосредственно или через вершину S2.


Назовем начальной вершиной (Sbegin) пустой набор, а конечной (Send) - набор, содержащий все команды линейного участка. Каждому пути, ведущему из Sbegin в Send, соответствует определенная VLIW-последовательность, эквивалентная исходной. Задача состоит в том, чтобы найти самый короткий путь, соответствующий самой быстрой VLIW-последовательности.


Важно отметить, что по крайней мере один путь из начальной вершины в конечную существует. Ему соответствует VLIW-последовательность, совпадающая с исходной. Будем называть этот путь тождественным.


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


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


При каждом создаваемом наборе Si поддерживается следующая информация:


1. стоимость набора Cost(Si) - длина кратчайшего (из построенных до сих пор) пути из Sbegin в Si;


2. набор Sk=Pred(Si), такой что дуга (Sk, Si) принадлежит кратчайшему пути из Sbegin в Si.


Построив таким образом все пути из Sbegin в Send мы сможем затем восстановить (в обратном направлении) оптимальный путь как Send, Pred(Send), Pred(Pred(Send)), ... . Соответствующую ему последовательность VLIW-строк также можно восстановить из наборов, через которые проходит кратчайший путь.


На рис. 4 показан фрагмент графа наборов и отмечен кратчайший путь из начальной вершины в конечную. Из последовательности наборов Send={1,2,3,4,5,6,7,8}, Pred(Send)={1,2,3,5,6}, Pred(Pred(Send))={1,2,3}, Pred(Pred(Pred(Send)))={}, можно восстановить оптимальную последовательность VLIW-строк.


------------------------------------------------------------------

. . .


{1} {1,2} {1,2,3,4}

{1,2,3,4,5,6}

{1,2,3,5}


{}=========>{1,2,3}===========>{1,2,3,5,6}========>{1,2,3,4,5,6,7,8}


{1,2,3,4,5}

. . .

------------------------------------------------------------------

Рис. 4. Фрагмент графа наборов. Отмечен кратчайший путь от начальной вершины к конечной.


Ниже приведен алгоритм построения графа наборов с полным перебором всех путей из начальной вершины в конечную. Далее в п. 3.2.6 описано уточнение алгоритма, позволяющее учесть аппаратные задержки, а в п. 3.2.7 рассматриваются эвристики, применяемые для сокращения перебора. В п. 3.3 описаны две реализованные в постпроцессоре оптимизации, направленные на увеличение числа возможных способов генерации VLIW-строк, с тем чтобы расширить зону поиска решения.