6.3.4.4 DNS算法

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