А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 209
Текст из файла (страница 209)
В примере 11.56 показан один из таких случаев. Чтобы удовлетворить все зависимости, каждая итерация внешнего цикла должна выполнять в точности те вычисления, которые содержатся в исходном коде. Однако такой код может все еше быть распараллелен на уровне внутренних циклов, для чего может потребоваться добавление как минимум и синхронизаций, где и— количество итераций во внешнем цикле. аког (з = 0; з < 100; 1++) ( гог (3 = 0; 3 < 100Р 3++) х[,) = х[,) + .[, ,)! /* (.~) */ 2[1) = х[А[з)); /* (а2) */ а) б) Рнс.
11.53. Последовательный внешний цикл (а) и его граф зависимостей программы (б) Пример 11.56. На рис. 11.53 показана более сложная версия проблемы, с которой мы сталкивались в примере 11.50. Как видно из графа зависимостей программы на рис. 1!.53, б, инструкции а~ и аз принадлежат одному и тому же сильно связанному компоненту. Поскольку мы не знаем содержимое матрицы А, мы должны считать, что обращение в инструкции зз может считывать любой из элементов Х. В приведенном коде имеется истинная зависимость инструкции аз от аг и антизависимость в! от аз. Для конвейеризации нет никакой возможности, поскольку все операции, принадлежащие итерации 1 во внешнем цикле, должны предшествовать операциям в итерации (+ 1. Продолжим поиск возможностей распараллеливания во внутреннем цикле.
При этом мы обнаруживаем, что итерации во втором цикле могут быть распараллелены без применения синхронизации. Таким образом, все- 1022 Глава ! !. Оптимизация параллелизма и локальности го нам потребуется 200 барьеров синхронизации — по одному до и после каждого выполнения внутреннего цикла. П 11.9.6 Ограничения временного разбиения Перейдем теперь к задаче поиска конвейерного распараллеливания. Наша цель состоит в превращении вычисления в набор конвейеризуемых задач. При поиске конвейерного параллелизма мы не решаем, как при распараллеливании циклов, что и каким процессором будет выполняться. Вместо этого мы задаем следующий фундаментальный вопрос: каковы все возможные последовательности выполнения, которые соблюдают исходные зависимости данных в цикле? Очевидно, что всем зависимостям данных удовлетворяет исходная последовательность выполнения.
Вопрос в том, существуют ли аффинные преобразования, позволяющие создать альтернативный план выполнения, при котором итерации внешнего цикла выполняют множество операций, отличающееся от исходного, но при этом удовлетворяют всем зависимостям данных. Если мы можем найти такие преобразования, то можем конвейеризовать цикл.
Ключевой момент заключается в том, что если имеется свобода в планировании операций, то имеется и параллелизм; детально вопрос о том, как получить конвейерный параллелизм из таких преобразований, будет рассмотрен ниже. Для того чтобы найти приемлемое переупорядочение внешнего цикла, нам надо найти одномерные аффинные преобразования, по одному для каждой инструкции, которые отображают исходные значения индекса цикла на номер итерации во внешнем цикле.
Преобразования допустимы, если присваивания удовлетворяют всем зависимостям данных в программе. "Ограничения временнбго разбиения*' (!)гпе-раг111!оп сопя!га)п!з), показанные ниже, просто гласят, что если одна операция зависит от другой, то первая не должна быть назначена итерации внешнего цикла более ранней, чем вторая. Если они назначены одной и той же итерации, то понятно, что первая операция должна быть выполнена в пределах этой итерации только после второй. Отображение аффинного разбиения программы является корректным временным разбиением (!ела!-11те рагй1юп) тогда и только тогда, когда для любых двух (не обязательно различных) зависимых обращений, скажем, У~ = (Е1,11, В1, Ь1) в инстРУкции а1, вложенной в 4 циклов, и Уз = (%г, !з, Вз, Ьз) в инстРУкции вз, вложенной в г(з циклов, отображения одномерных разбиений (С1,с1) и (Сг, сз) ДЛЯ ИНСтРУКЦИй а1 И аг СООтВЕтСтВЕННО УДОВЛЕтВОРЯЮт ОГРаНИЧЕНИЯМ ВРЕМЕННОГО разбиения: ° для всех 11 из У"' и 1г из У"г, таких, что а) !1 ~мзг 12 б) В111+ Ь1 > О, 1О2З 11.9.
Конвейеризация в) В212 + Ь2 ) 0 и г) Г! 11 + 11 = Р212 + 12, выполняется С!11 + с1 < С212 + сг Это ограничение, проиллюстрированное на рис. 11.54, выглядит удивительно похожим на ограничения разбиения пространства. Это ослабление ограничений разбиения пространства состоит в том, что если две итерации обращаются к одной и той же ячейке памяти, то они не обязательно должны быть отображены в один и тот же раздел; мы требуем только, чтобы сохранялся относительный порядок их выполнения, т.е. в этих ограничениях вместо = используется <.
< 1 1 г Массив Временные шаги Рис. 11.54. Ограничения временных разбиений Мы знаем, что существует как минимум одно решение ограничений временных разбиений. Можно отобразить операции в каждой итерации внешнего цикла на ту же самую итерацию, и при этом все зависимости данных будут удовлетворены. Это — решение ограничений временных разбиений для программы, которая не может быть конвейеризована. С другой стороны, если можно найти несколько независимых решений ограничений временных разбиений, то программа может быть конвейеризована.
Каждое независимое решение соответствует циклу во внешней полностью переставляемой вложенности. Как и следовало ожидать, у программы из примера 11.56, у которой отсутствует конвейеризуемый параллелизм, имеется только одно независимое решение ограничений временных разбиений, а у примера БОК-кода имеется два независимых решения. Пример 11.57. Рассмотрим пример 11.56, в частности зависимости данных между обращениями к массиву Х в инструкциях а! и а2. Поскольку в аз обращение ППППП П П П П П П ППППП П П П П П П П П П П 1024 Глава ! 1.
Оптимизация параллелизма н локальности не является аффинным, аппроксимируем это обращение путем моделирования матрицы Х в анализе зависимостей, включающих аг, просто как скалярной переменной. Пусть (г, г) — индексное значение динамического экземпляра ан а 1'— индексное значение динамического экземпляра аг. Пусть отображениями а1 и аг являются соответственно ([Сы, Сгг], сг) и ([Сш] сг).
Рассмотрим сначала временные ограничения, накладываемые зависимостями зг от ан Мы получаем 1 < 1', т.е. преобразованная (1, г)-я итерация а1 должна выполняться не позже преобразованной г'-й итерации аг. Сы С1г1 +с1 < Сг1г +сг Раскрывая это соотношение, получаем Сыг+ Сг1,г + с| < Сшг' + сг Поскольку г может иметь произвольно большое значение, не зависящее от 1 и г', Сгг должно быть равно О. Таким образом, одно из возможных решений ограничений следующее: Сы = Сг1 = 1 и Сгг = сг = сг = 0 Такие же рассуждения о зависимости а1 от зг и аг от самой себя приводят к аналогичному ответу.
В этом частном решении 1-я итерация внешнего цикла, состоящая из экземпляра г инструкции аг и всех экземпляров (1, г) инструкции аы получает временную отметку г. Прочие допустимые варианты выбора Сы, Сгы сг и сг дают аналогичные назначения, хотя имеются временные метки, когда ничего не происходит. Иначе говоря, все способы планирования внешнего цикла требуют, чтобы итерации выполнялись в том же порядке, в котором они выполняются в исходном коде. Это утверждение справедливо и когда все 100 итераций выполняются на одном и том же процессоре, и когда они выполняются на 100 различных процессорах, и в любом промежуточном между этими двумя крайностями случае. и Пример 11.58. В КОК-коде, показанном на рис.
11.50, а, обращение для записи Х [г+ 1] зависит от самого себя и от трех обращений для чтения. Мы ищем отображение ([Сн Сг], с) для инструкции присваивания, такое, что при наличии зависимости (1', гс) от (1, г) выполняется соотношение По определению (г, 1) с (г', гг); т.е. либо 1 < 1', либо (1 = 1' Л г < гс). Рассмотрим три пары зависимостей данных. 1025 11.9. Конвейеризация 1.
Истинная зависимость обращения для чтения Х [т'+ 2] от обращения для записи Х [з + 1]. Поскольку эти экземпляры должны обращаться к одному и тому же месту в памяти, з' + 1 = у'+ 2, или з = ~'+ 1. Подставляя з = 2ч + 1 во временные ограничения, мы получаем С1 (г' — 1) — Сз > 0 Поскольку т' = з'+ 1, з > з', и предыдущие ограничения сводятся к 1 < г'. Следовательно, с — с >о 2. Антизависимость обращения для записи Х [з + 1] от обращения для чтения Х [з + 2].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
