Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
КРИТЕРИИ ОЦЕНКИ ВЫПУСКНОЙ РАБОТЫ ПО КУРСУ«ОСНОВЫ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ»(ДЛЯ МАГИСТРАНТОВ, АСПИРАНТОВ И СОИСКАТЕЛЕЙДНЕВНОЙ И ЗАОЧНОЙ ФОРМ ОБУЧЕНИЯ...полностью>>
'Документ'
Постоянно озабоченная тем, чтобы найти служителя Церкви, способного разрешить ее сомнения относительно условий, на которых она могла бы войти в Церков...полностью>>
'Документ'
Концепция совершенствования региональной политики в Российской Федерации (далее — Концепция) определяет цели и задачи региональной политики Российско...полностью>>
'Доклад'
В мае 2003 года Совет управляющих принял резолюцию 19/13 об участии молодежи в работе ООН-Хабитат. В резолюции к Директору-исполнителю обращалась про...полностью>>

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

Главная > Реферат
Сохрани ссылку в одной из сетей:

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

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

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

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

Содержание

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.h>

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<N; 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 Алгоритм комбинирования

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



Скачать документ

Похожие документы:

  1. Учебное пособие допущен о министерством образования и науки Российской Федерации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности «Прикладная информатика (в сфере сервиса)» Омск 2005

    Учебное пособие
    Учебное пособие разработано с целью обеспечения обучающихся и преподавателей систематизированным учебным материалом по теоретическим основам операционных систем.
  2. Отче т о деятельности российской академии наук в 2003 году

    Реферат
    В 2003 году Российская академия наук, как и ранее, проводила фундаментальные и прикладные исследования в соответствии с Приоритетными направлениями развития науки, технологий и техники и Перечнем критических технологий Российской
  3. Комплекс технических и про­граммных средств, предназначенный для автоматизации подготовки и реше­ния задач пользователей. Структура

    Конспект
    Основные характеристики ЭВМ. Общие принципы построения современных ЭВМ. Общие сведения и классификация устройств памяти. Архитектурная организация процессора ЭВМ.
  4. Учебное пособие предназначено для студентов очной и заочной форм обучения специальности 351400 «Прикладная информатика ( в сфере сервиса )»

    Учебное пособие
    Учебное пособие предназначено для студентов очной и заочной форм обучения специальности 351400 «Прикладная информатика (в сфере сервиса)», изучающих дисциплину «Вычислительные системы, сети и телекоммуникации», и разработано с целью
  5. К. т н. А. К. Ким, к т. н. В. Ю. Волконский, к т. н. Ф. А. Груздов, М. С

    Документ
    К.т.н. А.К. Ким, к.т.н. В.Ю. Волконский, к.т.н. Ф.А. Груздов, М.С. Михайлов, Ю.Н. Парахин, д.т.н., проф. Ю.Х. Сахин, д.т.н., проф. С.В. Семенихин, М.В.

Другие похожие документы..