Анализ эффективности ленточного алгоритма
На каждой итерации каждый процессор выполняет умножение имеющихся на процессоре полос матрицы А и матрицы В. Поскольку число итераций алгоритма совпадает с количеством процессоров, сложность параллельного алгоритма без учета затрат на передачу данных может быть определена при помощи выражения:
С учетом этой оценки показатели ускорения и эффективности данного параллельного алгоритма матричного умножения принимают вид:
С учетом числа и длительности выполняемых операций время выполнения вычислений параллельного алгоритма может быть оценено следующим образом:
Оценка трудоемкости выполняемых операций передачи данных может быть определена как:
где α – латентность, β – пропускная способность сети передачи данных, а w есть размер элемента матрицы в байтах.
С учетом полученных соотношений общее время выполнения параллельного алгоритма матричного умножения определяется следующим выражением:
Анализ эффективности алгоритма фокса
Построение оценок будет происходить при условии выполнения всех ранее выдвинутых предположений - все матрицы являются квадратными размера n×n, количество блоков по горизонтали и вертикали являются одинаковым и равным q (т.е. размер всех блоков равен k×k, k=n/q), процессоры образуют квадратную решетку и их количество равно p=q2.
Алгоритм Фокса требует для своего выполнения q итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц А и В и прибавляет результаты умножения к текущему значению блока матрицы C. С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок n3/p. Как результат, показатели ускорения и эффективности алгоритма имеют вид:
Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы A на столбец блока матрицы В можно оценить как 2(n/q)-1. Количество строк и столбцов в блоках равно n/q и, как результат, трудоемкость операции блочного умножения оказывается равной (n2/p)(2n/q-1). Для сложения блоков требуется n2/p операций. С учетом всех перечисленных выражений время выполнения вычислительных операций алгоритма Фокса может быть оценено следующим образом:
Оценим затраты на выполнение операций передачи данных между процессорами. На каждой итерации алгоритма перед умножением блоков один из процессоров строки процессорной решетки рассылает свой блок матрицы A остальным процессорам своей строки.
Как результат, время выполнения операции передачи блоков матрицы A может оцениваться как:
где α – латентность, β – пропускная способность сети передачи данных, а w есть размер элемента матрицы в байтах.
Далее после умножения матричных блоков процессоры передают свои блоки матрицы В предыдущим процессорам по столбцам процессорной решетки. Эти операции могут быть выполнены процессорами параллельно и, тем самым, длительность такой коммуникационной операции составляет:
Просуммировав все полученные выражения, можно получить, что общее время выполнения алгоритма Фокса может быть определено при помощи следующих соотношений:
