А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 202
Текст из файла (страница 202)
Пример 11.41. В этом примере показано, каким образом формулируются ограничения разбиения пространства для программы, состоящей из небольшой вложенности циклов с двумя инструкциями, аз и аз, показанной на рис. 11.26. аког (1 = 1; 1 <= 100; 1++) ~ох (З = 1; З <= 100; З++) ( Х[1 З] = Х[з.,з] + У[з-1 З]; /* (в1) */ Х[з.,>] = У[1,2] + Х[з.,з-1]; /* (в2) */ Рис. 11.26. Вложенность циклов, демонстрирующая длинную цепочку зависимых операций Зависимости данных этой программы показаны на рис. 11.27.
Здесь каждая черная точка представляет экземпляр инструкции аз, а каждая белая точка — экземпляр инструкции вз, Точка с координатами [1, з) представляет экземпляр инструкции, выполняемой для данных значений индексов циклов. Заметим, однако, что в каждой паре для одного и того же значения [г, з) экземпляр вз находится непосредственно под экземпляром аы так что масштаб ) [по вертикали) на рисунке больше масштаба 1 [по горизонтали). Заметим, что Х [з, з] записывается инструкцией аз [г, з), т.е.
экземпляром инструкции вз со значениями индексов 1 и з] После оно считывается инструкцией аз [(, з + 1), так что инструкция аз [(, з) должна предшествовать инструкции аз [г, з + 1). Вот почему на диаграмме от черных точек к белым направлены вер~и- 985 1!.7. Поиск параллельности, не требующей синхронизации / =4 ° 4, О 1 =3 2 =2 1 2 3 4 5 6 Рис. 11.27. Зависимости в коде из примера !!.4! кальные стрелки. Аналогично У [1,7] записывается инструкцией а2 (г, 2) и позже считывается инструкцией а! (1+ 1,7).
Таким образом, инструкция аз (1,7) должна предшествовать инструкции а3 (г + 1, 2), что поясняет наличие стрелок от белых точек к черным. Из приведенной диаграммы легко увидеть, что данный код можно распараллелить без синхронизации, назначив каждую цепочку зависимых операций одному и тому же процессору. Однако написать КРМП-программу, которая реализует эту схему отображения, не так-то легко. В то время как циклы в исходной программе содержат по 100 итераций, всего имеется 200 цепочек, одна половина из которых начинается и заканчивается инструкциями аы а другая половина начинается и заканчивается инструкциями аз.
Длины цепочек варьируются от 1 до 100 итераций. Поскольку имеются две инструкции, мы ищем два аффинных разбиения, по одному для каждой инструкции. Все, что нам надо, — выразить ограничения разбиений пространств для одномерных аффинных разбиений. Эти ограничения будут использованы позже методом, который пытается найти все независимые одномерные аффинные разбиения и скомбинировать их для получения многомерных аффинных разбиений. Таким образом, мы можем представить аффинное разбиение для каждой инструкции матрицей 1 х 2 и вектором 1 х 1, которые транслируют вектор индексов [г,Я в единственный номер процессора.
Пусть ([СПСш], [с3]) и ([С23С22], [сз]) представляют собой одномерные аффинные разбиения для инструкций а! и аз соответственно. Применим шесть проверок зависимостей данных. 1. Между записями Х [1,7] в инструкции з3. 986 Глава 11. Оптимизация параллелизма н локальности 2. Между записью Х [г, Я и чтением Х [г, Я в инструкции ап 3.
Между записью Х [г, Я в инструкции а~ и чтением Х [г, з — Ц в инструкции а2. 4. Между записями У [г, Я в инструкции аз. 5. Между записью У [г, з] и чтением У [г, 1] в инструкции аз. 6. Между записью У [г, т] в инструкции аз и чтением У [1 — 1, з] в инструкции аз 1 < г < 100 1 < г' < 100 г=г / 1 < 1 < 100 1< за<100, у =.1ч — 1 имеем [с„с„] []+ [.,] = [с., с„] [,]:-[.,] Иначе говоря, первые четыре условия гласят, что (г, з) и (1', ~') лежат внутри пространства итераций вложенности циклов, а последние два — что динамические обращения Х [г,Я и Х [1,1 — Ц относятся к одному и тому же элементу массива. Аналогично можно вывести и ограничения разбиений пространства и для обращений У [1 — 1, Я в инструкции аз и У [г, Я в инструкции ап и 11.7.4 Решение ограничений разбиений пространств После того как ограничения разбиений пространства определены, для поиска аффинных разбиений, удовлетворяющих этим ограничениям, можно использовать стандартные методы линейной алгебры.
Давайте рассмотрим поиск решения примера 11.41. Пример 11.42. Аффинное разбиение для примера 11.41 можно найти следующим образом. Как видите, все проверки зависимостей данных простые и повторяющиеся. В коде присутствуют только две зависимости — в случае 3 между экземплярами обращений к Х [1, Я и Х [1, з — Ц и в случае 6 между экземплярами обращений к У [г, 1] и У [г — 1,Я. Ограничения разбиений пространства, навязанные зависимостями данных между х [1, з] в инструкции а~ и х [1,1 — Ц в инструкции аз, можно выразить следующим образом. Для всех (г, у) и (1, 1 ), таких, что 987 11.7.
Поиск параллельности, не требующей синхронизации 1. Создаем ограничения разбиений пространства, показанные в примере 11.41. Границы циклов используются только при определении зависимостей данных, но не в остальной части алгоритма. 2. В уравнениях неизвестными переменными являются 1, ~.", 7', 7', Сы, Спн сы Сгы Сгг и сг. Уменьшим количество неизвестных, воспользовавшись уравнениями из функций обращений: 1 = 1' и 7' = 7' — 1. Мы используем метод исключения Гаусса, который из четырех переменных делает две— скажем, 1з = 1 = 1' и 12 = 7' = 7л — 1.
Уравнение для разбиения при этом превращается в [ Ы Сы — С21 С12 — Сгг~ + [с1 — с2 — Сгг~ = О Ы 3. Приведенное выше уравнение выполняется для всех комбинаций 1з и 12. Таким образом, должны выполняться следующие соотношения: Сы-С„=О Йг — Сгг = О сз — гг — С22 = О Если мы выполним те же действия над ограничениями, связанными с об- ращениями к У 11 — 1, Я и У 1з, Я, мы получим Сы -С„=О С!2 — С22 = О с1 — с2 + С21 = О Собрав все вместе и упростив, мы получим следующие соотношения; Сы = Сщ = — С22 = — Сгг = сг — с~ 4. Ищем все независимые решения уравнений, на этом шаге включая только неизвестные из матрицы коэффициентов и игнорируя неизвестные в константных векторах. В матрице коэффициентов имеется только один независимый выбор, так что искомые аффинные разбиения могут иметь ранг не выше 1.
Для простоты выбираем Сы = 1. Приравнять Сы к нулю нельзя, так как это приведет к матрице коэффициентов с нулевым рангом и отображению всех итераций на один и тот же процессор. Получаем Сгз = 1, Сгг = — 1 и Сгг = — 1. 5. Ищем постоянные члены. Мы знаем, что их разность сг — сз должна быть равна — 1. Для простоты выбираем сг = О; тогда сз = — 1. 988 Глава 11. Оптимизация параллелизма и локальности Пусть р — идентификатор процессора, выполняющего итерацию (1, т).
При использовании этого обозначения аффинное разбиение принимает вид + ]о~ Иначе говоря, (1, 2)-я итерация а1 назначается процессору р = 1 — 2 — 1, а (1, 2)-я итерация аз — процессору р = 1' †,1. и Алп1ритм 11.43. Поиск не требующего синхронизации аффинного разбиения программы с наивысшим рангом Вход: программа с аффинным обращением к массиву. Выход: разбиение.
Метод: выполнить следующее. 1. Найти все зависимые пары обращений в программе среди всех пар обращений У1 = (Р1,11, В1, Ь1) в инструкции ат, вложенной в д1 циклов, и У2 = = (Е2, 62, В2, Ьз) в инструкции а2, вложеннои в 112 циклов. Пусть (Сы с1 ) и (С2, сз) представляют (пока что неизвестные) разбиения инструкций а1 и аз соответственно. Ограничения разбиений пространства гласят, что если Р111 + 11 = Р212 + 12, то С111 + с1 = С212 + с2 для всех 11 и 12 в соответствующих границах циклов. Обобщим область определения итераций так, чтобы она включала все 11 из Е"' и 12 из Я"', т.е.
предполагается, что границы распространяются от минус до плюс бесконечности. Это предположение имеет смысл, поскольку аффинное разбиение не может использовать тот факт, что индексная переменная может принимать только ограниченное множество целочисленных значений. 2. Для каждой пары зависимых обращений снижаем количество неизвестных в векторах индексов. а) Заметим, что Р1 + 1' представляет собой тот же вектор, что и 989 11.7. Поиск параллельности, не требующей синхронизации Иначе говоря, добавляя дополнительный компонент 1 в низ вектора- столбца 1, вектор-столбец Г можно сделать дополнительным, последним столбцом матрицы г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
