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



             

Проблема синхронизации параллельных вычислений - часть 3


рис. 11.4. Следует обратить внимание, что, несмотря на идеальное распределение вычислительной нагрузки между процессорами, для приведенного на рис. 11.4 соотношения параллельных и последовательных вычислений, в каждый текущий момент времени (после момента первой синхронизации) только не более двух процессоров одновременно выполняют действия, связанные с решением задачи. Подобный эффект вырождения параллелизма из-за интенсивной синхронизации параллельных участков программы обычно именуется сериализацией (serialization).

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

Размер сеткиПоследовательный метод Гаусса - Зейделя (алгоритм 11.1)Параллельный алгоритм 11.2Параллельный алгоритм 11.3ktktSktS
1002100,062101,970,032100,032,03
2002730,3427311,220,032730,142,43
3003050,8830529,090,033050,362,43
4003183,7831854,200,073180,645,90
5003436,0034385,840,073431,065,64
6003368,81336126,380,073361,505,88
70034412,11344178,300,073442,425,00
80034316,41343234,700,073438,082,03
90035820,61358295,030,0735811,031,87
100035125,59351366,160,0735113,691,87
2000367106,753671585,840,0736756,631,89
3000370243,003703598,530,07370128,661,89

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


Рис. 11.4.  Пример возможной схемы выполнения параллельных потоков при наличии синхронизации (взаимоисключения)

Как показывают выполненные рассуждения, путь для достижения эффективности параллельных вычислений лежит в уменьшении необходимых моментов синхронизации параллельных участков программы. Так, в нашем примере мы можем ограничиться распараллеливанием только одного внешнего цикла for. Кроме того, для снижения количества возможных блокировок применим для оценки максимальной погрешности многоуровневую схему расчета: пусть параллельно выполняемый поток первоначально формирует локальную оценку погрешности dm только для своих обрабатываемых данных (одной или нескольких строк сетки), затем при завершении вычислений поток сравнивает свою оценку dm с общей оценкой погрешности dmax.




Содержание  Назад  Вперед