А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 193
Текст из файла (страница 193)
Оптимизация параллелизма н локальности кость хр мы устраняем переменную з, теряем высоту отдельных точек и получаем двумерный отпечаток объекта на плоскости х!д Генерация границ циклов — всего лишь одно из множества применений проекций. Формально проекция может быть определена следующим образом. Пусть Я— и-мерный многогранник. Проекция Я на первые т его измерений представляет собой множество точек (хз, хз,..., х„,), таких, что для некоторых х „з, х .„з, ..,, х„вектоР 1х!, хз,..., х„~ пРинадлежит Я. Вычислить пРоекцию можно пРи помощи алгоритма исключения Фурье — Монкина.
Алгоритм 11.11. Исключение Фурье-Моцкина Вход: многогранник Я с переменными хз, хз,..., х„, т.е. Я представляет собой множество линейных ограничений, включающих переменные хь Одна из переменных, х, является исключаемой. ВыхОд: многогранник Ус переменными х!,...,х !,х +!,...,х„(т.е, со всеми переменными Я за исю!ючением х ), представляющий собой проекцию Я на измерения, отличные от пи МЕтод: пусть С вЂ” все ограничения в Я, включающие х .
Выполняем следующее. 1. Для каждой пары нижних и верхних границ х„, в С, таких как 2 (~ с!хт сзх,„( П создаем новое ограничение сзЛ ( с!У Заметим, что с! и сз представляют собой целые числа, в то время как Ь и У могут быть выражениями с переменными, отличными от х 2. Если целые с! и сз имеют общий делитель, делим на него обе стороны неравенства. 3.
Если новые неравенства являются несовместимыми, то решения для Я не существует, т.е, многогранники Я и У являются пустыми множествами. 4. Я' представляет собой множество ограничений Я вЂ” С плюс все ограничения, сгенерированные на шаге 2. Заметим кстати, что, если х имеет и нижних границ и с верхних, исключение х приведет к ис неравенствам, но не более.
о Ограничения, добавляемые на первом шаге алгоритма 11.11, соответствуют импликации ограничений С на остальные переменные системы. Следовательно, в У существует решение тогда и только тогда, когда существует как минимум одно 943 !1 3. Пространства итераций соответствующее решение в Я. Диапазон х для данного решения У может быть получен путем замены всех переменных, кроме х„„их фактическими значениями в ограничениях С. Пример 11.12. Рассмотрим неравенства, определяющие пространство итераций на рис. 11.11.
Предположим, что мы хотим применить исключение Фурье-Моцкина для получения проекции двумерного пространства на измерение з, избавляясь от измерения 1. Для г сушествует одна нижняя граница, 0 < г, и две верхние, 1 < з и 1 < 5. Это приводит нас к генерации двух ограничений; 0 < 3 и 0 < 5. Последнее неравенство тривиально и его можно игнорировать. Первое же дает нижнюю границу !', а исходная верхняя граница ! < 7 дает новую верхнюю границу.
о Генерация границ циклов Теперь, когда мы определили исключение Фурье — Моцкина, получение алгоритма для генерации границ цикла для сканирования выпуклого многоугольника (алгоритм 11.13) оказывается совсем простым делом. Мы вычисляем зраницы цикла в порядке от внутреннего к внешним циклам.
Все неравенства, включающие индексные переменные внутренних циклов, записываются как нижние или верхние границы этих переменных. Затем мы исключаем измерение, представляющее наиболее глубоко вложенный цикл, и получаем многогранник с размерностью, на единицу меньшей исходной. Мы повторяем эти действия для всех индексных переменных. Алгоритм 11.13. Вычисление границ для заданного порядка переменных Вход: выпуклый многогранник э" с переменными но..., н„. Выход: множества нижних границ Ь, и верхних границ 17, для каждой переменной е„выраженные только с использованием переменных и, где з < 1. МЕтод: алгоритм, приведенный на рис. 1!.15. и Пример 11.14.
Применим алгоритм 11.!3 для генерации границ циклов, сканирующих пространство итераций на рис. 11.11 по вертикали. Упорядочение переменных — 3, 1. Алгоритм генерирует следуюшие границы; Л;: 0 Ц: 5,1 Лэ: О 5гэ: 7 Мы должны обеспечить выполнение всех ограничений, так что граница 1 представляет собой ппп (5, з). Избыточностей в этом примере нет. П Глава 11. Оптимизация параллелизма н локальности 5'„= Я;!* Используем алгоритм 11.11 для поиска границ *! 1'ог ( 1 = и; г' > 1; 1 — — ) ! Ь,, = все нижние границы с, в Я,, 17,, = все верхние границы и; в Я.,; Я,, ! =- ограничения, которые возвращаются при применении алгоритма 11.11 для исключения с, из ограничений о,; !* Устранение избыточностей *! Ь'~ = я; ФОГ(м, = 1;7 <и;$++) ! Удаляем из Е„ь и 17,ь все границы, вытекающие из о'; Добавляем остальные ограничения на н; из Ь„, и 17,, в У; Рис.
!! . ! 5. Кол для выражения границ переменных лля заданного порядка переменных 11.3.6 Изменение осей Заметим, что сканирования пространства итераций по горизонтали и вертикали, как уже говорилось, являются всего лишь двумя из гораздо большего количества способов обхода пространства. Имеется множество других возможных способов; например, можно обойти пространство итераций из примера 11.6 по диагонали, как рассматривается в примере 11.15. Пример 11.15.
Пространство итераций, показанное на рис. 1!.11, может быть сканировано по диагонали, как показано на рис. 11.! б. Разность между координатами у' и ! на каждой диагонали постоянна и составляет в данном примере от О до 7. Таким образом, мы определяем новую переменную й = ! — 1 и сканируем пространство итераций в лексикографпческом порядке по отношению к й и 1. Подставляя ! = 1 — й в неравенства, мы получим О<) — й<б 1-lг< 1 <7 Чтобы создать границы циклов для описанного выше порядка, можно применить алгоритм 11.13 к полученному множеству неравенств с упорядочением переменных Й, 1 Л,; й 5+1,7 7,„: О 17ь: 7 945 )!.3. Пространства итераций [3, 3), [4, 4], [5, 5! [3, 4), [4, 5], [5, 6] [3, 5], [4, 6], (5, 7) [3, 6), (4, 7] [3, 7) [О, О), (1, !), [2, 2), [О, 1), [1, 2), [2., 3), [О, 2), [1, 3), [2, 4), [О, 3], [1, 4), [2, 5), [О, 4), [1, 5), [2, 6), (О, 5), [1, 6), (2, 7) (О, 6], [1, 7) [О, 7) Рис.
! !. 16. Подиагональное упорядочение простран- ства итераций, показанного на рис. ! !. ! ! На основании этих неравенств мы генерируем следующий код, заменяя ! на 3 — и в обращении к массиву: аког()с = 0; )с <= 7; )с++) аког(3 = 1с; 3 <= заз.п(5+)с,7)з 3++) Е(3,3-)с) = 0; 11.3.7 Упражнения к разделу 11.3 Упражнение 11.3.1. Преобразуйте каждый из следующих циклов в такой вид, в котором на каждой итерации индексная переменная увеличивается на 1.
а) аког(г = 10' г < 50! г = г + 7) Х(г,г+1) = 0; б) аког(г = -3; 1 <= 10; г = г + 2) Х(х) = Х(а+1)! в) аког(з. = 50; 1 >= 10; з.--) Х(з.) = 0; В общем случае можно изменить оси многогранника путем создания новых индексных переменных циклов, которые представляют аффинные комбинации исходных переменных, и определения упорядочения этих переменных. Сложная проблема возникает при выборе корректных осей, удовлетворяющих зависимостям данных при достижении поставленной цели — параллельности и локальности.
Эта проблема будет рассматриваться начиная с раздела 11.7. Пока же мы выяснили, что если оси выбраны, то, как показал пример 1!.!5, сгенерировать требуемый код достаточно просто. Имеется масса порядков обхода итераций, с которыми описанный метод справиться не в состоянии. Например, мы можем пожелать сначала обойти все нечетные строки пространства итераций, а затем перейти к четным.
Или начать со средины пространства и идти к его краям. Однако для приложений с аффинными функциями обращения к данным описанные здесь методы охватывают большинство желательных упорядочений итераций. 946 Глава 11. Оптимизация параллелизма и локальности Упражнение 11.3.2. Изобразите или опишите пространства итераций для каждой из следующих вложенностей циклов: а) вложенность циклов на рис. 11.17, а; б) вложенность циклов на рис. 11.17, 6; в) вложенность циклов на рис. 11.17, ы. аког (г = 21 г < 30; г++) аког (3 = а+21 3 < 40-х; 3++) Х[з.,3) = 0; а) Вложенность циклов к упражнению 11.3.2, и Гог (г = 10з х <= 1000! г++) Гог (3 = зз 3 < а+10; 3++) Х[з.,3) = О; б) Вложенность циклов к упражнению 11.3.2, 6 Гог (з = 01 г < 100! х++) Гог (3 = 0; З < 100+з.з 3++) Гог (К = а+31 К < 100-х-Зз К++) Х [ з., 3, 1с ] = 0 з в) Вложенность циклов к упражнению 11.3.2, ы Рис.
11.17. Вложенности циклов к упражнению 11.3.2 Упражнение 11.3.3. Запишите ограничения для каждой из вложенностей циклов на рис. !!.17 в виде (11.1), т.е. укажите значения векторов! и Ь и матрицы В. Упражнение 11.3.4. Обратите каждый из порядков вложенности циклов на рис. 11.17. Упражнение 11.3.5. Воспользуйтесь алгоритмом исключения Фурье-Моцкина для исключения з, 'из каждого из множеств ограничений, полученных в упражнении 11.3.3. Упражнение 11.3.6. Воспользуйтесь алгоритмом исключения Фурье — Моцкина для исключения 7' из каждого из множеств ограничений, полученных в упражнении 11.3.3. 947 11.3.
Пространства итераций Упражнение 11.3.7. Для каждой из вложенностей циклов на рис. 11.!7 перепишите код так, чтобы ось ( была заменена главной диагональю, т.е. осью, направление которой определяется равенством 1 = ). Новая ось должна соответствовать внешнему циклу. Упражнение 11.3.8. Повторите упражнение ! !.3.7 для следующих замен осей: а) замените 1 на ( + ), т.е. направление оси задается линиями, для которых сумма 1+ ) представляет собой константу; б) замените ) на 1 — 2); новая ось соответствует внешнему циклу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
