c++ - 将类似生活游戏的程序分区以进行负载平衡的并行计算

Question

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

1. Maintain a m*1 array to store how many elements is in each row.
2. After scanning the testcase, allocate i*n matrix for each task. The elements in the matrix should equal to the others tasks. Store the number of elements in each task at the same time.(need a t*1 array here)
3. After each cycle, reallocate the matrix bound to each task. It will take O(t*m) to do this.

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

Answer 1

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

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