了解块和 Block-Cyclic 矩阵分布
Understanding Block and Block-Cyclic Matrix Distributions
在处理矩阵的并行分解时，我熟悉块分布，其中我们有（比方说）4 个进程，每个进程都有自己的矩阵子区域：
例如，这里我们有一行中的进程数 (procrows) 等于 2，一列中的进程数 (proccols) 也等于二，并且sub-matrices A_local 如果原始矩阵大小为 N x M.
，则大小为 N/2 x M/2
我正在阅读这个 example，它使用 "block-cyclic" 分布，在这部分：
/* 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 是硬编码的，很好，但是对于读入的矩阵，有一个 header:
Nb and Mb will be the number of rows and columns of the blocks [of the matrix]
我不明白这个； Nb和Mb不完全由N、M、procrows、proccols决定吗？
编辑
从 运行 这个例子我可以看到进程 0 上的子矩阵包含矩阵左上角的所有元素，就像我上面的图片一样，这与 Jonathan 的回答相矛盾.但是，它与 ScaLAPACK 的 Cholesky 配合使用时效果很好。
您在问题中描述的矩阵块分解是一种非常有效的矩阵分布方法，但这不是唯一的方法。
特别是，块数据分布（将矩阵分解为 procrows x process 个子矩阵）有点不灵活。如果矩阵大小不能被一行或一列中的进程数整除——通常你无法控制矩阵的大小，并且 procrows/proccols 只能有一定的灵活性——你最终可能会出现严重的负载平衡问题。此外，有时能够 "over decompose" 解决问题非常方便；将其分解成比您的任务更多的部分。特别是，对于 MPI，由于每个任务都是一个进程，因此有时能够为每个进程运行多个子矩阵很有用，这样您就可以通过线程处理这种额外的并行级别（大多数内置单进程线性代数库）。
获得最大 负载平衡灵活性并获得最高程度的可用进程间并行性的方法是纯循环分布。在 1d 循环分布中，假设将 15 个项目分配给 4 个处理器，处理器 1 将获得项目 1，处理器 2 将获得项目 2，处理器 3 将获得项目 3，处理器 4 将获得项目 4，然后处理器 1 将获得项目 5，依此类推在;你在处理器之间循环项目。
另一方面，在 1d 块分解中，处理器 1 将获得项目 1-4，处理器 2 将获得 5-9，依此类推。
下面是来自有用 LLNL parallel computing tutorial 的图，每个颜色标记哪个处理器获得了数据区域：
因此，循环分解对于并行性和负载平衡是非常有利的，但对于数据访问来说很糟糕；您希望能够访问以进行线性代数运算的每个相邻数据都是处理器外的。另一方面，块分解最大程度地有利于数据访问；您拥有尽可能大的连续数据块，因此您可以对漂亮的大子矩阵进行矩阵运算；但它对并行性不灵活，并且会在负载平衡方面产生成本。
Block-Cyclic是两者之间的插值；您将矩阵过度分解为块，然后将这些块循环分布在各个进程中。这使您可以调整数据访问连续性和灵活性之间的权衡。如果 block-cyclic block sizes 为 1，则为循环分布；如果它们是 N/procrows 或 N/proccols 你有块分布；但你也可以介于两者之间。
请注意，在 2D 中，原则上您可以沿行和列选择不同的分解，有时如果您的矩阵仅用于一种计算，这很有用；但更常见的情况是所有维度的分解都是相同的，所以当人们说 "block decomposition" 或 "block-cyclic decomposition" 时，他们通常是指所有维度。
Scalapack pages at netlib 上对此有很好的描述。
在处理矩阵的并行分解时，我熟悉块分布，其中我们有（比方说）4 个进程，每个进程都有自己的矩阵子区域：
例如，这里我们有一行中的进程数 (procrows) 等于 2，一列中的进程数 (proccols) 也等于二，并且sub-matrices A_local 如果原始矩阵大小为 N x M.
N/2 x M/2
我正在阅读这个 example，它使用 "block-cyclic" 分布，在这部分：
/* 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 是硬编码的，很好，但是对于读入的矩阵，有一个 header:
Nb and Mb will be the number of rows and columns of the blocks [of the matrix]
我不明白这个； Nb和Mb不完全由N、M、procrows、proccols决定吗？
编辑
从 运行 这个例子我可以看到进程 0 上的子矩阵包含矩阵左上角的所有元素，就像我上面的图片一样，这与 Jonathan 的回答相矛盾.但是，它与 ScaLAPACK 的 Cholesky 配合使用时效果很好。
您在问题中描述的矩阵块分解是一种非常有效的矩阵分布方法，但这不是唯一的方法。
特别是，块数据分布（将矩阵分解为 procrows x process 个子矩阵）有点不灵活。如果矩阵大小不能被一行或一列中的进程数整除——通常你无法控制矩阵的大小，并且 procrows/proccols 只能有一定的灵活性——你最终可能会出现严重的负载平衡问题。此外，有时能够 "over decompose" 解决问题非常方便；将其分解成比您的任务更多的部分。特别是，对于 MPI，由于每个任务都是一个进程，因此有时能够为每个进程运行多个子矩阵很有用，这样您就可以通过线程处理这种额外的并行级别（大多数内置单进程线性代数库）。
获得最大 负载平衡灵活性并获得最高程度的可用进程间并行性的方法是纯循环分布。在 1d 循环分布中，假设将 15 个项目分配给 4 个处理器，处理器 1 将获得项目 1，处理器 2 将获得项目 2，处理器 3 将获得项目 3，处理器 4 将获得项目 4，然后处理器 1 将获得项目 5，依此类推在;你在处理器之间循环项目。
另一方面，在 1d 块分解中，处理器 1 将获得项目 1-4，处理器 2 将获得 5-9，依此类推。
下面是来自有用 LLNL parallel computing tutorial 的图，每个颜色标记哪个处理器获得了数据区域：
因此，循环分解对于并行性和负载平衡是非常有利的，但对于数据访问来说很糟糕；您希望能够访问以进行线性代数运算的每个相邻数据都是处理器外的。另一方面，块分解最大程度地有利于数据访问；您拥有尽可能大的连续数据块，因此您可以对漂亮的大子矩阵进行矩阵运算；但它对并行性不灵活，并且会在负载平衡方面产生成本。
Block-Cyclic是两者之间的插值；您将矩阵过度分解为块，然后将这些块循环分布在各个进程中。这使您可以调整数据访问连续性和灵活性之间的权衡。如果 block-cyclic block sizes 为 1，则为循环分布；如果它们是 N/procrows 或 N/proccols 你有块分布；但你也可以介于两者之间。
请注意，在 2D 中，原则上您可以沿行和列选择不同的分解，有时如果您的矩阵仅用于一种计算，这很有用；但更常见的情况是所有维度的分解都是相同的，所以当人们说 "block decomposition" 或 "block-cyclic decomposition" 时，他们通常是指所有维度。
Scalapack pages at netlib 上对此有很好的描述。