Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Последовательный алгоритм суммирования

Параллельные численные методы для решения типовых задач вычислительной математики

Вычисление частных сумм последовательности числовых значений

Рассмотрим для первоначального ознакомления со способами построения и анализа параллельных методов вычислений сравнительно простую задачу нахождения частных сумм последовательности числовых значений

,

где есть количество суммируемых значений (данная задача известна также под названием prefix sum problem – см. п. 3.3).

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

.

Последовательный алгоритм суммирования

Традиционный алгоритм для решения этой задачи состоит в последовательном суммировании элементов числового набора

Вычислительная схема данного алгоритма может быть представлена следующим образом (см. рис. 4.1):

,

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

есть множество дуг, определяющих информационные зависимости операций.

Рис. 4.1. Последовательная вычислительная схема алгоритма суммирования

Как можно заметить, данный "стандартный" алгоритм суммирования допускает только строго последовательное исполнение и не может быть распараллелен.