ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ ЦИКЛИЧЕСКИХ УЧАСТКОВ ПРОГРАММ

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

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

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

1. Тип «скалярный ® скалярный». В циклах этого типа не присутствуют массивы от индекса цикла и можно легко пока­зать, что он либо эквивалентен некоторой циклической конст­рукции, либо задает рекурсивное применение некоторой, может быть, достаточно сложной составной операции вида: WHILE P DO x : = f (x). Стандартный прием «извлечения быстродействия» для такого цикла - сдваивание, т.е. следующая замена:

WHILE P DO x : = f (f (x)).

Выигрыш получается за счет того, что композиция ff вы­числяется, как правило, быстрее, чем дважды f.

Например, f есть линейное преобразование: x : = ax + b. Для вычисления двух таких итераций требуется два умножения, два сложения и два обращения к памяти. В то же время итера­ция x: = a(ax + b) + b = a2x + ab + b при совмещении операций a2, ab и предположении, что время умножения больше времени сложения, требует двух умножений, одного сложения и одного обращения к памяти. Этот прием может быть повторен произ­вольное число раз, что в итоге дает известный метод рекурсив­ного сдваивания.

2. Тип «скалярный ® векторный» производит на основе некоторой скалярной информации генерацию некоторого мас­сива, зависящего от параметра цикла i. Пример такого цикла можно получить, модифицировав цикл WHILE P DO x : = f (x) :

WHILE P DO x (i) : = f (x (i - 1)); i = i + 1. Отличие последнего цикла в том, что вычисляется не толь­ко окончательное значение х, но и сохраняются все промежу­точные.

3. Тип «векторный ® скалярный» задает выполнение неко­торых редуцирующих действий над массивом, в результате чего получается скаляр. Простейший пример - «свертывание» мас­сива посредством некоторой ассоциативной операции A:

х = х (1) Е х (2) Е х (3) Е ... Е х (n). Конструкции такого рода хорошо изучены и реализуются параллельно в порядке, максимально близком к полному лога­рифмическому дереву.

4. Тип «векторный ® векторный». Преобразование инфор­мации, задаваемое такими циклами, заключается в переработке элементов одного массива в другой. В качестве примера рас­смотрим упорядочение элементов массива Х путем вычисления позиции p(i) i-го элемента в упорядоченном массиве:

FOR i = 1, n DO, FOR j = 1, n DO,

IF x (j) < x (i) THEN p(i) : = p(i) + 1.

Цикл вычисляет для каждого i число p(i) элементов масси­ва Х, строго меньших x(i). Первоначально массив Р нулевой. В итоге p(i) будет указывать номер элемента, после которого дол­жен стоять x(i). Параллельную версию цикла можно записать так: «

FOR i = 1, n DO PARALLEL p(i) : = X k(x} < x, ).

j=1

Для каждого i одновременно суммируются все результаты сравнений, а вычисление p(i) можно организовать по типу пол­ного логарифмического дерева.

Характерной особенностью всех перечисленных примеров является то, что время реализации цикла было уменьшено с вели­чины порядка n (в последнем случае - даже n2) до величины O (log n). Но никакой даже самый глубокий формальный анализ не по­зволил бы осуществить эти преобразования без обращения «внутрь» тела цикла. Во всех случаях использовались некоторые специфические законы: ассоциативность, дистрибутивность, а в последнем цикле - особое свойство оператора условного перехо­да. Однако, если иметь минимальную информацию о структуре тела цикла и входящих в него операций, преобразование уже мож­но было бы выполнить автоматически. Таким образом, четкой грани между формальным и специальным подходом нет. Она фиксируется, как только фиксируется какая-то гипотеза о дос­тупности информации о теле. Наиболее универсальный случай -это представление тела цикла в виде «черного ящика».

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

Все методы можно условно разделить на три категории.

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

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

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