А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 205
Текст из файла (страница 205)
! 1.28 Рис. 1!.34. Код к примеру 11.48 ) 1Г (р < -1) Х[101+р, 100]=Х[101+р, 100]+у[101+р-1, 100]; /* (В1) */ ) 1ООО Глава 11. Оптимизация параллелизма и локальности Семь примитивных аффиипых преобразований Каждое аффинное преобразование может быть выражено в виде ряда примитивных аффинных преобразований, каждое из юторых соответствует простому изменению на уровне исходного текста.
Существует семь типов примитивных преобразований. Первые четыре из них проиллюстрированы на рис. 11.35, а последние три, известные как унимодулярные преобразования, показаны на рис. 11.36. На рисунках показано по одному примеру для каждого примитива: исходный код, аффинное разбиение и код, получившийся в результате преобразования. Изображены также зависимости данных для кода до и после преобразования. Из диаграмм зависимостей данных видно, что каждый примитив соответствует простому геометрическому преобразованию и порождает относительно простое преобразование кода.
Вот эти семь примитивов. 1. Слияние. Преобразование слияния характеризуется отображением нескольких индексов циклов исходной программы на один и тот же индекс цикла. Новый цикл объединяет инструкции из разных циклов. 2. Расщепление. Расщепление представляет собой преобразование, обратное слиянию.
Оно отображает один н тот же индекс цикла для разных инструкций на различные индексы циклов в преобразованном коде. Таким образом, исходный цикл разбивается на несколько циклов. 3. Реиндексирование. Реиндексирование сдвигает динамические выполнения инструкции на постоянное количество итераций. Аффинное преобразование при этом содержит константный член. 4. Масштабирование. Последовательные итерации в исходной программе разносятся с использованием постоянного множителя. Соответствующее аффинное преобразование имеет положительный коэффициент, не равный 1. 5. Реверс. Выполнение итераций в цикле в обратном порядке.
Реверс характеризуется наличием юэффициента — 1 в аффинном преобразовании. 6. Перестановка. Перестановка внешнего и внутреннего циклов. Аффинное преобразование состоит из переставленных строк тождественной матрицы. 7. Сдвиг. Обход пространства итераций "под углом". Аффинное преобразование представляет собой унимодулярную матрицу с единицами на главной диагонали. Геометрическая интерпретация распараллеливания Приведенные аффинные преобразования, кроме слияния, порождаются путем применения алгоритма аффинного разбиения, не требующего синхронизации, 1001 11.7. Поиск параллельности, не требующей синхронизации ПРЕОБРАЗОВАННЫЙ КОД ИОХОДНЫЙ КОД РАЗБИЕНИЕ Слияние (бзяоп) Рог (р=1; р<=м; р++)( х[р] = е[р]; х[р] = х[р]; в| ..Р=( зз ° Р =.7 Расщепление (бвв]оп) Рог (р=1; р<=М; р++)( х1р1 = е[р]; х[р1 - х(р]; в| .. (=р в2 Э=Р Реиндек- сирование (те(пс]ех(пи) в|.
Р=( вз: р = ( — 1 Масштабирование (вса![пЕ) в|.р= 2*1 (вз: Р = .7) Рис. 11.35. Примитивные аффинные преобразования (часть 1) Еог (1=1; 1<=М; 1++) Х[1] = Е[1]; /*в1*/ Еог (1=1; 1<=м; 1++) Х[1] = Х[1]; /*в2*/ Рог (1=1; 1<=м; 1++) ( Х[1] = 2[11; /*в1*/ Х[11 = Х[1-1]; /*в2*/ Рог (1=1; 1<=м; 1++) Х[2*11 = Е[2*11; /*в1*/ е (1=1; 1<=гм; 1++) Х[1]=Х[11; /*в2*/ Еог (1 1| 1<=М) 1++) Х[11 = Е[1]' /*в1в/ Еог (1=1' 1<=м) 1++) Х[1] = Х[1]; /*в2*/ ЕЕ (М>=1) Х[1]-Х[01; Еог (р=1; р<=М-1; р++)( х1р1=е[р]| х[р+1]=х[р]; ) Ег (М>=1) Х[М]=Е[м]; Е (р=1| р<=г*М; р++)( ЕЕ (р вес( 2 == О) х[р1 = е[р]; х[р] = х[р]; ) 1002 Глава 11. Оптимизация параллелизма и локальности ПРЕОБРАЗОВАННЫЙ КОД ИОКОДный кОД РАЗБИЕНИЕ Реверс (гечегза]) а! .
р = ]'т' — ( (аз Р .)) Ш й1:. Перестановка (репин(ай оп) Ш1 Рис. 11.36. Примитивные аффинные преобразования (часть 2) к соответствующим исходным кодам. (Как слияние может распараллеливать код с синхронизацией, мы рассмотрим в следующем разделе.) В каждом из примеров генерируемый код содержит (внешний) распараллеливаемый цикл, итерации которого могут быть назначены различным процессорам, причем синхронизация при этом не требуется. Еог (1=0; 1<=И~ 1++) у[Н-1] = Е[1]; /*31*/ гог (3=0! З<=Н~ З++) Х[З] У[1]~ /*в2*/ Еог (1=1; 1<=И; 1++) Еог (З=О; З<=М! З++) Е[1,2] Е[1-1,З]; гог (1=1' 1<=Н+М 1' 1++) Еог (З свах(1,1+И); З<=ксап(Е,М)! 2++) Е[Е,З] Е[1-1,1-1]! ~:Н"И Сдвиг (з]сеъчпй) [:]=[' 'И Еог (р=О; р<=Н! р++)( т[р] = е[н-р]; х[р] = т[р]; Еог (р=О; р<=М; р++) Еог (с[=1! сз<=ир 1++) Е[о,р] = Е[с)-1,р]; Еог (р=1; р<=Н! р++) Еог (с(=1; с(<=М; с(++) Е[р Ч-р] Е[р-1,о-р-1]; 1ООЗ 1! .7.
Поиск параллельности, не требующей синхронизации Унимодулярные преобразования Унимодулярное преобразование представлено только унимодулярной матрицей коэффициентов, без константного вектора. Унимодулярная маглрица— это квадратная матрица, детерминант которой равен ~1.
Важность унимодулярных матриц заключается в том, что они взаимно однозначно отображают п-мерное пространство итераций на другой п-мерный многогранник. В приведенных примерах иллюстрируется наличие простой геометрической интерпретации распараллеливания. Ребра зависимостей всегда идут от более раннего экземпляра к более позднему. Так, зависимости между различными инструкциями, не вложенными ни в один общий цикл, следуют лексическому порядку; зависимости между инструкциями, вложенными в один и тот же цикл, следуют лексикографическому порядку. Геометрически зависимости двумерной вложенности циклов всегда направлены в диапазоне [0,180 ), что означает, что угол зависимости должен быть меньше 180', но не меньше 0'.
Аффинные преобразования изменяют порядок итераций таким образом, что все зависимости являются зависимостями между операциями, находящимися в одной н той же итерации охватывающего цикла. Распараллелить простой исходный текст можно путем изображения зависимостей и геометрического поиска соответствующего преобразования. 11.7.9 Упражнения к разделу 11.7 Упражнение 11.7.1. Дан цикл аког (1 = 2; 1 < 100; з++) А[1) = А!1-2)! а) Чему равно наибольшее количество процессоров, которые могут быть эффективно использованы для выполнения этого цикла? б) Перепишите код с использованием процессора р в качестве параметра.
в) Запишите ограничения разбиения пространства для данного цикла и найдите одно их решение. г) Что собой представляет аффинное разбиение данного цикла с наивысшим рангом? Упражнение 11.7.2. Повторите упражнение 11.7.1 для вложенностей циклов, представленных на рнс. !!.37. 1004 Глава 11. Оптимизация параллелизма и локальности аког (1 = Ор 1 <= 97з 1++) А[1] = А('+2]; а) аког (1 = 1; 1 <= 100; 1++) аког (7 = 11 5 <= 1001 З++) аког ()с = 1' )с <= 100; )с++) ( А(1, 7, 1с] = А[1, 7, 1с] + В(1-1, 7, 1с]; В[1,7,)с] = В(1,7,)с] + С(1,7-1,)с]; С ( 3., 7, )с] = С [1, 7, )с] + А( э., 7, )с-1]; !6) аког (1 = 11 1 <= 100; 1++) аког (> = 1; Э <= 100; 7++) аког ()с = 1; )с <= 100; )с++) ( А[1,7,)с] = А[1,7,)с] + В(1-1,7,)с]; В[1г7~)с] — В[1 Эг)с] + А[1г3 1г)с] С[1,7,)с] = С[1,7,)с] + А[1,7,)с-1] + В[1,7,)с]; !в) Рис.
11.37. Исходные тексты к упражнению 11.7.2 Упражнение 11.7.3. Перепишите код аког (1 = 0; 1 < 100з 1++) А[1] = 2*А[1]; аког (7 = Ор 7 < 100; 7++) А[7] = А(7] + 11 так, чтобы он состоял из одного цикла. Перепишите этот код с использованием номера процессора р так, чтобы этот код мог быть разделен между 100 процессорами, причем итерация р выполнялась бы процессором р.
Упражнение 11.7.4. В коде аког (1 = 11 1 < 100; 1++) ~ог (7 = 1: 7 < 100; 1++) А[з. З ] (А[1-1,3]+А[1+1,Э]+А(1,З-1]+А(1,7+1])/4з /* (в) */ 1005 ! !.8. Синхронизация между параллельными циклами единственные ограничения заключаются в том, что инструкция я, образующая тело вложенности циклов, должна выполнять итерации я (1 — 1, ) ) н я (г, ) — 1) до итерации а (1, )). Убедитесь в том, что это единственные необходимые ограничения. Затем перепишите код так, чтобы внешний цикл имел индексную переменную р и на р-й итерации внешнего цикла выполнялись все экземпляры а (г, )), такие, что 1+,) = Р.
Упражнение 11.7.5. Повторите упражнение 11.7.4, но так, чтобы на р-й итерации внешнего цикла выполнялись те экземпляры а, для которых 1 — ) = р. ! Упражнение 11.7.6. Объедините циклы Хог (1 = Ор 1 < 100р х++) А[1] = В[1]; аког (з = 98; з >= 0; з = з-2) В[х] = 1; в один цикл с сохранением всех имеющихся зависимостей. Упражнение 11.7.7. Покажите, что матрица [' '1 унимодулярна. Опишите преобразование над двумерной вложенностью циклов, выполняемое ею. Упражнение 11.7.8. Повторите упражнение 11.7.7 для матрицы ["] 11.8 Синхронизация между параллельными циклами Если не разрешать процессорам синхронизироваться, то большинство программ не смогут быть распараллелены.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
