А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 192
Текст из файла (страница 192)
Все итерации цикла представлены точками с целочисленными координатами„находящимися в описанном граничными неравенствами многограннике. И наоборот, все целочисленные точки внутри полиэдра представляют итерации вложенности циклов в некоторый момент времени. Пример 11.б. Рассмотрим двумерную вложенность циклов, показанную на рис. 1).!О. Эта двумерная вложенность может быть смоделирована двумерным многоугольником, показанным на рис.
11.11. Две оси представляют значения индексов циклов ! и ~. Индекс ! может принимать любое целочисленное значение между О н 5; индекс )' может принимать целочисленные значения, такие„что х~() =.7. и аког(1 = О; 1 <= 5; 1++) аког(7' = з; 7' <= 7; 7++) Е[7,з.] = О; Рис. 11.10. Двумерная вложенность циклов 11.3.2 Порядок выполнения вложенности циклов Последовательное выполнение вложенности циклов сканирует итерации в их пространстве в возрастающем лексикографическом порядке. Вектор! = [1о, гы..., 1„) лексикаграфически меньше вектора 1 = '[(о,!зы...,(„,~, что записывается как 1 -< !', тогда и только тогда, когда существует т ( пйп(п,п'), гакое, что 938 Глава !1.
Оптимизация параллелизма и локальное~и 11.3.3 Матричная запись неравенств Математически итерации цикла глубиной д могут быть представлены как )1е У ~ В1+ Ь > О~ (11.1) Здесь 1. Я, как принято в математике, представляет множество целых чисел — положительных, отрицательных и нуля; 2. В представляет собой целочисленную матрицу размером И х д; 3. Ь вЂ” целочисленный вектор длиной и'; 4. Π— вектор длиной Н, все элементы которого нулевые. Пример 11.8.
Неравенства из примера 11.6 можно записать так, как показано на рис. 1!.13. Здесь диапазон 1 описывается неравенствами ( > 0 и 1 < 5; диапазон з описывается неравенствами з > 1 и з < 7. Мы должны привести каждое неравенство к виду иг'+ ц1 + зс > О. Тогда (и, с) становится строкой матрицы В в неравенстве (11.1), а ю — соответствующим компонентом вектора Ь. Например, 1 > 0 соответствует указанному виду, если и = 1, ц = 0 и ш = О. Это неравенство представлено первой строкой матрицы В и верхним элементом вектора Ь на рис. 11.13.
1 0 — 1 0 — 1 1 0 — 1 0 5 0 7 М" Рис. 11.13. Неравенство, определяющее пространство итераций В качестве другого примера неравенство 1 < 5 можно эквивалентно записать как ( — 1) 1+ (О) з + 5 > О, что представлено второй строкой В и Ь на рис. 11.13. Точно так же неравенство з > ( превращается в ( — 1) 1+ (1) з + 0 > 0 и представлено третьей строкой; а неравенство з < 7 становится (0) 1 + (-1) з + 7 > 0 и представлено последней строкой матрицы и вектора. и 11.3.4 Добавление символьных констант Иногда приходится оптимизировать вложенность циклов, в которой участвуют некоторые переменные, являющиеся инвариантами для всех циклов во вложенности.
Мы называем такие переменные символьными консталталзи (яутЬойс 939 !!.3. Пространства итераций Работа с неравенствами Преобразовывать неравенства, как в примере 11.8, можно так же, как равенства, т.е. выполняя прибавление или вычитание с обеих сторон или умножая обе стороны на константу. Следует только помнить одно правило — при умножении обеих сторон неравенства на отрицательное число необходимо изменить направление неравенства. Так, ( < 5, умноженное на — 1, становится неравенством — 1 > — 5. Добавляя 5 к обеим сторонам неравенства, мы получаем -! + 5 > О, что соответствует второй строке на рис.
11.13. сопя!ап!з), но при описании границ пространства итераций должны рассматривать их как переменные и создавать записи для них в векторе индексов циклов, т.е. в векторе 1 в общем виде (11.1). Пример 11.9. Рассмотрим простой цикл аког(1 = О; 1 <= пг 1++) ( Этот цикл определяет одномерное пространство итераций с индексом 1, ограниченное неравенствами ( > О и ( < п. Поскольку и — символьная константа, мы должны включить ее в качестве переменной, что даст нам вектор индексов циклов ((, и]. В матричном виде указанное пространство итераций определяется как Заметим, что хотя вектор массива индексов двумерен, только первое его измерение, представляющее г, является частью выхода — множества точек, лежащих в пространстве итераций. о 11.3.5 Управление порядком выполнения Линейные неравенства, выделенные из нижней и верхней границ тела цикла, определяют множество итераций в выпуклом многограннике.
Как таковое представление не определяет порядка выполнения итераций в пределах пространства итераций. Исходная программа накладывает на выполнение итераций последовательный порядок, являющийся лексикографическим порядком по отношению к переменным индексов циклов, упорядоченным от внешних циклов к внутренним. Однако итерации в пространстве могут быть выполнены в произвольном 940 Глава !!. Оптимизация параллелизма и локальности порядке, лишь бы учитывались их зависимости данных (т.е. порядок, в котором выполняются записи и чтения любого элемента массива в пределах вложенности циклов, остается неизменным). Задача выбора такого упорядочения, которое отвечает зависимостям данных и оптимизирует локальность данных и параллелизм, сложна и будет рассмотрена позже, начиная с раздела 11.7. Здесь же мы считаем, что корректный порядок, отвечающий всем требованиям, задан, и покажем, как сгенерировать код, обеспечивающий реализацию этого порядка.
Начнем с рассмотрения альтернативы порядку из примера 11.6. Пример 11.10. Зависимостей между итерациями в примере 11.6 нет. Следовательно, мы можем выполнять итерации в произвольном порядке, как последовательно, так и параллельно. Поскольку итерация [г,Я обращается к элементу У ) ), г~, исходная программа обходит массив в порядке, показанном на рис.
11.14, а. Для повышения пространственной локальности предпочтительнее обход соседних слов, например, в порядке, показанном на рис. 11.14, б. Этот шаблон обращений получится, если выполнять итерации в порядке, показанном на рис. 11.14, в. Иначе говоря, пространство итераций на рис. 11.11 сканируется не по горизонтали, а по вертикали, так что 7 становится индексом внешнего цикла. Код, выполняющий итерации в указанном порядке, имеет вид аког(э' = О; З <= 7; з++) аког(з. =- О; 1 <= звзп(5,7)! з.++) 2[э,з.] = О; Как же сгенерировать границы циклов, которые сканируют пространство в лексикографическом порядке переменных для данного выпуклого многогранника и упорядочения индексных переменных? В приведенном выше примере ограничение ! < ! рассматривается как нижняя граница индекса з' во внутреннем цикле исходной программы, но как верхняя граница для индекса 1 (опять же, во внутреннем цикле) в преобразованной программе.
Границы внешнего цикла, выраженные в виде линейной комбинации обычных и символьных констант, определяют диапазон всех возможных значений, которые может принимать его индексная переменная. Границы переменных внутренних циклов выражаются как линейные комбинации переменных внешних циклов, символьных и обычных констант. Они определяют диапазон значений переменной для каждой комбинации значений переменных внешних циклов. Проекция Говоря геометрически, найти границы индекса внешнего цикла во шюженности циклов глубиной 2 можно путем проекции выпуклого многогранника, представляющего пространство итераций, на внешнее измерение пространства.
Про- 941 11.3. Пространства итераций г(о,о], г(1,о], г[2,о], г(з,о], г[4,о], г(б,о], г[1,ц, г[2,ц, г(з,ц, г[4,ц, г[б,ц, г(2,з], г[з,2], г[4,2], г(5,2], г[3,3], г!4,3], г(5,3], г(4,4], г[5,4], г[5 5] а) Исходный порядок обращений г(1,ц г [2, Ц, г (2, 2] г[з.ц., г(з,2], г [4, Ц, г (4, 2(, г(5.Ц, г[5,2], г (6, Ц , г [6, 2], г (7, Ц , г [7. 2], г (з. з] г (4. з], г (4, 4] г (5, з] . г (5, 4], г (5, 5( г (6, з] . г !6, 4], г (6. 5] г (7, 3(, г (7, 4],. г (7, 5] Предпочтительный порядок обращений (о, о] 1о.Ц. [1,Ц (О, 2] .
[1, 2], (о, з], [1, з], [О, 4], (1. 4], [О, 5], (1. 5], !О, 6], [1, 6], ,"О, 7], (1, 7], (2, 2] (2. 3] . [3, 3] [2: 4] (3 4] (4: 4] (2 5] (3 5] (,! 5] (5 5] (2, 6], [3, 6], (4, 6], (5, 611 [2, 7], (3, 7], (4, 7], [5, 7] в) Предпочтительный порядок итераций Рис. 11.14. Персупорялочение обращений к злемситам массива и итераций во вложенно- сти циклов екция многогранника на пространство меньшей размерности интуитивно представляет собой тень, отбрасываемую объектом на это пространство. Проекция двумерного пространства итераций на рис.
! !.11 на ось ! представляет собой вертикальный отрезок от 0 до 5, а проекция на ось ! — горизонтальный отрезок от 0 до 7. При проекции трехмерного объекта вдоль оси л на двумерную плос- г !о, о] г (1, о], г (2, о], г [з,о], г (4., о], г (5.,0], г(б,о], г(7.,о]. б) г(б,о], г(7,о] г (6, ц, г (7, ц г [6. 2], г [7, 2] г [6., з], г (7, 3] г [6 4], г (7 4] г (6, 5], г (7, 5] 942 Глава 1! .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
