А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 216
Текст из файла (страница 216)
В случае аффинности обращений и границ циклов задача может быть выражена как выяснение существования решения матрично-векторного уравнения в многограннике, определяющем пространство итераций. + Ранг матрицы и повторное использование. Матрица, описывающая обращение к массиву, может предоставить важную информацию об этом обращении. Если ранг матрицы принимает максимально возможное значение (минимум от количества строк и столбцов), то в процессе итераций повторное обращение не выполняется ни к одному элементу.
Если массив хранится построчно (постолбцово), то ранг матрицы с удаленной последней (первой) строкой указывает, обладает ли обращение хорошей локальностью, т.е. выполняется ли обращение к элементам в одной строке кэша примерно в одно и то же время. + Завнсииости данных и диофантовы уравнения. То, что два обращения к одному и тому же массиву работают с одной и той же его областью, еще не означает, что они в действительности обращаются к одним и тем же элементам.
Дело в том, что обращения могут пропускать некоторые элементы; в качестве примера можно привести ситуацию, когда первое обращение работает с нечетными элементами, а второе — с четными. Чтобы убедиться в наличии зависимости данных между обращениями, следует решить целочисленное диофантово уравнение. 1056 Глава 11. Оптимизация параллелизма и локальности + Решение диафантавых линейных уравнений. Ключевым методом является вычисление наибольшего общего делителя коэффициентов при переменных.
Целочисленное решение существует только в том случае, когда константный член делится на наибольший общий делитель. + Ограничения пространственного разбиения. Для распараллеливания выполнения вложенности циклов мы должны отобразить итерации циклов на пространство процессоров, которое может иметь одно или несколько измерений.
Ограничения пространственного разбиения гласят, что если два обращения в двух разных итерациях зависимы (т.е. обращаются к одному и тому же элементу массива), то они должны отображаться на один и тот же процессор. Если отображение итераций на процессоры аффинное, задачу можно сформулировать в матрично-векторном виде. + Прил|итивные преобразования кода.
Преобразования, использующиеся для распараллеливания программ с аффинными обращениями к массивам, представляют собой комбинации семи примитивов: слияния циклов, расщепления циклов, реиндексирования (добавления константы к индексам циклов), масштабирования (умножения индексов циклов на константу), реверса индекса цикла, перестановки порядка циклов и сдвига (переписывания циклов так, что линии обхода пространства итераций не лежат вдоль олной из осей). + Синхронизация параллельных операций. Иногда больший параллелизм может быть получен путем вставки синхронизирующих операций между шагами программы. Например, последовательные вложенности циклов могут иметь зависимости данных, но синхронизация между циклами может позволить распараллелить эти циклы по отдельности. + Конвейеризация.
~от метод распараллеливания позволяет процессорам совместно использовать данные, синхронно передавая определенные данные (обычно элементы массивов) от одного процессора к соседнему процессору в пространстве процессоров. Данный метод может повысить локальность данных, к которым обращается каждый из процессоров. + Ограничения временного разбиения. При выяснении возможностей конвейеризации требуется найти решение ограничений временного разбиения, которые гласят, что если два обращения к массиву могут работать с одним и тем же элементом массива, то обращение в итерации, которое выполняется первым, должно быть назначено стадии конвейера, которая выполняется не позже стадии, которой назначено второе обращение. 1057 1!.13.
Список литературы к главе ! ! + Решение ограничений временного разбиения. Лемма Фаркаша предоставляет метод поиска всех аффинных отображений временного разбиения, допустимых для данной вложенности циклов с обращениями к массиву. Этот метод по сути заменяет дуальной основную формулировку линейных неравенств, выражающих ограничения временного разбиения.
+ Блокирование. Этот метод разбивает каждый из нескольких циклов во вложенности на два цикла. Преимущество этого метода состоит в том, что это может позволить нам работать с малыми частями (блоками) многомерного массива, по одному блоку за раз. Это, в свою очередь, повышает локальность программы, позволяя всем необходимым данным размещаться в кэше при выполнении одного блока. + Раеналаеование. Подобно блокированию, этот метод разбивает подмножество циклов вложенности на два. Возможное преимущество заключается в том, что обращения к многомерному массиву выполняются "полосами", что может привести к улучшенному использованию кэша. 11.13 Список литературы к главе 11 За детальным рассмотрением многопроцессорных архитектур мы отсылаем читателя к книге Хеннесси (Неппеьву) и Паттерсона (Рацегвоп) [9].
Концепция анализа зависимостей данных разработана Лампортом ((.шпрогг) [13], а также Куком (Кцск), Мураокой (Мшаока) и Ченом (СЬеп) [б]. Ранние проверки наличия зависимостей данных использовали эвристики для доказательства независимости пар обращений путем определения отсутствия решений диофантовых уравнений и систем действительных линейных неравенств [5, 6, 2б]. Майдан (Марап), Хеннесси (Непчеззу) и Лам (1.агп) [18] сформулировали тест зависимости данных как задачу целочисленного линейного программирования и показали, что она может быть точно н эффективно решена на практике.
Анализ зависимостей данных, описанный здесь, основан на работах Майдана (Марап), Хеннесси (Неппевву) и Лама (1.агп) [18], а также Паха (Рп8Ь) и Воннакотта (ЪЪппасоц) [23], которые, в свою очередь, используют методы исключения Фурье-Моцкина [7] и алгоритм Шостака [25]. К 70-м и началу 80-х годов относятся преобразования циклов для повышения векторизации и распараллеливания: слияния циклов [3], расщепления циклов [1], располосования [17] и обмена циклами [28].
К этому времени относятся три основных экспериментальных проекта распараллеливания/векторизации: Рагабгазе под руководством Кука (Кцск) в Университете Иллинойса [2Ц, проект РРС под руководством Кеннеди (Кеппег)у) в Университете Райса [4] и проект РТВА)ч) под руководством Аллена (А!!еп) из 1ВМ КезеагсЬ [2]. 1058 Глава 11. Оптимизация параллелизма н локальности Мак-Келлар (МсКейаг) и Коффман (Сойпап) [191 первыми рассмотрели применение блокирования для повышения локальности данных. Лам (Ьагп), Ротберт (КосЬЬегс) и Вольф (%о!С) [12! выполнили первый глубокий эмпирический анализ блокирования при использовании кэшей современных архитектур.
Вольф (%о[С) и Лам (Ьаш) [271 воспользовались методами линейной алгебры для вычисления повторного использования данных в циклах. Саркар (Баг1саг) и Гао (бас) [241 открыли оптимизацию сжатия массивов. Лампорт (Ьагпрогг) [131 первым смоделировал циклы как пространства итераций и использовал частный случай аффинного преобразования для поиска параллелизма в многопроцессорных системах. Корни аффинных преобразований произрастают из алгоритма проектирования систолических матриц [1!1. Предназначавшиеся для параллельных алгоритмов, непосредственно реализованных в СБИС, систолические массивы требовали минимизации взаимодействия при распараллеливании. Для отображения вычислений на пространственные и временные координаты были разработаны специальные алгебраические методы.
Концепция аффинного планирования и применение леммы Фаркаша в аффинных преобразованиях были введены Футриером (Реаиспег) [8]. Алгоритм аффинного преобразования, описанный в данной книге, основан на работе Лима (Ьпп) и др. [14 — 161. Портерфилд (Рогсегбе!д) [221 предложил один из первых алгоритмов компиляции для предвыборки данных. Моури (Мо агу), Лам (1.асп) и Гупта (бирса) [20! применили анализ повторного использования для минимизации накладных расходов предвыборки и повышения общей производительности программы.
1. АЬи-ЯиГаЬ, 'чч'., О. 3. Кис(с, апс! О. Н. Ьасчг(е, "Оп сйе рег1оппапсе епЬапсешепс оГ ра81п8 вувгепсв СЬгои8Ь ргойгагп апа!уяв апс! сгапв!оппасюпв", 1ЕЕЕ Тгапв. оп Сотрийпй С-30:5 (1981), рр. 341 — 356. 2. АПеп, К Е., М. Вот!се, Р. СЬаг!ев, К. Сусгоп, апс! 3. Реггапсе, "Ап очегчсечч оГ сЬе РТКАХ апа!уяв вувгегп Сог ши!ссргосевяп8", Х Рагайе! апИ ОсйгпЬигег! Сотригсп8 5:5 (1988), рр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
