А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 186
Текст из файла (страница 186)
Говоря более конкретно,мы будем рассматривать программы, обращения к массивам в которых аф4инлы (айне) по отношению к индексам охватывающих циклов. Например, если г и з — индексные переменные охватывающих циклов, то У [г] [1] и Я]1] ]1+ 1] — аффинные обращения. Функция от одной или нескольких переменных ты жз,..., т„называется иф4инной, если она может быть выражена как сумма константы и константных множителей, умноженных на переменные, те.
как со+с~кз+сзхз+...+с„к„, где сш сы..., г — константы. Аффинные функции обычно известны как линейные, хотя, строго говоря, линейная функция не должна иметь член со. Вот простой пример соответствующего цикла: аког(з = 0; з < 10г з++) 2[5.1 = 0; Поскольку итерации цикла записывают разные ячейки памяти, разные итерации могут одновременно выполняться разными процессорами. С другой стороны, если прн этом выполнялась бы другая инструкция, скажем, Е [ З 1 = 1, то надо было бы отслеживать, не может ли г быть равной з, и, если может, выяснять, в каком порядке следует выполнять экземпляры этих двух инструкций, которые работают с одним и тем же значением индекса массива.
Знать, какие итерации могут обращаться к одним и тем же ячейкам памяти, крайне важно. Это знание позволяет определить зависимости данных, которые следует учитывать при планировании кода как для однопроцессорных, так и для многопроцессорных систем. Наша цель заключается в том, чтобы найти план, который учитывает все зависимости данных, так что операции, обрашаюшиеся к одной и той же ячейке памяти или строке кэша, выполняются по возможности 913 поближе друг к другу, причем в многопроцессорной системе — на одном и том же процессоре.
Представленная в этой главе теория основана на линейной алгебре и методах целочисленного программирования. Мы моделируем итерации в цикле глубиной вложенности и как и-мерный многогранник, границы которого определяются границами цикла в коде. Аффинные функции отображают каждую итерацию на массив ячеек памяти, к которым она обращается. Для определения наличия двух итераций, обращающихся к одной и той же ячейке памяти, можно использовать целочисленное линейное программирование. Множество преобразований кода, рассматриваемое здесь, подразделяется на две категории: аффинное разбиение (айне рап!!!оп!пй) и блокирование (Ыоск!пй).
Аффинное разбиение разделяет многогранник итераций на компоненты, выполняемые либо различными машинами, либо последовательно. Блокирование, с другой стороны, создает иерархию итераций. Предположим, у нас имеется цикл, построчно сканирующий массив. Вместо этого можно разделить массив на блоки и посетить все элементы блока перед переходом к следующему блоку.
Получающийся в результате код будет состоять из внешних циклов, обходящих блоки, и внутренних, сканирующих элементы в пределах каждого блока. Для определения как наилучшего аффинного разбиения, так и наилучшей схемы блоков используются методы линейной алгебры. Мы начнем с обзора концепций оптимизации параллельных вычислений и локальности в разделе 11.!.
Затем в разделе ! !.2 теоретические концепции будут дополнены конкретным примером — умножением матриц, — который покажет, как преобразование цикла (1оор !гапз!оппабоп), изменяющее порядок вычисления в цикле, может повысить локальность и эффективность распараллеливания. В разделах ! 1.3-11.6 представлена предварительная информация, необходимая для выполнения преобразований циклов. В разделе 11.3 показана модель отдельной итерации цикла, в разделе 11.4 — модель функций индексов массива, которые отображают каждую итерацию цикла на ячейки массива, к которым обращается эта итерация. В разделе 11.5 рассматривается, как с помощью алгоритмов линейной алгебры определить, какие итерации цикла обращаются к одной и той же ячейке цикла или строке кэша, а в разделе 11.6 — как найти все зависимости данных среди обращений к массиву в программе.
В оставшейся части главы эта информация применяется для выполнения оптимизации. В разделе 11.7 сначала рассматривается более простая задача поиска параллельности, не требующей синхронизации. Для получения наилучшего аффинного разбиения мы просто находим решение с ограничением, заключающимся в том, что операции с зависимостями данных назначаются одному и тому же процессору. Однако имеется не так уж много программ, которые могут быть распараллелены без необходимости синхронизации. Поэтому в разделах 11.8 — 11.9.9 мы рас- 914 Глава 11. Оптимизация параллелизма и локальности сматриваем общий случай поиска параллельности, требующей синхронизации.
Мы вводим концепцию конвейеризации, показывающую, как найти аффинное разбиение, максимизирующее степень допустимой конвейеризации программы. Как выполнить оптимизацию локальности, будет рассмотрено в разделе !1.!О. И наконец, мы рассмотрим, как аффинные преобразования могут пригодиться для оптимизации других видов параллелизма. 11.1 Фундаментальные концепции В этом разделе вводятся фундаментальные концепции, связанные с оптимизацией параллелизма и локальности, Если операции могут выполняться параллельно, то они могут быть переупорядочены для других целей, например для повышения локальности.
И наоборот, если зависимости данных в программе диктуют последовательное выполнение команд, то речь не идет ни о параллельности, ни о возможности переупорядочения команд для повышения локальности. Таким образом, анализ параллелизма одновременно находит возможности для повышающих локальность перемещений кода. Для минимизации взаимосвязей в параллельном коде мы группируем все связанные операции и назначаем их одному процессору.
Получающийся в результате код должен обладать локальностью данных. Один грубый подход для получения хорошей локальности данных в однопроцессорной системе заключается в том, чтобы процессор поочередно выполнял код, предназначенный для разных процессоров. Этот вводный раздел мы начнем с обзора параллельных архитектур компьютеров. Затем мы рассмотрим базовые концепции распараллеливания и использование подобных соображений для оптимизации локальности. И наконец, мы неформально познакомимся с математическими концепциями, используемыми в данной главе.
11.1.1 Многопроцессорность Наиболее популярной параллельной архитектурой является симметричная мультипроцессорность (зупнпе1Пс пш!бргосеззог — ЗМР). Высокопроизводительные персональные компьютеры зачастую оснащены двумя процессорами, а многие серверные машины имеют четыре, восемь, а иногда даже десятки процессоров. Еще большее распространение мультипроцессорные системы получили с возможностью компоновки нескольких высокопроизводительных процессоров в одной микросхеме.
Процессоры в симметричной мультипроцессорной системе используют одно адресное пространство. Для взаимодействия друг с другом они просто пишут информацию в ячейки памяти, которая затем считывается другим процессором. 915 11.1. Фундаментальные концепции Симметричная многопроцессорность названа так в связи с тем, что все процессоры могут обращаться ко всей памяти в системе с одинаковым временем доступа. На рис. 11.1 показана высокоуровневая архитектура многопроцессорной системы.
Процессоры могут иметь свои кэши первого, второго, а иногда даже третьего уровней. Кэши наивысшего уровня подключаются к физической памяти обычно через общую шину. Рис. 11.1. Симметричная многопроцессорная архитектура Симметричные многопроцессорные системы используют протокол когерентной кэш-памяти 1сопегеп1 сасне рго1осо!) для сокрытия наличия кэшей от программиста.
При использовании такого протокола несколько процессоров могут одновременно хранить копии одной и той же строки кэша' при условии, что они только считывают оттуда данные. Когда процессор должен записать данные в строку кэша, копии этой строки из всех других кэшей удаляются. Когда процессор запрашивает данные, отсутствующие в кэше, запрос идет к общей шине, н данные выбираются либо из памяти, либо из кэша другого процессора. Время, затрачиваемое одним процессором на общение с другим, примерно вдвое превышает стоимость обращения к памяти.
Данные, единицей которых служит строка кэша, сначала должны быть записаны из кэша первого процессора в память, а затем выбраны из памяти в кэш второю процессора. Вы можете подумать, что межпроцессорное взаимодействие — относительно дешевая операция, раз она всего лишь в два раза медленнее обращения к памяти. Но вы должны помнить, что обращения к памяти очень дброги по сравнению с обращением к кэшу — они могут быть медленнее в сотни раз. Этот анализ подводит нас к сходству ьО коше и строках кзшв рассказывалось в разделе 7.4. 916 Глава 11. Оптимизация параллелизма н локальности между параллельностью и локальностью.
Для эффективной работы процессора— как самого по себе, так и в контексте многопроцессорной системы — требуется, чтобы большинство данных, с которыми он работает, находились в кэше. В начале 2000-х годов проектирование симметричных многопроцессорных систем не выходило за пределы десятков процессоров, поскольку общая шина (или любой иной способ межпроцессорного взаимодействия) не могла обеспечить быструю работу при большем количестве процессоров. Чтобы обеспечить масштабируемость многопроцессорных систем, потребовалось введение еще одного уровня в иерархии памяти. Вместо памяти, доступной каждому процессору, в новой архитектуре память распределена для каждого процессора отдельно, так, чтобы каждый процессор мог быстро работать со своей локальной памятью, как показано на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
