А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 204
Текст из файла (страница 204)
Пока же вспомним, что получающийся таким образом код очень далек от оптимального. 11.7.б Устранение пустых итераций Рассмотрим первое из двух преобразований, необходимых для генерации эффективного ЯРМО-кода. Код, выполняемый каждым процессором, проходит по всем итерациям исходной программы и отбирает только те из них, которые должны быть выполнены этим процессором.
Если код имеет к степеней параллельности, то в результате каждый процессор выполняет работу, которая на к порядков величины больше необходимой. Цель первого преобразования состоит в сокращении границ циклов для устранения всех пустых итераций. Начнем с рассмотрения инструкций в программе по одной. Выполняемое каждой частью пространство итераций инструкции представляет собой исходное пространство итераций плюс ограничения, навязываемые аффинным разбиением. Плотные границы для каждой инструкции можно сгенерировать путем применения к новому пространству итераций алгоритма 11.13.
Новый индексный вектор подобен исходному последовательному индексному вектору с добавлением идентификаторов процессоров в качестве внешних индексов. Вспомним, что алгоритм генерирует плотные границы для каждого индекса, выраженные через индексы охватывающих циклов. 994 Глава !1. Оптимизация параллелизма н локальности После нахождения пространств итераций различных инструкций мы объединяем их цикл за циклом, получая границы как объединения границ для каждой инструкции. Некоторые циклы могут свестись к одной итерации, как проиллюстрировано в приведенном далее примере 11.46, и мы можем просто устранить такой цикл и установить индексную переменную равной значению для этой единственной итерации. Пример 11.46. Для приведенного на рис.
11.30, а цикла алгоритм 11.43 создает два аффинных разбиения: аг.р=г' аз.р з Алгоритм 11.45 генерирует код, показанный на рис. 11.30, б. Применение алгоритма 11.13 к инструкции з~ дает границы р < 1 < р, или просто 1 = р. Аналогично для инструкции аз алгоритм находит ! = р. Таким образом, мы получаем код, приведенный на рис.
11.30, в. Распространение копий переменных 1 и з приводит к устранению ненужных проверок и коду, показанному на рис. 11.30, г. о Вернемся теперь к примеру 11.44 и проиллюстрируем объединение нескольких пространств итераций разных инструкций. Пример 11.47. Уплотним границы циклов в коде из примера 11.44. Пространство итераций, выполняемое частью р для инструкции аы определяется следующими уравнениями и неравенствами: — 100 < р < 99 1 < з < 100 1< 1 < Г00 1 — р — 1=1 Применение алгоритма 11.13 приводит к ограничениям, показанным на рис.
11.31, а. Алгоритм 1! .13 генерирует ограничение р + 2 < ! < 100 + р + 1 из г — р — 1 = з и 1 < з < 100 и уплотняет верхнюю границу рдо 98. Аналогичные границы для каждой переменной инструкции аз показаны на рис. 11.31, б. Пространства итераций для а~ и аз на рис. 11.31 похожи, но, как и следовало ожидать, исходя из рис. 11.27, некоторые из границ отличаются на единицу. Код на рис. 11.32 выполняется в пределах объединения пространств итераций. Например, для 1 в качестве нижней границы используется щах (1, р + 1), а в качестве верхней — ппп(100, 101+ р). Обратите внимание, что внутренний цикл состоит из двух итераций, за исключением первого и последнего выполнений, когда выполняется только одна итерация. Таким образом, накладные расходы на генерацию индексов циклов снижаются на один порядок величины.
Поскольку пространство 11 П. Поиск параллельности, ие требующей синхронизации Гог (з.=1; 1<=)Ч; 1++) 7[1) = 2[1)з /* (я1) */ Ког (3=1; 3<=)Ч; 3++) Х[31 = У[З1з /* (в2) */ а) Исходный код йог (р=1; р<=Нз р++) ( аког (1=1; 1<=М; 1++) Н (р == 1) Х[з.) = 2[1); /* (я1) */ аког (3=1; З<=М; 3++) 1Г (р == 3) Х[3) = У[3)з /* (в2) */ б) Результат применения алгоритма 11.45 аког (р=1; р<=Ы; р++) ( 1Г (р == 1) г[1) = 2[1); /* (в1) */ 3 = Р: з.б (р == 3) Х[3) = Х[3)з /* (я2) */ в) Результат применения алгоритма 11.13 аког (р=1; р<=(яз р++) Х[р) = 2[р)з /* (я1) */ Х[р) = х[р)з /* (яг) */ г) Окончательный код Рис. 11.30.
Код к примеру 11.46 итераций выполняется большее количество раз, чем каждая из инструкций аз и аз, проверки для выбора выполняемых инструкций остаются необходимыми. о 996 Глава 11. Оптимизация параллелизма и локальности ( — р — 1 < 3 < ( — р — 1 1<3 < Гоо (: р+2<(<100+р+1 1 < ( < 100 р: -100 <р<98 а) Границы для инструкции лз ( — р<з<( — р 1<3 < Гоо (; р+1<(<100+р 1 < з < 100 р: — 99 < р < 99 б) Границы для инструкции лз Рис. 11.31. Плотные границы р, 1 н1 лля рис. ! 1.29 Гог (р -100; р <= 99; р++) гог (1 = шах(1,р+1)з 1 <= щгп(100,101+р); 1++) гог (3 = щах(1, 1-р-1)з 3 <= тгп(100,1-р)з 3++) ( гг (р == 1-3-1) Х[1,3) = Х[з.,З) + х[1-1,3)1 /* (в1) */ гх (р == 1-3) у[1,3) = Х[з.,3-1) ж у[з.,3); /* (а2) */ Рис.
11.32. Код с рис. 11.29, улучшенный при помощи более плотных границ 11.7.7 Устранение проверок из внутреннего цикла Второе преобразование состоит в устранении проверок из внутреннего цикла. Как видно нз приведенного выше примера, проверки необходимы, если пространства итераций инструкций в цикле пересекаются, но не полностью. Чтобы избежать необходимости проверок, разобьем пространство итераций на подпространства, каждое из которых выполняет одинаковое множество инструкций.
Та- 997 11.7. Поиск параллельности, не требующей синхронизации кая оптимизация требует дублирования кода и должна использоваться только для устранения проверок во внутренних циклах. Для разделения пространства итераций с целью устранения проверок во внутренних циклах мы многократно выполняем следующие действия до тех пор, пока все проверки из внутренних циклов не будут устранены.
1. Выбираем цикл, который содержит инструкции с разными границами. 2. Разделяем цикл, используя условие, при котором некоторая инструкция исключается как минимум из одного из его компонентов. Условие выбирается среди границ различных перекрывающихся многогранников. Лучше, если все итерации некоторой инструкции находятся только в одной из полуплоскостей условия. 3. Генерируем код для каждого из пространств итераций отдельно. Пример 11.48. Удалим проверки из кода на рис.
11.32. Инструкции а~ и вз отображаются на одно и то же множество идентификаторов процессоров, за исключением граничных частей. Таким образом, пространство разбиений разделяется на три подпространства: 1. р=-100; 2. — 99<р<98; 3. р=99. Код каждого подпространства может быть уточнен с учетом значения (или значений) р. На рис. 11.33 приведен код для каждого из трех пространств итераций. Обратите внимание на то, что первому и третьему пространствам не требуются циклы по 1 и з, поскольку при конкретных значениях р, определяющих эти пространства, циклы становятся вырожденными, содержащими только одну итерацию.
Например, в пространстве 1 подстановка р = — 100 в границы циклов ограничивает 1 значением 1, а у — значением 100. Присваивания значений переменной р в первом и третьем пространствах представляют собой "мертвый код", который может быть удален. Далее мы разделяем цикл с индексом 1 в пространстве 2. Вновь первая и последняя итерации оказываются отличными от остальных. Таким образом, мы разбиваем цикл на три подпространства: а) шах (1, р+ 1) < 1 < р+ 2, где выполняется только инструкция вз, б) шах(1,р+ 2) < 1 < ппп(100,100+ р), где выполняются инструкции в~ н зз 998 Глава 11. Оптимизация параллелизма и локальности /* Пространство 1 */ р = -100; 1з 100 з Х[1,3] = Х[1,3] + у[1-1,3]; /ь (а1) */ /* Пространство 2 */ аког (р = -99з р <= 98; р++) аког (1 = шах(1,р+1)з 1 <= азгп(100,101+р)з 1++) аког (3 = азах(1,з.-р-1)з 3 <= тзп(100,1-р); 3++) ( 1Г (р =- 1-3-1) Х[1,3] = Х[1,3] + з[1-1,3]; /* (в1) */ (Р == 1 3) 7[1,3] = Х[з.,3-1] + 1[1,3]; /* (а2) */ /* Пространство 3 */ р = 99з 100; 3=1з 7[1,3] = Х[1,З-1] + 1[1,3]з /* (в2) */ Рис.
11.33. Разбиение пространства итераций по значениям р в) 101 + р < з < ппп (101 + р,100), где выполняется только инструкция зз. Вложенность циклов в пространстве 2 на рис. 11.33 можно, таким образом, переписать так, как показано на рис. 11.34, а. На рис. 11.34, б показана оптимизированная программа. Мы подставили код на рис. 11.34, а во вложенность циклов на рис.
! 1.33. Кроме того, мы внесли присваивания р, г' и з в обращения к массивам. При оптимизации на уровне промежуточного кода некоторые из этих присваиваний будут идентифицированы как общие подвыражения и удалены из кода обращения к массивам. а 11.7.8 Преобразования исходного кода Мы видели, как на основе простых аффинных разбиений для каждой инструкции можно получить программы, существенно отличающиеся от исходных. Но из рассмотренных примеров не видно, как аффинные разбиения коррелируют с изменениями на уровне исходного текста.
В этом разделе показано, как можно относительно легко объяснить изменения исходного кода, если разделить аффинные разбиения на серии примитивных преобразований. 11.7. Поиск параллельности, не требующей синхронизации /* Пространство (2) */ бог (р = -99; р <= 98; р++) ( /* Пространство (2а) */ 1й (р >= 0) ( 1 = р+1; 3=1; У[1,3] = Х[1,1-1] + У[1,3]; /* (в2) */ /* Пространство (2Ь) */ бог (1 = мах(1,р+2); 1 <= нйп(100,100+р)з 1++) ( 1-р-1; Х[1,3] = Х[1,3] + г[1-1,1]з /* (в1) */ 1-р.
Х[1,3] = Х[1,З-1] + У[1,3]з /* (в2) */ /* Пространство (2с) */ 18 (р <= -1) = 101+р; 3 = 1ОО; Х[1,3] = Х[1,3] + Х[1-1,3]! /* (в1) */ а) Разбиение пространства 2 цо значениям з /* Пространство (1); р = -100 */ Х[1,100] = Х[1,100] + У[0,100]з /* (в1) */ /* пространство (2) */ бог (р = -99; р <= 98; р++) йй (р >= О) Х[р+1, 1] = Х[р+1, О] + 1'[р+1, 1] ' /* бог (1 = мах(1,р+2)! 1 <= тйп(100,100+Р)з 1++) ( Х[1,1-р-1] = Х[1,1-р-1] + У[1-1,з-р-1]; /* У[1,з -р] = Х[1, 1-р-1] + У[1, 1-р]; /* (в2) */ (в1) */ (в2) */ /* Пространство (3); р = 99 */ У[100,1] = Х[100,0] + У[100,1]; /* (в2) */ б) Оптимизированный код, эквивалентный коду на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
