Xreferat.com » Рефераты по информатике и программированию » Обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд

Обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд

Шумаков С.М.

Введение

Процессоры, способные одновременно и независимо выполнять несколько команд, обладают исключительно высоким потенциалом производительности и находят все более широкое применение. О процессорах такого типа говорят, что они поддерживают параллелизм на уровне команд (Instruction Level Parallelism, ILP). Далее для краткости они будут называться ILP-процессорами. Класс ILP-процессоров включает суперскалярные процессоры и процессоры с очень длинным командным словом (Very Large Instruction Word, VLIW), к числу которых относятся, в частности, многие модели цифровых процессоров обработки сигналов (ЦПОС).

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

Для реального использования высокой производительности ILP-процессоров необходимы компиляторы с языков высокого уровня, способные генерировать эффективный код. Применение одних лишь традиционных методов оптимизации кода оказывается совершенно недостаточным. Например, согласно [3] или [41], типичный компилятор для ЦПОС (поддерживающий только традиционные оптимизации) генерирует код, который по времени выполнения может уступать оптимальному в 5-10 и более раз.

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

В разделе 2 дается краткий обзор ILP-процессоров и их основных характеристик. Раздел 3 посвящен критериям оптимизации кода для ILP-процессоров. В разделе 4 представлена примерная схема работы компилятора, характеризуются основные задачи, связанные с оптимизацией кода для ILP-процессоров. В разделе 5 дается обзор способов формирования областей (фрагментов компилируемой программы), в рамках которых возможно эффективное распараллеливание. В разделе 6 описываются методы оптимизации, направленные на усиление внутреннего программного параллелизма в рамках выделенных областей. В разделе 7 рассматриваются методы распараллеливания кода в предварительно выделенных областях. Раздел 8 посвящен специфике оптимизации кода для ЦПОС. В разделе 9 приводится информация о языковых расширениях и их роли в увеличении эффективности процессоров. В заключении (раздел 10) представлены некоторые из актуальных нерешенных до настоящего время проблем оптимизации кода для ILP-процессоров.

ILP-платформы

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

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

ни одна из команд ci не использует в качестве входных операндов результаты других команд c1, ..., cn;

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

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

Пусть исполнение команды состоит из 3-х этапов

по 1 процессорному такту на каждый:

1) чтение команды из памяти (Ч);

2) декодирование (Д);

3) исполнение (И).

Последовательное исполнение команд
Этапы Ч1 Д1 И1 Ч2 Д2 И2 Ч3 Д3 И3
Такты  1 2 3 4 5 6 7 8 9
Конвейерное исполнение команд
Устройство чтения: Ч1 Ч2 Ч3 Ч4 Ч5 Ч6 Ч7
Устройство декодирования: Д1 Д2 Д3 Д4 Д5 Д6 Д7
Устройство исполнения: И1 И2 И3 И4 И5 И6 И7
Такты  1 2 3 4 5 6 7 8 9
Конвейерное суперскалярное исполнение команд
Устройство чтения 1: Ч1 Ч2 Ч3 Ч4 Ч5 Ч6 Ч7
Устройство декодирования 1: Д1 Д2 Д3 Д4 Д5 Д6 Д7
Устройство исполнения 1: И1 И2 И3 И4 И5 И6 И7
Устройство чтения 2: Ч1 Ч2 Ч3 Ч4 Ч5 Ч6 Ч7
Устройство декодирования 2: Д1 Д2 Д3 Д4 Д5 Д6 Д7
Устройство исполнения 2: И1 И2 И3 И4 И5 И6 И7
Такты  1 2 3 4 5 6 7 8 9

Рис. 1. Последовательное и параллельное исполнение команд

