А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 214
Текст из файла (страница 214)
В случае, когда внешний цикл на рис. 11.63 имеет небольшие известные границы, нам не надо выполнять описанные преобразования — можно просто переставить два цикла исходной программы. 1046 Глава 11. Оптимизация параллелизма и локальности Чередование инструкций в параллельном цикле Рассмотрим ситуацию, когда параллелизуемый цикл содержит последовательность инструкций аы аз,..., я . Если некоторые из этих инструкций сами по себе являются циклами, то инструкции из соседних итераций могут быть разделены большим количеством операций. Повторным использованием между итерациями вновь можно воспользоваться при помощи чередования их выполнений, как показано на рис.
11.64. Такое преобразование распределяет обработанный цикл по инструкциям. Как и ранее, если внешний цикл имеет небольшое фиксированное количество итераций, можно просто распределить исходный цикл по всем инструкциям, не прибегая к располосованию. аког (11=0; 11<о; 11+=4) ( Еог (1=11; 1<пйп(п,11+4); 1++) <Я1> аког (1=11; 1<пап(п,11+4); 1++) <Я2> аког (1=0; 1<п; 1++) ( <Я1> <Я2> б) Преобразованный код а) Исходная программа Рис. 11.64. Преобразование, черелующее инструкции Используем для обозначения выполнения инструкции гп в итерации ) запись а, О).
Вместо исходного последовательного порядка выполнения, показанного на рис. 11.65, а, код выполняется в порядке, показанном на рис. 11.65, 6. Пример 11.70. Вернемся к многосеточному примеру и покажем, как можно воспользоваться повторными использованиями между итерациями внешних параллельных циклов. Заметим, что обращения РИ' (1, Е, )', 11, РИ~ (1, к — 1, ), г] и РЯ [1, )с + 1,), г~ во внутренних циклах в коде на рис. 11.62 обладают малой пространственной локальностью. Анализ повторного использования, описанный в разделе !!.5, указывает, что цикл с индексом 1 является носителем пространственной локальности, а цикл с индексом )с — группового повторного использования. Цикл с индексом к и так является внутренним, так что нас интересует чередование операций с РИг в блоке частей с последовательными значениями 1.
Применим преобразование для получения чередующихся инструкций в цикле, что даст нам код, показанный на рис. 11.66, а затем применим то же преобразование к внутреннему циклу и получим код на рис. 11.67. Заметим, что в силу чередования В итераций из цикла с индексом 1 нам требуется преобразование переменных АР, АМ и Т в массивы, способные одновременно хранить В результатов. и 1047 11.1О. Оптимизации локальности в1 (О), в2 (О), ..., в (О), в1 (1) ~ в2 (1) ~ ° ° ° ~ вт (1) ~ в1(2), в2 (2), ..., в„, (2), в1 (3), в2 (3) ~ ° ° ° ~ вт (3) ~ в1 (4), в2 (4), ..., в„,(4), в1 (5), в2 (5), ..., вт (5), в1 (6), з2 (6), ..., в (6), в1 (7), в2 (7), ..., в (7), а) Исходный порядок з1 (О), з1 (1), в1 (2), в1 (3), з2(0), в2 (1), в2 (2), в2 (3), в (О), в (1), в (2), з (3), в1 (4), в1 (5), з1 (6), в1 (7), в2 (4), в2 (5), в2 (6), в2 (7), в (4), в (5), в (6), з (7), б) Преобразованный порядок Рис.
11.65. Распределение обработанного цикла 11.10.4 Алгоритмы оптимизации локальности Алгоритм 11.71 оптимизирует локальность для одиопроцессориой системы, а алгоритм 11.72 оптимизирует как локальность, так и параллелизм для многопроцессорной системы. Алгоритм 11.71. Оптимизация локальности данных в однопроцессорной системе Вход: программа с аффиииыми обращениями к массиву. Выход: эквиаалеитиая программа, максимизирующая локальность данных.
Метод: выполнить следующие действия. 1. Применить алгоритм 11.64 для оптимизации аремеиибй локальности вычисленных результатов. 1048 Глава ! !. Оптимизация параллелизма и локальности Тот (З = 2, Тот (11 Тот <= 51, э++) 2, 11 <= 11, 11+=Ь) ( (1 = 11! 1 <= са1п(11+Ь-1,11); 1++) 1Ь 1-11+1; АР[1Ь] Т 1.0/(1.0 +АР[ТЬ])с 0[2,1Ь] = Т*АР[1Ь]; пи[1,2,5, 1] т*пи[1,2,5,1]; Ест (1 = 11; 1 <= сато(11+Ь-1,11)с 1++) ( Т~~ (1=3, )с <= )с1-1, )с++) 1Ь = 1-11+1; АМ АР[1Ь] 1 АР[1Ь] Т ...АР[1Ь)-АМ*!)[1Ь,)с-1]...; 0[1Ь,)с] = Т*АР; пи[1,к,5, 1] = т*(пи[1,к,й, 1]+пи[1,к-1,5, 1]).. ) (1 = 11; 1 <= атп(11+Ь-1,11); 1++) Тот ()с=)с1-1, )с>=2, )с--) ( пи[1,)с,1, 1] = пи[1,)с,5,1] +п[1н,)с]*пи[1,)с+1,5,1]с /* Конец кода, выполняемого процессором (1,1) */ Тот 2.
Применить алгоритм 1!.68 для сжатия массивов там, где это возможно. 3. Определить подпространство итераций, которые могут совместно использовать одни и те же данные или строки кэша, применив методы, описанные в разделе 11.5. Для каждой инструкции определить те измерения внешнего параллельного цикла, которые содержат повторные использования. 4. Для каждого внешнего параллельного цикла, являющегося носителем повторного использования, переместить блок итераций во внутренний блок путем многократного применения примитивов чередования. 5. Применить блокирование к подмножеству измерений во внутренней полностью переставляемой вложенности циклов, являющейся носителем повторного использования.
Рис. ! !.66. Фрагмент кода, представленный на рнс. ! !.23, после разбиения, сжатия мас- сивов н блокирования 1049 ! !.!О. Оптимизации локальности 1++ ) <= 11, 11+=Ь) <= азап(11+Ь-1,11); 1++) ( = 1-11+1! Тот (1 = 2, Йог ( з'.з. Гог 1.0/(1. О +АР[1Ы ); Т*АР[ТЬ]з з.] = Т*0И[1,2,1,1]; ) аког (1=3, )с <= )с1-1, )с++) Тот (1 = 11; 1 <= звал(11+Ь-1,11)з 1++) ( 1ь = 1-11+1; А!.з = АР[ТЬ]; АР[ТЬ] Т ...АР[ТЬ)-АМ*0[1Ь,)с-1]...з 0[1Ь,)с] = Т*АРз пи[1,)с, 7,1] = т*(0и[1,)с, 1, 1]+пи[ 1,)с-1, 5, 1] ) .. Тот (1=)с1-1, )с>=2, Еог (1 = 11; з. 0И[1,)с,1,11 /* Конец кода, Рис. ! !.67.
Фрагмент кода, представленного на рис. ! !.23, после разбиения, сжатия мас- сивов, блокирования и чередования внутреннего цикла 6. Блокировать внешнюю полностью переставляемую вложенность циклов для высших уровней иерархии памяти, таких как кэш третьего уровня и физическая память. 7.
При необходимости расширить скаляры и массивы до длины блоков. и Алгоритм 11.72. Оптимизация параллелизма и локальности данных в многопроцессорной системе Вход: программа с аффинными обращениями к массиву. ВЫХОД: эквивалентная программа, максимизирующая параллелизм и локальность данных. Мнт(зд: выполнить следующие действия. 1. Применить алгоритм 1].64 для распараллеливания исходной программы и создания БРМР-программьь Э <= 31~ = 2, Тз. (1=11; 1ь АР[зЬ] Т 0[2,1Ь] 0и[1,2,7 )с--) ( <= взап(11+Ь-1,11)з 1++) 0И[1 )с,),1] +0[Ты,)с]*0И[1,)с+1,7 1)' выполняемого процессором (1,1) */ 1050 Глава )!. Оптимизация параллелизма и локальности 2. Применить алгоритм 11.71 к полученной в шаге ! ЯРМО-программе для оптимизации ее локальности.
о 11.10.5 Упражнения к разделу 11.10 Упражнение 11.10.1. Выполните сжатие массивов в следующих векторных опе- рациях: Тог (1=0; 1<п; 1++) Т[1] = А[1] * В[1]; аког (1=0; 1<п; з.++) ()[1] = Т[1.] + С[1]; Упражнение 11.10.2. Выполните сжатие массивов в следующих векторных опе- рациях: аког (з.=О; з.<п; з.++) Т[1] = А[1] + В[з.]; Тог (1=0; з <и; 1++) Я[з.] = С[1] + (з[1]; аког (1 0; 1<п; з ++) В[1] = Т[1] * Я[1]; Упражнение 11.10.3. Выполните располосование внешнего цикла на полосы ши- риной 10: аког (1=п-1; 1>=Оз 1--) гог (3=0' 3<п' З++) 11.11 Прочие применения аффинных преобразований До сих пор мы сосредоточивались на машинах, имеющих архитектуру с общей памятью, но теория аффинных преобразований циклов имеет много других приложений.
Можно применить аффинные преобразования к другим видам параллелизма, включая машины с распределенной памятью, векторными командами, Я(МГ)-командами (Я(пд)е !пя(пзсйоп Мц!бр)е Гзага — одна команда, много данных) или машины с одновременным выполнением нескольких команд. 11.11.1 Машины с распределенной памятью В случае машин с распределенной памятью, в которых процессоры взаимодействуют путем пересылки сообщений друг другу, еще более важную роль играет назначение процессорам больших независимых вычислительных модулей, таких как генерируемые алгоритмом аффинного разбиения. Помимо разбиения вычислений, при компиляции требуется решение ряда других вопросов. 1051 11.11.
Прочие применения аффиниых преобразований 1. Распределение даннвт. Если процессоры работают с разными частями массива, то каждому из них требуется выделить память, достаточную для хранения только используемой части. Для определения частей массивов, используемых каждым процессором, можно применить проецирование.
Входными данными в этом случае являются линейные неравенства, представляющие границы циклов, функции обращения к массивам и аффинные разбиения, отображающие итерации на идентификаторы процессоров. Исключая индексы циклов, для каждого идентификатора процессора можно найти множество используемых им элементов массива.
2. Код взаимодействия. Требуется генерация явного кода для отправки и получения данных процессорами. В каждой точке синхронизации необходимо а) определить, какие данные, находящиеся у одного процессора, требуются другим процессорам; б) сгенерировать код, который находит все отсылаемые данные и пакует их в буфер; в) сгенерировать код, который определяет данные, необходимые процессору, распаковывает полученные сообщения и перемещает полученные данные в соответствующие места в памяти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
