棋盘划分把矩阵划分称为若干个子矩阵并映射到不同的处理器上,每个处理器都不包含完整的行和列。和条带状划分类似,棋盘划分也可以分为块棋盘划分和循环棋盘划分,见图6.3.2。
对于实际的网格状互联网络结构,矩阵的棋盘划分可以方便地映射到其上。比如把一个n×n的矩阵按照棋盘划分映射到一个q×q的二维网格上(设p=q×q),则每个处理器包含个矩阵元素。
利用棋盘划分可以划分到更细的粒度(最多可以划分成n×n块),从而可以达到更高的并行度。
(a)
(b)
图6.3.2 16个处理器上8×8矩阵的均匀棋盘划分和映射
(a) 块棋盘划分;(b) 循环棋盘划分
|