Теория и практика параллельных вычислений
Анализ эффективности параллельных вычислений
Выполним анализ эффективности параллельного алгоритма Флойда, обеспечивающего поиск всех кратчайших путей. Как и ранее, проведем этот анализ в два этапа. На первом оценим порядок вычислительной сложности алгоритма, затем на втором этапе уточним полученные оценки и учтем трудоемкость выполнения коммуникационных операций.
Общая трудоемкость последовательного алгоритма, как уже отмечалось ранее, имеет порядок сложности n3. Для параллельного алгоритма на отдельной итерации каждый процессор выполняет обновление элементов матрицы А. Всего в подзадачах n2/p таких элементов, число итераций алгоритма равно n – таким образом, показатели ускорения и эффективности параллельного алгоритма Флойда имеют вид:
|
(10.1) |
Следовательно, общий анализ сложности дает идеальные показатели эффективности параллельных вычислений. Для уточнения полученных соотношений введем в полученные выражения время выполнения базовой операции выбора минимального значения и учтем затраты на выполнение операций передачи данных между процессорами.
Коммуникационная операция, выполняемая на каждой итерации алгоритма Флойда, состоит в передаче одной из строк матрицы А всем процессорам вычислительной системы. Как уже показывалось ранее, такая операция может быть выполнена за ?log2p? шагов. С учетом количества итераций алгоритма Флойда при использовании модели Хокни общая длительность выполнения коммуникационных операций может быть определена при помощи следующего выражения
|
(10.2) |
где, как и ранее, – латентность сети передачи данных, ? – пропускная способность сети, а w есть размер элемента матрицы в байтах.
С учетом полученных соотношений общее время выполнения параллельного алгоритма Флойда может быть определено следующим образом:
|
(10.3) |
где ? есть время выполнения операции выбора минимального значения.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий