Параллельные вычисления
 Скачать 1.75 Mb.
|
|
а циклов for (i = 1; i < N; i++) for (j = 1; j < M; j++) (7) A[i][j] = A[i-1][i] + A[i][j-1]; метод координат неприменим, т.к. любое разбиение (и по измерению I и по измерению J) перпендикулярными осям координат плоскостями приводит к разрыву информационных зависимостей. Несмотря на это можно заметить, что существуют удовлетво- ряющие условию i+j=const гиперплоско- сти (пунктир на рис.22, проходящие через не со- держащие информаци- онных зависимостей вер- шины; при этом па- раллельно работающим процессорам следует на- значить вычисления тела цикла для каждой из ги- перплоскостей i+j=const Часто удается добить- ся повышения эффек- тивности распараллели- вания программы при помощи эквивалентных преобразований - таких преобразований кода программы, при которых полностью сохраняется результат ее выполнения при изменении последовательности действий. Рисунок 21 — Пространство итераций для фрагмента (6) - 83 - Первым этапом рабо- ты по распараллелива- нию является выявление зависимостей; второй шаг - распараллелива- ние циклов с использо- ванием результатов первого этапа. Примеры автоматических (выпол- няемых распараллели- вающим компилятором) эквивалентных преобра- зований в применении к циклам приведены ниже в табл.6. Если последователь- ная программа содер- жит два оператора S 1 и S 2 , причем S 1 находится перед S 2 , то говорят, что ме- жду этими двумя операторами существует зависимость по данным, если они считывают или записывают данные в общей области памяти таким образом, что порядок их выполнения нельзя изменять без изменения конечного ре- зультата вычислений. Имеются три основных типа зависимости по данным: • Потоковая зависимость - оператор S 2 потоково зависит от S 1 , если S 2 счи- тывает из ячейки, в которую записывает S 1 (такая зависимость называет- ся истинной). • Антизависимость - оператор S 2 является антизависимым относительно S 1 , если S 2 записывает в ячейку, из которой S 1 считывает. • Зависимость по выходу - оператор S 2 зависит по выходу от S 1 , если опе- ратор S 2 записывает данные в ту же ячейку памяти, что и S 1 Часто просто говорят ‘S 2 зависит от S 1 ’, если между ними существует за- висимость по данным (тип зависимости не важен). Зависимости по данным легко определяется в последовательном коде, содержащем ссылки только на скаляры. Намного труднее определить зависимости в циклах и при ссылках на массивы (что обычно встречается вместе), поскольку ссылки в массивы имеют индексы, а в индексах часто используются параметры циклов, т.е. ин- дексы массива имеют различные значения на разных итерациях цикла. Общая проблема вычисления всех зависимостей по данным в программе неразре- шима из-за синонимичности имен массивов, которая возникает при исполь- зовании указателей или вызовов функций внутри индексных выражений. Да- Рисунок 22 — Пространство итераций для фрагмента (7) - 84 - же если указатели не разрешены (как в Fortran’e) и индексные выражения яв- ляются линейными функциями, проблема является NP-трудной, т.е. эффек- тивного алгоритма решения ее скорее всего не существует. Ниже рассматриваются несколько полезных преобразований для циклов: локализация, расширение скаляра, распределение цикла, слияние циклов, раз- вертка и сжатие, развертка цикла, разделение на полосы, разделение на блоки, перекос цикла, которые помогают выявлять параллельность, устранять зависимости и оптимизировать использование памяти: • Перестановка циклов - внешний и внутренний циклы меняются местами. • Локализация - каждому процессу дается копия переменной. • Расширение скаляра - скаляр заменяется элементом массива. • Распределение цикла - один цикл расщепляется на два отдельных цикла. • Слияние циклов - два цикла объединяются в единый. • Развертка и сжатие - комбинируются перестановка циклов, разделение на полосы и развертка. • Развертка цикла - тело цикла повторяется, благодаря чему выполняется меньше итераций. • Разделение на полосы - итерации одного цикла разделяются на два вло- женных цикла. • Разделение на блоки - область итераций разбивается на прямоугольные блоки. • Перекос цикла - границы цикла изменяются таким образом, чтобы вы- делить параллельность фронта волны. Распределение циклов используется для устранения зависимости в цикле (фак- тически для выявления параллелизма). Если исходный цикл имеет вид (здесь и далее используется нотация языка программирования, равноудаленная и от For- tran’а и от C) for [i=1 to n] { a[i] = … ; … = … + a[i-1]; } Здесь второй оператор тела цикла зависит от результата, вычисленного пер- вым на предыдущей итерации. При условии отсутствия иных зависимостей (кроме указанной) цикл распределяется следующим образом (каждый из двух циклов легко распараллеливается, хотя сами циклы должны выполняться после- довательно): for [i=1 to n] a[i] = … ; - 85 - for [i=1 to n] … = … + a[i-1]; При слиянии циклы, имеющие одинаковые заголовки и независимые тела, объединяются (сливаются) в единый цикл; слияние приводит к уменьшению числа процессоров и их укрупнению (более крупнозернистый параллелизм). Развертка и сжатие приводит к сближению обращений к ячейкам памяти, при этом производительность повышается за счет кэширования. В примере ум- ножения матриц: for [i=1 to n] for [j=1 to n] for [k=1 to n c[i, j] = c[i, j] + a[i, k] * b[k, j]; сначала разворачивается внешний цикл, затем полученные циклы сжима- ются (сливаются) таким образом, чтобы операторы сложения оказались в цикле максимальной вложенности. После развертки внешнего цикла и сжатия выше- расположенного фрагмента получим (считая n четным): for [i=1 to n by 2] // половина всех итераций (только нечетные i) for [j=1 to n] for [k=1 to n] (8) { c[i, j] = c[i, j] + a[i, k] + b[k, j]; c[i+1, j] = c[i+1, j] + a[i, k] + b[k, j]; } Здесь в каждом внешнем цикле вычисляются два скаляра c[i, j] и c[i+1, j] , рас- полагающиеся в смежных ячейках памяти (при условии, что матрицы в ОП хра- нятся по столбцам – что характерно для Fortran’а и отнюдь не для C/C++). А что мешает в каждом внешнем цикле вычислять не 2, а 3,4,5.. скаляров (конечно, если n не делится нацело на это число, понадобится некоторое дополнение алго- ритма)? В случае разделения на полосы цикл делится надвое, причем во внешнем цик- ле перебираются полосы, а внутренний итерирует все элементы данной полосы. Например, для умножения матриц единократное развертывание внешнего цикла равноценно разделению полосы шириной 2 итерации (дополнительные итера- ции производятся по индексу i1 ): for [i=1 to n by 2] // половина всех итераций (только нечетные i) for [i1=i to i+1] // полоса из двух итераций for [j=1 to n] for [k=1 to n] c[i1, j] = c[i1, j] + a[i1, k] + b[k, j]; - 86 - Преобразование развертки и сжатия равноценны разделению на полосы внешнего цикла, перемещению разделенного цикла на место внутреннего и его развертки (цикл максимальной вложенности использует индекс i1 ): for [i=1 to n by 2] // половина всех итераций (только нечетные i) for [j=1 to n] for [k=1 to n] for [i1=1 to i+1] // полоса из двух итераций c[i1, j] = c[i1, j] + a[i1, k] + b[k, j]; После развертки внутреннего цикла (т.е. замены i1 двумя значениями – i и i+1 ) получается программа, равноценная полученной преобразованием развертки и сжатия (8). При разделении на блоки распределение данных в памяти компактируется и, следовательно, повышается эффективность кэширования на МВС с общей памя- тью или размещение данных в распределенной памяти. В качестве примера рас- сматривается фрагмент транспонирования матрицы: for [i=1 to n] for [j=1 to n] b[i, j] = a[j, i]; При условии хранения в памяти массивов по строкам (характерно для C/C++) д о ступ к элементам матрицы b осуществляется с шагом 1 (каждый элемент b размещается рядом с предыдущим вычисленным элементом b в соответствии с внутренним циклом по j ). Однако доступ к элементам матрицы a осуществляется с шагом n (длина всей строки). Т.о. при ссылках на a кэш используется неэф- фективно (в кэш загружается излишне много значений элементов a , из которых реально нужна всего 1/n ). Разбиение матрицы на блоки делит область итераций на прямоугольники (квадраты в частном случае), размер данных в которых не превышают размера кэша. При желании полностью поместить в кэш m ×m (само собой, m (значений матриц a или b ) следует изменить алгоритм транспонирования таким образом: for [i=1 to n by m] // для каждой m-й строки for [j=1 to n by m] // и m-ного столбца… for [i1=i to min(i+m-1, n)] // блок размером m строк for [j1=j to min(j+m-1, n)] // блок размером m столбцов b[i1, j1] = a[j1, i1]; - 87 - Теперь в двух внутренних циклах доступен квадрат из m ×m элементов мат- риц a и b , который полностью помещается в кэш. Преобразование разделения на блоки является комбинацией разделения на полосы и перестановки циклов. Преобразование перекос циклов используется с целью выделения скрытой па- раллельности в основном вдоль волновых фронтов (в этом случае обновления величин в массивах распространяется подобно волне). Типичный пример – ре- шение дифуравнений в частных производных методом Гаусса-Зейделя при 5- точечном шаблоне на равномерной квадратной сетке размером n ×n [3]: Рисунок 23 — Зависимости по данным в методе итераций Гаусса-Зейделя: a) – исход- ное пространство итераций, б) – пространство итераций после сдвига цикла. for [i=1 to n] for [j=1 to n] a[i, j] = 0.25 × (a[i-1, j]) + a[i, j-1] + a[i+1, j] + a[i, j+1]); При перекосе цикла смещаются границы цикла таким образом, чтобы волно- вые фронты устанавливались не по диагонали, а по столбцам (что иллюстриро- вано схемой рис.23). Перекос осуществляется методом прибавления к гранич- ным значениям индекса внутреннего цикла числа, кратного величине индекса внешнего цикла, затем в теле внутреннего цикла из значения индекса это число вычитается. Образующий кратное сомножитель называется сомножителем пе- рекоса. Преобразованный т.о. вышеприведенный фрагмент при равном 1 со- множителе перекоса приведен ниже: for [i=1 to n] for [j=i+1 to i+n] // прибавить i к имеющимся границам (9) a[i, j-i] = 0.25 × (a[i-1, j-i]) + a[i, j-1-i] + a[i+1, j-i] + a[i, j+1-i]); Перекос цикла позволил выявить параллельность, ибо после преобразований зависимостей в каждом столбце области итераций больше нет, однако зависи- мости остались во внешнем цикле. Из фрагмента (9) видно, что границы внутреннего цикла зависят от значений индекса внешнего. Однако границы исходных циклов независимы, поэтому вы- - 88 - полнить перестановку циклов возможно. После перестановки циклов получаем для общего случая ( Li, Ui – нижняя и верхняя границы исходного внешнего цик- ла, Lj и Uj – то же для внутреннего цикла, k – сомножитель перекоса): for [j = (k ×LI + Lj) to (k×Ui + Uj)] for [i = max(Li, ceil((j - Uj) / k)) to min(Ui, ceil(j - Lj) / k))] … Конкретное применение этого преобразования для метода Гаусса-Зейделя приводит к такому коду: for [j=2 to n+n] for [i=max(1, j-n) to min(n, j-1)] a[i, j-i] = 0.25 × (a[i-1, j-i]) + a[i, j-1-i] + a[i+1, j-i] + a[i, j+1-i]); После этого внутренний цикл несложно распараллелить, напр., путем созда- ния процессов для каждой итерации внешнего цикла. Несмотря на наличие аппарата выявления информационных зависимостей в циклах, претендующий на опыт распараллеливания алгоритмов программист должен приучаться видеть параллелизм в простых конструкциях, например for (i = 1; i < N; i++) { A[i] = A[i] + B[i]; (8) C[i] = C[i-1] + B[i]; } В приведенном фрагменте существует зависимость по информации между i- той и (i-1)-й итерациями в операторе C[i] = C[i-1] + B[i] , поэтому просто распре- делить итерации между процессорами нельзя. Однако фрагмент (8) легко разбить (операция распределение циклов) на два одномерных цикла (т.к. опе- раторы A[i] = A[i] + B[i] и C[i] = C[i-1] + B[i] информационно независимы), причем первый эффективно распараллеливается: for (i = 1; i < N; i++) A[i] = A[i] + B[i]; for (i = 1; i < N; i++) C[i] = C[i-1] + B[i]; 3.3 Эквивалентные преобразования алгоритмов, избыточность вычислений и обменов данными Эквивалентным преобразованием (ЭкП) алгоритма является замена данно- го алгоритма (или его части) на алгоритм, гарантирующий получение такого же конечного результата на всех наборах входных данных в точной арифме- - 89 - тике (учет ограниченной машинной точности представления данных может накладывать ограничения на ЭкП). Одним из ЭкП, достаточно часто используемое в распараллеливающих компиляторах, является редукция высоты дерева. Один из методов реализа- ции такого преобразования – использование ассоциативных, коммутативных и дистрибутивных свойств арифметики, таким путем компиляторы могут об- наруживать неявный параллелизм в алгебраических выражениях и генериро- вать объектный (а затем и исполняемый) код для многопроцессорных систем с указанием операций, которые можно выполнять одновременно. На рис.24 показано (в виде графа алгоритма), как от- транслировал бы алгебраиче- ское выражение обычный компилятор (слева) и как оно может быть обработано рас- параллеливающим компиля- тором (справа); при этом не принимается во внимание возможное изменение точно- сти вычислений [2]. Как вид- но, во многих случаях воз- можно уменьшить число яру- сов (редуцировать высоту де- рева) путем выявления (ранее скрытого) параллелизма в вы- числениях. Не следует забывать, что подобная оптимизация про- грамм совсем не бесплатна – необходимы увеличенные за- траты времени и вычисли- тельных ресурсов в период анализа/компиляции. Очень эффективны эквива- лентные преобразования при оптимизации циклов (гнезд циклов). В табл.6 приведены некото- рые преобразования циклов, автоматически осуществляе- мые распараллеливающим Fortran-компилятором Рисунок 24 — Уменьшение высоты дерева: a) - за счет ассоциативности, б) - за счет коммутатив- ности и в) - за счет дистрибутивности (слева – обычный компилятор, справа - распараллели- вающий) - 90 - Lahey/Fujitsu Fortran’95 (LF95, http://www.lahey.com) для Linux (LF95’Pro включает возможность автоматической и OpenMP-параллелизации). Распа- раллеливающие компиляторы постоянно совершенствуются и в настоящее время пригодны для создания эффективных параллельных программ с разде- ляемыми переменными; особенно это касается научных программ, содержа- щих много циклов и длительных вычислений. В табл.6 приведены некоторые преобразования циклов, автоматически осуществляемые распараллеливающим Fortran-компилятором Lahey/Fujitsu Fortran’95 (LF95, http://www.lahey.com ) для Linux (LF95’Pro включает возмож- ность автоматической и OpenMP-параллелизации). Распараллеливающие компиляторы постоянно совершенствуются и в настоящее время пригодны для создания эффективных параллельных программ с разделяемыми пере- менными; особенно это касается научных программ, содержащих много цик- лов и длительных вычислений. Таблица 6 — Операции над массивами и автоматическая параллелиза- ция (на примере Fortran-базированной распараллеливающей систе- мы LF95’Pro). № № Преобразо- вание До преобразо- вания После преобразо- вания После распараллеливания 1 Сечения (slic- ing) циклов do i=1, 50000 a(i)=b(i)+c(i) end do Процессор 1: do i1=1,25000 a(i1)=b(i1)+c(i1) end do Процессор 2: do i2=25001,50000 a(i2)=b(i2)+c(i2) end do 2 Перестановка вложенных (nested) циклов do i= 2,10000 do j=1,10 a(i,j)=a(i-1,j) +b(i,j) end do end do do j=1,10 do i=2,10000 a(i,j)=a(i-1,j) +b(i,j) end do end do Процессор 1: do j=1,5 do i=210000 a(i,j)=a(i-1,j) +b(i,j) end do end do Процессор 2: do j=6,10 do i=2,10000 a(i,j)=a(i-1,j) +b(i,j) end do end do 3 Слияние (fu- sion) циклов do i=1,10000 a(i)=b(i)+c(i) end do do i=1,10000 d(i)=e(i)+f(i) end do do i=1,10000 a(i)=b(i)+c(i) d(i)=e(i)+f(i) end do Процессор 1: do i=1,5000 a(i)= b(i)+c(i) d(i)=e(i)+f(i) end do Процессор 2: do i=5001,0000 a(i)=b(i)+c(i) d(i)=e(i)+f(i) end do 4 Приведение (reduction) циклов. Приведение циклов может sum=0 do i=1,10000 sum=sum+a(i) end do Процессор 1: sum1=0 do i=1,5000 sum1=sum1+a(i) end do Процессор 2: sum2=0 do i=5001,0000 sum2=sum2+a(i) end do - 91 - быть причиной изменений в результатах (в пределах оши- бок округле- ния). Далее частичные суммы складываются: sum=sum1+ sum2 Во многих случаях приведенные (лежащие, впрочем, на поверхности) пре- образования помогают и разработчику при создании новых программ. Одна- ко перед реальным программированием в любом случае полезно обдумать последовательность вычислений (алгоритмизацию). Классический пример – параллельная сортировка (по аналогии с лежащим на поверхности распарал- леливанием алгоритма суммирования элементов массива складывается убеж- дение в возможности эффективного крупноблочного распараллеливания ме- тодом сортировки на каждом процессоре части общего массива; однако по- нимание проблем, связанных с пересечением частично отсортированных множеств приходит обычно позднее); последовательные и мелкозернистые параллельные алгоритмы сортировки описаны, напр., в работе [3]. Распараллеливающие компиляторы хорош |