А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 211
Текст из файла (страница 211)
Каждый процессор выполняет итерации в й-м цикле последовательно. Процессор, соответствующий значениЯм [Рь Рз,..., Рь ~] пеРвых Й вЂ” 1 индексов циклов, может выполнить итерацию 1 в Й-м цикле только по получении сигналов от процессоров [Р1 1~Р2~ ~рь — 1]1 ~[ры ~Рь — 2~Рь — 1 Ц о том, что они выполнили свои 1-е итерации в Й-м цикле. Волновое распараллеливание Легко также сгенерировать 1с — 1 внутренних распараллеливаемых циклов из вложенности с й внешними полностью переставляемыми циклами. Хотя конвейеризация предпочтительнее, данная информация приводится здесь для полноты изложения.
Мы разбиваем вычисления во вложенности циклов с й внешними полностью переставляемыми циклами с использованием новой индексной переменной 1', где 1ОЗг Глава 11. Оптимизация параллелизма и локальности г' определяется как некоторая комбинация всех индексов 6 циклов. Например, одной из таких комбинаций является Г = (з + + (ь. Мы создаем внешний последовательный цикл, который итерирует г' разделов разбиения в возрастающем порядке; вычисления в каждом из разделов упорядочены, как и ранее.
Первые )с — 1 циклов в каждом разделе гарантированно распараллеливаемы. Интуитивно в двумерном пространстве итераций такое преобразование при выполнении внешнего цикла группирует итерации вдоль 135- градусных диагоналей. Эта стратегия гарантирует, что итерации в каждой итерации внешнего цикла не будут иметь зависимостей данных. Блокирование Полностью переставляемая вложенность циклов глубиной й может быть блокирована в к размерностях. Вместо назначения итераций процессорам на основе значения индексов внешнего или внутреннего цикла мы можем агрегировать блоки итераций в один модуль.
Блокирование полезно как для повышения степени локальности данных, так и для минимизации накладных расходов конвейеризации. Предположим, что имеется двумерная полностью переставляемая вложенность циклов, как на рис. 11.55, а, и мы хотим разбить вычисления на 6 х 6 блоков. Порядок выполнения блочной версии кода показан на рис. 11.5б, а сам код — на рис. 11.55, б. аког (1=0з 1<пз з.++) гог (З=1з З<пз З++) ( <Я> ) а) Простая вложенность циклов аког (11 = О; 11<пз 1+=Ъ) аког (зЗ = О; ЗЗ<п; ЗЗ+=Ь) аког (1 = 11*Ьз 1 <= звйп(11*Ь-1, и); 1++) аког (З = 11*Ь| З <= гайп(З3*Ь 1, и); 3++) ( <Я> ) б) Блочная версия вложенности циклов Рис. 11.55. Двумерная вложенность циклов и ее блочная версия Если назначить каждый блок одному процессору, то передача данных от одной итерации к другой в пределах блока не потребует межпроцессорного взаимодействия.
В качестве альтернативы можно огрубить уровень модульности конвейеризации, назначив одному процессору столбец блоков. Заметим, что каждый про- 1034 Глава 11. Оптимизация параллелизма и локальности Йог (з. = 1; з. <= Нз 1++) ( йог (7 = 1; 7 <= з.-1; 7++) Гог (К = 11 К <= ]-1з К++) Х[',7] = Х[1,]) — Х[1,К] * Х[7,К]з Х[1 з) = Х[з з) / Х[з ) аког (в = 1; в <= 1-1; в++) Х [ з., 11 = Х [ з., з. 1 — Х [ з., в! * Х [ з., в1 Х[1,1] = ас)гг(Х[1, з.) ); Рис.
1!.57. Разложение Холецкого аког (12 = 1; 12 <= Нз 12++) аког (З2 = 1; 72 <= 12; 72++) ( /* Начало кода для процессора (12,З2) */ аког (К2 = 1; К2 <= 12; К2++) [ // Отображение: 12 = 1, 72 = 7, К2 = 1й (52<12 йй 1сг<~2) Х[12,72) = Х[12,72) — Х[з.2,)с2] * хцг,кг]; // Отображение: 12 = 1, 72 = 7, К2 = з 1й (52==К2 йй ]2<12) Х[12,72] = Х[з2,72] / Х[72,72]з // Отображение: 12 = 1, зг = 1, К2 = 1й (12==72 йй К2<12) Х[12,з.2) = Х[з.2,з.2] — Х[12,)с21 * Х[з.2, 1с2]; // Отображение: 12 = 1, з 2 = 1, К2 зй ( 12==72 й й ~ 2==1с2 ) Х[1с2, )с2] = ас)гг(х[1сг, 1сг] ) з /* Конец кода для процессора (12,З2) */ Рис. 11.58.
Код на рнс. 11.57, переписанный как полностью переставляемая вложенность циклов 1ОЗ5 11.9. Конвейеризация процессор выполняет наиболее глубоко вложенный цикл — с индексом к2. Прежде чем выполнить Й-ю итерацию, процессор ожидает сигналов от процессоров с идентификаторами (12 — 1, т2) и (12, з2 — 1). После выполнения итерации он, в свою очередь, посылает сигналы процессорам (12 + 1, 12) и (12, 12 + 1). а 11.9.9 Параллелизм с минимальной синхронизацией В последних трех разделах были описаны три мошных алгоритма распараллеливания. Алгоритм 11.43 находит параллелизм, не требуюший синхронизации; алгоритм 11.54 находит параллелизм, требующий константного количества синхронизаций, а алгоритм 11.59 находит конвейеризуемый параллелизм, требующий О(п) синхронизаций, где п — количество итераций во внешнем цикле.
В качестве первого приближения наша цель состоит в распараллеливании как можно большего количества вычислений при внесении как можно меньшего количества синхронизаций. Приведенный ниже алгоритм 11.64 находит в программе все степени параллелизма, начиная с наиболее крупномасштабного. На практике, чтобы распараллелить код для многопроцессорной системы, нам не требуется работать с параллелизмом на всех возможных уровнях. Мы начинаем с внешних циклов и идем вглубь до тех пор, пока не будут распараллелены все вычисления, а все процессоры — полностью загружены. Алгоритм 11.64.
Поиск всех степеней максимально крупномодульного параллелизма в программе Вход: распараллеливаемая программа. Выход: распараллеленная версия исходной программы. МЕтод: выполняем следующие действия. 1. Находим максимальную степень параллелизма, не требуюшего синхронизации, путем применения к программе алгоритма 11.43.
2. Находим максимальную степень параллелизма, требующего О (1) синхронизаций, путем применения алгоритма 11.54 к каждому пространственному разбиению, найденному на шаге 1. (Если параллелизм, не требующий синхронизации, в программе не обнаружен, вся программа рассматривается как единственная часть пространственного разбиения.) 3. Находим максимальную степень параллелизма, требующего О (и) синхронизаций. Применяем алгоритм 11.59 к каждой из частей разбиений, найденных на шаге 2, для поиска конвейеризуемого параллелизма. Затем применим алгоритм 11.54 к каждой из частей, назначенных каждому процессору (или к телу последовательного цикла, если конвейеризуемый параллелизм не обнаружен). 1О36 Глава ! !.
Оптимизация параллелизма и локальности 4. Находим максимальную степень параллелизма с последовательно возрастающими степенями синхронизаций, для чего рекурсивно применяем шаг 3 к вычислениям, принадлежащим каждому из пространственных разбиений, сгенерированных на предыдущем шаге. а Пример 11.65. Вернемся к примеру 11.56. Шаги 1 и 2 алгоритма 11.64 не обнаруживают никакого параллелизма, так что нам требуется больше чем константное количество синхронизаций для распараллеливания данного кода. Применение на шаге 3 алгоритма 11.59 определяет, что имеется только один внешний цикл, который представляет собой внешний цикл в исходном коде на рис.
11.53. Таким образом, цикл не обладает конвейеризуемым параллелизмом. Во второй части шага 3 мы применяем алгоритм 11.54 для распараллеливания внутреннего цикла. Код в пределах раздела рассматривается нами как целая программа, с тем отличием, что номер раздела при этом считается символьной константой. В итоге мы обнаруживаем, что внутренний цикл распараллеливаем, а значит, код может быть распараллелен с использованием и барьеров синхронизации. о Алгоритм 11.64 находит в программе весь возможный параллелизм на каждом уровне синхронизации. Алгоритм предпочитает схемы распараллеливания с меньшей степенью синхронизации, однако меньшая степень синхронизации не означает минимизации взаимодействия. Далее мы рассмотрим две модификации алгоритма, которые призваны преодолеть это слабое место. Учет стоимости взаимодействия Если не найден параллелизм, не требующий синхронизации, шаг 2 алгоритма 11.64 распараллеливает каждый сильно связанный компонент независимо.
Однако может оказаться возможным распараллелить ряд компонентов без синхронизации и взаимодействия. Одно из решений состоит в жадном поиске параллелизма, не требующего синхронизации, среди подмножеств графа зависимостей программы, которые совместно используют большое количество данных. Если между сильно связанными компонентами требуется взаимодействие, то можно заметить, что одно взаимодействие может оказаться существенно дороже других. Например, стоимость перемещения матрицы значительно больше, чем простой обмен информацией между двумя соседними процессорами. Предположим, что а! и аз — инструкции в двух различных сильно связанных компонентах, обращающихся к одним и тем же данным в итерациях 11 и 1з соответственно, Если мы не можем найти отображения разделов (С!, с!) и (Сз, сз) для инструкций а! и зз, такие, что С!ц + с! — Сз!з — са = О., 1037 11.9.
Конвейеризация то вместо удовлетворения указанного ограничения можно попытаться удовлетворить ограничению Сз!1+ сз — Сз]з — сз < б, где б -- малая константа. Компромисс между синхронизацией и взаимодействием Иногда оказывается более выгодным выполнить большее количество синхронизаций, минимизируя при этом обмен информацией. В примере 11.66 рассматривается одна такая ситуация. Таким образом, если мы не можем распараллелить код с использованием взаимодействия только между соседними строго связаннымн компонентами, то вместо независимого распараллеливания каждого компонента мы должны попытаться конвейеризовать вычисления. Как показано в примере 11.66, конвейеризация может быть применена к последовательности циклов. Пример 11.66.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
