matrix - 了解 block 和 block 循环矩阵分布

Question

在处理矩阵的并行分解时，我熟悉 block 分布，其中我们有(比如说)4 个进程，每个进程都有自己的矩阵子区域:

例如，我们的行中的进程数 (procrows) 等于 2，列中的进程数 (proccols) 也等于两个，如果原始矩阵大小为 N x M，则子矩阵 A_local 的大小将为 N/2 x M/2。

我正在读这篇文章example它使用“ block 循环”分布，在这部分中:

/* Begin Cblas context */
/* We assume that we have 4 processes and place them in a 2-by-2 grid */
int ctxt, myid, myrow, mycol, numproc;
int procrows = 2, proccols = 2;
Cblacs_pinfo(&myid, &numproc);
Cblacs_get(0, 0, &ctxt);
Cblacs_gridinit(&ctxt, "Row-major", procrows, proccols);

它们有 procrows 和 proccols 是硬编码的，很好，但是对于读入的矩阵，有一个标题:

Nb and Mb will be the number of rows and columns of the blocks [of the matrix]

我不明白这个； Nb 和 Mb 不是完全由 N、M、procrows 和 proccols 决定吗？

<小时/>

编辑

通过运行示例，我可以看到进程 0 上的子矩阵具有矩阵左上角的所有元素，就像上面的图片一样，这与乔纳森的答案相矛盾。不过，它与 ScaLAPACK 的 Cholesky 配合得很好。

Answer 1

正如您在问题中所描述的那样，矩阵的 block 分解是一种完全有效的分配矩阵的方法，但这并不是唯一的方法。

特别是， block 数据分布(将矩阵分解为 procrows x process 子矩阵)有点不灵活。如果矩阵大小不能被行或列中的进程数整除 - 通常您无法控制矩阵的大小，并且只能使用 procrows/proccols 进行一些灵 active - 您最终可能会遇到严重的负载平衡问题。另外，有时能够“过度分解”问题也非常方便；将其分解为比您的任务更多的部分。特别是，对于 MPI，由于每个任务都是一个进程，因此有时能够为每个进程提供多个要操作的子矩阵很有用，这样您就可以通过线程处理这种额外级别的并行性(大多数任务都内置了线程)。单进程线性代数库)。

获得最大负载平衡灵 active 以及最高程度的可用进程间并行性的方法是纯粹的循环分布。在一维循环分布中，假设在 4 个处理器之间划分 15 个项目，处理器 1 将获得项目 1，处理器 2 将获得项目 2，3 将获得项目 3，4 将获得项目 4，然后处理器 1 将获得项目 5，依此类推在;您可以在处理器之间循环处理项目。

另一方面，在一维 block 分解中，处理器 1 将获得项目 1-4，处理器 2 将获得项目 5-9，依此类推。

来自有用的数字LLNL parallel computing tutorial接下来，用每种颜色标记哪个处理器获得了数据区域:

因此，循环分解对于并行性和负载平衡来说是最大的好处，但对于数据访问来说却是糟糕；您希望能够访问以进行线性代数运算的每条相邻数据都位于处理器外。另一方面， block 分解最大限度地有利于数据访问；您拥有尽可能大的连续数据 block ，因此您可以对漂亮的大子矩阵进行矩阵运算；但它的并行性不灵活，并且会在负载平衡方面产生成本。

Block-Cyclic是两者之间的插值；您将矩阵过度分解为 block ，并在进程之间循环分配这些 block 。这使您可以调整数据访问连续​​性和灵 active 之间的权衡。如果 block -循环 block 大小为 1，则为循环分布；如果它们是 N/procrows 或 N/proccols 你有一个 block 分布；但您也可以选择介于两者之间的任何内容。

请注意，在 2D 中，原则上您可以沿行和列选择不同的分解，有时，如果您的矩阵仅用于一种计算，这会很有用；但更常见的情况是所有维度上的分解都是相同的，因此当人们说“ block 分解”或“ block 循环分解”时，他们通常意味着沿着所有维度。

Scalapack pages at netlib对此有很好的描述。 .