Естественным развитием средств конвейерной обработки явились процессоры с множественной выдачей команд на исполнение (multiple issue processors) - суперскалярные и VLIW-процессоры. Суперскалярный процессор исполняет обычный последовательный код, но может выбирать в нем и выдавать на выполнение одновременно несколько команд - не более n, где n - темп выдачи команд данного процессора. Различаются суперскалярные процессоры с упорядоченной и неупорядоченной выдачей команд на исполнение. Процессор первого типа выдает команды на исполнение в точности в том порядке, в котором они закодированы в программе. На каждом такте на исполнение выдается от 1 до n очередных команд с учетом возможности их параллельного исполнения. Процессор второго типа анализирует команды в пределах некоторого "окна" - текущего фрагмента входной программы - выбирая в нем для выдачи на исполнение от 1 до n команд с учетом связей по данным и возможности параллельного исполнения.

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

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

Следует отметить, что и для суперскалярных процессоров применение ILP-оптимизаций при компиляции дает существенное повышение производительности (см. [55], [58]). Повышению эффективности исполнения на суперскалярных ЭВМ может способствовать также встраивание избыточной информации о программе, доступной во время компиляции и позволяющей процессору динамически производить дополнительные оптимизации. Пример применения этого подхода можно найти в [50].

VLIW-процессор способен работать с большей эффективностью, чем суперскалярный, поскольку у него нет необходимости заниматься динамическим анализом кода. Суперскалярный процессор, тем не менее, превосходит его в качестве планирования команд, поскольку имеет больше информации. Так, при статическом анализе невозможно предсказать случаи непопадания в кэш при чтении из памяти, из-за чего при выполнении возможны простои, в то время как динамический планировщик в этом случае может запустить другие готовые к исполнению команды. Компилятор не имеет права поменять местами команду чтения из памяти с последующей командой записи в память, поскольку адрес записи, возможно, совпадает с адресом чтения. Динамическому планировщику эти адреса уже известны, следовательно, он обладает большей свободой переупорядочения команд. Еще одно преимущество суперскалярных процессоров заключается в поддержке механизма предсказания ветвлений (branch prediction) и выполнения по прогнозу ветвления (control speculation). Аппаратура выбирает направление ветвления исходя из частоты предыдущих ветвлений в этой точке и с упреждением исполняет команды из более вероятной ветви. Это дает ускорение, если прогноз был верен. При неверном прогнозе аппаратура аннулирует результаты упреждающих вычислений.

Концепция явного параллелизма на уровне команд (EPIC - Explicitly Parallel Instruction Computing) возникла из стремления объединить преимущества двух типов архитектур. Идеология EPIC заключается в том, чтобы, с одной стороны, полностью возложить составление плана выполнения команд на компилятор, с другой стороны, предоставить необходимые аппаратные средства, позволяющие при статическом планировании на стадии компиляции использовать механизмы, подобные тем, которые применяются при динамическом планировании в суперскалярных архитектурах (см. [13]).

В разд. 7.4 и 7.6 рассматриваются некоторые характерные для EPIC-архитектур аппаратные средства

поддержка упреждающего выполнения команд на основе прогноза направления ветвления (control speculation);

поддержка выполнения по прогнозу данных (data speculation);

поддержка условного выполнения (predicated execution)

и их использование при статическом планировании.

С точки зрения применимости различных методов оптимизации существенно различие между VLIW-процессорами с регулярной и нерегулярной организацией командного слова. Последние отличаются тем, что на параллельно исполняемые инструкции налагаются дополнительные ограничения. В частности, для параллельно исполняемой инструкции могут допускаться в качестве операндов не все сочетания регистров или не все способы адресации, которые возможны в такой же инструкции, если параллельно с ней не закодированы другие инструкции. Такие особенности характерны, в частности, для цифровых процессоров обработки сигналов, где, в целях ускорения выборки команд, а также для сокращения общего размера кода и энергопотребления, проектировщики стремятся минимизировать длину командного слова и используют для этого нерегулярные способы кодирования. Нерегулярная организация командного слова (см. например, [52]) и связанные с ней ограничения параллелизма исполнения, называемые ограничениями кодирования, существенно усложняют задачу генерации эффективного кода при компиляции ([41],[59]).

