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

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

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

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

1006 Глава 11. Оптимизация параллелизма и локальности 11.8.1 Постоянное количество синхронизаций Программа, в которой отсутствует распараллеливание, не нуждающееся в синхронизации, может содержать последовательность циклов, некоторые из которых распараллеливаемы, если рассматривать их независимо. Распараллелить такие циклы можно путем введения синхронизирующих барьеров до и после их выполнения (см. пример 11.49).

Пример 11.49. На рис. 11.38 показано программное представление алгоритма интегрирования с чередующимся направлением. В нем нет параллельности, не требующей синхронизации. Зависимости в первой вложенности циклов требуют, чтобы каждый процессор работал со столбцом массива Х; во второй вложенности циклов каждый процессор должен работать со строкой массива Х.

Чтобы обеспечить отсутствие необходимости взаимодействия, весь массив должен обрабатываться одним процессором, так что ни о какой параллельности не может быть и речи. Заметим, однако, что при этом оба цикла по отдельности вполне распараллеливаем ы. аког (1 = 1г 1 < и; 1++) аког (3 = 0; 3 < и; 3++) Х[1,3] = й(Х[1,3] + Х[1-1,3]); бог (1 = 0; з. < иг 1++) аког (3 = 1; 3 < и; 3++) Х[1,3] = д(Х[1,3] + Х[1,3-1]); Рис. 11.38. Две последовательные вложенности циклов Один из способов распараллеливания кода состоит в том, что различные процессоры работают с различными столбцами массива в первом цикле, после чего выполняются синхронизация и ожидание завершения работы всеми процессорами, а после этого процессоры приступают к работе со строками массива во втором цикле. Таким путем все вычисления алгоритма могут быть распараллелены при помощи добавления единственной операции синхронизации.

Заметим, что в то время как достяпочно только одной операции синхронизации, такое распарюшеливание требует пересылки почти всех данных матрицы Х между процессорами. Снизить степень взаимодействия между процессорами можно путем введения дополнительных операций синхронизации, о чем мы поговорим в разделе 11.9.9. р Может показаться, что описанный подход применим только к программам, состоящим из последовательностей вложенностей циклов. Однако преобразования кода могут создать дополнительные возможности оптимизации. Можно применить расщепление цикла для разделения циклов в исходном тексте на несколько меньших циклов, которые затем можно по отдельности распараллелить при помощи разделения их барьерами (см. пример 11.50).

1007 1!.8, Синхронизация между параллельными циклами Пример 11.50. Рассмотрим цикл аког (1=1; 1<=и; 1++) ( Х[1] = У[1] + Е[з.]; /* (в1) */ и[А[1]] = х[1]; /* (з2) */ При отсутствии информации о значениях массива А мы должны предполагать, что доступ в инструкции аз может записывать любые элементы массива Гт". Таким образом, экземпляры аз должны выполняться последовательно в том же порядке, в котором они находятся в исходной программе, Здесь нет параллелизма, не требующего синхронизации, так что алгоритм 11 43 просто назначит все вычисления одному и тому же процессору.

Однако параллельно можно выполнять как минимум экземпляры инструкций аь Можно распараллелить часть данного кода, обеспечив выполнение разных экземпляров инструкции з~ разными процессорами, после чего один процессор, скажем, нулевой, выполнит все инструкции яз в одном последовательном цикле, как показано в БРМ[3- коде на рнс. 11.39. и Х[р] = у[р] + 8[р]; /* (а1) */ /* Барьер синхронизации */ 1~ (р == 0) гог (1=1; 1<=и; 1++) И[А[1]] = Х[1]; /* (з2) */ Рис. 11.39. 8РМ0-код к примеру 11.50; р — переменная, в которой хранится идентифика- тор процессора 11.82 Графы зависимостей программ Чтобы обнаружить все возможные при помощи добавления постоянного количества синхронизаций распараллеливания, можно применить "жадное" расщепление исходной программы.

Разобьем циклы на максимально возможное количество отдельных циклов, а затем независимо распараллелим каждый из циклов. Чтобы найти все возможные расщепления цикла, воспользуемся абстракцией графа зависимостей программы (ргойгащ-оерепг(епсе йгарп — Р]3О). Граф зависимостей программы представляет собой граф, узлами которого являются инструкции присваивания в программе, а ребра указывают зависимости данных между инструкциями и их направления. Ребро от инструкции а~ к инструкции аз имеется в том случае, когда имеется зависимость данных между некоторым динамическим экземпляром а~ и более поздним динамическим экземпляром зз. 1008 Глава 11.

Оптимизация параллелизма и локальности Для построения РОО программы мы сначала находим все зависимости данных между каждой парой (не обязательно различных) статических обращений в каждой паре (не обязательно различных) инструкций. Предположим, мы определили, что существует зависимость между обращением У) в инструкции з~ и обращением Уз в инструкции вз. Вспомним, что экземпляр инструкции определяется индексным вектором 1 = ~гы 1з,..., г' ~, где 1ь — индекс цикла Й-й вложенности, в котором находится рассматриваемая инструкция.

1. Если существует зависимая пара экземпляров, 1~ инструкции в~ и 1з инструкции вз, и 1~ в исходной программе выполняется до 1з, что записывается как 1з -~„„1з, то в РОО имеется ребро от а ~ к аз. 2. Аналогично, если существует зависимая пара экземпляров, 1~ инструкции в~ и 1з инструкции яз, и 1з с„„1ы то в РОО имеется ребро от зз к ап Заметим, что возможна ситуация, когда зависимости данных между инструкциями з~ и зз генерируют как ребро от а~ к аз, так и ребро от зз к зп В частном случае совпадения инструкций а~ и аз 1~ -с„„)з тогда и только тогда, когда 1~ -с 1з (1~ лексикографически меньше 1з). В общем случае з~ и аз могут быть различными инструкциями, возможно, принадлежащими разным вложенностям циклов.

