Анализ эффективности параллельного алгоритма Флойда проведем в два этапа. На первом этапе оценим порядок вычислительной сложности алгоритма, затем на втором этапе уточним полученные оценки и учтем трудоемкость коммуникационных операций.

Общая трудоемкость последовательного алгоритма равна n³. Для параллельного алгоритма на отдельной итерации каждый процессор выполняет обновление элементов матрицы A. Всего в подзадачах n²/p таких элементов (p – число процессоров), число итераций алгоритма равно n, таким образом, показатели ускорения и эффективности параллельного алгоритма Флойда имеют вид:

S_p = n³/(n³/p) = p,

E_p = n³/(p(n³⁄p)) = 1.

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

Коммуникационная операция, выполняемая на каждой итерации алгоритма Флойда, состоит в передаче одной из строк матрицы A всем процессорам вычислительной системы. Выполнение такой операции может быть выполнено за log₂ p шагов. С учетом количества итераций алгоритма Флойда длительность выполнения коммуникационных операций может быть определена как

T_p(comm) = n log₂ p (α + wn/β),

где α – латентность сети передачи данных, β – пропускная способность сети, w – размер элемента матрицы в байтах.

С учетом полученных соотношений общее время время выполнения параллельного алгоритма Флойда составляет

T_p = n²(n/p) τ + n log₂ p (α + wn/β),

где τ есть время выполнения операции выбора минимального значения.