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

Выполним анализ эффективности параллельного алгоритма умножения матрицы на вектор при обычных уже предположениях, что матрица А является квадратной, т.е. m=n. Будем предполагать также, что процессоры, составляющие многопроцессорную вычислительную систему, образуют прямоугольную решетку p=s×q (s – количество строк в процессорной решетке, q – количество столбцов).

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

(6.16)

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

Общее время умножения блоков матрицы А и вектора b может быть определено как

(6.17)

Операция редукции данных может быть выполнена с использованием каскадной схемы и включает, тем самым, log₂q итераций передачи сообщений размера . Как результат, оценка коммуникационных затрат параллельного алгоритма при использовании модели Хокни может быть определена при помощи следующего выражения

(6.18)

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

(6.19)

Дата добавления: 2015-06-28