Теория и практика параллельных вычислений
Исключение неоднозначности вычислений
Подход, рассмотренный в п. 11.2.4, уменьшает эффект состязания потоков, но не гарантирует единственности решения при повторении вычислений. Для достижения однозначности необходимо использование дополнительных вычислительных схем.
Возможный и широко применяемый в практике расчетов способ состоит в разделении места хранения результатов вычислений на предыдущей и текущей итерациях метода сеток. Схема такого подхода может быть представлена в следующем общем виде:
Алгоритм 11.4. Параллельная реализация сеточного метода Гаусса – Якоби
// Алгоритм 11.4 omp_lock_t dmax_lock; omp_init_lock(dmax_lock); do { dmax = 0; // максимальное изменение значений u #pragma omp parallel for shared(u,un,N,dmax) private(i,temp,d,dm) for ( i=1; i<N+1; i++ ) { dm = 0; for ( j=1; j<N+1; j++ ) { temp = u[i][j]; un[i][j] = 0.25*(u[i-1][j]+u[i+1][j]+ u[i][j-1]+u[i][j+1]–h*h*f[i][j]); d = fabs(temp-un[i][j]) if ( dm < d ) dm = d; } omp_set_lock(dmax_lock); if ( dmax < dm ) dmax = dm; omp_unset_lock(dmax_lock); } } // конец параллельной области for ( i=1; i<N+1; i++ ) // обновление данных for ( j=1; j<N+1; j++ ) u[i][j] = un[i][j]; } while ( dmax > eps );
Как следует из приведенного алгоритма, результаты предыдущей итерации запоминаются в массиве u, новые вычисления значения запоминаются в дополнительном массиве un. Как результат, независимо от порядка выполнения вычислений для проведения расчетов всегда используются значения величин uij от предыдущей итерации метода. Такая схема реализации сеточных алгоритмов обычно именуется методом Гаусса – Якоби. Этот метод гарантирует однозначность результатов независимо от способа распараллеливания, но требует использования большого дополнительного объема памяти и обладает меньшей (по сравнению с алгоритмом Гаусса – Зейделя) скоростью сходимости. Результаты расчетов с последовательным и параллельным вариантами метода приведены в табл. 11.2.
| 100 | 5257 | 1,39 | 5257 | 0,73 | 1,90 |
| 200 | 23067 | 23,84 | 23067 | 11,00 | 2,17 |
| 300 | 26961 | 226,23 | 26961 | 29,00 | 7,80 |
| 400 | 34377 | 562,94 | 34377 | 66,25 | 8,50 |
| 500 | 56941 | 1330,39 | 56941 | 191,95 | 6,93 |
| 600 | 114342 | 3815,36 | 114342 | 2247,95 | 1,70 |
| 700 | 64433 | 2927,88 | 64433 | 1699,19 | 1,72 |
| 800 | 87099 | 5467,64 | 87099 | 2751,73 | 1,99 |
| 900 | 286188 | 22759,36 | 286188 | 11776,09 | 1,93 |
| 1000 | 152657 | 14258,38 | 152657 | 7397,60 | 1,93 |
| 2000 | 337809 | 134140,64 | 337809 | 70312,45 | 1,91 |
| 3000 | 655210 | 247726,69 | 655210 | 129752,13 | 1,91 |
(k – количество итераций, t – время (сек), S – ускорение)
Рис. . Схема чередования обработки четных и нечетных строк
Иной возможный подход для устранения взаимозависимости параллельных потоков состоит в применении схемы чередования обработки четных и нечетных строк (red/black row alternation scheme), когда выполнение итерации метода сеток подразделяется на два последовательных этапа, на первом из которых обрабатываются строки только с четными номерами, а затем на втором этапе — строки с нечетными номерами (см. рис. 11.7). Данная схема может быть обобщена на применение одновременно и к строкам, и к столбцам (шахматное разбиение) области расчетов.
Рассмотренная схема чередования строк не требует, по сравнению с методом Якоби, какой-либо дополнительной памяти и обеспечивает однозначность решения при многократных запусках программы. Но следует заметить, что оба рассмотренных в данном пункте подхода могут получать результаты, которые не совпадут с решением задачи Дирихле, найденным при помощи последовательного алгоритма. Кроме того, эти вычислительные схемы имеют меньшую область и худшую скорость сходимости, чем исходный вариант метода Гаусса – Зейделя.
