А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 207
Текст из файла (страница 207)
Если инструкция является циклом, то ее дочерними узлами являются компоненты тела цикла, обычно представляющие собой последовательность из одной или нескольких инструкций. вО; Ь1: аког (з. = О; ...) [ в1; 1,2: аког (3 = О; ...) в2; вЗ; ) 1,3: Еог (К = Оз .. ° ) в5; Рис. 11.43. Иерархически структурированная программа Пример 11.53. Иерархическая структура программы, которая представлена на рнс. 11.43, показана на рис. 11.44. Иерархическая природа последовательности выполнения видна из рис. 11.45. Единственный экземпляр во предшествует всем другим операциям, будучи первой выполняемой инструкцией. Затем мы выполня- 1ОП 11.8.
Синхронизация между параллельными циклами ем все команды из первой итерации внешнего цикла перед командами из второй итерации и т.д. Для всех динамических экземпляров, для которых индекс цикла г имеет значение О, инстРУкции вы Ез, Ьз и вз выполнЯютсЯ в лексическом поРЯдке. Можно повторить те же рассуждения для генерации остальной части порядка выполнения. п Ргоа 42 зз з4 Рис.
1! .44. Иерархическая структура программы нз примера 11.53 1: во г: 2,, 3: 4: 1=0 вз из з= — 0 вз гз в=О в4 В4 10: 11: ва 12: 1=1 в2 13; Рнс. 11.45. Порядок выполнения программы из примера 11.53 Можно разрешить упорядочение двух экземпляров из двух разных инструкций иерархическим методом. Если имеются общие циклы, в которых находятся эти инструкции, то надо сравнить значения индексов этих обших циклов, начиная с внешнего цикла.
Как только между индексными значениями будет найдено несоответствие, их разность определит порядок инструкций. Переходить к сравнению 1012 Глава 1!. Оптимизация параллелизма и локальности значений индексов внутренних циклов следует только тогда, когда значения индексов внешних циклов совпадают. Этот процесс аналогичен сравнению времени, выраженному в часах, минутах и секундах.
Сначала мы сравниваем часы; если эти значения одинаковы, мы переходим к сравнению минут и тд. Если индексные значения одинаковы для всех общих циклов, то разрешение порядка выполняется на основе относительного лексического расположения инструкций. Поэтому рассмотренный здесь порядок выполнения простых программ с вложенными циклами часто называют иерархическим временем ()з)егагсЫса! бше). Пусть а1 — инструкция, вложенная в цикл на глубине г!ы а аз — в цикл на глубине дз, количество общих (внешних) циклов — 4 понятно, что с! < г!1 и г! < г!з.
Предположим, что экземпляр а1 — ! = [!г, гз,..., гн, [, а экземпляр язв 1= Б),)з,,,Зи,[ ! ~„„1 тогда и только тогда, когда либо 1. [гцкз,...,!и) с [тг,)з,...,Я, либо 2. [гг 1г,, !и) = [ты.Зз,...,,)и! и а, лексически появляется перед аз. Предикат (гы !з,..., гн[ -к [)г, зз,..., Я можно записать как дизъюнкцию линейных неравенств: (гг < уг) ъ' (г~ = з~ л !з < зз)ч ... ~I (!1 = зг л ... л гн г = уд 1 л !и < зи) Ребро РПО от аг к аз существует в том случае, когда условие зависимости данных и одно из выражений дизъюнкции могут быть истинны одновременно.
Таким образом, для решения вопроса о существовании одного ребра нам может потребоваться решить г! или д + 1 целочисленных линейных программ, в зависимости от того, находится ли инструкция аг лексически до аз. 11.8.4 Алгоритм распараллеливания Теперь мы представим простой алгоритм, который сначала разделяет вычисления на максимально возможное количество циклов, а затем независимо распараллеливает их. Алгоритм 11.54. Максимизация степени параллельности с использованием О (1) синхронизаций Вход: программа с обращениями к массивам. Выход: БРМП-код с константным количеством барьеров синхронизации.
Метод: выполняем следующие действия. 1. Строим граф зависимостей программы и разбиваем инструкции на сильно связанные компоненты. Вспомним, что сильно связанным компонентом называется максимальный подграф исходного графа, в котором из каждого узла полграфа можно достичь любого другого его узла (см. раздел )0.5.8). 1813 11.9. Конвейеризация 2. Преобразуем код так, чтобы он выполнял сильно связанные компоненты в топологическом порядке, при необходимости применяя расщепление. 3. Применяем алгоритм 11.43 к каждому сильно связанному компоненту для поиска распараллеливаний, не требующих синхронизации. Барьеры синхронизации вставляются до и после каждого распараллеливаемого сильно связанного компонента.
а Алгоритм 11.54 находит все степени параллелизма при использовании О (1) синхронизаций, но при этом он имеет ряд слабых мест. Во-первых, он может вносить излишние синхронизации. Очевидно, что если мы применим этот алгоритм к программе, которая может быть распараллелена без синхронизации, то алгоритм будет распараллеливать каждую инструкцию независимо, вводя при этом барьеры синхронизации между параллельными циклами, выполняющими каждую инструкцию. Во-вторых, при ограниченном количестве синхронизаций схема распараллеливания при каждой синхронизации может перемещать между процессорами большое количество данных. В некоторых случаях стоимость взаимодействий процессоров делает параллелизм слишком дорогим, так что такую программу лучше выполнять последовательно, на одном процессоре.
В следующем разделе мы рассмотрим вопросы повышения локальности и снижения количества взаимодействий процессоров. 11.8.5 Упражнения к разделу 11.8 Упражнение 11.8.1. Примените алгоритм 11.54 к коду на рис. 11.46. аког (а=О; а<1001 г++) А[а] = А[з.] + Х[з.]з /* (в1) */ аког (а=01 а<1001 х++) аког (З=Оз 3<200; 3++) В[з.,3] = з[з.,3] + А[з.] + А[3]; /* (в2) */ Рис.
11.46. Код к упражнению 11.8.1 Упражнение 11.8.2. Примените алгоритм 11.54 к коду на рис. 11.47. Упражнение 11.8.3. Примените алгоритм ! 1.54 к коду на рис. 11.48. 11.9 Конвейеризация При конвейеризации задача разбивается на ряд стадий, выполняемых на разных процессорах. Например, задача, вычисляемая с использованием цикла из и, 1014 Глава 1 1. Оптимизация параллелизма и локальности й'ог (з.=Ор з.<100; з.++) А[з.] = А[1] + Х[з.)р /* (в1) */ бог (1=0р 1<100! 1++) В[з.] = В[з.) + А[з.]р /* (в2) */ аког (З=Ор З<100р З++) С[З) = У[2] + В[З]р /* (вз) */ Рис.
11.47. Код к упражнению 11.8.2 аког (1=0р 1<100р 1++) А[з.] = А[1) + Х[1); /* (в1) */ аког (1=0р 1<100! 1++) ( аког (З=Ор 2<100! З++) В[З) = А[з.] + Х[З)р /* (в2) */ С[з.) = В[з.) + Е[з.]р /* (вз) */ аког (З=Ор З<100р З++) 0[1,З) = А[з.] + В[2)р /* (в4) */ Рис. 11.48. Код к упражнению 11,8.3 итераций, может быть структурирована, как конвейер из и стадий.
Каждая стадия назначается своему процессору; когда один процессор завершает выполнение своей стадии, результаты его работы передаются другому процессору в качестве входных данных. Далее мы рассмотрим концепцию конвейеризации более детально. Затем в разделе 11.9.2 для иллюстрации условий применимости конвейеризации будет приведен численный алгоритм реального времени, известный как последовательная сверхрелаксация. Формально ограничения, которые необходимо разрешить, будут определены в разделе 11.9.6, а описание алгоритма для их разрешения— в разделе 11.9.7. Программы, имеющие множественные независимые решения ограничений временных разбиений, известны как имеющие внешние лолнослрью переставляемые циклы (бз11у реппц1аЫе 1оорз); такие циклы, как будет показано в разделе 11.9.8, легко конвейеризуются.
11.9.1 Что такое конвейеризация Наши первоначальные попытки распараллеливания циклов разбивали итерации вложенности циклов таким образом, чтобы две итерации, использующие одни и те же данные, назначались одному и тому же процессору. Конвейеризация позволяет процессорам использовать одни и те же данные, но в общем случае делает 1015 1!.9. Конвейеризация это только "локально*'„ с передачей данных от одного процессора другому, соседнему с ним в пространстве процессоров. Вот простой пример.
Пример 11.55. Рассмотрим цикл йох (1 = 1; 1 <= пза 1++) аког (з =1; з <=п; э++) Х[1] = Х[1) + у[1,З)а Этот код суммирует 1-ю строку У и добавляет ее к т-му элементу Х. Внутренний цикл, соответствующий суммированию, должен выполняться последовательно из-за зависимости данныхт. Однако разные задачи суммирования независимы. Этот код можно распараллелить, заставляя каждый процессор выполнять отдельное суммирование.
Процессор т обращается к строке т массива У и обновляет 1-й элемент массива Х. В качестве альтернативы можно структурировать процессоры для выполнения конвейерного суммирования и получить параллелизм за счет перекрытия суммирований, как показано на рис. 11.49. Говоря более точно, каждая итерация внутреннего цикла может рассматриваться как стадия конвейера: стадия ) берет элемент Х, сгенерированный предыдущей стадией, добавляет его к элементу У и передает результат следующей стадии.
Заметим, что в этом случае каждый процессор обращается к одному столбцу, а не к строке, массива У. Если У хранится постолбцово, то при такой организации вычислений повышается локальность. Рис. 11.49. Конвейерное выполнение примера 11.55 при т = 4 и и = 3 Можно инициировать новую задачу, как только первый процессор выполнит первую стадию предыдущей. Изначально конвейер пуст, и только первый процессор выполняет первую стадию. После ее завершения результат передается второму процессору, в то время как первый процессор начинает вторую задачу, 7 Вспомните, что в свое время мы договорились не использовать коммутативность и ассоциатив- ность сложения.
101б Глава 11. Оптимизация параллелизма н локальности и т.д. Таким образом конвейер постепенно заполняется, пока все процессоры не будут заняты. Когда первый процессор завершает последнюю задачу, конвейер начинает опустошаться; при этом все большее количество процессоров освобождается — до тех пор, пока последний процессор не выполнит свою последнюю задачу. В устойчивом состоянии конвейером из п процессоров могут параллельно выполняться и задач.
а Интересно сравнить конвейеризацию с простым параллелизмом, когда разные процессоры выполняют разные задачи. ° Конвейеризация применима только ко вложенностям с глубиной не менее 2. Каждую итерацию внешнего цикла можно рассматривать как задачу, а итерации во внутреннем цикле — как стадии этой задачи. ° Задачи, выполняемые конвейерно, могут зависеть одна от другой. Информация, относяшаяся к одной и той же стадии каждой задачи, хранится одним и тем же процессором; таким образом, результаты, сгенерированные г-й стадией задачи, могут использоваться г-й стадией следующей задачи без затрат на сообщение между процессорами. Аналогично каждый элемент входных данных, используемый одной стадией различных задач, как было проиллюстрировано примером 11.55, хранится только одним процессором.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
