Использование параллелизма

Предположим теперь, что мы научились каким-то образом строить и исследо­вать информационную историю выполнения программы. Выделив в ней мно­жества информационно независимых операций, приходим к вопросу: каким же образом распределять эти множества между процессорами или другими обра­батывающими устройствами?

Достаточно очевидным способом будет следующий. Пометим в информацион­ной истории те операции, которые зависят только от внешних данных програм­мы и скажем, что такие операции принадлежат к первому ярусу информацион­ной истории. На второй ярус поместим операции, зависящие только от опера­ций первого яруса и внешних данных и так далее. Распределив таким образом операции информационной истории, получаем ее вид, называемый ярусно-параллелъной формой программы. Количество ярусов ярусно-параллельной формы называется длиной критического пути. По построению операции, по­павшие на один ярус, не могут состоять в отношении информационной зависи­мости, а значит, могут быть выполнены одновременно. Таким образом, процесс получения параллельной программы может быть следующим: сначала распре­деляем между процессорами операции первого яруса, после из завершения -операции второго яруса и т.д. Поскольку любая операция n-го яруса зависит хо­тя бы от одной операции (п-1)-го яруса, то ее нельзя начать выполнять раньше, чем завершится выполнение операций предыдущего яруса, а значит, ярусно-параллельная форма представляет собой в определенном смысле максимально параллельную реализацию программы. При этом длина критического пути ха­рактеризует количество параллельных шагов, необходимых для ее выполнения.

Однако ярусно-параллельная форма почти никогда не используется для практи­ческого распараллеливания программ. Причиной этого является то, что описан­ный способ распараллеливания плохо согласован как с конструкциями реаль­ных языков программирования, так и с архитектурными особенностями совре­менных компьютеров. Чтобы убедиться в этом, можете попробовать сконст­руировать таким способом параллельную реализацию практически любого ал­горитма и оценить как сложность написания такой программы, так и количест­во необходимых коммуникаций между процессорами.

В реальности гораздо чаще используются другие способы распараллеливания, использующие характерные особенности наиболее распространенных языков программирования. Так, самым простым вариантом распределения работ меж­ду процессорами является примерно следующая конструкция (крупноблочное распараллеливание):

if (MyProc = 0) {/* операции, выполняемые 0-ым процессором */}

if (MyProc = K) {/* операции, выполняемые K-ым процессором */}

При этом предполагается, что каждый процессор каким-то образом может по­лучить уникальный номер, присвоить его переменной MyProc и использовать в дальнейшем для получения участка кода для независимого исполнения. Таким образом, в приведенном примере операции в первых фигурных скобках будут выполнены только процессором с номером 0, операции во вторых фигурных скобках - процессором с номером K и т.д. При этом, естественно, необходимо, чтобы одновременно разные процессоры могли выполнять только блоки ин­формационно независимых операций, что может потребовать операций син­хронизации процессоров, а также при необходимости нужно обеспечивать об­мен данными между процессорами.

Однако далеко не всегда удается выделить в программе достаточно большое число блоков независимых операций, а значит, при значительном числе про­цессоров в используемом компьютере, часть из них будет простаивать. Поэто­му наряду с предыдущим способом используют также более низкоуровневое распараллеливание. Как показывает практика, наибольший ресурс параллелиз­ма в программах сосредоточен в циклах. Поэтому наиболее распространенным способом распараллеливания является то или иное распределение итераций циклов. Если между итерациями некоторого цикла нет информационных зави­симостей, то их можно тем или иным способом раздать разным процессорам для одновременного исполнения. Условно это может быть выражено примерно следующей конструкцией:

