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



Анализ эффективности - часть 2


Следовательно, вычислительная трудоемкость параллельного алгоритма определяется выражением:

(6.5)

С учетом этой оценки показатели ускорения и эффективности параллельного алгоритма имеют вид:

(6.6)

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

(здесь и далее операция есть округление до целого в большую сторону).

Оценка трудоемкости операции обобщенного сбора данных уже выполнялась в лекции 4 (см. п. 4.3.4). Как уже отмечалась ранее, данная операция может быть выполнена за log2p

итераций1). На первой итерации взаимодействующие пары процессоров обмениваются сообщениями объемом (w есть размер одного элемента вектора c в байтах), на второй итерации этот объем увеличивается вдвое и оказывается равным и т.д. Как результат, длительность выполнения операции сбора данных при использовании модели Хокни может быть определена при помощи следующего выражения

(6.7)

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

(6.8)

(для упрощения выражения в (6.8) предполагалось, что значения n/p и log2p являются целыми).




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