0

考虑在m*n矩阵上进行类似生活游戏的计算，开发每个循环需要O(m*n) 。
我将使用 Pthread 和 MPI 将此程序修改为并行版本。最简单的方法是静态分区，这意味着将m行拆分为t个任务，每个任务处理一个m/t * n矩阵。（t代表线程或进程的数量）
但是，这种解决方案的负载平衡并不好。一个任务可能什么都不处理，而另一个任务必须计算一个几乎满的矩阵。
我的第一个想法是使这种计算更加负载平衡是这样的：

  1. 维护 am*1 数组来存储每行有多少个元素。
  2. 扫描测试用例后，为每个任务分配 i*n 矩阵。矩阵中的元素应该等于其他任务。同时存储每个任务中的元素个数。（这里需要at*1数组）
  3. 在每个循环之后，重新分配绑定到每个任务的矩阵。这样做需要 O(t*m)。

这会将重新分配时间从O(m*n)减少到O(t*m)。我的第一个问题是我可以更快地重新分配吗？
其次，当计算矩阵“边缘”上的元素时，任务必须与附近的任务进行通信，这在 MPI 中可能需要相当长的时间。为了减少这种情况，我想我可以将原点矩阵分成几个矩形而不是细长的正方形。但是我不知道怎么做，有没有算法名称的关键字供我搜索？
谢谢你。

4

2 回答 2

2

仅使用大矩阵并不是处理人生游戏的最佳方式。由于活细胞往往是稀疏的，添加一个仅包含活细胞的列表可以让您不必在所有空白区域浪费时间。

您可以将工作列表的部分分配给线程。

于 2013-05-05T13:50:25.373 回答
1

计算m*n，它将为您提供单元格的数量。如果要将其拆分为t字段，则每个字段都需要有m*n/t单元格，或者是每边sqrt(m*n/t)长的正方形。

我认为进行负载平衡的最简单方法是创建一个工作队列，将矩阵切割成不仅仅是 t 个部分，并让每个工作人员在第一个工作完成后获取一个新工作（或者，如果你有网络延迟，有一个小的本地缓存并保持它被填满）。

如果你这样做，由于四舍五入，上述方法可能不会使所有正方形的大小完全相同，这也无关紧要。

于 2013-05-05T11:45:07.970 回答