Пример 11.51. В программе из примера 11.50 между экземплярами инструкций з~ зависимостей нет. Однако 1-й экземпляр инструкции аз должен выполняться после 1 го экземпляра инструкции зз. Что еще хуже, посколысу ссылка И' 1А 11Ц может приводить к записи любого элемента массива И', 1-й экземпляр яз зависит от всех предыдущих экземпляров зз, т.е. инструкция аз зависит сама от себя.

РОО для программы из примера 1!.50 показан на рис. 11.40. Обратите внимание на наличие в графе единственного цикла, содержащего только узел зз. и Рис. 11.40. Граф зависимостей программы для кода из примера 11.50 Граф зависимостей программы облегчает определение того, можно ли разделить инструкции в цикле. Инструкции, соединенные в цикл в РОО, разделены быть не могут. Если в~ — зз — зависимость между двумя инструкциями в цикле, то некоторый экземпляр з~ должен быть выполнен до некоторого экземпляра аз, и наоборот. Заметим, что такая взаимозависимость наблюдается, только если в~ 1009 !1.8.

Синхронизация между параллельными циклами и аз находятся в одном общем цикле. Из-за этой взаимозависимости мы не можем выполнить все экземпляры одной инструкции до другой, а значит, и выполнить расщепление. С другой стороны, если зависимость аз — ая — однонаправленная, то можно разделить цикл и сначала выполнить все инструкции аз, а затем все ~нструкции аз.

йот (х = Оз з < и; з++) ( Е[з.] = 8[1.] / В)[х]; Хек (Э = з.; з < и; з++) ( х[з,э] = у[',э]*у[а,з]з 8[э] = Е[з] + Х[з.,э]з /* (в1) */ /* (в2) */ /* (вЗ) */ а) Программа б) Ее граф зависимостей Рис. 11.41. Программа и граф зависимостей к примеру 11.52 Пример 11.52. На рис. 11.41, б показан граф зависимостей программы для кода, представленного на рис. 11.41, а. Инструкции аз и аз принадлежат циклу в графе, а значит, не могут быть помещены в разные циклы. Однако мы можем отделить инструкцию аз и выполнить все ее экземпляры до остальных вычислений, как показано на рис. 11.42.

Первый цикл распараллеливаем, второй — нет. Можно распараллелить первый цикл, поместив барьеры до и после параллельных вычислений. и 11.8.3 Иерархическое время Вычислить отношение .<„м в общем виде очень сложно, но имеется семейство программ, к которым применимы описываемые в данном разделе оптимизации и для которых сузцествует простой способ вычисления зависимостей.

Предположим, что программа блочно структурирована, состоит из циклов и простых [О[О Глава 11. Оптимизация параллелизма и локальности аког (1 = Ор 1 < п; 1++) аког (3 = 1; 3 < пр 3++) Х[1,3) = У[1,3)*У[1,3); аког (1 = О; 1 < и; 1++) ( е[1) = е[1) I (4[1); Йог (3 = 3.; 3 < и; 3++) Е[3) = Е[3) + Х[',3); /* (в2) */ /Я (в1) */ /* (вЗ) */ Рис. 11.42. Группирование сильно связанных компонентов вложенности циклов арифметических операций и не содержит иных управляющих конструкций.

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

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

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