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



             

Разделение вычислений на независимые части


Как следует из общей схемы алгоритма Флойда, основная вычислительная нагрузка при решении задачи поиска кратчайших путей состоит в выполнении операции выбора минимальных значений (см. Алгоритм 10.1). Данная операция является достаточно простой, и ее распараллеливание не приведет к заметному ускорению вычислений. Более эффективный способ организации параллельных вычислений может состоять в одновременном выполнении нескольких операций обновления значений матрицы A.

Покажем корректность такого способа организации параллелизма. Для этого нужно доказать, что операции обновления значений матрицы A на одной и той же итерации внешнего цикла k могут выполняться независимо. Иными словами, следует показать, что на итерации k не происходит изменения элементов Aik и Akj ни для одной пары индексов (i, j). Рассмотрим выражение, по которому происходит изменение элементов матрицы A:

Aij min (Aij, Aik + Akj).

Для i=k получим

Akj min (Akj, Akk + Akj),

но тогда значение Akj не изменится, т.к. Akk=0.

Для j=k выражение преобразуется к виду

Aik min (Aik, Aik + Akk),

что также показывает неизменность значений Aik. Как результат, необходимые условия для организации параллельных вычислений обеспечены, и, тем самым, в качестве базовой подзадачи может быть использована операция обновления элементов матрицы A (для указания подзадач будем применять индексы обновляемых в подзадачах элементов).




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