Файл: 12. Параллельные методы решения дифференциальных уравнений в частных производных.pdf

12 600 336 8,81 336 5,20 1,69 336 5,34 1,65 700 344 12,11 344 8,13 1,49 344 10,00 1,21 800 343 16,41 343 12,08 1,36 343 12,64 1,30 900 358 20,61 358 14,98 1,38 358 15,59 1,32 1000 351 25,59 351 18,27 1,40 351 19,30 1,33 2000 367 106,75 367 69,08 1,55 367 65,72 1,62 3000 370 243,00 370 149,36 1,63 370 140,89 1,72
(k – количество итераций, T – время в сек., S – ускорение)
Рис. 12.8.
Движение фронта волны вычислений
Возможная схема параллельного метода, основанного на эффекте волны вычислений, может быть представлена в следующей форме:
//Алгоритм 12.5
// Параллельный метод Гаусса-Зейделя (волновая схема) omp_lock_t dmax_lock; omp_init_lock(dmax_lock); do { dmax = 0; // максимальное изменение значений u
// нарастание волны (nx – размер волны)
for ( nx=1; nx
dm[nx] = 0;
#pragma omp parallel for shared(u,nx,dm) \
private(i,j,temp,d)
for ( i=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
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
omp_set_lock(dmax_lock);
if ( dmax < dm[i] ) dmax = dm[i];
omp_unset_lock(dmax_lock);
} // конец параллельной области
} while ( dmax > eps );
Алгоритм 12.5.
Параллельный алгоритм, реализующий волновую схему вычислений

13

