Теория и практика параллельных вычислений
Проблема синхронизации параллельных вычислений
Первый вариант параллельного алгоритма для метода сеток может быть получен, если разрешить произвольный порядок пересчета значений uij. Программа для данного способа вычислений может быть представлена в следующем виде:
Алгоритм 11.2. Первый вариант параллельного алгоритма Гаусса – Зейделя
// Алгоритм 11.2 omp_lock_t dmax_lock; omp_init_lock (dmax_lock); do { dmax = 0; // максимальное изменение значений u #pragma omp parallel for shared(u,N,dmax) private(i,temp,d) for ( i=1; i<N+1; i++ ) { #pragma omp parallel for shared(u,N,dmax) private(j,temp,d) for ( j=1; j<N+1; j++ ) { 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]) omp_set_lock(dmax_lock); if ( dmax < d ) dmax = d; omp_unset_lock(dmax_lock); } // конец вложенной параллельной области } // конец внешней параллельной области } while ( dmax > eps );
Следует отметить, что программа получена из исходного последовательного кода путем добавления директив и операторов обращения к функциям библиотеки OpenMP (эти дополнительные строки в программе выделены темным шрифтом).
Рис. 11.3. Параллельные области, создаваемые директивами OpenMP
Как следует из текста программы, параллельные области в данном примере задаются директивой parallel for, являются вложенными и включают в свой состав операторы цикла for. Компилятор, поддерживающий технологию OpenMP, разделяет выполнение итераций цикла между несколькими потоками программы, количество которых обычно совпадает с числом процессоров в вычислительной системе. Параметры директивы shared и private определяют доступность данных в потоках программы – переменные, описанные как shared, являются общими для потоков, для переменных с описанием private создаются отдельные копии для каждого потока, которые могут использоваться в потоках независимо друг от друга.
Наличие общих данных обеспечивает возможность взаимодействия потоков. В этом плане разделяемые переменные могут рассматриваться как общие ресурсы потоков, и, как результат, их применение должно выполняться с соблюдением правил взаимоисключения (изменение каким-либо потоком значений общих переменных должно приводить к блокировке доступа к модифицируемым данным для всех остальных потоков).
В данном примере таким разделяемым ресурсом является величина dmax, доступ потоков к которой регулируется специальной служебной переменной (замком) dmax_lock и функциями omp_set_lock (разрешение или блокировка доступа) и omp_unset_lock (снятие запрета на доступ). Подобная организация программы гарантирует единственность доступа потоков для изменения разделяемых данных. Участки программного кода (блоки между обращениями к функциям omp_set_lock и omp_unset_lock), для которых обеспечивается взаимоисключение, обычно именуются критическими секциями.
Результаты вычислительных экспериментов приведены в табл. 11.1
(здесь и далее для параллельных программ, разработанных с использованием технологии OpenMP, использовался четырехпроцессорный сервер кластера Нижегородского университета с процессорами Pentium III, 700 Mhz, 512 RAM).
Оценим полученный результат. Разработанный параллельный алгоритм является корректным, т.е. обеспечивающим решение поставленной задачи. Использованный при разработке подход обеспечивает достижение практически максимально возможного параллелизма – для выполнения программы может быть задействовано вплоть до N2 процессоров. Тем не менее результат не может быть признан удовлетворительным: программа будет работать медленно и вместо ускорения мы получим замедление вычислений. Основная причина такого положения дел – чрезмерно высокая синхронизация параллельных участков программы. В нашем примере каждый параллельный поток после усреднения значений uij должен проверить (и возможно, изменить) значение величины dmax. Разрешение на использование переменной может получить только один поток – все остальные потоки должны быть блокированы. После освобождения общей переменной управление может получить следующий поток и т.д. В результате необходимости синхронизации доступа многопотоковая параллельная программа превращается фактически в последовательно выполняемый код, причем менее эффективный, чем исходный последовательный вариант, т.к. организация синхронизации приводит к дополнительным вычислительным затратам – см.
рис. 11.4. Следует обратить внимание, что, несмотря на идеальное распределение вычислительной нагрузки между процессорами, для приведенного на рис. 11.4 соотношения параллельных и последовательных вычислений, в каждый текущий момент времени (после момента первой синхронизации) только не более двух процессоров одновременно выполняют действия, связанные с решением задачи. Подобный эффект вырождения параллелизма из-за интенсивной синхронизации параллельных участков программы обычно именуется сериализацией (serialization).
| 100 | 210 | 0,06 | 210 | 1,97 | 0,03 | 210 | 0,03 | 2,03 |
| 200 | 273 | 0,34 | 273 | 11,22 | 0,03 | 273 | 0,14 | 2,43 |
| 300 | 305 | 0,88 | 305 | 29,09 | 0,03 | 305 | 0,36 | 2,43 |
| 400 | 318 | 3,78 | 318 | 54,20 | 0,07 | 318 | 0,64 | 5,90 |
| 500 | 343 | 6,00 | 343 | 85,84 | 0,07 | 343 | 1,06 | 5,64 |
| 600 | 336 | 8,81 | 336 | 126,38 | 0,07 | 336 | 1,50 | 5,88 |
| 700 | 344 | 12,11 | 344 | 178,30 | 0,07 | 344 | 2,42 | 5,00 |
| 800 | 343 | 16,41 | 343 | 234,70 | 0,07 | 343 | 8,08 | 2,03 |
| 900 | 358 | 20,61 | 358 | 295,03 | 0,07 | 358 | 11,03 | 1,87 |
| 1000 | 351 | 25,59 | 351 | 366,16 | 0,07 | 351 | 13,69 | 1,87 |
| 2000 | 367 | 106,75 | 367 | 1585,84 | 0,07 | 367 | 56,63 | 1,89 |
| 3000 | 370 | 243,00 | 370 | 3598,53 | 0,07 | 370 | 128,66 | 1,89 |
(k-количество итераций, t-время (сек), S-ускорение)
Рис. 11.4. Пример возможной схемы выполнения параллельных потоков при наличии синхронизации (взаимоисключения)
Как показывают выполненные рассуждения, путь для достижения эффективности параллельных вычислений лежит в уменьшении необходимых моментов синхронизации параллельных участков программы. Так, в нашем примере мы можем ограничиться распараллеливанием только одного внешнего цикла for. Кроме того, для снижения количества возможных блокировок применим для оценки максимальной погрешности многоуровневую схему расчета: пусть параллельно выполняемый поток первоначально формирует локальную оценку погрешности dm только для своих обрабатываемых данных (одной или нескольких строк сетки), затем при завершении вычислений поток сравнивает свою оценку dm с общей оценкой погрешности dmax.
Новый вариант программы решения задачи Дирихле имеет вид:
Алгоритм 11.3. Второй вариант параллельного алгоритма Гаусса – Зейделя
// Алгоритм 11.3 omp_lock_t dmax_lock; omp_init_lock(dmax_lock); do { dmax = 0; // максимальное изменение значений u #pragma omp parallel for shared(u,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]; 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 < d ) dm = d; } omp_set_lock(dmax_lock); if ( dmax < dm ) dmax = dm; omp_unset_lock(dmax_lock); } } // конец параллельной области } while ( dmax > eps );
Как результат выполненного изменения схемы вычислений, количество обращений к общей переменной dmax уменьшается с N2 до N раз, что должно приводить к существенному снижению затрат на синхронизацию потоков и уменьшению проявления эффекта сериализации вычислений. Результаты экспериментов с данным вариантом параллельного алгоритма, приведенные в табл. 11.1, показывают существенное изменение ситуации – ускорение в ряде экспериментов оказывается даже большим, чем используемое количество процессоров (такой эффект сверхлинейного ускорения достигается за счет наличия у каждого из процессоров вычислительного сервера своей быстрой кэш-памяти). Следует также обратить внимание, что улучшение показателей параллельного алгоритма достигнуто при снижении максимально возможного параллелизма (для выполнения программы может использоваться не более N процессоров).
