6.3.4.4 DNS算法
考虑复杂度为O(n
3
)的串行矩阵相乘算法的并行化,设处理器个数为p,则并行处理时间T
p
至少为n
3
/p。前面所讲述的方法(不论是简单矩阵分块法,Cannon法,还是Fox算法)都有p<n
2
,因此T
p
至少为n。典型的情况是:处理器个数p=n
2
,并行处理时间T
p
=n。能不能利用大于n
2
的处理器个数得到小于n的并行处理时间呢?这是本小节所要解决的问题。