Оптимизация кода для процессоров, допускающих распараллеливание вычислений

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

Тогда компилятор может порождать объектный код таким образом, чтобы в нем содержалось максимально возможное количество соседних операций, все опе­ранды которых не зависят друг от друга. Решение такой задачи в глобальном объеме для всей программы в целом не представляется возможным, но для конкретного оператора оно, как правило, заключается в порядке выполнения опера­ций. В этом случае нахождение оптимального варианта сводится к выполнению перестановки операций (если она возможна, конечно). Причем оптимальный вариант зависит как от характера операции, так йот количества имеющихся в про­цессоре конвейеров для выполнения параллельных вычислений. Например, операцию A+B+C+D+E+F на процессоре с одним потоком обработки данных лучше выполнять в порядке ((((A+B)+C)+D)+Е)+F. Тогда потребуется меньше ячеек для храпения промежуточных результатов, а скорость выполнения от по­рядка операций в данном случае не зависит.

Та же операция на процессоре с двумя потоками обработки данных в целях уве­личения скорости выполнения может быть обработана в порядке ((А+В)+С)+ +((D+E)+F). Тогда по крайней мере операции А+В и D+E, а также сложение с их ре­зультатами могут быть обработаны, в параллельном режиме. Конкретный поря­док команд, а также распределение регистров для хранения промежуточных ре­зультатов будут зависеть от типа процессора.

На, процессоре с тремя потоками обработки данных ту же операцию можно уже разбить на части в виде (A+B)+(C+D)+(E+F). Теперь уже три операции А+В, C+D и E+F могут быть выполнены параллельно. Правда, их результаты уже должны быть обработаны последовательно, но тут уже следует принять во внимание соседние операции для нахождения наиболее оптимального варианта.

Формальные методы описания перевода

Синтаксически управляемый перевод

Схемы компиляции

Выделяют две основные схемы компиляции:

- последовательную;

- интегрированную.

Последовательная схема представляет собой - совокупность последовательно выполняемых программных ком­понентов, каждый из которых соответствует одному этапу компиляции (рис. 5.1.1). Последовательная схема предполагает не менее одного просмотра (прохода) программы на каждом этапе. Например, при генерации кода может выполняться два просмотра, а каж­дый метод машинно-независимой оптимизации требует по край­ней мере одного просмотра. Рассмотренные методы построения промежуточной программы не требуют наличия разбора, и синтаксический анализатор может вообще не выполнять ни­какого преобразования программы. Последовательная схема, несомненно, проста и понятна, но она громоздка (по объему занимаемой памяти и времени компиляции программы) и при­меняется редко.

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

Рис. 5.1 - Схемы компиляции: а - последовательная,

б - интегрированная

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

СУ-схемы

Интегрированные схемы компиляции базируются на теории пере­вода языков, ключевыми понятиями которой являются схема синтаксически управляемого перевода (СУ-схема), синтакси­чески управляемый перевод (СУ-перевод), преобразователь с мага­зинной памятью (МП - преобразователь). Рассмотрим эти понятия.

Определение. СУ-схемой Т называется пятерка следующих объектов

T={V_T, V_N, ,R,S), где

V_T — конечный входной алфавит, терминалы;

V_N — конечное множество нетерминалов;

— конечный выходной алфавит;

R — конечное множество правил вида A-> , где V*,

(V_N )*;

S — аксиома (начальный символ) схемы.

Определение. СУ-схема называется простой, если в каждом правиле А-> одноименные нетерминалы встречаются в и в одном и том же порядке. СУ-схема называется постфиксной, если V_N ^* * в каждом правиле {А-> ) R.

Определение. СУ-переводом , определяемым (генерируемым) СУ-схемой T={V_T, V_N, ,R,S), называется множество пар

Грамматика G_BX = {V_T, V_N, P,S), где Р = {А -> | (А -> ) R}, называется входной грамматикой СУ-схемы. Грамматика G_ВЫХ ={ ,V_N, P^’,S), где P^’ = {А -> | (А -> ) R}, называется выходной грамматикой СУ-схемы.

