А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 208
Текст из файла (страница 208)
° Если задачи независимы, то простое распараллеливание дает более высокую степень использования процессора, поскольку процессоры могут выполнять всю свою работу без затрат на накладные расходы по заполнению и освобождению конвейера. Однако, как показано в примере 11.55, шаблон обращения к данным в конвейерной схеме отличается от такового в случае простого распараллеливания. Конвейеризация может оказаться предпочтительнее, если она снижает обьем межпроцессорного взаимодействия. 11.9.2 Последовательная сверхрелаксация: пример Последоваглельная сверхрелаксация (зцссеьа1че очег-ге!ахабоп — КОК) представляет собой способ ускорения сходимости методов релаксации для решения систем линейных уравнений.
На рис. 11.50, а показан относительно простой пример, иллюстрирующий соответствующий шаблон обрашения к данным. Здесь новое значение элемента массива зависит от значений его соседей. Такая операция выполняется до тех пор, пока не будет достигнуто выполнение некоторого критерия сходимости. На рис. 11.50, б показаны ключевые зависимости данных.
Здесь не приведены зависимости, которые могут быть получены из уже имеющихся на рисунке. Например, итерация 11, Я зависит от итераций 11, 1 — 1], [г, з — 2~ н т.д. Из приведенных зависимостей очевидно, что параллелизм, не требуюший синхронизации, 1017 11.9. Конвейеризация аког (1 = 0; 1 <= тт 1++) аког (3 = 0; З <= пр З++) Х[З+1) = 1/3 * (Х[З) + Х[З+1) + Х[З+2) ) ' а) Исходный текст б) Зависимости данных в приведенном коде Рис. 11.50. Пример последовательной сверхрелаксации в данном случае не имеет места. Поскольку наидлиннейшая цепочка зависимостей состоит из О(пг+ и) ребер, при добавлении синхронизации мы получим одну степень параллелизма и сможем выполнять О (тт~) операций за О (пт+ п) единиц времени.
В частности, заметим, что итерации, лежащие вдоль 150-градусных диагоналейа на рис. 11.50, б, не связаны никакими зависимостями. Они зависят только от итераций, лежащих на диагоналях, находящихся ближе к началу координат. Следовательно, можно распараллелить приведенный код путем выполнения итераций поочередно на каждой из диагоналей, начиная с начала координат и двигаясь от него в сторону увеличения значений индексных переменных. Будем говорить об итерациях вдоль каждой диагонали как о волновом фронте (ччачеиоп)), а саму схему распараллеливания именовать волновой (тчачеГгоп1[пя).
11.9.3 Полностью переставляемые циклы Сначала рассмотрим понятие полкой переставляемости (тц1! репин)аЫ1[ту), концепции, которая используется в конвейеризации и других оптимизациях. Циклы полностью переставляемы (йг11у реппц1аЫе), если они могут быть произвольным образом переставлены без изменения семантики исходной программы. Если циклы приведены к полностью переставляемому виду, код можно легко конвейеризовать и применить к нему преобразования, такие как блокирование, для повышения локальности данных.
"Послеловатсльпостсй точек, образованных многократными перемещениями па 1 вниз и па 2 вправо. 1018 Глава 11. Оптимизация параллелизма и локальности КОК-код, такой как на рис. 11.50, а, полностью переставляемым не является. Как было показано в разделе 11.7.8, перестановка двух циклов означает, что итерации в исходном пространстве итераций выполняются не построчно, а постолбцово. Например, исходное вычисление в итерации [2, 3[ будет выполнено до итерации [1, 4[, что нарушает показанные на рис.
11.50, б зависимости. Мы можем, однако, преобразовать код так, чтобы сделать его полностью переставляемым. Применение аффинного преобразования [' '1 к исходному коду дает код, показанный на рис. 11.51, а. Такой преобразованный код полностью переставляем, и его переставленная версия показана на рис. 11.51, в. Пространства итераций и зависимости данных этих двух программ приведены на рис.
11.51, б и д соответственно. Из показанных схем легко увидеть, что такое упорядочение сохраняет относительный порядок между всеми зависимыми парами обращений. При перестановке циклов мы радикально изменяем множество операций, выполняемых в каждой итерации внешнего цикла. То, что у нас имеется эта степень свободы при планировании, означает, что имеется определенная нежесткость в упорядочении операций в программе. Нежесткость в планировании означает наличие возможностей для распараллеливания. Ниже в этом разделе будет показано, что если вложенность циклов содержит к внешних полностью переставляемых циклов, то добавление 01п) синхронизаций позволяет получить О 1)с — 1) степеней параллелизма (здесь п — количество итераций в цикле).
11.9.4 Конвейеризация полностью переставляемых ЦИКЛОВ Вложенность циклов с к внешними полностью переставляемыми циклами может быть структурирована как конвейер с О(к — 1) размерностями. В БОК- примере й = 2, так что процессоры можно структурировать как линейный конвейер. Конвейеризовать 8ОК-код можно двумя разными способами, показанными на рис. 11.52, а и б, соответствующими двум перестановкам на рис. !1.51, а и в соответственно. В каждом случае каждый столбец пространства итераций составляет задачу, а каждая строка — стадию. Мы назначаем стадию 1 процессору 1; таким образом, каждый процессор выполняет внутренний цикл кода. Игнорируя граничные условия, процессор может выполнить итерацию 1 только после того, как процессор р — 1 выполнит итерацию 1 — 1.
Предположим, что каждый процессор требует в точности одного и того же количества времени для выполнения итераций, а синхронизация выполняется мгно- 1019 11.9. Конвейеризация Еог (1 = 0; 1 <= зв; 1++) Гог (з = з.; з <= 1+и; з++) Х[з-1+1] = из * (Х[з-1] + Х[З-1+1] + х[З- +г]); а) Код на рис. 11.50 после преобразования [ з ог] б) Зависимости данных кода из части а гог (З = 0; 3 <= аз+из З++) аког (з. = злах(0,))з з. <= га1п(аз,д), 1++) Х[з-1+1] = 1/3 * (Х[з-1] + Х[з-1+1] + Х[]-1+2])1 в) Перестановка циклов в коде из части а г) Зависимости данных кода из части в Рис. ! 1.51. Полностью переставляемая версия кода, приведенного на рис. 11.50 1йгб Глава 11. Оптимизация параллелизма и локальности /* 0 <= р <= зв */ гог (3 = р' 3 <= р+и' 3++) ( 11 (р > 0) згайс (р-1); Х[3-р+1] = 1/3 * (Х[3-р] + Х[3-р+1] + Х[3-р+2])з 1й (р < зв1п (пз,3)) а1дпа1 (р+1); а) Процессоры назначены строкам /* 0 <= р <= пз+п */ аког (з.
= злах(О,р)з з. <= звфп(вз,р)з з.++) ( (р > азах(0,1)) згайс (р-1)з Х[р-1+1] = 1/3 * (Х[р-1] + Х[р-1+1] + Х[р-1+2]); 1й (р < пз+п) й (р > 1) вйдпа1 (р+1); б) Процессоры назначены столбцам Рис. 11.52. Две реализации конвейеризации кода, представленного на рис. 11.5! венно. Обе схемы параллельно выполняют одни н те же итерации; единственное отличие заключается в том, что при этом используются другие назначения процессорам. Все выполняемые параллельно итерации лежат на 135-градусных диагоналях в пространстве итераций на рис. !1.51, б, которые соответствуют 150- градусным диагоналям в пространстве итераций исходного кода (см. рис. 11.50, 6]. Однако на практике процессоры с кэшированием не всегда выполняют один и тот же код за одно и то же время; варьируется и время синхронизации.
В отличие от применения барьеров синхронизации, когда все процессоры работают по жесткой схеме, конвейернзапия требует от процессора синхронизации и обмена информацией не более чем с двумя другими процессорами. Таким образом, конвейеризация характеризуется ослабленным волновым фронтом, позволяя одним процессорам ненадолго вырываться вперед, а другим отставать. Такая гибкость сокращает время, которое процессоры затрачивают на ожидание других процессоров, и повышает производительность параллельной работы.
Приведенные выше схемы конвейеризации — всего лишь два из множества возможных способов конвейеризации вычислений. Как уже говорилось, если цикл полностью переставляем, имеется достаточная свобода в выборе способа распараллеливания кода. Первая схема отображает итерацию [(,2] на процессор г; вторая отображает итерацию ](, з] на процессор з] Можно создать альтернативные способы конвейеризации, отображая итерацию [г, з] на процессор со!+ сз з, где со и сз — положительные константы.
Такая схема создает конвейеры с ослабленными волновыми фронтами в диапазоне от 90' до 180' (исключая граничные значения). 10г1 !!.9, Конвейеризация 11.9.5 Общая теория Рассмотренный выше пример иллюстрирует общую теорию, лежащую в основе конвейеризации: если можно получить как минимум два разных внешних цикла вложенности при удовлетворении всех зависимостей, то такие вычисления могут быть конвейеризованы. Вложенность с к внешними полностью переставляемыми циклами имеет степень конвейерного параллелизма, равную й — 1. Вложенности, которые не могут быть конвейеризованы, не имеют возможности изменять внешние циклы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
