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

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

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

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

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

Контрольные вопросы изадачи

Вопросы

1. Справедливы ли следующие утверждения:

--- любой язык программирования является контекстно-свободным языком;

--- синтаксис любого языка программирования может быть описан с помощью контекстно-свободной грамматики;

--- любой язык программирования является контекстно-зависимым языком;

--- семантика любого языка программирования может быть описана с помощью контекстно-свободной грамматики?

2. Какие задачи в компиляторе решает семантический анализ? Можно ли построить компилятор без семантического анализатора? Если да, то какие условия должны при этом выполняться?

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

4. Ha языке C описаны переменные:

1nt i.j,k: /* целочисленные переменные */

double x.y,z; /* вещественные переменные */

объясните, есть ли различия в объектном коде, порождаемом компиляторов для

перечисленных ниже пар операторов, и если есть, то в чем они заключаются:

O i = x/y; i = (int)(x/y);

O i = x/y; i = ((int)x)/((int)y);

O i = j/k; i = ((double)j)/(double)k);

O z = x/y: z=((int)x)/((1nt)y);

O z = j/k; z = (doub1e)(j/k);

O z = j/k; z = ((double)j)/( (doub1e)k);

Объясните, какие функции по преобразованию типов должен будет включи в объектный код компилятор в каждом из перечисленных случаев. B как случаях выполняется неявное преобразование типов?

5. Функция ftest, описанная в исходной программе на языке C++ как «vt ftest(int i)», помещается в библиотеку. B объектном коде библиотеки она г лучит имя, присвоенное компилятором. Это имя может иметь вид, подобно «ftest@i@v». Если разработчик пользуется одним и тем же компилятором, имя функции будет присваиваться одно и то же. Почему тем не менее не с: ит вызывать функцию из библиотеки по этому имени? Что должен предпринять разработчик, чтобы функция в библиотеке имела имя «ftest»?

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

7. Может ли компилятор для языков C и Pascal использовать статическую cxe организации дисплея памяти процедуры (функции)? A динамическую схеъ

8. Синтаксис языка Pascal предусматривает возможность вложения процедуру функций. Как это должно отразиться на организации дисплея памяти, eё учесть, что, согласно семантике языка, вложенные процедуры и функции І гут работать с локальными данными объемлющих процедур и функций? Tребуются ли какие-либо изменения в стековой организации дисплея память таком случае?

9. От чего зависит состав информации, хранящейся в таблице RTTI? Регламетируется ли состав информации в этой таблице синтаксисом или семантики исходного языка программирования? Зависит ли информация в таблице от архитектуры целевой вычислительной системы?

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

11. От чего зависит эффективность объектного кода, построенного компиляром? Влияют ли на эффективность результирующего кода синтаксис и мантика исходного языка программирования?

12. B чем заключается основной принцип СУ-перевода? Является ли СУ-га вод наиболее эффективным методом порождения результирующего кода?

13. Сравните между собой основные способы внутреннего представления программ. Ha каких этапах компиляции лучше всего использовать каждый из этих способов? Какие (или какой) из способов внутреннего представления программы обязательно должен уметь обрабатывать компилятор?

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

15. От чего зависит код, порождаемый процедурой СУ-перевода для каждого узла дерева операций? Должна ли процедура СУ-перевода обращаться к таблице символов? Должна ли процедура СУ-перевода учитывать тип операндов? Как зависят действия этой процедуры от типа порождаемого ею внутреннего представления программы?

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

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

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

19. Массив A содержит 10 элементов (индексы от O до 9). Будет ли условный оператор языка Pascal «if (i<10) and (A[i]=0) then ...» правильным с точки зрения порождаемого компилятором объектного кода? Будет ли правильным с этой же точки зрения оператор «if (i<=0) ог (i>=10) ог (A[i]=0) then ...»? Что можно сказать об объектном коде, порождаемом компилятором для каждого из этих операторов, если компилятор не будет выполнять оптимизацию логических выражений?

20. Какое значение будет иметь переменная i после выполнения следующего оператора языка C:

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

21. Какие варианты распараллеливания выполнения операций может использовать компилятор при порождении объектного кода, необходимого для вычисления выражения <<A*B*C + A*D/E - B/E - F»?

Задачи

1. Функции описаны на языке Pascal следующим образом:

procedureA(i : integer: j: integer):

var t: float:

begin

Функция A вызывает функцию B, которая затем рекурсивно вызывает фуІ цию A. Отобразите содержимое стека, после выполнения одного такого вывода, двух таких вызовов. Объясните, как будет происходить возврат программу, если после двух вызовов рекурсия заканчивается.

2. Ha языке Pascal описаны следующие типы данных:

Какой размер памяти потребуется для этих переменных, если считать, размер памяти, необходимой для типов данных «char» и «byte», составляя 1 байт, а размер памяти для типа данных «integer» — 2 байта?

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

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

напишите для каждого из них выражение в форме инфиксной записи.

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

5. Для грамматики, приведенной выше в задаче № 4, постройте схему СУ-перевода во внутреннее представление программы в форме триад. Выполните перевод в форму триад цепочки символов «а^ла&-а&(а^А—а)».

6. Для грамматики, приведенной выше в задаче № 4, постройте схему СУ-перевода во внутреннее представление программы в форме команд ассемблера (например, Intel 80x86). Выполните перевод в ассемблерный код цепочки символов «а^Ла&~а&(а^Л—а)».

7. Дана последовательность операций:

O преобразуйте ее в форму записи на основе триад; O выполните свертку операций.

8. Дана последовательность операций:

--- преобразуйте ее в форму записи на основе триад;

--- выполните исключение лишних операций.

9. Постройте алгоритм распределения регистров для хранения промежуточных результатов на основе внутреннего представления программы в форме триад.

10. Постройте алгоритм перевода внутреннего представления программы в форме триад в последовательность команд ассемблера.