二维网格互联结构上的矩阵转置

　　设处理器数目p≤n²，则整个n×n的矩阵分成p个大小为的子块，这些子块自然影射到网格互联结构的p个处理器上。算法可以分两步来完成：第一步，将各个子块看作一个整体进行图6.3.4(a)所示的子块转置，这一步由各处理器互相通信；第二步，各处理器分别对自己的内部子块进行局部转置，如图6.3.4(b)所示。
　　

(a) 子块间转置；　　
　　　　　　　　　　
　　　
b) 子块内转置
图6.3.4 16个处理器上块棋盘划分的8×8矩阵的转置

　　整个算法的运行时间分析如下：第一步子块间转置最长的路径约为，移动单个子块的时间为，所以各个子块到达目的地的时间为；第二步大小为的子块转置需要的时间量级是n²/p，所以算法的总运行时间为：