前文（稀疏矩陣的分解和圖）討論了稀疏矩陣和圖的關係。基於稀疏矩陣或者圖的並行計算往往依賴於對圖的分區。今天我們看看如何通過圖的分區來分配計算中的負載。

我們先把負載和圖聯繫起來。這裡的負載可以簡單理解為工作量，也就是完成一定計算需要的一種或者幾種資源的量，比如說CPU時間或者內存數量。我們把計算單元抽象成圖中的每個節點，計算單元之間需要交換的信息抽象成圖中的邊。在並行計算中，我們需要把圖切割成小份，然後把每個小份分配給一組硬體計算資源，比如說一個CPU，或者一個計算節點。為了提高並行計算的效率，對圖的分區主要考慮平衡負載和減少通信量這兩個方面。

首先，我們需要分區後每個子圖的節點數目儘可能相同，這樣每組計算資源就得到了同樣的負載。在更一般的情況下，我們可以對圖中每個節點賦予一個權重，從而通過權重的大小來反映每個節點需要的不同計算負載。我們甚至可以考慮異質計算的情形：每組硬體計算資源有不同的處理能力，我們讓分區後子圖的節點加權求和的結果和處理能力相匹配，從而通過能者多勞來提高整體的效率。我們把平衡負載看做對圖分區的約束。

其次，我們希望每個子圖之間需要交換的信息儘可能少。由於圖中的邊代表計算單元之間傳輸的信息，這也就要求我們在對圖分區的時候切割的邊越少越好。同樣我們也可以給每個邊賦予一個權重來反應單元間需要的不同通信量。我們把減少通信量看做圖分區的目標。

下面我們看一個圖分區的例子。以基於網格的計算為例（比如說有限元），網格的分區要求我們把網格中的單元分區到不同的子區域，同時要求分區邊界處的單元儘可能少從而減少分區間的通信量。我們把網格轉換成分區時對應的圖。網格中每個單元對應圖中的一個節點，我們在相鄰的單元間創建一條邊。從而我們可以通過對圖的分區實現對網格的分區。圖1把一個網格分成了三個分區。在我們的例子中，我們假設每個單元需要同樣的計算，每次切割帶來同樣大小的通信量。

我們再看一個更有意思的例子。實際中，我們的負載平衡約束可能會多於一個。比如我們既需要平衡計算帶來的負載，但同時也需要平衡存儲帶來的開銷。計算也有可能包含多個過程，每個過程之間必須實現同步。比如，在多物理場的計算中，我們可能需要先計算結構的部分，再計算流體的部分。也有可能在完成整體計算之後，在某個感興趣的局部做更詳細的計算。如果我們只考慮總體的負載平衡，那麼有可能無法達到最優分區狀態。圖2示例了兩個不同的計算區域a和b，並給出了兩種不同的分區，其中第一種分區約束一個總體負載平衡，第二種分區有兩個約束，分別對應區域a和b的負載平衡。兩種不同的分區帶來的計算花銷在圖3種進行比較。可以看出考慮區域a和b負載平衡約束的分區優於只考慮單個約束的分區。

是不是感覺有哪裡不對？我們實際上忽略了多個約束對分區間的通信量帶來的影響。不難發現，圖2中有兩個約束的分區帶來的切割比單個約束的切割要長，也就是說分區間的通信量會更大。如果我們把分區當成一個優化過程，約束越多，可能達到的最優目標也會越差。當我們使用更多的分區時，我們傾向於得到一個分別對區域a和b分區的結果。我們把圖2中的網格分成6個分區，結果如圖4所示。可以看到使用兩個約束的分區會把不連續的單元分配到同一個子區域中。實際中使用需要權衡負載平衡和分區間的通信量。

最後強調一點的是，精確求解有最小切割的分區在理論是不可計算的。好在我們可以實現某些近似演算法，這些近似演算法在實際使用中也取得了較好的效果，具體可以參見METIS（本文中例子即使用METIS實現）和SCOTCH。總的來說，分區演算法本身的並行效率和質量還有待提高，尤其它是另外一些重要演算法的基礎，比如說稀疏矩陣分解中對變數的排序（稀疏矩陣的分解和圖(2)），這一步往往是約束直接求解並行效率的瓶頸之一。

推薦閱讀：