Теория и практика параллельных вычислений

         

Волновые схемы параллельных вычислений


Рассмотрим теперь возможность построения параллельного алгоритма, который выполнял бы только те вычислительные действия, что и последовательный метод (может быть только в несколько ином порядке) и, как результат, обеспечивал бы получение точно таких же решений исходной вычислительной задачи. Как уже было отмечено выше, в последовательном алгоритме каждое очередное k-е приближение значения ui,j вычисляется по последнему k-му приближению значений ui-1,j и ui,j-1 и предпоследнему (k-1)-му приближению значений ui+1,j и ui,j+1. Таким образом, при требовании совпадения результатов вычислений последовательных и параллельных вычислительных схем в начале каждой итерации метода только одно значение u11 может быть пересчитано (возможности для распараллеливания нет). Но далее после пересчета u11 вычисления могут выполняться уже в двух узлах сетки u12 и u21 (в этих узлах выполняются условия последовательной схемы), затем после пересчета узлов u12 и u21 — в узлах u13, u22 и u31 и т.д. Обобщая сказанное, можно увидеть, что выполнение итерации метода сеток можно разбить на последовательность шагов, на каждом из которых к вычислениям окажутся подготовленными узлы вспомогательной диагонали сетки с номером, определяемым номером этапа – см. рис. 11.8. Получаемая в результате вычислительная схема получила наименование волны или фронта вычислений, а алгоритмы, построенные на ее основе, — методов волновой обработки данных (wavefront или hyperplane methods). Следует отметить, что в нашем случае размер волны (степень возможного параллелизма) динамически изменяется в ходе вычислений – волна нарастает до своего пика, а затем затухает при приближении к правому нижнему узлу сетки.


Рис. 11.8.  Движение фронта волны вычислений

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

Алгоритм 11.5. Параллельный алгоритм, реализующий волновую схему вычислений

Пример 11.5.

(html, txt)

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

Содержание  Назад  Вперед







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий