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

                                         - 82 -

  for (i = 1; i < N; i++)
   for (j = 1; j < M; j++)                                          (6)
     A[i][j] = A[i-1][j] + A[i][j];

  приведено на рис.21 (окружности соответствуют отдельным операторам
вычисления и присваивания, стрелки - информационным зависимостям).
  Из рис.21 видно, что разбиение пространства итераций по измерению I
приводит к разрыву информационных зависимостей; для измерения J таково-
го не происходит, поэтому возможно применение метода координат с разбие-
нием пространства итераций гиперплоскостями, перпендикулярными оси J (на
рис.21 – пунктир). Эти операции назначаются для выполнения на одном про-
цессоре.
  Для гнезда циклов

  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)
преобразований - таких
преобразований      кода
программы, при которых полностью сохраняется результат ее выполнения при
изменении последовательности действий.