А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 201
Текст из файла (страница 201)
йот (Е = )с1-11 К >= 2; К--) аког (3 = 2; 3 <= 31; 3++) йот (1 = 2; 1 <= 11з 1++) РИ[1,1с, 3, з.] = пн[ 1,1с, 3, з.] + 0[К, 3, 1] *пн[ 1, 1с+1, 3, 1]; Рнс. 11.23. Фрагмент кода многосеточного алгоритма Код на рис. 11.23 работает со скалярной переменной Т и различными массивами разной размерности. Сначала рассмотрим использование переменной Т. Поскольку каждая итерация цикла использует одну и ту же переменную Т, мы не можем выполнять их параллельно. Но Т применяется только для хранения дважды используемых в одной и той же итерации общих подвыражений.
В первом из трех вложений циклов на рис. 11.23 каждая итерация наиболее глубоко вложенного цикла записывает в Т значение, которое тут же используется два раза в пределах той же итерации. Можно устранить зависимости, заменив каждое использование Т выражением, стоящим справа в операции присваивания, без изменения семантики программы. Можно также заменить скаляр Т массивом. Тогда каждая итерация Ц, з) будет использовать собственный элемент массива Т ~2', (). При таком изменении вычисление каждого элемента массива в каждой инструкции присваивания зависит только от других элементов массивов с теми же значениями последних двух компонентов [соответственно 7' и з).
Таким образом, можно сгруппировать все операции, работающие с (2, з)-м элементом массивов, в один модуль и выполнять его в исходном последовательном порядке. Такая модификация дает О[ — 1) х [[[ — 1) вычислительных модулей, независимых друг от друга. Заметим, что вторая и третья вложенности в исходной программе включают третий цикл с индексом к. Однако в связи с отсутствием зависимостей между 980 Глава !1. Оптимизация параллелизма и локальности динамическими обращениями с одними и теми же значениями з и з можно безопасно выполнять циклы Й внутри циклов з и з, т.е. внутри вычислительного модуля. Знание того, что эти вычислительные модули независимы, позволяет выполнить множество преобразований этого кода. Например, вместо выполнения кода так, как указано в исходной программе, однопроцессорная система может осуществить те же вычисления путем выполнения за один раз модулей с независимыми вычислениями.
Это приводит нас к коду, показанному на рис. 11.24, в котором результаты вычислений тут же используются в других вычислениях, что приводит к повышению временнбй локальности. Рог () = 2з ] <= з1з з++) Тот (1 = 2з 1 <= з1з з++) ( АР[э,1] Т[з,1] 1. О/(1. О + АР[), 1) ); Р[2,з,11 = т[2,1]*АР[),з]з РИ[ 1, 2, 3, 1] = Т[5, 1] *РИ[ 1, 2, ~, 1] з Кос (К = Зз К <= К1-1; К++) АМ[3 1) = АР[Э 1] ' АР[э,1] Т(з,ь) = ...АР[э,з.] — АМ[),1)ЯР[К-1,5,1]...з Р(К,з,1] = Т[З,1)*АР[3,1]з ОН[1, К, з, 1 ] = Т [], 1] * (РИ[1, К, З, 1] + РИ[1, К-1, з, 1) ) ..
Тот (К = К1-1з К >= 2з К--) РИ[1 К ~ 1) = РХ[1 К з 3.] + Р[К з з.]*ОХ[1 К+1 Рис. !!.24. Результат преобразования кода, представленного па рис. 1!.23 Независимые вычислительные модули могут также быть назначены разным процессорам и выполняться параллельно, без какой бы то ни было синхронизации или взаимодействия процессоров. Поскольку имеется [з( — 1) х [(( — 1) независимых вычислительных модулей, можно загрузить работой до О) — 1) х х [(( — 1) процессоров. При организации процессоров в виде двумерного массива с индексами (2, з), где 2 < з < з[ и 2 < з < (1, БРМП-программа, выполняемая каждым из процессоров, представляет собой просто тело внутреннего цикла на рис.
11.24. Приведенный пример иллюстрирует фундаментальный подход к поиску параллельности, не требующей синхронизации. Сначала мы разбиваем вычисления на максимально возможное количество независимых модулей. Это разбиение показывает, какие варианты планирования доступны. Затем мы некоторым обра- 981 ! 1.7. Поиск параллельное~и, не требующей синхронизации зом распределяем вычислительные модули по процессорам в зависимости от их количества. Наконец мы генерируем ЯРМО-программу, которая выполняется на каждом из процессоров. 11.7.2 Разбиения аффинного пространства Говорят, что вложенность циклов имеет й степеней параллельности, если в ней имеется Й распараллеливаемых циклов, т.е. таких циклов, что между их различными итерациями отсутствуют зависимости данных.
Например, код на рис. 11.24 имеет 2 степени параллельности. Оказывается удобно назначать операции в вычислении с Й степенями параллельности массиву процессоров с Й измерениями. Изначально будем считать, что каждое измерение процессорного массива имеет столько же процессоров, сколько итераций в соответствующем цикле. После обнаружения всех независимых вычислительных модулей мы отображаем эти "виртуальные" процессоры на фактические.
На практике каждый процессор отвечает за выполнение достаточно большого количества итераций, поскольку в противном случае выполняемая процессором работа не сможет компенсировать накладные расходы распараллеливания. Мы разбиваем распараллеливаемую программу на элементарные инструкции, такие как трехадресные команды. Для каждой инструкции мы находим разбиение аффинного пространства, которое отображает каждый динамический экземпляр инструкции, идентифицируемый его индексом цикла, на идентификатор процессора. Пример 11.40. Как говорилось выше, код на рис.
11.24 имеет две степени параллельности. Мы рассматриваем массив процессоров как двумерное пространство. Пусть (ры рз) — идентификатор процессора в массиве. Схема распараллеливания, рассматривавшаяся в разделе 11.7.1, может быть описана простой функцией аффинного разбиения.
Все инструкции в первой вложенности циклов имеют одно и то же аффинное разбиение Все инструкции во второй и третьей вложенностях имеют следующее аффинное разбиение: П Алгоритм поиска параллельности, не требующей синхронизации, состоит из трех шагов. 982 Глава 11.
Оптимизация параллелизма и локальности 1. Для каждой инструкции программы находим аффинное разбиение, максимизирующее степень параллельности. Заметим, что в общем случае в качестве вычислительного модуля рассматриваются не отдельные обращения, а инструкции. К каждому обращению в инструкции должно применяться одно и то же аффинное разбиение. Такое группирование обращений имеет смысл, поскольку между обращениями в одной инструкции практически всегда имеются зависимости. 2. Назначаем полученные независимые вычислительные модули процессорам и выбираем чередование шагов для каждого процессора.
При назначении следует учитывать вопросы локальности. 3. Генерируем ЯРМО-программу для каждого процессора. Далее мы рассмотрим, как найти функции аффинного разбиения, как генерировать последовательную программу, которая выполняет полученные при разбиении разделы друг за другом, и как генерировать ЗРМП-программу, которая выполняет разделы на разных процессорах. После того как мы рассмотрим обработку параллельности с синхронизацией в разделах 1!.8-11.9.9, в разделе 11.10 мы вернемся к упомянутому выше шагу 2 и обсудим оптимизацию локальности в однопроцессорных и многопроцессорных системах. 11.7.3 Ограничения разбиений пространства Для отсутствия взаимодействия каждая пара операций с зависимостями данных должна быть назначена одному и тому же процессору.
Эти ограничения мы будем называть "ограничениями разбиений пространства". Любое отображение, удовлетворяющее этим ограничениям, создает независимые друг от друга разделы. Заметим, что эти ограничения могут быть удовлетворены, если поместить все операции в один раздел. К сожалению, в этом "решении" параллельность отсутствует как таковая. Наша цель заключается в создании максимально возможного количества независимых разделов, удовлетворяющих ограничениям разбиения пространства, т.е. операции не помещаются в один раздел, если без этого можно обойтись. Поскольку мы ограничили себя аффинными разбиениями, вместо количества независимых модулей мы можем максимизировать степень (количество измерений) параллелизма.
Иногда оказывается возможным создать больше независимых модулей при использовании кусочно-аффинного разбиения (р1есеюЬе ац1пе раг6- йоп). Кусочно-аффинное разбиение разделяет экземпляры одного обращения на различные множества, позволяя при этом выполнять для каждого множества свое аффинное разбиение. Однако здесь мы не будем рассматривать эту возможность. Формально аффинное разбиение программы не требует синхронизации 1зупспгоп|га11оп Ггее) тогда и только тогда, когда для каждых двух (не обязательно 983 11.7. Поиск параллельности, не требующей синхронизации ° для всех 1т из У~' и 1з из г,~', таких, что а) В11т+Ьт >О, б) Вз1з+ Ьз ) О и в) Гт)т + 11 = Ез1з + $ъ выполнЯетсЯ соотношение С|11 + ст = Сз1з + сз. Цель алгоритма распараллеливания состоит в поиске для каждой инструкции разбиения с наивысшим рангом, удовлетворяющего приведенным ограничениям.
ППППП П П П П П П П П ППППП ППП ППП ППП ППП ППП Циклы П П П П ППП Идентификатор процессора Рис. 11.25. Ограничения разбиений пространства Показанная на рис. 11.25 диаграмма иллюстрирует суть ограничений разбиений пространства. Предположим, что есть два статических обращения в двух вложенностях циклов с индексными векторами 11 и 1з.
Эти обращения зависимы в том смысле, что они вместе обращаются как минимум к одному общему элементу массива и как минимум одно из них — обращение для записи. На рисунке показаны некоторые динамические обращения в двух циклах, которые обращаются к одному и тому же элементу массива согласно функциям аффинного доступа Ет1т + 11 и Ез1з + $з. Синхронизация в этом случае не будет нужна только в том случае, когда аффинные разбиения для двух статических обращений Ст1т + ст и Со1з + сз назначают динамические обращения одному и тому же процессору.
различных) зависимых обращений У~ = (ГП1ы Вы Ьт) в инструкции вт, вложен- ной в 4 циклов, и У~ = ($'з, 1з, Вз, Ьз) в инструкции вз, вложенной в с1з циклов, разбиения (Сыс1) и (Сз,сз) инструкций вт и вз соответственно удовлетворяют следующим ограничениям разбиения пространства: 984 Глава 11. Оптимизация параллелизма н локальности Если мы выберем аффинное разбиение с рангом, равным максимальному рангу среди всех инструкций, то мы получим наибольший возможный параллелизм. Однако при таком разбиении некоторые процессоры могут простаивать в то время, когда другие процессоры выполняют инструкции, аффинные разбиения которых имеют меньший ранг.
Эта ситуация может быть вполне приемлема, если время, затрачиваемое на выполнение этих инструкций, относительно мало. В противном случае можно выбрать аффинное разбиение, ранг которого меньше максимально возможного, но при этом больше О. В примере 11.41 показана небольшая программа, разработанная для иллюстрации мощи этого метода. Реальные приложения обычно существенно проще, но могут иметь граничные условия, напоминающие некоторые из рассматривавшихся нами. Данный пример будет использоваться нами и далее в этой главе в качестве иллюстрации того, что в случае программы с аффинным доступом и относительно простыми ограничениями разбиения пространства решение может быть получено путем применения стандартных методов линейной алгебры и что требуемая ЗРМР-программа может быть механически сгенерирована на основе аффинных разбиений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