14
При разработке алгоритма, реализующего волновую схему вычислений, оценку погрешности решения можно осуществлять для каждой строки в отдельности (массив значений dm). Этот массив является общим для всех выполняемых потоков, однако, синхронизации доступа к элементам не требуется, так как потоки используют всегда разные элементы массива (фронт волны вычислений содержит только по одному узлу строк сетки).
После обработки всех элементов волны в составе массива dm находится максимальная погрешность выполненной итерации вычислений. Однако именно эта последняя часть расчетов может оказаться наиболее неэффективной из-за высоких дополнительных затрат на синхронизацию. Улучшение ситуации, как и ранее, может быть достигнуто за счет увеличения размера последовательных участков и сокращения, тем самым, количества необходимых взаимодействий параллельных участков вычислений.
Возможный вариант реализации такого подхода может состоять в следующем:
chunk = 200; // размер последовательного участка
#pragma omp parallel for shared(n,dm,dmax) \
private(i,d)
for ( i=1; i
d = 0;
for ( j=i; j
if ( d < dm[j] ) d = dm[j];
omp_set_lock(dmax_lock);
if ( dmax < d ) dmax = d;
omp_unset_lock(dmax_lock);
} // конец параллельной области
Подобный прием укрупнения последовательных участков вычислений для снижения затрат на синхронизацию именуется
фрагментированием (chunking). Результаты экспериментов для данного варианта параллельных вычислений приведены в табл. 12.3.
Следует обратить внимание еще на один момент при анализе эффективности разработанного параллельного алгоритма. Фронт волны вычислений плохо соответствует правилам использования
кэша
- быстродействующей дополнительной памяти компьютера, используемой для хранения копии наиболее часто используемых областей оперативной памяти. Эффективное использование кэша может существенно повысить (в десятки раз) быстродействие вычислений. Размещение данных в кэше может происходить или предварительно (при использовании тех или иных алгоритмов предсказания потребности в данных) или в момент извлечения значений из основной оперативной памяти. При этом подкачка данных в кэш осуществляется не одиночными значениями, а небольшими группами –
строками кэша (cache line). Загрузка значений в строку кэша осуществляется из последовательных элементов памяти; типовые размеры строки кэша обычно равны 32, 64, 128, 256 байтам (дополнительная информация по организации памяти может быть получена, например, в (см., например, Хамахер и
Вранешич (2003)). Как результат, эффект наличия кэша будет наблюдаться, если выполняемые вычисления используют одни и те же данные многократно (
локальность обработки данных) и осуществляют доступ к элементам памяти с последовательно возрастающими адресами
(
последовательность доступа).
В рассматриваемом нами алгоритме размещение данных в памяти осуществляется по строкам, а фронт волны вычислений располагается по диагонали сетки, и это приводит к низкой эффективности использования кэша. Возможный способ улучшения ситуации – опять же укрупнение вычислительных операций и рассмотрение в качестве распределяемых между процессорами действий процедуру обработки некоторой прямоугольной подобласти (
блока) сетки области расчетов - см. рис. 12.9.

граничные значения значения предшествующей итерации значения текущей итерации узлы, в которых могут быть пересчитаны значения значения, которые должны передаваться между границами блоков блоки узлов сетки
Рис. 12.9.
Блочное представление сетки области расчетов
Порождаемый на основе такого подхода метод вычислений в самом общем виде может быть описан следующим образом (блоки образуют в области расчётов прямоугольную решётку размера NBxNB):
//Алгоритм 12.6
// Параллельный метод Гаусса-Зейделя (блочная волновая схема) do {
// нарастание волны (размер волны равен nx+1)
for ( nx=0; nx
оков
// NB количество бл
#pragma omp parallel for shared(nx) private(i,j)
for ( i=0; i
j = nx – i;
// <обработка блока с координатами (i,j)>
} // конец параллельной области
}
// затухание волны
for ( nx=NB-2; nx>-1; nx-- ) {
#pragma omp parallel for shared(nx) private(i,j)
for ( i=0; i
j = 2*(NB-1) - nx – i;
// <обработка блока с координатами (i,j)>
} // конец параллельной области
}
// <определение погрешности вычислений>
} while ( dmax > eps );
Алгоритм 12.6.
Блочный подход к методу волновой обработки данных
Вычисления в предлагаемом алгоритме происходят в соответствии с волновой схемой обработки данных – вначале вычисления выполняются только в левом верхнем блоке с координатами (0,0), далее для обработки становятся доступными блоки с координатами (0,1) и (1,0) и т.д. – см. результаты экспериментов в табл. 12.3.
Блочный подход к методу волновой обработки данных существенным образом меняет состояние дел – обработку узлов можно организовать построчно, доступ к данным осуществляется последовательно по элементам памяти, перемещенные в кэш значения используются многократно.
Кроме того, поскольку обработка блоков будет выполняться на разных процессорах и блоки не пересекаются по данным, при таком подходе будут отсутствовать и накладные расходы для обеспечения однозначности (
когерентности) кэшей разных процессоров.
Наилучшие показатели использования кэша будут достигаться, если в кэше будет достаточно места для размещения не менее трех строк блока (при обработке строки блока используются данные трех строк блока одновременно). Тем самым, исходя из размера кэша, можно определить рекомендуемый максимально-возможный размер блока. Так, например, при кэше 8 Кб и 8-байтовых значениях данных этот размер составит приближенно 300 (8Кб/3/8). Можно определить и минимально-допустимый размер
15

16
блока из условия совпадения размеров строк кэша и блока. Так, при размере строки кэша 256 байт и 8- байтовых значениях данных размер блока должен быть кратен 32.
Последнее замечание необходимо сделать о взаимодействии граничных узлов блоков. Учитывая граничное взаимодействие, соседние блоки целесообразно обрабатывать на одних и тех же процессорах.
В противном случае можно попытаться так определить размеры блоков, чтобы объем пересылаемых между процессорами граничных данных был минимален. Так, при размере строки кэша в 256 байт, 8- байтовых значениях данных и размере блока 64х64 объем пересылаемых данных 132 строки кэша, при размере блока 128х32 – всего 72 строки. Такая оптимизация имеет наиболее принципиальное значение при медленных операциях пересылки данных между кэшами процессоров, т.е. для систем с неоднородным доступом к памяти (nonuniform memory access - NUMA).
12.2.7. Балансировка вычислительной нагрузки процессоров
Как уже отмечалось ранее, вычислительная нагрузка при волновой обработке данных изменяется динамически в ходе вычислений. Данный момент следует учитывать при распределении вычислительной нагрузки между процессорами. Так, например, при фронте волны из 5 блоков и при использовании 4 процессоров обработка волны потребует двух параллельных итераций, во время второй из которых будет задействован только один процессор, а все остальные процессоры будут простаивать, дожидаясь завершения вычислений. Достигнутое ускорение расчетов в этом случае окажется равным 2.5 вместо потенциально возможного значения 4. Подобное снижение эффективности использования процессоров становится менее заметным при большой длине волны, размер которой может регулироваться размером блока. Как общий результат, можно отметить, что размер блока определяет
степень разбиения
(
granularity) вычислений для распараллеливания и является параметром, подбирая значения которого, можно управлять эффективностью параллельных вычислений.
Для обеспечения равномерности (
балансировки) загрузки процессоров можно задействовать еще один подход, широко используемый для организации параллельных вычислений. Этот подход состоит в том, что все готовые к выполнению в системе вычислительные действия организуются в виде
очереди
заданий. В ходе вычислений освободившийся процессор может запросить для себя работу из этой очереди; появляющиеся по мере обработки данных дополнительные задания пополняют задания очереди. Такая схема балансировки вычислительной нагрузки между процессорами является простой, наглядной и эффективной. Это позволяет говорить об использовании очереди заданий как об
общей
модели организации параллельных вычислений для систем с общей памятью.
Рассмотренная схема балансировки может быть задействована и для рассматриваемого примера. В самом деле, в ходе обработки фронта текущей волны происходит постепенное формирование блоков следующей волны вычислений. Эти блоки могут быть задействованы для обработки при нехватке достаточной вычислительной нагрузки для процессоров
Общая схема вычислений с использованием очереди заданий может быть представлена в следующем виде:
//Алгоритм 12.7
// Параллельный метод
Гаусса-Зейделя
(блочная волновая схема,
очередь заданий)
// <инициализация служебных данных>
// <загрузка в очередь указателя на начальный блок>
// взять блок из очереди (если очередь не пуста) while ( (pBlock=GetBlock()) != NULL ) {
// <обработка блока>
// отметка готовности соседних блоков omp_set_lock(pBlock->pNext.Lock); // сосед справа pBlock->pNext.Count++; if ( pBlock->pNext.Count == 2 )
PutBlock(pBlock->pNext); omp_unset_lock(pBlock->pNext.Lock); omp_set_lock(pBlock->pDown.Lock); // сосед снизу pBlock->pDown.Count++; if ( pBlock->pDown.Count == 2 )
PutBlock(pBlock->pDown); omp_unset_lock(pBlock->pDown.Lock);
} // завершение вычислений, т.к. очередь пуста
Алгоритм 12.7.
Общая схема вычислений с использованием очереди

