На этом шаге мы рассмотрим общие положения алгоритма Флойда.
Разделение вычислений на независимые части
Как следует из общей схемы алгоритма Флойда, основная вычислительная нагрузка при решении задачи поиска кратчайших путей состоит в выполнении операции выбора минимальных значений. Данная операция является достаточно простой, и ее распараллеливание не приведет к заметному ускорению вычислений. Более эффективный способ организации параллельных вычислений может состоять в одновременном выполнении нескольких операций обновления значений матрицы А. Покажем корректность такого способа организации параллелизма. Для этого нужно доказать, что операции обновления значений матрицы на одной и той же итерации внешнего цикла k могут выполняться независимо. Иными словами, следует показать, что на итерации k не происходит изменения элементов Aik и Akj ни для одной пары индексов (i, j). Рассмотрим выражение, по которому происходит изменение элементов матрицы A:
Aij <- min (Aij, Aik+ Akj).
Для i = k получим
Akj <- min (Akj, Akk+ Akj),
но тогда значение Akj не изменится, так как Аkk = 0.
Для j = k выражение преобразуется к виду Aik <- min (Aik, Aik+ Akk).
что также показывает неизменность значений Aik. Как результат, необходимые условия для организации параллельных вычислений обеспечены и, тем самым, в качестве базовой подзадачи может быть использована операция обновления элементов матрицы А (для указания подзадач будем использовать индексы обновляемых в подзадачах элементов).
Выделение информационных зависимостей
Выполнений вычислений в подзадачах становится возможным только тогда, когда каждая подзадача (i, j) содержит необходимые для расчетов элементов Aij, Aik, Akj матрицы А. Для исключения дублирования данных разместим в подзадаче (i, j) единственный элемент Aij, тогда получение всех остальных необходимых значений может быть обеспечено только при помощи передачи данных. Таким образом, каждый элемент Akj строки k матрицы А должен быть передан всем подзадачам (k, j), 1<=j<=n, а каждый элемент Aik столбца k матрицы А должен быть передан всем подзадачам (i, k), 1<=i<=n.
Масштабирование и распределение подзадач по процессорам
Как правило, число доступных процессоров p существенно меньше, чем число базовых задач n2 (p << n). Возможный способ укрупнения вычислений состоит в использовании ленточной схемы разбиения матрицы А - такой подход соответствует объединению в рамках одной базовой подзадачи вычислений, связанных с обновлением элементов одной или нескольких строк (горизонтальное разбиение) или столбцов (вертикальное разбиение) матрицы A. Эти два типа разбиения практически равноправны - учитывая дополнительный момент, что для алгоритмического языка C массивы располагаются по строкам, будем рассматривать далее только разбиение матрицы A на горизонтальные полосы. Следует отметить, при таком способе разбиения данных на каждой итерации алгоритма Флойда потребуется передавать между подзадачами только элементы одной из строк матрицы A. Для эффективного выполнения подобной коммуникационной операции топология сети должна представлять собой гиперкуб или полный граф.
На следующем шаге мы рассмотрим алгоритм Прима.