ПримерРассмотрим СУ-схему Т₁ перевода арифметичес­ких выражений в обратную польскую запись. В основе этой схе­мы лежит соответствие правил записи арифметических выраже­ний в обычной (инфиксной) форме и в ПОЛИЗ. Для упрощенных выражений такое соответствие приводится ниже.

Правила инфиксной формы Правила ПОЛИЗ

S->E S->E

E->E+T E->ET+

E->T E->T

T->T*F T->TF*

T->F T->F

F->(E) F->E

F-> имя F->имя

СУ-схема Т₁ представляется пятеркой Т₁ = {V_T, V_N, ,R,S), где S — аксиома, V_T= {+, *, имя, (,)}; = {+, *, имя}; V_N= {S, Е,T, F} и множество R содержит следующие правила:

1)S ->E,E 2)E->E+T,ET+ 3)E->T,T 4)T->T*F,TF* 5)T->F,F 6)F->(E),E 7)F ->имя, имя

Входной грамматикой СУ-схемы Т₁ является G_ВХ = (Vt, Vn, Р, S), где множество правил Р представлено правилами инфиксной фор­мы. G_ВЫХ= ( , Vn, P^’ , S) — выходная грамматика СУ-схемы T₁, а ее правила Р^’ — это правила ОПЗ. Как показывает анализ пра­вил СУ-схемы, Т₁ — простая постфиксная СУ-схема. Нетрудно убедиться также, что в ней существует, например, вывод (S, S) =>* (a+b*c, abc*+), порождающий элемент перевода (а+b*с, abc*+) (T₁).

МП-преобразователи

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

Определение. МП - преобразователем называют восьмерку вида

Q - конечное множество состояний преобразователя;

- конечный входной алфавит;

Г - конечный магазинный алфавит;

- конечный выходной алфавит;

- отображение множества (Q * ( * Г) в множество всех подмножеств множества (Q * Г** *), т.е.

q_о - начальное состояние преобразователя, q₀Q;

Z_o - начальное содержимое магазина, Z_oГ;

F - множество заключительных состояний преобразователя, F Q.

Определение. Конфигурация МП - преобразователя — это четверка (q,w, , у)(Q х * х Г* х *). Начальная конфигурация — (q₀ ,w, Z_o, ), заключительная конфигурация — (q, , , у), где q F. Если од­ним из значений функции (q, a, Z) является (q^’, , r), то шаг ра­боты преобразователя можно представить в виде отношения на конфигурациях

(q, aw, Za, у) |- (q^’,wо, а, уr) для любых w *, Г*, у *.

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

(q_о, w, Z_o, ) |-* (q, , , у) для некоторых q F и Г*.

Определение. Переводом (преобразованием) , определяемым МП - преобра­зователем Р, называется множество

(Р) = {(w,у) | (q₀,w, Z_o, )|-* (q, , ,у) для q F, Г*.

Определение. МП - преобразователь будет детерминированным, если, как и МП - автомат, он имеет не более одной возможной очередной кон­фигурации. Расширенный МП - преобразователь отличается от рассмотренного только магазинной функцией

: (Q х ( ) х Г*) -> P(Q х Г* х *).

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

1. Если T={V_T, V_N, ,R,S) - простая СУ-схема с входной грамматикой LL(k), то СУ-перевод (Т) можно осуществить детерминированным МП - преобразователем.

2. Если T={V_T, V_N, ,R,S) - простая постфиксная СУ-схема с входной грамматикой LR(k), то перевод (T) можно выполнить детерминированным МП - преобразователем.

Существуют алгоритмы, позволяющие построить детерми­нированный МП - преобразователь по заданной СУ-схеме пере­вода. В их основе лежат алгоритмы построения таблиц разбора.

Простые СУ-переводы образуют важный класс переводов, поскольку для каждого из них можно построить детерминиро­ванный МП - преобразователь, отображающий входную строку (цепочку) в выходную строку (цепочку). Такие переводы иногда называют цепочечными.