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

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

Тогда компилятор может порождать объектный код таким образом, чтобы в нем содержалось максимально возможное количество соседних операций, все опе­ранды которых не зависят друг от друга. Решение такой задачи в глобальном объеме для всей программы в целом не представляется возможным, но для конкретного оператора оно, как правило, заключается в порядке выполнения опера­ций. В этом случае нахождение оптимального варианта сводится к выполнению перестановки операций (если она возможна, конечно). Причем оптимальный вариант зависит как от характера операции, так йот количества имеющихся в про­цессоре конвейеров для выполнения параллельных вычислений. Например, операцию 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 Формальные методы описания перевода

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

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

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

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

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

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

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

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

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

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

5.1.2 СУ-схемы

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

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

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₁).

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

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

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

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) можно выполнить детерминированным МП - преобразователем.

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

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