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

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

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

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

 // Алгоритм 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.13) и т.д. Ранг матрицы Определитель с элементами, стоящими на пересечении произвольных строк, и столбцов матрицы, называется минором -го порядка этой матрицы. Линейная и векторная алгебра Аналитическая геометрия Математический анализ

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

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

Другой способ измерения производительности заключается в определении числа вещественных операций, выполняемых компьютером в единицу времени. Единицей измерения является Flops (Floating point operations per second) - число операций с плавающей точкой, производимых компьютером за одну секунду. Такой способ является более приемлемым для пользователя, поскольку последний знает вычислительную сложность своей программы и, пользуясь этой характеристикой, может получить нижнюю оценку времени ее выполнения.

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