分區，以與負載平衡

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

僅使用大矩陣並不是處理生命遊戲的最佳方式。由於活細胞趨於稀疏，添加活細胞列表可讓您不浪費時間在所有空白區域。

您可以將工作列表的各個部分分配給線程。