for (i = 0; i < N;

{

if (i ~ MyProc)

{

/* операции i-й итерации для выполнения процессором MyProc */

}

}

Здесь конструкция i ~ MyProc применена для того, чтобы указать, что номер итерации i каким-то образом соотносится с номером процессора MyProc. Кон­кретный способ задания этого соотношения определяет то, какие итерации цикла на какие процессоры будут распределяться. В принципе, ничто не меша­ет, например, раздать всем процессорам по одной итерации, а все остальные итерации выполнить каким-то одним процессором. Однако очевидно, что в по­давляющем числе случаев такое распределение неэффективно, поскольку все процессоры, кроме одного, выполнив свою итерацию, будут, скорее всего, про­стаивать. Таким образом, одним из требований к распределению итераций (как, впрочем, и к процессу распараллеливания вообще) является по возможности равномерная загрузка процессоров. Наиболее распространенные способы рас­пределения итераций циклов в той или иной степени удовлетворяют этому тре­бованию.

Блочное распределение итераций предполагает, что распределение итераций цикла по процессорам ведется блоками по несколько последовательных итера­ций. В простейшем случае количество итераций цикла n делится на число про­цессоров p, результат округляется до ближайшего целого сверху и число Tn/p1 определяет количество итераций в блоке. При этом почти все процессоры по­лучают одинаковое количество итераций, однако один или несколько послед­них процессоров могут простаивать. Выбор меньшего размера блока может уменьшить этот дисбаланс, однако при этом часть итераций останется нерас­пределенной. Если нераспределенные итерации снова начать распределять та­кими же блоками, начиная с первого процессора, то получим блочно-циклическое распределение итераций. Если уменьшать количество итераций дальше, то дойдем до распределения по одной итерации, которое называется циклическим распределением. Циклическое распределение позволяет миними­зировать дисбаланс в загрузке процессоров, возникавший при блочных распре­делениях.

Рассмотрим небольшой пример. Пусть требуется распределить по процессорам итерации следующего цикла:

for (i = 0; i < N; i++)

a[i] = a[i] + b[i];

Пусть в целевом компьютере имеется P процессоров с номерами 0...P-1. Тогда блочное распределение итераций этого цикла можно записать следующим об­разом:

k = (N-1)/P + 1; /* размер блока итераций */

ibeg = MyProc * k; /* начало блока итераций процессора MyProc */

iend = (MyProc + 1) * k - 1; /* конец блока итераций процессора MyProc */

if (ibeg >= N) iend = ibeg - 1; /* если процессору не досталось итераций */

else if (iend >= N) iend = N - 1; /* если процессору досталось меньше итераций */

for (i = ibeg; i <= iend; i++)

a[i] = a[i] + b[i];

Циклическое распределение итераций того же цикла можно записать так:

for (i = MyProc; i < N; i+=P)

a[i] = a[i] + b[i];

Нужно заметить, что все соображения о распределении итераций циклов с це­лью достижения равномерности загрузки процессоров имеют смысл только в предположении, что распределяемые итерации приблизительно равноценны по времени исполнения. Во многих реальных случаях (например, при решении матричных задач с треугольной матрицей) это может быть не так, а значит, мо­гут потребоваться совершенно другие способы распределения.

Однако только равномерной загрузки процессоров обычно недостаточно для получения эффективной параллельной программы. Только в крайне редких случаях программа не сдержит информационных зависимостей вообще. Если же есть информационная зависимость между операциями, которые при вы­бранной схеме распределения попадают на разные процессоры, то потребуется пересылка данных. Обычно пересылки требуют достаточно большого времени для своего осуществления, поэтому другой важной целью при распараллелива­нии является минимизация количества и объема необходимых пересылок дан­ных. Так, например, при наличии информационных зависимостей между i-й и (i+D-й итерациями некоторого цикла блочное распределение итераций может оказаться эффективнее циклического, потому что при блочном распределении соседние итерации попадают на один процессор, а значит, потребуется меньшее количество пересылок, чем при циклическом распределении.

До сих пор говорилось о распределении итераций одномерных циклов, однако в программах часто встречаются многомерные циклические гнезда, причем каж­дый цикл такого гнезда может содержать некоторый ресурс параллелизма. Для его использования производят анализ и разбиение пространства итераций ис­следуемого фрагмента. Пространством итераций гнезда тесновложенных цик­лов называют множество целочисленных векторов I, координаты которых за­даются значениями параметров циклов данного гнезда. Задача распараллелива­ния при этом сводится к разбиению множества векторов I на подмножества, которые выполняются последовательно друг за другом, но в рамках каждого такого подмножества итерации могут быть выполнены одновременно и незави­симо.

Среди методов анализа пространства итераций можно выделить несколько наи­более известных: методы гиперплоскостей, координат, параллелепипедов и пи­рамид.

Метод гиперплоскостей заключается в том, что пространство итераций раз­мерности n разбивается на гиперплоскости размерности n-1 так, что все опера­ции, соответствующие точкам одной гиперплоскости, могут выполняться одно­временно и асинхронно. Метод координат заключается в том, что пространст­во итераций фрагмента разбивается на гиперплоскости, ортогональные одной из координатных осей. Метод параллелепипедов является логическим развити­ем двух предыдущих методов и заключается в разбиении пространства итера­ций на n-мерные параллелепипеды, объем которых определяет результирующее ускорение программы. В методе пирамид выбираются итерации, вырабаты­вающие значения, которые далее в теле гнезда циклов не используются. Каждая такая итерация служит основанием отдельной параллельной ветви, в которую также входят все итерации, влияющие информационно на выбранную. При этом зачастую информация в разных ветвях дублируется, что может привести к потере эффективности.

Рассмотрим небольшой пример:

for (i = 1; i < N; i++)

for (j = 1; j < M;j++ )

a[i,j] = a[i-1,j]+a[i,j];

Пространство итераций данного фрагмента можно изобразить следующим образом:

На этом рисунке кружки соответствуют отдельным срабатываниям оператора присваивания, а стрелки показывают информационные зависимости. Сразу видно, что разбиение пространства итераций по измерению I приведет к разры­ву информационных зависимостей. Однако информационных зависимостей по измерению J нет, поэтому возможно применение метода координат с разбиени­ем пространства итераций гиперплоскостями, ортогональными оси J, например, как показано на рисунке пунктирными линиями. Затем операции, попавшие в одну группу, распределяются для выполнения на один процессор целевого компьютера.

Немного усложним пример:

for (i = 1; i < N; i++)

for (j = 1; j < M; j++)

a[i,j] = a[i-1,j] + a[i,j-1];

Пространство итераций данного фрагмента можно изобразить следующим об­разом:

Очевидно, что метод координат в данном случае неприменим, потому что лю­бое разбиение как по измерению I, так и по измерению J приведет к разрыву информационных зависимостей. Однако на рисунке пунктирными линиями по­казаны гиперплоскости I + J = const, которые содержат вершины, между ко­торыми нет информационных зависимостей. Это означает возможность приме­нения метода гиперплоскостей, при котором осуществляется перебор гиперп­лоскостей I + J = const, и для каждой из них соответствующие операции рас­пределяются между процессорами целевого компьютера.

Если переходить от распараллеливания отдельных циклических конструкций к распараллеливанию целой программы, то может оказаться невыгодным исполь­зовать весь найденный ресурс параллелизма (в особенности, на компьютерах с распределенной памятью), поскольку потребуется большое количество пере­распределений данных между выполнением циклов.

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

Приведем один небольшой пример. Допустим, что в программе содержится та­кой цикл:

for (i = 1; i < N; i++)

{

a[i] = a[i] + b[i];

c[i] = c[i-1] + b[i];

}

В данном цикле есть информационные зависимости между срабатываниями второго оператора из тела цикла на i-й и (i-D-й итерациях. Поэтому нельзя просто раздать итерации исходного цикла для выполнения различным процессорам. Однако, достаточно очевидно, что этот цикл можно разбить на два, пер­вый из которых станет параллельным:

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];

В некоторых случаях и эквивалентные преобразования бессильны помочь в распараллеливании программы, но допустимы другие методы при предположении, что можно пренебречь ошибками округления. Например, пусть нужно произвести суммирование элементов массива:

for (i = 0, s = 0; i < N; i++)

s+=a[i];

Если подойти к этому циклу формально, то распараллелить его не получится, так как между итерациями цикла существуют информационные зависимости. Однако, если ошибками округления, вызванными разным порядком суммиро­вания элементов массива a, допустимо пренебречь, то данный фрагмент можно распараллелить при помощи широко известной схемы сдваивания: на первом шаге первый процессор суммирует элементы a[0] и а[1], второй процессор суммирует элементы а[2] и а[3] и т.д., на следующем шаге попарно суммиру­ются эти частичные суммы и так до получения окончательного результата. Ес­ли имеется N/2 процессоров, то весь алгоритм суммирования выполняется за log₂N параллельных шагов.