Параллельные вычисления. Баканов В.М. - 81 стр.

                                              - 81 -


ловиям (с некоторыми оговорками) соответствует, например, распределение
по процессорам вычисление одной и той же функции в нескольких точках
(при поиске экстремумов функции многих переменных градиентными мето-
дами). Циклическое распределение итераций предполагает выполнение все-
ми процессорами по одной последовательной итерации цикла (для простых
операций в теле цикла размер гранулы может при этом оказаться чересчур
мелким).
  В программах часто встречаются многомерные циклические гнезда, при-
чем каждый цикл такого гнезда может содержать некоторый ресурс паралле-
лизма. Пространство итераций (Lamport L., 1973) гнезда тесно вложенных
циклов называют множество целочисленных векторов, координаты которых
задаются значениями параметров циклов данного гнезда. Задача распаралле-
ливания в этом случае сводится к разбиению этого множества векторов на
выполняющиеся друг за другом последовательно подмножества, однако для
каждого подмножества итерации могут быть выполнены параллельно (внут-
ри подмножества не существует информационных зависимостей).
  Среди методов анализа пространства итераций известны методы гиперп-
лоскостей, координат, параллелепипедов и пирамид (*). При использовании
метода гиперплоскостей пространство итераций размерности n разбивается
на гиперплоскости размерности n − 1 таким образом, что все операции, соот-
ветствующие точкам одной гиперплоскости, могут выполняться параллельно.
Метод координат заключается в том, что пространство итераций фрагмента
разбивается на гиперплоскости, перпендикулярные одной из координатных
осей. Метод параллелепипедов является логическим развитием двух преды-
дущих методов и заключается в разбиении пространства итераций на n-
мерные параллелепипеды, объем которых определяет результирующее уско-
рение программы. При использовании метода пирамид находятся итера-
ции, вырабатывающие значения, которые далее в теле гнезда циклов не ис-
пользуются; каждая такая итерация служит основанием отдельной параллель-
ной ветви, в которую входят и все итерации, информационно влияющие на
выбранную (неприятным эффектом при этом является дублирование ин-
формации в разных ветвях, что может приводить к потере эффективности).
  Известны методы (напр., метод линейного преобразования), являющиеся
более мощными, нежели метод гиперплоскостей и даже метод координат
Лэмпорта, (**).
  Пространство итераций для простого цикла


*
     А.С.Антонов. Введение в параллельные вычисления (методическое пособие). // Изд.
     МГУ им.М.В.Ломоносова, НИВЦ. -М.: 2002, -69 c.
**
     Lamport L. The coordinate method for the parallel execution of DO-loops. // Sagamore com-
     puter conference on parallel processing, 1973.