А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 203
Текст из файла (страница 203)
Таким образом, уравнение рз1~+1~ = г2!2+ + 12 можно переписать как !з р1 к2 (!1 12)) 12 1 б) Приведенные выше уравнения в общем случае имеют несколько решений. Однако мы все равно можем использовать исключение Гаусса для решения уравнений относительно !з и !2. Мы исключаем максимально возможное количество переменных, пока не останемся только с теми переменными, исключить которые невозможно. Получающееся в результате решение для !з и !2 имеет вид Здесь $5 — верхнетреугольная матрица, а 1 — вектор свободных переменных, пробегающий по всем целым числам.
в) Можно применить использованный в п. 2, а способ, чтобы переписать уравнение разбиений. Подставляя вектор (!ы!2, 1) в результат, полученный в п. 2, б, ограничения разбиений можно записать в виде Ы ~Сз — С2 (сз — с2)~ П вЂ” ' 0 й 3. Избавимся от переменных, не связанных с разбиениями. Приведенные выше уравнения выполняются для всех комбинаций 1, если Сь — С2 (с~ — с2)~ П = О [ Перепишем эти уравнения в виде Ах = О, где х — вектор всех неизвестных коэффициентов аффинного разбиения. 4. Найдем ранг аффинного разбиения и решение для матриц коэффициентов.
Поскольку ранг аффинного разбиения не зависит от значений константных членов разбиения, мы убираем все неизвестные из константных векторов наподобие сь и с2, тем самым заменяя уравнение Ах = О упрощенными ограничениями А'х' = О. Мы находим решение уравнения А'х' = О и выражаем его как  — множество базисных векторов нуль-пространства А'. 990 Глава 11. Оптимизация параллелизма и локальности 5. Находим константные члены. Выводим по одной строке искомого аффинного разбиения из каждого базисного вектора в В и, используя уравнение Ах = О, получаем константные члены.
и Заметим, что в шаге 3 игнорируются ограничения, накладываемые границами циклов на переменные С Ограничения в результате оказываются более строгими, так что алгоритм оказывается безопасным, т.е. мы накладываем ограничения на С и с в предположении произвольности с По-видимому, могут существовать и иные решения для С и с, корректные только потому, что некоторые значения $ невозможны. То, что мы не ищем эти иные решения, может привести к снижению степени оптимизации, но не может привести к изменениям в программе, которые изменили бы ее функциональность. 11.7.5 Простой алгоритм генерации кода Алгоритм 11.43 генерирует аффинные разбиения, которые разделяют вычисления на независимые части. Полученные части могут быть назначены разным процессорам произвольным образом, поскольку они не зависят друг от друга. Процессору может быть назначено несколько вычислительных модулей, причем их вычисления могут чередоваться, лишь бы при этом операции в пределах каждого модуля, которые зависят друг от друга, выполнялись в требуемом порядке.
Относительно просто сгенерировать корректную программу для заданного аффинного разбиения. Мы сначала рассмотрим алгоритм 11.45 -- простой метод генерации кода для одного процессора, который выполняет каждую из независимых частей последовательно. Такой код оптимизирует временную локальность, поскольку обращения к массиву с несколькими использованиями весьма близки по времени.
Кроме того, код может быть легко преобразован в ЗРМ0-программу, которая выполняет каждую часть на отдельном процессоре. К сожалению, генерируемый таким образом код неэффективен; позже мы рассмотрим оптимизации, которые повышают его эффективность. Основная идея заключается в следующем. У нас имеются границы индексных переменных вложенности циклов, а в алгоритме 1!.43 мы определили разбиение для обращений некоторой инструкции з. Предположим, что мы хотим сгенерировать последовательный код, который последовательно выполняет действия каждого процессора.
Мы создаем внешний цикл, который обходит все процессоры, т.е. каждая итерация этого цикла выполняет операции, назначенные одному из процессоров, соответствующему данной итерации. Исходная программа вставляется в этот цикл в качестве его тела; кроме того, добавляются проверки, гарантирующие, что каждый процессор выполняет только те операции, которые были ему назначены. Таким образом, мы гарантируем, что процессор выполняет все предназначенные ему команды и делает это в исходном последовательном порядке. ! !.7.
Поиск параллельности, не требующей синхронизации Пример 11.44. Сгенерируем код, который последовательно выполняет независимые части из примера 11.41. Исходная последовательная программа с рис, 1!.2б повторена на рис. 11.28. аког (1 = 18 х <= 100! 1++) аког (з = 1з з <= 100; З++) ( Х[1,з] = Х[з.,з] + У[1-1,2]з /* (а1) */ У[а,з] = У[1,з] + Х[з.,З-1]з /* (в2) */ Рнс. 11.28.
Исходная последовательная программа, представленная на рнс. !1.2б (повтор) В примере 11.42 алгоритм аффинного разбиения обнаруживает одну степень параллелизма. Таким образом, пространство процессоров может быть представлено одной переменной р. Вспомним также, что мы выбрали аффинное разбиение так, что для всех значений индексных переменных 1 и з (1 <1 < 100 и 1 < з < 100) 1. экземпляр (г, )) инструкции вз назначается процессору р = з — 1 — 1; 2, экземпляр (з, )') инструкции аз назначается процессору р = г' — зз Можно сгенерировать код в три этапа.
1. Для каждой инструкции находим все идентификаторы процессоров, участвующихв вычислениях. Объединимограничения1 < ( < 100 и 1 < з < 100 с одним из уравнений, р = г' — 1 — 1 или р = з' — з', и исключим г' и у, получив новые ограничения: а) †1 < р < 98 при использовании функции р = г' — з — 1, которая была получена для инструкции аз,.
б) — 99 < р < 99 при использовании функции р = ~, '— ), которая была получена для инструкции вя. 2. Находим идентификаторы всех процессоров, участвующих в выполнении любой инструкции. После объединения указа гных выше диапазонов мы получаем — 100 < р < 99; этих границ достаточно, чтобы охватить все экземпляры обеих инструкций — и вз, и вз. 3. Сгенерируем код, который последовательно выполняет вычисления каждой части разбиения.
Код, показанный на рис. 11.29, имеет внешний цикл, проходящий по всем идентификаторам процессоров, участвующих в вычислениях (строка 1). Для каждого идентификатора генерируются индексы 992 всех итераций исходной последовательной программы (строки 2 и 3), что- бы выбрать те из них, которые должен выполнить процессор р.
Проверки в строках 4 и 6 обеспечивают выполнение инструкций а~ и аз только тогда, когда их должен выполнять процессор р. Рис. 11.29. Переписанный кол с рис. 11.28 с итерациями в пространстве процессоров Несмотря на то что сгенерированный код корректен, он очень неэффективен. Во-первых, хотя каждый процессор выполняет вычисления не более чем из 99 итераций, он генерирует индексы циклов для 100 х 100 итераций, на порядки больше, чем это необходимо. Во-вторых, каждому суммированию во внутреннем цикле предшествует проверка, являющаяся источником накладных расходов.
С неэффективностями такого рода мы будем бороться в разделах 11.7.6 и 11.7.7 соответственно. о Хотя код на рис. 1!.29 и выглядит как созданный для однопроцессорной системы, можно взять его внутренние циклы в строках 2-8 и выполнить их на 200 различных процессорах, каждый из которых имеет разное значение р — от — 100 до 99.
Можно разделить ответственность за выполнение внутреннего цикла и между меньшим количеством процессоров, лишь бы каждый процессор знал, за какие значения р он отвечает, и выполнял строки 2 — 8 для этих значений р. Алгоритм 11.45. Генерация кода, последовательно выполняющего части разбие- ния программы Вход: программа Р с аффинным обращением к массиву. Каждая инструкция в в программе имеет связанные с ней границы вида В,!+ Ь, > О, где 1 — вектор ин- дексов циклов вложенности, в которой находится в. С з связано также разбиение С,1+ с, = р, где р — пт-мерный вектор переменных, представляющий идентифи- катор процессора; т — максимальный ранг разбиения среди разбиений для всех инструкций программы Р.
ВыхОД: программа, эквивалентная Р, с итерациями в пространстве процессоров вместо итераций, связанных с индексами циклов. МетоД: делаем следующее. 1) аког (р = -100; 2) бог (х = 1 3) аког (3 4) зй 5) 6) х1 7) 8) ) Глава 11. Оптимизация параллелизма и локальности р <= 99; р++) з <= 100р 1++) = 1; 3 <= 100; 3++) ( (р == 1-3-1) Х[,,3) = Х[з,3) + У['-1,3); /* (в1) */ (Р == з.-3) у[1 3) = х[1,3-1) + у[1,31; /* (в2) */ 993 11.7. Поиск параллельности, не требующей синхронизации 1. Для каждой инструкции используем исключение Фурье — Моцкнна, чтобы удалить из границ все индексные переменные.
2. Используем алгоритм 11.13 для определения границ идентификаторов разбиения. 3. Генерируем циклы, по одному для каждого из гп измерений в пространстве процессоров. Пусть р = ]рырз,...,р ] — вектор переменных для этих циклов, т.е. для каждого измерения в пространстве процессоров имеется одна переменная. Диапазон каждой переменной цикла р, определяется объединением пространств разбиений для всех инструкций программы Р. Заметим, что объединение пространств разбиений не обязательно выпуклое. Чтобы алгоритм оставался простым, вместо перечисления только тех частей, в которых имеются непустые вычисления, можно установить нижнюю границу для каждого р; равной минимальному значению среди всех нижних границ инструкций, а верхнюю — максимальному значению среди всех верхних границ.
В этом случае некоторые значения р могут не иметь никаких операций. Код, выполняемый каждой частью, представляет собой исходную последовательную программу. Однаиэ каждая инструкция защищена предикатом, так что выполняются только принадлежащие части операции. П Пример работы алгоритма 11.45 будет приведен ниже.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
