理解块和块循环矩阵分布

Question

理解块和块循环矩阵分布

9

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

Block Matrix Decomposition

因此，例如，在这里，我们将一行中的进程数（procrows）设置为2，列中的进程数（proccols）也设置为2，如果原始矩阵大小为 N x M，则子矩阵A_local的大小为N/2 x M/2。我正在阅读这个 example，它使用“块循环”分配，在这部分中：

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

我不理解这个，难道 Nb 和 Mb 不完全由 N、M、procrows 和 proccols 确定吗？

编辑

从运行示例中，我可以看到进程0上的子矩阵具有矩阵左上角的所有元素，就像我上面的图片一样，这与Jonathan的答案相矛盾。然而，它在ScaLAPACK的Cholesky中正常工作。

- gsamaras

@VladimirF 我执行了代码，子矩阵是4x4，程序被称为使用cmd参数调用，设置Nb = Mb = 2。感谢您的评论，但至少在这个时候对我来说没有意义。 :/ - gsamaras

嗯，@VladimirF，我无法将所有信息都放在那里，所以我不确定要添加什么。那么，为什么要让它们相同呢？我的意思是，我想要动态的，以便在较小的矩阵中使用更少的进程进行工作。我应该使procrows = Nb吗？另外，您会回答吗？ - gsamaras

1

请选择一个更好的标题。 - Jeff Hammond

1

这不是关于CBLACS、BLACS、MPI或SCALAPACK的问题；而是关于矩阵块循环分布的问题。实际上，通常情况下，行中进程数与块数不同（较小），尽管它们相等也是合法的。 - Jonathan Dursi

抱歉 @JonathanDursi，我不知道！ - gsamaras

显示剩余6条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jonathan Dursi · Accepted Answer

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

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

为了实现最大的负载平衡和最高程度的进程并行性，最好采用纯循环分配。在一维循环分配中，例如将15个项目分配给4个处理器，处理器1将获得项目1，2将获得项目2，3将获得项目3，4将获得4，然后处理器1将获得项目5，以此类推；你需要在处理器之间轮流分配项目。

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

下面是来自有用的LLNL parallel computing tutorial的图示，每种颜色标识哪个处理器获得了数据的区域：

enter image description here

因此，循环分解对于并行性和负载平衡非常有利，但对于数据访问来说则非常糟糕；你希望访问的每个相邻数据块都在处理器之外，无法进行线性代数运算。另一方面，块分解对于数据访问非常有利；你可以获得尽可能大的连续数据块，因此可以对漂亮的大子矩阵进行矩阵运算；但在并行性方面不够灵活，并且在负载平衡方面也会产生成本。

块循环分解是两者之间的插值；你将矩阵过度分解为块，并将这些块循环地分配到进程中。这使你可以调整数据访问连续性和灵活性之间的权衡。如果块循环的块大小为1，则具有循环分布；如果它们为N/procrows或N/proccols，则具有块分布；但你也可以在两者之间任意选择。

请注意，在二维情况下，您原则上可以选择沿行和列的不同分解方式，有时如果您的矩阵只会在一种计算中使用，这可能很有用; 但更常见的情况是在所有维度上分解相同，因此当人们说“块分解”或“块循环分解”时，通常是指在所有维度上。

关于这个的一个很好的描述可以在netlib的Scalapack页面上找到。