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

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


Рассмотрим теперь возможность построения параллельного алгоритма, который выполнял бы только те вычислительные действия, что и последовательный метод (может быть только в несколько ином порядке) и, как результат, обеспечивал бы получение точно таких же решений исходной вычислительной задачи. Как уже было отмечено выше, в последовательном алгоритме каждое очередное 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).
Этот массив является общим для всех выполняемых потоков, однако синхронизации доступа к элементам не требуется, так как потоки используют всегда разные элементы массива (фронт волны вычислений содержит только по одному узлу строк сетки).

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

chunk = 200; // размер последовательного участка #pragma omp parallel for shared(n,dm,dmax) private(i,d) for ( i=1; i<nx+1; i+=chunk ) { d = 0; for ( j=i; j<i+chunk; j++ ) if ( d < dm[j] ) d = dm[j]; omp_set_lock(dmax_lock); if ( dmax < d ) dmax = d; omp_unset_lock(dmax_lock); } // конец параллельной области



Таблица 11.3. Результаты экспериментов для параллельных вариантов алгоритма Гаусса - Зейделя с волновой схемой расчета (p=4) Размер сеткиПоследовательный метод Гаусса - Зейделя (алгоритм 11.1)Параллельный алгоритм 11.5Параллельный алгоритм 11.6ktktSktS
1002100,062100,300,212100,160,40
2002730,342730,860,402730,590,58
3000,883051,630,543051,530,57
4003183,783182,501,513182,361,60
5003436,003433,531,703434,031,49
6003368,813365,201,693365,341,65
70034412,113448,131,4934410,001,21
80034316,4134312,081,3634312,641,30
90035820,6135814,981,3835815,591,32
100035125,5935118,271,4035119,301,33
2000367106,7536769,081,5536765,721,62
3000370243,00370149,361,63370140,891,72


(k – количество итераций, t – время (сек), S – ускорение)

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

Содержание раздела