§30. Алгоритм суммирования ряда чисел

Требуется найти сумму ряда . Последовательный алгоритм выглядит следующим образом:

Шаг 1: формируется массив

Шаг 2:

Шаг 3:

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

Приведем алгоритм:

Шаг 1: формируется массив на

Шаг 2:

Шаг 3: на

Шаг 4: на

Шаг 5:

Шаг 6: на

Для правильной интерпретации алгоритма приведем описание результата выполнения 2 шага: на 1 процессоре будут храниться , на 2 процессоре , на -м - .

Заметим, что приведенный параллельный алгоритм вычисления суммы ряда на практике будет выполняться медленнее, чем последовательный. Это объясняется тем, что для выполнения 4 шага пришлось осуществлять рассылку данных, причем количество выполняемых арифметических операций примерно равно числу посылаемых данных, а так как выполнение одной арифметической операции занимает меньше времени, чем пересылка одного машинного слова, то в итоге реализации такого параллельного алгоритма получается проигрыш по времени по сравнению с последовательным. Следовательно, распараллеливать алгоритм суммирования имеет смысл лишь в том случае, если члены ряда формируются независимо на каждом процессоре или в процессе выполнения глобального расчета они уже распределены по процессорам.

В качестве примера рассмотрим суммирование числового ряда для вычисления числа . Формула для нахождения числа :

.

Для определения числа интеграл будем вычислять методом трапеций (параллельная программа приведена на рис. 55).

Рис. 55. Пример распараллеливания алгоритма суммирования ряда чисел