Для описания имеющихся в задаче блоков узлов сетки в алгоритме используется структура со следующим набором параметров:
- Lock – семафор, синхронизирующий доступ к описанию блока,
- pNext – указатель на соседний справа блок,
- pDown – указатель на соседний снизу блок,
- Count – счетчик готовности блока к вычислениям (количество готовых границ блока).
Операции для выборки из очереди и вставки в очередь указателя на готовый к обработке блок узлов сетки обеспечивают соответственно функции
GetBlock и PutBlock.
Как следует из приведенной схемы, процессор извлекает блок для обработки из очереди, выполняет необходимые вычисления для блока и отмечает готовность своих границ для соседних справа и снизу блоков. Если при этом оказывается, что у соседних блоков являются подготовленными обе границы, процессор передает эти блоки для запоминания в очередь заданий.
Использование очереди заданий позволяет решить практически все оставшиеся вопросы организации параллельных вычислений для систем с общей памятью. Развитие рассмотренного подхода может предусматривать уточнение правил выделения заданий из очереди для согласования с состояниями процессоров (близкие блоки целесообразно обрабатывать на одних и тех же процессорах), расширение числа имеющихся очередей заданий и т.п. Дополнительная информация по этим вопросам может быть получена, например, в Xu and Hwang (1998).
12.3. Организация параллельных вычислений для систем с
распределенной памятью
Использование процессоров с распределенной памятью является другим общим способом построения многопроцессорных вычислительных систем. Актуальность таких систем становится все более высокой в последнее время в связи с широким развитием высокопроизводительных кластерных вычислительных систем (см. раздел 1).
Многие проблемы параллельного программирования (состязание вычислений, тупики, сериализация) являются общими для систем с общей и распределенной памятью. Момент, который отличает параллельные вычисления с распределенной памятью, состоит в том, что взаимодействие параллельных участков программы на разных процессорах может быть обеспечено только при помощи
передачи сообщений (message passing).
Следует отметить, что процессор с распределенной памятью является, как правило, более сложным вычислительным устройством, чем процессор в многопроцессорной системе с общей памятью. Для учета этих различий в дальнейшем процессор с распределенной памятью будет именоваться как
вычислительный сервер (сервером может быть, в частности, многопроцессорная система с общей памятью). При проведении всех ниже рассмотренных экспериментов использовались 4 компьютера с процессорами Pentium IV, 1300 Mhz, 256 RAM, 100 Mbit Fast Ethernet.
12.3.1. Разделение данных
Первая проблема, которую приходится решать при организации параллельных вычислений на системах с распределенной памяти, обычно состоит в выборе способа разделения обрабатываемых данных между вычислительными серверами. Успешность такого разделения определяется достигнутой степенью локализации вычислений на серверах (в силу больших временных задержек при передаче сообщений интенсивность взаимодействия серверов должна быть минимальной).
1
{
{
{
{
{
{
{
{
{
{
• • • • • • •
{
{
• • • • • • •
{
{
• • • • • • •
{
{
• • • • • • •
{
{
• • • • • • •
{
{
• • • • • • •
{
{
• • • • • • •
{
{
{
{
{
{
{
{
{
{
0
Процессоры
2
{
{
{
{
{
{
{
{
{
{
• • • • • • •
{
{
• • • • • • •
{
{
• • • • • • •
{
{
• • • • • • •
{
{
• • • • • • •
{
{
• • • • • • •
{
{
• • • • • • •
{
{
{
{
{
{
{
{
{
{
(i,j)
(i
+
1,j)
(i-1,j)
(i,j
+
1)
(i,j-1)
Рис. 12.10.
Ленточное разделение области расчетов между процессорами (кружки представляют граничные узлы сетки)
17

18
В рассматриваемой учебной задаче по решению задачи Дирихле возможны два различных способа разделения данных –
одномерная или ленточная схема (см. рис. 12.10) или двухмерное или блочное разбиение (см. рис. 12.9) вычислительной сетки. Дальнейшее изложение учебного материала будет проводиться на примере первого подхода; блочная схема будет рассмотрена позднее в более кратком виде.
При ленточном разбиении область расчетов делится на горизонтальные или вертикальные полосы
(не уменьшая общности, далее будем рассматривать только горизонтальные полосы). Число полос определяется количеством процессоров, размер полос обычно является одинаковым, узлы горизонтальных границ (первая и последняя строки) включаются в первую и последнюю полосы соответственно. Полосы для обработки распределяются между процессорами.
Основной момент при организации вычислений с подобным разделением данных состоит в том, что на процессор, выполняющий обработку какой-либо полосы, должны быть продублированы граничные строки предшествующей и следующей полос вычислительной сетки (получаемые в результате расширенные полосы показаны на рис. 12.10 справа пунктирными рамками). Продублированные граничные строки полос используются только при проведении расчетов, пересчет же этих строк происходит в полосах своего исходного месторасположения. Тем самым дублирование граничных строк должно осуществляться перед началом выполнения каждой очередной итерации метода сеток.