А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 210
Текст из файла (страница 210)
Здесь з + 2 = /+ 1, или з = у' — 1. Подставляя 1 = ~' — 1 во временные ограничения, получаем С1 (г' — 1)+Сз > 0 При 1 = г' получаем С,>0 При 1 < 1', поскольку Сз > О, получаем с >о 3. Зависимость по выходу обращения для записи Х [1+ 1] от себя самого. Здесь з = з', Временные ограничения сводятся к С1 (г~ — г) > 0 Поскольку существенны только значения 1 < г', мы вновь получаем с >о Остальные зависимости не приводят к новым ограничениям.
Всего существует три ограничения: с >о Сз>0 с — с >о Двумя независимыми решениями этих ограничений являются 10гб Глава 11. Оптимизация параллелизма и локальности Первое решение сохраняет порядок выполнения итераций во внешнем цикле. Как исходный ЮК-код на рис. 11.50, а, так и преобразованный код на рис. 11.51, а являются примерами таких схем. Второе решение размещает итерации вдоль 135- градусных диагоналей в том же внешнем цикле. В качестве соответствующего примера можно привести код, показанный на рис.
11.51, б. Обратите внимание на существование многих других возможных пар независимых решений. Например, также представляют собой независимые решения тех же ограничений. Для упрощения преобразования кода мы выбираем среди решений наипростейшие векторы. и 11.9.7 Решение временных ограничений с использованием леммы Фаркаша Поскольку ограничения временного разбиения подобны ограничениям пространственного разбиения, нельзя ли использовать для их решения аналогичный алгоритм? К сожалению, небольшие отличия между этими двумя задачами превращаются в большие технические различия в методах их решения.
Алгоритм 11,43 просто находит С1, с1, Сг и сг, такие, что для всех 11 из У ' и 12 из Я ', если Ы1 И2 т'111 + 11 = р212 + 12, то С111+ с1 = С212+ сг Линейные неравенства, связанные с границами циклов, используются только для определении наличия зависимости между двумя обращениями, и не более того.
При поиске решений ограничений временных разбиений игнорировать линейные неравенства ! -с 1' нельзя; такое игнорирование приводит к тому, что допустимым является только гривиш1ьное решение, помещающее все итерации в один раздел. Таким образом, алгоритм поиска решений ограничений временных разбиений должен работать как с уравнениями, так и с неравенствами. Обобщенная задача, которую мы хотим решить, формулируется следующим образом. Для данной матрицы А найти вектор с, такой, что для всех векторов х, таких, что Ах > О, выполняется сг х > О. Другими словами, мы ищем такое с, что скалярное произведение с и любых координат в многограннике, определяемом неравенствами Ах > О, всегда имеет неотрицательное значение.
Помочь в решении задачи может лемма Фаркаша (Рагказ' 1егпта). Пусть А— матрица действительных чисел размером т х п, а с — ненулевой вектор размером 1027 11.9. Конвейеризация О лемме Фаркаша Доказательство леммы можно найти во многих книгах по линейному программированию. Эта лемма, доказанная в 1901 году, является одной из теорем алыпернатив.
Все эти теоремы эквивалентны, но, несмотря на многолетние попытки, до сих пор так и не найдено простое, интуитивно понятное доказательство ни данной леммы, ни одного из ее эквивалентов. и. Лемма Фаркаша гласит, что решение в действительных числах имеет либо основная система неравенств Ах> О,с х (О, либо дуальиая Агу у>О но не обе одновременно. Дуальная система может быть решена с применением исключения Фурье— Моцкина переменных у. Для каждого с, для которого имеется решение дуальной системы, лемма Фаркаша гарантирует отсутствие решения основной системы, т.е.
можно доказать, что сгх > 0 для всех х, таких, что Ах > О, путем поиска решения у дуальной системы А~у = с и у > О. Алгоритм 11.59. Поиск множества допустимых максимально независимых отображений временных разбиений для внешнего последовательного цикла Вход: вложенность циклов с обращениями к массиву. Выход: максимальное множество линейно независимых отображений временных разбиений. МЕТОД: алгоритм состоит из следующих шагов. 1. Найдем все зависимые пары обращений в программе. 2. Пусть для каждой пары зависимых обращений У~ = (Гы Гы Вы Ь,) в инструкции яы вложенной в д~ циклов, и У2 = (Вз,$з, Вз, Ьз) в инструкции вз, вложенной в дз циклов (Сыс~) и (Сз,сз), представляют собой (неизвестные) отображения временных разбиений зг и аз соответственно.
Вспомним, что ограничения временных разбиений гласят, что я для всех 1~ из У~' и 1з из Я~', таких, что а) [~ -с„„1з, б) В~1~+Ь| >О, 1028 Глава 1!. Оптимизация параллелизма и локальности в) В212+ Ь2 > 0 и г) Е111 +11 = рг12+ 12, выполняется С111 + с1 ~ (С212 + с2. Поскольку 11 .с„,м 12 — дизъюнктивное объединение ряда условий, можно создать систему ограничений для каждого условия и решить каждое из них отдельно, как описано далее. а) Аналогично шагу 2, а из алгоритма ! !.43, применим исключение Гаусса к уравнениям Е111 + 1! = Е212 + Г2 для приведения вектора 1г к некоторому вектору неизвестных х.
б) Пусть с — все неизвестные в отображениях раздела. Выразим линейные неравенства ограничений, связанных с отображениями, в виде с~Рх > 0 для некоторой матрицы Р. в) Запишем предшествуюшие ограничения индексных переменных цикла и границы цикла как Ах > 0 для некоторой матрицы А. г) Применим лемму Фаркаша. Поиск х, удовлетворяюшего двум приведенным выше ограничениям, эквивалентен поиску у, такого, что А у=Р сну>0 Заметим, что здесь Р~ с соответствует ст в лемме Фаркаша и что мы используем обратный вид леммы. д) Применим исключение Фурье — Моцкина для удаления переменных у и выразим ограничения, накладываемые на коэффициенты с, в виде Ес>0.
е) Пусть Е'с' > 0 — система без константных членов. 1029 11.9. Конвейеризация 3. Найдем максимальное множество линейно независимых решений системы Е'с' > 0 с использованием алгоритма Б.1 из приложения Б. Подход этого сложного алгоритма заключается в отслеживании текущего множества решений для каждой из инструкций и в последующем инкрементном поиске более независимых решений путем вставки ограничений, которые обеспечивают линейную независимость решения как минимум для одной инструкции. 4. Из каждого найденного решения с' выведем одно аффинное отображение временного разбиения. Постоянный член получается при использовании Ес>0. и Пример 11.60. Ограничения из примера 11.57 могут быть переписаны как >О г' — Сзз — Сш Сгз (сз — сз)] (-1 О 1 О~ >О Лемма Фаркаша гласит, что эти ограничения эквивалентны следующим: из>0 ся — сз Решив данную систему, получаем Сы=Сщ>ОнСш=сз сз=О Обратите внимание на то, что частное решение, полученное в примере 11.57, удовлетворяет указанным ограничениям.
и 11.9.8 Преобразования кода Если существует Й независимых решений ограничений временнбго разбиения вложенности циклов, то ее можно преобразовать во вложенность с и внешними 1ОЗО Глава 11. Оптимизация параллелизма н локальности полностью переставляемыми циклами, что, в свою очередь, обеспечит возможность создания Й вЂ” 1 степеней конвейеризации или Й вЂ” 1 внутренних распараллеливаемых циклов. Кроме того, к полностью переставляемым циклам можно применить блокирование как для повышения локальности данных в однопроцессорной системе, так и для снижения синхронизации процессоров при параллельном выполнении программы.
Использование полностью переставляемых циклов Из к независимых решений ограничений временного разбиения можно легко создать вложенность циклов с Й внешними полностью переставляемыми циклами. Этого можно добиться, делая к-е решение й-й строкой нового преобразования. После создания аффинного преобразования можно применить алгоритм 11.45 для генерации кода. Пример 11.61.
Вспомним решения, найденные в примере 11.58 для ЯОй-кода: Делая первое решение первой строкой, а второе, соответственно, второй, получаем преобразование которое приводит к коду, показанному на рис. 11.51, а. Если же сделать первой строкой второе решение, то получится преобразование [' '1 которое дает нам код, показанный на рис. 11.51, в. Легко видеть, что такие преобразования дают корректную последовательную программу.
Первая строка разбивает все пространство итераций в соответствии с первым решением. Временные ограничения гарантируют, что такая декомпозиция не нарушает никакие зависимости данных. Затем мы разбиваем итерации в каждом внешнем цикле в соответствии со вторым решением. Такое разбиение также должно быть допустимым, поскольку мы работаем с подмножествами исходного пространства итераций.
То же самое относится и к остальным строкам матрицы. Поскольку мы можем упорядочить решения произвольным образом, циклы полностью переставляемы. 1ОЗ1 11.9, Конвейеризация Использование конвейеризации Цикл с й внешними полностью переставляемыми циклами легко преобразовать в код с к — 1 степенью конвейерного параллелизма. Пример 11.62. Вернемся к нашему БОК-примеру. После того как циклы преобразованы в полностью переставляемые, мы знаем, что итерация [гы гз] может быть выполнена при условии выполнения итераций [гы гз — Ц и [г1 — 1, 1з]. Гарантировать такой порядок выполнения в конвейере можно следующим образом.
Назначим итерацию 11 процессору рь Каждый процессор выполняет итерации во внутреннем цикле в исходном последовательном порядке, гарантируя, таким образом, что итерация [гы гз] выполняется после итерации [гы гз — Ц. Кроме того, потребуем, чтобы процессор р ожидал сигнала от процессора р — 1 о том, что он выполнил итерацию [Р— 1, 1з], перед тем как приступить к выполнению итерации [Р, гз].
Такой метод генерирует конвейеризованный код, показанный на рис. 11.52, а и б, из полностью переставляемых циклов, показанных на рнс. 11.51, а и в соответственно. и В общем случае имеется й внешних полностью переставляемых циклов, причем итерация со значениями индексов (гы...,гь) может быть выполнена без нарушения зависимостей данных при условии выполненности итераций [гз — 1, гз, , гь], [гы гз — 1, 1з, ..., гь], , , [1ы , гь ы 1ь — Ц Можно назначить части разбиения из первых 1с — 1 измерений пространства итераций О (и" ') процессорам следующим образом. Каждый процессор отвечает за одно множество итераций, у которых индексы Й вЂ” 1 измерений совпадают, а значения к-го индекса принимают все возможные значения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
