分区，以与负载平衡

Question

并行计算一个lifegame状方案考虑在一个m * n个矩阵lifegame样计算，它需要O（m * n个）开发每个周期。
我将使用Pthread和MPI将此程序修改为并行版本。最简单的方法是静态分区，这意味着分割m行到t任务，每个任务处理一个m/t * n矩阵。 （t代表线程或进程的数量）
但是，此解决方案的负载平衡不佳。一个任务可能不处理任何事情，而另一个任务则必须计算几乎满的矩阵。
我首先想到的，使这个计算多个负载均衡是这样的：

1. 保持一个M * 1数组来存储多少个元素是每一行英寸
2. 扫描测试用例后，为每个任务分配i * n矩阵。 矩阵中的元素应该等于其他任务。 同时存储每个任务中的元素数量（此处需要一个t * 1数组）
3. 每个周期后，重新分配绑定到每个任务的矩阵。这将需要O（t * m）。

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

Answer 1

计算m*n，它会给你的细胞数量。如果您想将其分割成t字段，则每个字段都需要有m*n/t个单元格，或者是一个正方形，每个边长为sqrt(m*n/t)。

我认为做负载平衡的最简单方法是创建一个工作队列，将矩阵切割成多于t块，并让每个工作人员在完成第一个工作时获取新工作（或者，如果你有网络延迟，有一个小的本地缓存并保持填充状态）。

如果你这样做，由于四舍五入，上面的方法可能不会使所有方块的尺寸完全相同。

Answer 2

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

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