А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 189
Текст из файла (страница 189)
925 Фундаментальные концепции цикл определяет одномерное пространство из десяти итераций, помечен- ных значениями индекса цикла 1 = О, 1,..., 9. 2. Пространство Данных. Пространство данных задается непосредственно объявлениями массивов. В нашем примере элементы массива проиндексированы значениями а = 0,1,...,99. Несмотря на то что любой массив представляет собой линейный участок в адресном пространстве программы, мы рассматриваем и-мерные массивы как и-мерные пространства и считаем, что отдельные индексы находятся в их границах. Массив в нашем примере одномерный.
3. Пространство процессоров. Будем считать, что в целевой системе имеется неограниченное количество виртуальных процессоров. Процессоры организованы в многомерное пространство, по одному измерению для каждого цикла вложения, которое мы хотим распараллелить. Если после распараллеливания оказывается, что физических процессоров у нас меньше, чем виртуальных, мы разделяем виртуальные процессоры на одинаковые блоки и назначаем каждый блок физическому процессору. В данном примере необходимо десять процессоров, по одному для каждой итерации цикла.
На рнс. 11.4 предполагается, что процессоры организованы в одномерном пространстве и пронумерованы от 0 до 9, так что процессор 1 выполняет 1-ю итерацию. Если у нас, скажем, всего пять физических процессоров, то мы можем назначить итерации 0 и 1 процессору О, итерации 2 и 3 — процессору 1 и т.д. Поскольку итерации независимы, не имеет значения, как именно будет выполнено их распределение по процессорам, важно лишь, что каждому из пяти процессоров будут назначены две итерации.
4. Аффинная индексная функция. Каждое обращение к массиву в коде опреде- ляет отображение итерации из пространства итераций на элемент массива в пространстве данных. Функция обращений является аффинной, если она включает только умножения индексных переменных на константы, а также суммирование полученных произведений и прибавление константы. Обе функции обращения в нашем примере — 1 и !+ 10 — аффинные.
Зная функцию обращения, мы можем говорить о размерности данных, к которым выполняется обращение. В нашем случае, поскольку каждая функция содержит только одну переменную цикла, пространство элементов массива, к которым выполняется обращение, одномерно. 5. Аффинное разбиение. Мы распараллеливаем цикл, используя аффинную функцию для назначения итераций из пространства итераций процессорам из пространства процессоров. В нашем примере мы просто назначаем итерацию 1 процессору г.
При помощи аффинной функции можно также 926 Глава 11. Оптимизация параллелизма и локальности указать новый порядок выполнения. Если мы хотим выполнять наш цикл последовательно, но в обратном порядке, достаточно просто определить упорядочиваюшую функцию как аффинное выражение 10 — 1. Таким образом, первой будет выполнена итерация 9, и т.д. 6. Область данных, к которым выполняется обращение. Для поиска наилучшего аффинного разбиения желательно знать область данных, к которым выполняется обращение. Можно получить эту область данных путем объединения информации о пространстве итераций с индексной функцией массива. В нашем случае обращение к массиву Я [1 + 10] затрагивает область (а, ] 1О < а < 20), а обращение Я [1] — область (а ] 0 < а < 101.
7. Зависимости данных. Для определения того, можно ли распараллелить данный цикл, следует выяснить, пересекают ли зависимости данных границы каждой итерации. В нашем примере мы сначала рассматриваем зависимости записей. Поскольку функция обращения У [1 + 10] отображает различные итерации на различные элементы массива, здесь нет зависимостей, которые относятся к порядку, в котором разные итерации записывают значения в массив. Но нет ли здесь зависимостей между обращениями для чтения и обращениями для записи? Поскольку записываются только элементы 7 [10], Я [1Ц,..., 7 [19] (обрашение к 7 [1+ 10]), а считываются только Я [0], У [1],..., Я [9] (обрашение к У [1]), нет никаких зависимостей, связанных с относительным порядком чтения и записи.
Таким образом, данный цикл можно распараллелить, т.е. каждая итерация цикла не зависит от всех остальных итераций, и эти итерации могут быть выполнены параллельно, в любом выбранном порядке. Заметим, однако, что если внести небольшие изменения, например установить верхний предел для индекса 1 равным 1О или более, то в таком случае возникнут зависимости, поскольку некоторые элементы массива У записываются в одной итерации, а затем считываются десятью итерациями позже.
В таком случае полное распараллеливание цикла невозможно, и нам надо хорошо подумать о том, как распределить итерации среди процессоров и в каком порядке их выполнять. и Формулировка задачи в терминах многомерных пространств и аффинных отображений между ними позволяет применить стандартный математический аппарат для решения задачи распараллеливания и оптимизации локальности в обшем виде. Например, область данных, к которым выполняется обращение, можно найти путем устранения переменных с использованием алгоритма ФурьеМоцкина (Еопг)ег-Могхк1п е!ппшайоп а1яог11)зш). Зависимости данных эквивалентны задаче целочисленного линейного программирования. Наконец, поиск аффинного разбиения соответствует решению множества линейных ограничений.
Не 927 1!.2. Пример посерьезнее: умножение матриц беспокойтесь, если вам ничего не говорят упомянутые здесь названия — все они будут пояснены позже, начиная с раздела 11.3. 11.2 Пример посерьезнее: умножение матриц Множество методов, используемых параллельными компиляторами, можно рассмотреть на одном большом примере. В этом разделе мы изучим хорошо известный алгоритм умножения матриц, чтобы показать, насколько нетривиальна задача оптимизации даже такого простого и легко распараллеливаемого шпоритма. Мы увндилп как переписывание кода может повысить локальность кода, т.е.
процессоры будут иметь возможность выполнять работу с существенно меньшим взаимодействием (с глобальной памятью или друг с другом — в зависимости от используемой архитектуры), чем в случае выбора обычной программы, непосредственно реализующей алгоритм. Мы также обсудим, как может повысить производительность такой программы, как матричное умножение, существование строк кэша, хранящих несколько последовательных элементов данных.
11.2.1 Алгоритм умножения матриц На рис. 1!.5 показана типичная программа умножения матриц.' Она принимает две матрицы, Х и У, размером и х и, и выдает их произведение в качестве матрицы Л. Вспомним, что Я, — элемент матрицы У в строке 1 и столбце у— должен быть равен ~,"я' ! Хвь')'ь . аког (з = 0; з < и; з++) лог (3 = 0; 5 < и; 5++) ( 2[з.,5] = 0.0; Гог ()< = 0; )с < и; )с++) г[',5) = К[',5! + Х[з,)с)*Х[)с,7)! Рис.
11.5. Базовый алгоритм умножения матриц Код на рис. ! 1.5 генерирует гзз результатов, каждый из которых представляет собой скалярное произведение одной строки и одного столбца из двух операндов- матриц. Очевидно, что вычисления каждого элемента Л независимы и могут быть выполнены параллельно. Чем больше значение п, тем большее количество раз алгоритм обращается к каждому элементу.
Всего в трех матрицах используются Зпз ячеек памяти, но 'П программах этой главы мы, в основном, используем синтаксис С, но при обращении к миоин мерным массивам (что является центральным вопросом этой главы) лля простоты чтения используется запись в стиле Роптал — У [з, т! вместо Х [г! [з!. 928 Глава 11. Оптимизация параллелизма и локальности алгоритм выполняет пз операций, состоящих в умножении элемента Х на элемент У и прибавлении полученного произведения к элементу Л. Таким образом, данный алгоритм выполняет интенсивные вычисления и обращения к памяти, которые в принципе, не должны быть его узким местом.
Последовательное выполнение умножения матриц Сначала рассмотрим, как ведет себя программа при последовательной работе на единственном процессоре. Наиболее глубоко вложенный цикл считывает и записывает один и тот же элемент У., используя при этом строку Х и столбец У. У 1г,Я можно легко хранить в регистре без обращений к памяти. Без потери общности будем считать, что матрицы располагаются в памяти построчно и что в одной строке кэша может храниться с элементов массива. п-! =О Рис. 11.6. Шаблон обращения к данным при умножении матриц На рис. 11.6 показан шаблон обращения к матрицам при выполнении одной итерации внешнего цикла, представленной на рис.
11.5. Конкретно на рисунке показана первая итерация, с 1 = О. Каждый раз при переходе от одного элемента первой строки Х к следующему мы посещаем каждый элемент одного столбца У. На рис. 1!.6 представлено предположительное размещение матриц в строках кэша. Каждый небольшой прямоугольник на рисунке представляет строку кэша, в которой хранятся четыре элемента массива (т.е. на рисунке представлен случай с = 4 и и = 12).
Обращение к Х обеспечивается небольшой нагрузкой на кэш. Одна строка Х распределена среди гз/с строк кэша. В предположении, что все они помещаются в кэше, можно считать, что для фиксированного значения индекса) наблюдается и/с промахов кэша, а общее количество промахов для всех элементов Х составляет пз(с — это минимально возможное значение (для удобства мы считаем, что п делится на с). 1!.2. Пример посерьезнее: умножение матриц 929 Однако при использовании одной строки Х алгоритм умножения матриц обращается ко всем элементам У столбец за столбцом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
