А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 212
Текст из файла (страница 212)
Для алгоритма интегрирования из примера 11.49 мы показали, что независимая оптимизация первой и второй вложенностей циклов обнаруживает параллелизм в каждой вложенности. Однако такая схема требует пересылки матрицы между циклами, что приводит к пересылке О (пз] данных. Если для поиска конвейеризуемого параллелизма использовать алгоритм 11.59, то обнаружится, что вся программа может быть преобразована в полностью переставляемую вложенность циклов, как показано на рис. 11.59. Затем для снижения накладных расходов, связанных с взаимодействием, можно применить блокирование. Такая схема может привести к использованию О (и) синхронизаций, но потребует сушественно меньшего количества взаимодействий.
а гог (З = 0; З < и; 3++) аког (г = 1; з < и+1; з++) ( гг (з. < и) Х(з.,з] = г(Х(з.,з] + Х[з.-1,3]) зй (з > 0) Х(1 — 1,э] = д(Х(з.-1,з],Х(з.-1,З-1]); Рис. 11.59. Полностью переставляемая вложенность циклов для кода нз примера 11.49 11.9.10 Упражнения к разделу 11.9 Упражнение 11.9.1. В разделе 11.9.4 мы рассматривали возможность использования диагоналей, отличных от горизонтальной и вертикальной осей, для конвейеризации кода на рис. ]1.51. Напишите код, аналогичный циклам на рис.
11.52, для диагоналей под углом а) 135', б) 120'. Упражнение 11.9.2. Код на рис. 11.55, б можно упростить, если и нацело делится на 5. Перепишите код при выполнении этого условия. 10ЗВ Глава 11. Оптимизация параллелизма и локальности Упражнение 11.9.3. На рис. 11.60 приведена программа для вычисления первых 100 строк треугольника Паскаля (т.е.
Р (г',Я представляет количество способов выбрать ) предметов из з, 0 < з' < з < 100). а) Перепишите код в виде единой, полностью переставляемой вложенности циклов. б) Воспользуйтесь конвейером из 100 процессоров для реализации этого кода. Напишите код для каждого процессора р с использованием переменной р и укажите необходимые синхронизации. в) Перепишите код с использованием квадратных блоков размером 10 х 10 итераций каждый. Поскольку итерации образуют треугольник, всего потребуется 1+ 2+ + 10 = 55 блоков. Приведите код для процессора (ры рз), которому назначен рз-й блок в направлении ( и рз-й — в направлении )', с использованием переменных р1 и рз. аког (1=0; 1<100; з++) ( Р[г,О] = 1; /* в1 */ Р[1 з] = 1; /* в2 */ ) аког (а=2! г<100! з++) аког (э=1! э<1; )++) Р[з.,Э] = Р[з-1,З-1] + Р[1-1,]]! /* вЗ */ Рис.
! !.60. Вычисление треугольника Паскаля ! Упражнение 11.9.4. Повторите упражнение 11.9.2 для кода на рис. 11.6!. Обратите внимание, что итерации в этой задаче образуют куб со стороной 10. Таким образом, в части в блоки имеют размер 10 х 10 х 10, а их общее количество— 1000 штук. ! Упражнение 11.9.5. Применим алгоритм 11,59 к простому примеру ограничений временного разбиения. Далее предполагается, что вектор !г представляет собой (гы )1 ), а вектор !з — ((з, )з). Условие !г .<„„!з состоит из дизьюнкции а) (1 < (з или б) (1 = (г и )г <,1з.
1039 11.10. Оптимизации локальности аког (1=0; 1<100! 1++) [ А[1, 0,0] = В1[з.]; /* в1 */ А[з.,99,0] = В2[з.]; /* в2 */ ) аког (9=1; 9<99! З++) ( А[ О З,О] = ВЗ[З]; /* вЗ */ А[99,5,0] = В4[З]! /* в4 */ аког (1=0; 1<99; 1++) аког (З=Ор З<99р З++) аког ()с=1; )с<100! )с++) А[з.,З,)с] = 4*А[1,З,)с-1] + А[з.-1,9,1с-1] + А[з.+1,З,)с-1] + А[з.,З-1,1с-1] А[1,5+1,)с-1]; /* в5 */ Рнс. ! 1.61. Код к упражнению 11.9.4 Прочими уравнениями и неравенствами являются 2(з + )! — 10 > 0 (з + 2)з — 20 > 0 г! = гз+ )з — 50 у! =,)э+ 40 Наконец, неравенство временнбго разбиения с неизвестными сз, с(з, ез, сз, Нз и ез имеет вид с!из+ йз]з+ е! < сз(з+ Иг,)з+ ез. а) Решите ограничения временного разбиения для случая 1, т.е.
для случая, когда (! < (з. В частности, исключите максимально возможное количество переменных из гз, )з, (з и зз и создайте матрицы П и А, как в алгоритме 11.59. Затем примените лемму Фаркаша к получившимся матричным неравенствам. б) Повторите часть а для случая 2, когда г! = (з и )! < )з. 11.10 Оптимизации локальности Производительность процессора — как в однопроцессорной, так и в многопроцессорной системе — существенно зависит от поведения кэша.
Промахи кэша могут потребовать для обработки десятков тактов, так что большое количество промахов кэша может существенно снизить производительность процессора. 1О4О Глава 11. Оптимизация параллелизма и локальности В контексте многопроцессорной системы с обшей шиной к дальнейшему снижению производительности процессоров могут привести конфликты шины.
Как мы увидим, даже если мы всего лишь хотим повысить локальность в однопроцессорной системе, алгоритм аффинного разбиения для распараллеливания применим и как средство для обнаружения возможных преобразований циклов. В этом разделе будут описаны три методики повышения локальности данных в однопроцессорных и многопроцессорных системах. 1. Повышение временнбй локальности вычисленных результатов путем использования их сразу же после генерации. Это достигается разделением вычислений на независимые части и выполнением всех зависимых операций в пределах части как можно ближе друг к другу. 2.
Сжатие массива (апау сопсгасйоп) снижает размерность массива и количество ячеек памяти, к которым выполняется обращение. Сжатие массива можно применить, только если в каждый момент времени используется только одна ячейка массива. 3. Помимо повышения временнбй локальности вычисленных результатов необходимо оптимизировать и их пространственную локальность, а также как временную, так и пространственную локальность данных, предназначенных только для чтения. Вместо поочередного выполнения каждой части кода ряд частей чередуется таким образом, что повторные использования в разных частях оказываются расположенными ближе друг к другу.
11.10.1 Временная локальность вычисляемых данных Алгоритм аффинного разбиения размещает вместе все зависимые операции; при последовательном выполнении полученных частей повышается временная локальность вычисляемых данных. Вернемся к многосеточному примеру, который рассматривался в разделе 11.7.1. Применение алгоритма 11.43 для распараллеливания кода на рис. 11.23 обнаруживает две степени параллелизма.
Код на рис. 11.24 содержит два внешних цикла, которые последовательно итерируют независимые части. Этот преобразованный код имеет повышенную временную локальность, поскольку вычисляемые результаты используются здесь же, в этой же самой итерации. Таким образом, даже если наша цель заключается в оптимизации для последовательного выполнения, оказывается выгодным использование распараллеливания для поиска связанных операций и размещения их рядом друг с другом. Алгоритм, который используется здесь, подобен алгоритму 11.64, который обнаруживает все уровни параллелизма, начиная с охватывающего внешнего цикла.
Как говорилось в разделе 11.9.9, если на каком-то уровне не удается найти параллелизм, не требующий синхронизации, то алгоритм распараллеливает сильно 1041 11.10, Оптимизации локальности связанные компоненты по отдельности. Такое распараллеливание имеет тенденцию к повышению обмена информацией между процессорами. Таким образом, мы объединяем раздельно распараллеленные сильно связанные компоненты, если они разделяют одни и те же повторные использования.
11.10.2 Сжатие массива Оптимизация сжатия массива предоставляет еще одну иллюстрацию компромисса между памятью и параллельностью, о котором мы говорили в разделе ! 0.2.3 в контексте параллелизма на уровне команд. Так же как применение большего количества регистров обеспечивает более высокий уровень параллелизма на уровне команд, так и использование большего количества памяти повышает параллелизм на уровне циклов. Как показано в многосеточном примере в разделе 11.7.1, преобразование временной скалярной переменной в массив позволяет разным итерациям использовать разные экземпляры временных переменных и выполняться одновременно. И наоборот, прн последовательном выполнении, в каждый момент времени работающем с одним элементом массива, массив можно сжать, заменив его скаляром, и заставить каждую итерацию работать с одной и той же ячейкой памяти.
В преобразованной многосеточной программе на рис. 1!.24 каждая итерация внутреннего цикла производит и потребляет различные элементы массивов АР, АМ, Т и строку массива Р. Если эти массивы не используются вне рассматриваемого фрагмента, итерации могут последовательно использовать одну н ту же память для данных вместо того, чтобы размещать значения в разных элементах и строках массивов. На рис. 11.62 показан результат снижения размерности массивов. Такой код работает быстрее исходного, поскольку он считывает и записывает меньшее количество данных. В частности, в случае, когда массив сводится к скалярной переменной, ее можно назначить регистру и полностью устранить необходимость обращения к памяти. Чем меньше количество используемой памяти, тем меньше доступный параллелизм. Итерации в преобразованном коде на рис.
1!.62 связаны зависимостями данных и больше не могут выполняться параллельно. Для распараллеливания кода между Р процессорами можно расширить каждую скалярную переменную в Р раз и предоставить каждому процессору собственную копию переменной. Таким образом, величина увеличения количества памяти непосредственно связана с количеством используемого параллелизма. Существуют три основных повода для поиска возможностей сжатия массивов.
1. Высокоуровневые языки программирования для научных приложений, такие как Ма!!аЬ и рог!гап 90, поддерживают операции на уровне массивов. Каждое подвыражение операции с массивами приводит к появлению временного массива. Поскольку массивы могут иметь большие размеры, 1042 Глава ! !. Оптимизация параллелизма н локальности гог (5 = 2, 3 <= ~1, 5++) бог (1 = 2, 1 <= 11, 1++) ( АР Т вЂ” 1.0/(1.0 +АР); Р[2) — Т*АР; РИ[1, 2, 7, 1) = Т*1И[1, 2, Э, 3.); Тог ()с=э, )с <= К1-1, )с++) АМ АР; АР Т ...АР -АМ*0[)с-1)...; Р[)с) Т*АР; Р(4[1,)с,з,1) = Т*(Р(4[1,)с,7,1]+РИ[1,)с-1,1,1]).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
