7

在处理矩阵的并行分解时，我熟悉块分布，我们有（比如说）4 个进程，每个进程都有自己的矩阵子区域：

块矩阵分解

因此，例如在这里我们有一行中的进程数 ( procrows) 等于 2，一列中的进程数 ( proccols) 也等于 2，如果原始矩阵大小为，则子矩阵A_local的大小为。N/2 x M/2N x M

我正在阅读这个使用“块循环”分布的例子，在这一部分：

/* 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 和 Mb 将是 [矩阵] 块的行数和列数

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

编辑

从运行示例中，我可以看到进程 0 上的子矩阵具有矩阵左上角的所有元素，就像我上面的图片一样，这与乔纳森的回答相矛盾。但是，它适用于 ScaLAPACK 的 Cholesky。

4

1 回答 1

12

您在问题中描述的矩阵块分解是分配矩阵的一种完全有效的方法，但这不是唯一的方法。

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

获得最大的负载平衡灵活性并获得最高程度的进程间并行性的方法是纯循环分布。在 1d 循环分布中，例如在 4 个处理器之间划分 15 个项目，处理器 1 将获得项目 1，2 将获得项目 2，3 将获得项目 3，4 将获得 4，然后处理器 1 将获得项目 5，以此类推在; 你在处理器之间循环项目。

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

下面是有用的LLNL 并行计算教程中的一个图，每个颜色标记了哪个处理器获得了一个数据区域：

在此处输入图像描述

所以循环分解对并行性和负载均衡有最大的好处，但对数据访问却很糟糕；您希望能够访问以进行线性代数运算的每个相邻数据都在处理器外。另一方面，块分解最有利于数据访问；你有尽可能大的连续数据块，所以你可以对好的大子矩阵进行矩阵运算；但它对于并行性不灵活，并且在负载平衡方面可能会产生成本。

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

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

netlib 的 Scalapack 页面上有一个很好的描述。

于 2015-06-29T13:17:31.607 回答