Возможные способы и особенности параллельной реализации алгоритма

Схематично основную вычислительную часть известного параллельного алгоритма [4, стр.3], реализующего двухшаговую разностную схему продольно-поперечной прогонки (т.е. метода переменных направлений) можно представить следующим образом (циклы, итерации которых заведомо можно выполнять независимо, запишем как dopar):

do n = 0, k

dopar j= 1, N _y – 1 // Начало тайла первого типа

do i= 1, N _x – 1

enddo

do i= 1, N _x – 1

enddo

Enddopar

dopar i= 1, N _x – 1 // Начало тайла второго типа

do j= 1, N _y – 1

enddo

do j= 1, N _y – 1

enddo

Enddopar

enddo(n)

Здесь и – коэффициенты прогонки, которые при подстановке формул (1.8)–(1.10) и (1.11)–(1.13) в (1.14) с учётом неявного направления текущей прогонки, выражаются через следующие функции:

,

(2.1)

(2.2)

(2.3)

(2.4)

Для приведённого псевдокода опущены операции пересылки данных между процессами, а также инициализации начальных и граничных значений с их последующим пересчётом по ходу выполнения алгоритма.

Конечные значения сеточной функции и будут являться приближённым решением исходной задачи (1.1)–(1.3).

Нетрудно заметить, что операциях пересылки между слоями можно использовать не сами значения сеточной функции на новом слое, а заранее вычисленные значения и , что значительно уменьшит объём пересылаемых данных.

В данном алгоритме используется естественный параллелизм, т.е. каждый процесс перед выполнением каждого тайла получает данные от всех других процессов, а после выполнения тайла пересылает данные всем другим процессам.