А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 194

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 194)

! Упражнение П.3.9. Пусть А, В и С вЂ” целочисленные константы, причем С > 1 и В > А. Перепишите цикл аког(г = А; г <= В; г = г + С) 2(з.] = 0; так, чтобы прирост переменной цикла был равен 1, а начальное ее значение было равно О, т.е. представьте цикл в виде аког(3 = 0; 3 <= Э; 3++) 2 [Е*3+Е] = 0; для некоторых Р, Е и Г. Выразите Р, Е и Е через А, В и С. Упражнение 11.3.10. Запишите для приведенной ниже обобщенной вложенности циклов ограничения, определяющие пространство итераций, в матричном виде, т.е. в виде В1 + Ь = О. аког(г = О~ г <= Ар з++) аког (3 = В*г ьСз 3 < О*з+Е; з++ ) Здесь А, В, С, Р и Š— константы. Уцражнеиие 11.3.11.

Повторите упражнение 11.3.10 для обобщенной вложенно- сти циклов с символьными целочисленными константами т и и: аког(г = 0; з <= вы г++) аког(З = А*а+В; 3 < С*г+п; 3++) Как и ранее, А, В и С вЂ” определенные целочисленные константы. В векторе неизвестных должны участвовать только г, у, т и п. Вспомните также, что выходными являются только переменные 1 и ). 948 Глава 11. Оптимизация параллелизма и локальности 11.4 Аффинные индексы массивов В этой главе рассматривается класс аффинных обращений к массивам, в котором каждый индекс массива представляет собой аффинное выражение от индексов циклов и символических констант.

Аффинные функции предоставляют собой лаконичное отображение пространства итераций на пространство данных, упрощающее определение того, какие итерации отображаются на одни и те же данные или одни и те же строки кэша. Аффинные функции обращения к данным могут быть представлены в матричном виде, так же, как и аффинные верхняя и нижняя границы цикла. Применение матричной записи позволяет применить стандартные методы линейной алгебры для получения разнообразной информации, например о размерности ланных, к которым выполняется обращение, или итерациях, которые обращаются к одним и тем же данным.

11.4.1 Аффннные обращения к данным Мы говорим, что обращение к массиву в цикле аффинное, если 1. границы цикла представляются аффинными выражениями от переменных охватывающих циклов н символьных констант; 2, индекс каждого измерения массива также представим в виле аффинного выражения от переменных окружающих циклов и символьных констшга Пример 11.16. 11рсдположим, что) и 1 — индексные переменные циклов, ограниченных аффинными выражениями. Примерами аффинных обращений к массивам могут служить 2 [1], Я [т'+ ) + 1,', 7 [0], У [!',Г[ н 7 [21+ 1,3*) — 10]. Еще одним примером может слу«ить У, [3 * л,п — )], где и — символическая константа вложения циклов.

Однако ни Я [1 з]. ни Я1п, «!] аффинными обращениями не являются. п Каждое аффинное обращение к массиву можно описать двумя матрицами и двумя векторами. Первая пара "матрица вектор" (В н Ь) описывает пространство итераций длл данных обращений, как в неравенстве (11.1). Вторая пара, которую мы обозначим как В и 1; представляет функции от индексных переменных циклов, которые возвращают индекс (или индексы) массива, используемые в качестве различных измерений при обращениях к массиву. Формально мы представляем обращения к массиву во вложенности циклов, которая использует вектор индексных переменных 1, в виде четверки У = (Г, Г, В, Ь).

Она отображает вектор 1 в границах В1+Ь ) 0 949 11.4. Аффинные индексы массивов на элемент массива г1+ Г Пример 11.17. На рис. 11.18 показаны некоторые распространенные обращения к массивам, выраженные в матричной форме. Циклами индексов являются 1 и 1, образующие вектор й Х, У и У вЂ” одно-, двух- и трехмерныс массивы соответственно. Рис. 11.18. Некоторые обращения к массивам и их матричное представление Первое обращение, Х [1 — 1], представлено с помощью матрицы Е размером 1 х 2 и вектора 1 длиной 1.

