Вычислительная математика Учебно-практическая задача Пути достижения параллелизма Моделирование и анализ параллельных вычислений Каскадная схема суммирования

Процессы и ресурсы Учебно-практическая задача

Учебно-практическая задача: Решение дифференциальных уравнений в частных производных

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

 // Алгоритм 6.5 omp_lock_t dmax_lock; 
omp_init_lock(dmax_lock); do { dmax = 0; // максимальное изменение значений u 
// нарастание волны (nx – размер волны) for ( nx=1; nx<N+1; nx++ ) { 
dm[nx] = 0; #pragma omp parallel for shared(u,nx,dm) private(i,j,temp,d) 
for ( i=1; i<nx+1; i++ ) { j = nx + 1 – i; temp = u[i][j]; u[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-u[i][j]); 
if ( dm[i] < d ) dm[i] = d; } // конец параллельной области } // затухание 
волны for ( nx=N-1; nx>0; nx-- ) { #pragma omp parallel for shared(u,nx,dm) 
private(i,j,temp,d) for ( i=N-nx+1; i<N+1; i++ ) { j = 2*N - 
nx – I + 1; temp = u[i][j]; u[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-u[i][j]) if ( dm[i] < d ) dm[i] = d; } // конец параллельной 
области } #pragma omp parallel for shared(n,dm,dmax) private(i) for 
( i=1; i<nx+1; i++ ) { omp_set_lock(dmax_lock); if ( dmax < 
dm[i] ) dmax = dm[i]; omp_unset_lock(dmax_lock); } // конец параллельной 
области } while ( dmax > eps ); 

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

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

Существуют два способа оценки пиковой производительности компьютера. Один из них опирается на число команд, выполняемых компьютером в единицу времени. Единицей измерения, как правило, является MIPS (Million Instructions Per Second). Производительность, выраженная в MIPS, говорит о скорости выполнения компьютером своих же инструкций. Но, во-первых, заранее не ясно, в какое количество инструкций отобразится конкретная программа, а, во-вторых, каждая программа обладает своей спецификой, и число команд от программы к программе может меняться очень сильно

Информатика, черчение, математика