Теория и практика параллельных вычислений

         

Организация волны вычислений


Представленные в пп. 11.3.1 – 11.3.3 алгоритмы определяют общую схему параллельных вычислений для метода сеток в многопроцессорных системах с распределенной памятью. Далее эта схема может быть конкретизирована реализацией практически всех вариантов методов, рассмотренных для систем с общей памятью (применение дополнительной памяти для схемы Гаусса – Якоби, чередование обработки полос и т.п.). Проработка таких вариантов не привносит каких-либо новых эффектов с точки зрения параллельных вычислений, и их разбор может использоваться как тема заданий для самостоятельных упражнений.

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

Размер сеткиПоследовательный метод Гаусса - Зейделя (алгоритм 11.1)Параллельный алгоритм 11.8Параллельный алгоритм с волновой схемой расчета (см. п. 11.3.4)ktktSktS
1002100,062100,540,112101,270,05
2002730,352730,860,412731,370,26
3003050,923050,921,003051,830,50
4003181,693181,271,333182,530,67
5003432,883431,721,683433,260,88
6003364,043362,161,873363,661,10
7003445,683442,522,253444,641,22
8003437,373433,322,223435,651,30
9003589,943584,122,413587,531,32
100035111,873514,432,683518,101,46
200036750,1936715,133,3236727,001,86
3000364113,1736437,962,9836455,762,03

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

В завершение рассмотрим возможность организации параллельных вычислений, при которых обеспечивалось бы нахождение таких же решений задачи Дирихле, что и при использовании исходного последовательного метода Гаусса – Зейделя. Как отмечалось ранее, такой результат может быть получен за счет организации волновой схемы расчетов. Для образования волны вычислений представим логически каждую полосу узлов области расчетов в виде набора блоков (размер блоков можно положить, в частности, равным ширине полосы) и организуем обработку полос поблочно в последовательном порядке (см. рис. 11.12). Тогда для полного повторения действий последовательного алгоритма вычисления могут быть начаты только для первого блока первой полосы узлов; после того как этот блок будет обработан, для вычислений будут готовы уже два блока – блок 2 первой полосы и блок 1 второй полосы (для обработки блока полосы 2 необходимо передать граничную строку узлов первого блока полосы 1). После обработки указанных блоков к вычислениям будут готовы уже 3 блока, и мы получаем знакомый уже процесс волновой обработки данных (результаты экспериментов см. в табл. 11.4).


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

Интересный момент при организации подобной схемы параллельных вычислений может состоять в попытке совмещения операций пересылки граничных строк и действий по обработке блоков данных.



Содержание раздела