На этом шаге мы рассмотрим еще одну схему разделения данных.
Ленточная схема разделения данных может быть естественным образом обобщена на блочный способ представления сетки области расчетов. При этом столь радикальное изменение способа разбиения сетки практически не потребует каких-либо существенных корректировок рассмотренной схемы параллельных вычислений. Основной новый момент при блочном представлении данных состоит в увеличении количества граничных строк на каждом процессоре (для блока их количество становится равным 4), что приводит, соответственно, к большему числу операций передачи данных при обмене граничных строк. Сравнивая затраты на организацию передачи граничных строк, можно отметить, что при ленточной схеме для каждого процессора выполняется 4 операции приема-передачи данных, в каждой из которых пересылается (N+2) значения. Для блочного же способа происходит 8 операций пересылки и объем каждого сообщения равен (N/корень_квадратный(NP) + 2) (N - количество внутренних узлов сетки, NP - число процессоров, размер всех блоков предполагается одинаковым). Тем самым, блочная схема представления области расчетов становится оправданной при большом количестве узлов сетки области расчетов, когда увеличение количества коммуникационных операций приводит к снижению затрат на пересылку данных в силу сокращения размеров передаваемых сообщений.
При блочном представлении сетки может быть реализован также и волновой метод выполнения расчетов. Пусть процессоры образуют прямоугольную решетку размером NB*NB (NB = корень_квадратный(NP)) и процессоры пронумерованы от 0 слева направо по строкам решетки.
Общая схема параллельных вычислений в этом случае имеет вид:
// действия, выполняемые на каждом процессоре 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 - точность решения
При реализации алгоритма нужно обеспечить, чтобы в начальный момент времени все процессоры (кроме процессора с нулевым номером) оказались в состоянии ожидания своих граничных узлов (верхней строки и левого столбца). Вычисления должен начинать процессор с левым верхним блоком, после завершения обработки которого обновленные значения правого столбца и нижней строки блока необходимо переправить правому и нижнему процессорам решетки соответственно. Данные действия обеспечат снятие блокировки процессоров второй диагонали процессорной решетки и т.д.
На процессорах, которые занимаются обработкой данных только в моменты, когда их блоки попадают во фронт волны вычислений, происходит значительное снижение полезной вычислительной нагрузки для процессоров. При этом балансировка (перераспределение) нагрузки является крайне затруднительной, поскольку связана с пересылкой между процессорами блоков данных большого объема. Возможный интересный способ улучшения ситуации состоит в организации множественной волны вычислений, в соответствии с которой процессоры после отработки волны текущей итерации расчетов могут приступить к выполнению волны следующей итерации метода сеток. После выполнения NB подобных шагов в обработке будет находиться одновременно NB итераций и все процессоры окажутся задействованными. Подобная схема организации расчетов позволяет рассматривать имеющуюся процессорную решетку как вычислительный конвейер поэтапного выполнения итераций метода сеток. Останов конвейера может осуществляться, как и ранее, по максимальной погрешности вычислений (проверку условия остановки следует начинать только при достижении полной загрузки конвейера после запуска NB итераций расчетов). Необходимо отметить также, что получаемое после выполнения условия остановки решение задачи Дирихле будет содержать значения узлов сетки от разных итераций метода и не будет, тем самым, совпадать с решением, получаемым при помощи исходного последовательного алгоритма.
На следующем шаге мы приведем оценку трудоемкости операций передачи данных.
