- Распределение задачи по m * n блоков, где подзадачи будут иметь вид
do k = 1, q
c(i, j) = c(i, j)+a(i, k)*b(k, j)
end do
- Распределение по m блоков, где подзадачи будут иметь вид
do j = 1, n
do k = 1, q
c(i, j) = c(i, j)+a(i, k)*b(k, j)
end do
end do
Рассмотрим первый вариант. В данном случае мы будем иметь m * n подзадач, где каждая подзадача будет определятся числом итераций по q. Сложность алгоритма составляет O(n3/p2), где p - количество процессоров.
Рассчитаем параметры ускорения и эффективности. Для данного случая ускорение Sp = p2, эффективность Ep= 1. Стоит заметить, что для обеспечения максимально возможного ускорения, нам потребуется m * n процессоров, что в реальных условия не всегда предоставляется возможным.
Для второго случая мы имеем меньшее количество подзадач, включающих в себя два цикла по n и q итераций соответственно. Сложность алгоритма составляет O(n3/p). Ускорение Sp= p, эффективность Ep= 1.
Умножение N матриц