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

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

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