Анализ эффективности параллельных вычислений

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

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

(10.1)

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

Коммуникационная операция, выполняемая на каждой итерации алгоритма Флойда, состоит в передаче одной из строк матрицы А всем процессорам вычислительной системы. Как уже показывалось ранее, такая операция может быть выполнена за ?log2p? шагов. С учетом количества итераций алгоритма Флойда при использовании модели Хокни общая длительность выполнения коммуникационных операций может быть определена при помощи следующего выражения

(10.2)

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

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

(10.3)

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

Общий анализ сложности параллельного алгоритма Прима для нахождения минимального охватывающего дерева дает идеальные показатели эффективности параллельных вычислений:

(10.4)

При этом следует отметить, что в ходе параллельных вычислений идеальная балансировка вычислительной нагрузки процессоров может быть нарушена. В зависимости от вида исходного графа G количество выбранных вершин в охватывающем дереве на разных процессорах может оказаться различным, и распределение вычислений между процессорами станет неравномерным (вплоть до отсутствия вычислительной нагрузки на отдельных процессорах). Однако такие предельные ситуации нарушения балансировки в общем случае возникают достаточно редко, а организация динамического перераспределения вычислительной нагрузки между процессорами в ходе вычислений является интересной, но одновременно и очень сложной задачей.

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

При выполнении вычислений на отдельной итерации параллельного алгоритма Прима каждый процессор определяет номер ближайшей вершины из Vj до охватывающего дерева и осуществляет корректировку расстояний di после расширения МОД. Количество выполняемых операций в каждой из этих вычислительных процедур ограничивается сверху числом вершин, имеющихся на процессорах, т.е. величиной ?n/p?. Как результат, с учетом общего количества итераций n время выполнения вычислительных операций параллельного алгоритма Прима может быть оценено при помощи соотношения:

(10.5)

(здесь, как и ранее, ? есть время выполнения одной элементарной скалярной операции).

Операция сбора данных от всех процессоров на одном из процессоров может быть произведена за ?log2p? итераций, при этом общая оценка длительности выполнения передачи данных определяется выражением (более подробное рассмотрение данной коммуникационной операции содержится в лекции 3):

(10.6)

где – латентность сети передачи данных, ? – пропускная способность сети, а w есть размер одного пересылаемого элемента данных в байтах (коэффициент 3 в выражении соответствует числу передаваемых значений между процессорами – длина минимальной дуги и номера двух вершин, которые соединяются этой дугой).

Коммуникационная операция передачи данных от одного процессора всем процессорам вычислительной системы также может быть выполнена за ?log2p? итераций при общей оценке времени выполнения вида:

(10.7)

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

(10.8)

Содержание раздела