了解块和块循环矩阵分布

Question

在处理矩阵的并行分解时,我熟悉块分布,我们有(比方说)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将是[矩阵]块的行数和列数

我不明白这一点; 不Nb与Mb完全由N,M,procrows和proccols确定？

---

编辑

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

Answer 1

正如您在问题中描述的那样阻止矩阵的分解是分配矩阵的一种非常有效的方法,但它不是唯一的方法.

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

获得方式最灵活的负载均衡,并有进程间的并行度最高的面世,是一场纯粹的环状分布.在1d循环分布中,比如在4个处理器之间划分15个项目,处理器1将获得项目1,2将获得项目2,3将获得项目3,4将获得4,然后处理器1将获得项目5,因此上; 你在处理器上循环项目.

另一方面,在1d块分解中,处理器1将获得项目1-4,处理器2将获得5-9,依此类推.

下面是有用的LLNL并行计算教程中的数字,每个颜色标记哪个处理器得到了数据的一个区域:

因此循环分解对并行性和负载均衡最大,但对数据访问来说却很糟糕 ; 您希望能够访问的每个相邻数据都可以执行线性代数操作.另一方面,块分解对数据访问最有利; 你有尽可能大的连续数据块,所以你可以在漂亮的大子矩阵上进行矩阵运算; 但它对于并行性来说是不灵活的,并且在负载平衡方面可能会花费.

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

请注意,在2D中,您原则上可以选择沿行和列的不同分解,有时如果您的矩阵仅用于某种​​计算,则这种分解很有用; 但更常见的情况是所有维度的分解是相同的,因此当人们说"块分解"或"块循环分解"时,它们通常意味着沿着所有维度.

对此的一个很好的描述是在netlib的Scalapack页面上.