Блочная схема разделения данных

Ленточная схема разделения данных может быть естественным образом обобщена на блочный способ представления сетки области расчетов (рис. 6.9). Сильное изменение изменение способа разбиения сетки практически не требует существенных корректировок рассмотренной схемы параллельных вычислений. Основной момент состоит в увеличении количества граничных строк на каждом процессоре (для блока их количество становится равным 4), что приводит к большему числу операций передачи данных при обмене граничных строк. Сравнивая затраты на организацию передачи граничных строк, можно заметить, что при ленточной схеме для каждого процессора выполняется 4 операции приема-передачи данных, в каждой из которых пересылается (N+2) значения; а для блочного способа происходит 8 операций пересылки и объем каждого сообщения равен () (NP – число процессоров, N – количество внутренних узлов сетки, размер всех блоков одинаков). Блочная схема представления области расчетов становится оправданной при большом количество узлов сетки области расчетов, когда увеличение количества коммуникационных операций приводит к снижению затрат на пересылку данных в силу сокращения размеров передаваемых сообщений. Результаты данных экспериментов приведены в табл. 6.5.

Таблица 6.5. Результаты экспериментов для систем с распределенной памятью, блочная схема разделения данных (p =4)

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

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

Общая схема параллельных вычислений будет иметь вид:

// Алгоритм 6.9 // схема Гаусса-Зейделя, блочное разделение данных // действия, выполняемые на каждом процессоре do { // получение граничных узлов if (ProcNum / NB!= 0) { // строка не нулевая // получение данных от верхнего процессора Receive(u[0][*],M+2,TopProc); // верхняя строка Receive(dmax,1,TopProc); // погрешность } if (ProcNum % NB!= 0) { // столбец не нулевой // получение данных от левого процессора Receive(u[*][0],M+2,LeftProc); // левый столбец Receive(dm,1,LeftProc); // погрешность If (dm > dmax) dmax = dm; } // <обработка блока с оценкой погрешности dmax> // пересылка граничных узлов if (ProcNum / NB!= NB-1) { // строка решетки не последняя // пересылка данных нижнему процессору Send(u[M+1][*],M+2,DownProc); // нижняя строка Send(dmax,1,DownProc); // погрешность } if (ProcNum % NB!= NB-1) { // столбец решетки не последний // пересылка данных правому процессору Send(u[*][M+1],M+2,RightProc); // правый столбец Send(dmax,1,RightProc); // погрешность } // синхронизация и рассылка погрешности dmax Barrier(); Broadcast(dmax,NP-1); } while (dmax > eps); // eps - точность решения

(в приведенном алгоритме функция Barrier () представляет операцию коллективной синхронизации, завершающую свое выполнение в тот момент, когда все процессоры осуществят вызов этой процедуры).

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

Анализ эффективности организации волновых вычислений в системах с распределенной памятью (табл. 6.5) показывает значительное снижение полезной вычислительной нагрузки для процессоров, которые занимаются обработкой данных только в те моменты, когда их блоки попадают во фронт волны вычислений. При этом балансировка (перераспределение) нагрузки является крайне затруднительной, т.к. связана с пересылкой между процессорами блоков данных большого объема. Возможный вариант улучшения алгоритма состоит в организации множественной волны вычислений, в соответствии с которой процессоры после отработки волны текущей итерации расчетов могут приступить к выполнению волны следующей итерации метода сеток. Например, процессор 0 (рис. 6.13), передав после обработки своего блока граничные данные и запустив вычисления на процессорах 1 и 4, оказывается готовым к исполнению следующей итерации метода Гаусса-Зейделя. После обработки блоков первой (процессорах 1 и 4) и второй (процессор 0) волн, к вычислениям будут готовы следующие группы процессоров (для первой волны - процессоры 2, 5 и 8, для второй волны - процессоры 1 и 4). А процессор 0 опять окажется доступным к запуску очередной волны обработки данных. После выполнения NB подобных шагов в обработке будет находиться одновременно NB итераций и все процессоры окажутся задействованными. Такая схема организации расчетов позволяет рассматривать имеющуюся процессорную решетку как вычислительный конвейер поэтапного выполнения итераций метода сеток. Останов конвейера может осуществляться по максимальной погрешности вычислений. Получаемое после выполнения условия остановки решение задачи Дирихле будет содержать значения узлов сетки от разных итераций метода и не будет совпадать с решением, получаемым при помощи исходного последовательного алгоритма.

Рис. 6.13. Организация волны вычислений при блочной схеме разделения данных