Заметим, что при выполнении матричного умножения и суммирования с вектором Г мы получаем единственную функцию 1 — 1, которая представляет собой формулу для обращения к одномерному массиву Х. Третье обращение, У [7', з + 1], после матричных умножения и сложения дает пару функций (з, 1+ 1), которые являются индексами двух размерностей при обращении к массиву.

Наконец, взглянем на четвертое обращение — У [1, 2[. Это константное обращение, так что ничего удивительного, что г представляет собой нулевую матрицу. Соответственно, вектор индексов циклов 1 в функции обращения не появляется.о 11.4.2 Аффинное и неаффинное обращения на практике В численных программах встречаются некоторые распространенные шаблоны обращения к данным, не являющиеся аффинными. Важным примером служат 950 Глава 11. Оптимизация параллелизма и локальности программы, работающие с разреженными матрицами. Один из методов хранения разреженных матриц заключается в хранении ненулевых элементов в векторе, а вспомогательный массив индексов используется для информации о том, где начинаются строки и какие столбцы содержат ненулевые значения. Для работы с такими данными используется косвенное обращение к массивам.

Обращение такого вида, такое как Х []' [(]], является неаффинным обращением к массиву Х. Если разреженность регулярная, как в ленточной матрице, в которой ненулевые элементы располагаются вокруг диагонали, то для обращения к ним могут использоваться плотные массивы, представляющие подобласти с ненулевыми элементами. В этом случае обращение может быть аффинным.

Другим распространенным примером неаффинного доступа являются линеаризованные массивы. Программисты иногда используют линейные массивы для хранения логически многомерных обьектов. Одной из причин такого решения может оказаться неизвестность различных измерений массива во время компиляции. Обращение, которое выглядит как Я [(, )], может быть выражено в виде У [( * и + )'], в котором участвует квадратичная функция (напомним, что символьные константы рассматриваются как переменные).

Линейное обращение можно преобразовать в многомерное, если каждое обращение может быть разложено на отдельные измерения с гарантией, что ни один из компонентов не выйдет за границы массива. Наконец, заметим, что для преобразования некоторых неаффинных обращений в аффинные может использоваться анализ переменных индукции, как показано в примере 11.18.

Пример 11.18. Код = и; аког (х = О; з <= и; х++) Е[э] = О; э+г; ) может быть переписан как = и; аког (х = О; х <= и; з++) ( 8[и+г*х] = О; ) 'зто делает обращение к массиву У аффинным. 11.4.3 Упражнения к разделу 11.4 Упражнение 11.4.!. Для каждого из приведенных обращений к массиву приведитс векгор Г и магрицу г, описывающие эти обращения. Считается, что вектор индексов ( имеет вид ц ),... и что все индексы циклов имеют аффинные границы. 951 ! !.5. Повторное использование данных а) Х!2аз+3,2ау — з~.

б) г'(з — у, у — а,Ус — з~. в) 7(3,2а у,й — 2» »+Ц. 11.5 Повторное использование данных Из функций обращения к массивам мы получаем два вида информации, полезной при решении задачи оптимизации локальности и распараллеливания. !. Повторное использование данных (»)ага генке). При оптимизации локальности необходимо определить множества итераций, которые обращаются к одним и тем же данным или одной и той же строке кэша. 2.

Зависимости данных. Для корректности преобразований распараллеливания и оптимизации локальности следует определить все зависимости данных в коде. Вспомним, что два (не обязательно различных) обрашения связаны зависимостями через данные (для краткости — зависимостями данных), если экземпляры обращений могут обращаться к одной и той же ячейке памяти и при этом как минимум одно из них представляет собой запись в память. Во многих случаях, когда мы выявляем итерации, использующие одни и те же данные, между ними обнаруживаются и зависимости данных.

При наличии зависимостей данных очевидно, что повторно используются одни и те же данные. Например, в матричном умножении один и тот же элемент выходного массива записывается О (и) раз. Операции записи должны выполняться в исходном порядке;з о повторном обращении к данным в этом случае можно говорить потому, что мы можем выделить регистр для хранения одного элемента выходного массива в процессе вычисления этого элемента. Однако не все повторные использования могут быть задействованы в оптимизации локальности; ниже приведен пример, иллюстрирующий это утверждение. Пример 11.19. Рассмотрим цикл йот (1 = О; 1 < и; 1++) Е(7*1+3) = Е(3*1+5); 'Здесь имеется один тонкий момент.

Из-за коммутатианости сложения мы должны получить один и тот же результат независимо от порядка суммироаания. Однако тю слишком частный случай. В общем случае определение того, что вычисление представляет собой последовательность арифметических шагов, за которыми следует запись результата, слишком сложна для компилятора. Мы не можем полагаться на применение алгебраических правил для безопасного переупорядочения кода. 952 Глава 11. Оптимизация параллелизма и локальности Мы видим, что на каждой итерации цикл выполняет запись в разные места, так что между различными операциями записи нет зависимостей данных по записи и повторных использований данных. Цикл считывает элементы 5, 8, 11, 14, 17, ...

и записывает элементы 3, 1О, 17, 24, ... Таким образом, чтение и запись обращаются к одним и тем же элементам 17, 38, 59 и т.д., т.е. целые числа вида !7+ 21з, з =- 0,1,2,... могут быть записаны как в виде 7(г + 3, так и в виде 3!з + 5 для некоторых целых (г и гз. Однако такое повторное использование встречается крайне редко и воспользоваться им очень сложно, если вообще возможно.

Характеристики

Список файлов книги