Еще одна разновидность ILP-архитектур - кластерные архитектуры, где функциональные устройства поделены на группы (кластеры), и с каждым кластером связан набор локальных регистров, недоступных для функциональных устройств других кластеров (см. [54]). На рис. 2 изображен пример кластерной архитектуры.

Рис. 2. Кластерная архитектура

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

Критерии оптимизации кода

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

минимизация времени выполнения программы;

минимизация размера кода;

минимизация энергопотребления.

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

Локальные методы оптимизации, применяемые в пределах линейных участков, обычно направлены на сокращение одновременно и времени выполнения, и размера кода. Методы реорганизации кода (такие как развертка циклов, встраивание функций и др. - см. разд., 6.1, 6.3), направлены на ускорение работы компилируемой программы ценой увеличения размера выходного кода.

Возможны и другие, более специальные критерии и ограничения. Например, в работах [39] и [40] рассматривается метод планирования инструкций в условиях, когда для некоторых из них заданы начальные и/или конечные времена Tmini, Tmaxi, так что инструкция i должна сработать не позднее момента Tmaxi и не ранее момента Tmini. Подобные ограничения характерны для систем реального времени, где определенные действия должны совершаться в пределах заданных временных интервалов.

Фактор скорости компиляции, по мнению многих авторов ([41], [45], [58] и др.), для ILP-процессоров следует считать второстепенным. В особенности это справедливо в контексте компиляции для ЦПОС. С одной стороны, генерация оптимального кода для них существенно затрудняется из-за ограничений параллельного исполнения, с другой стороны, эффективность результирующего кода для них имеет гораздо более важное значение, чем скорость компиляции.

Круг проблем, связанных с оптимизацией кода для ILP-процессоров

Прежде чем перейти к рассмотрению основных задач, относящихся к ILP-оптимизации, рассмотрим в общих чертах схему работы компилятора, которая представлена на рис. 3 (см., например, [5],[6]). Компилятор для ILP-процессора объединяет в себе стандартные механизмы компиляции, имеющие смысл для всех целевых платформ, и специализированные методы анализа и оптимизации, направленные на выявление, усиление и использование параллелизма на уровне команд.

Рис. 3. Примерная схема компиляции; постпроцессирование – необязательный этап

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

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

Затем проводятся оптимизации в терминах промежуточного представления. Примеры стандартных оптимизаций, поддерживаемых большинством современных компиляторов, - удаление избыточного кода, свертка константных вычислений, выделение общих подвыражений, вынесение инвариантных вычислений из циклов, понижение мощности операций и др. [61]. В ILP-компиляции особое внимание уделяется методам усиления программного параллелизма в телах циклов, которые подробно рассматриваются в разд. 6.

В контексте ILP наибольший интерес представляет оптимизирующее преобразование, называемое планированием. В ходе планирования последовательность команд, сформированная традиционными методами компиляции, переупорядочивается, и команды группируются таким образом, чтобы обеспечить максимально быстрое параллельное исполнение. При этом учитываются связи между командами по данным и по управлению, а также аппаратные возможности параллельного исполнения команд. В применении к компиляции для VLIW-процессоров данное преобразование кода называют также распараллеливанием (code parallelization) или сжатием (code compaction).

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

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

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

Перечислим коротко основные методы анализа, реорганизации и оптимизации кода, применяемые в ILP-компиляторах. Более подробно они рассматриваются в последующих разделах.

1. Выделение областей планирования. Область планирования - это фрагмент или множество фрагментов программы, в пределах которых применяется алгоритм планирования. В простейшем случае в качестве таких областей используются линейные участки в смысле [1] или [4] - последовательности команд, содержащие не более одной метки (в начале) и не более одной команды перехода (в конце). Однако в пределах линейного участка не всегда можно найти достаточно команд, способных исполняться параллельно. Поэтому разработчики компиляторов стремятся выделить более крупные области планирования, объединяющие несколько линейных участков. Различные типы областей планирования рассматриваются в разделе 5.

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: