基于圖剖分和圖排序的負載平衡算法研究.pdf

1、隨著高性能計算機系統(tǒng)的快速發(fā)展，并行計算已經成為科學和工程計算的基本支撐技術。負載平衡問題是并行計算研究的基本問題。尤其在數百個處理器以上規(guī)模的并行計算中，負載平衡問題是影響并行程序性能的關鍵。
　　長期以來，負載平衡算法的研究比較廣泛。但是，結合當前高性能計算機的發(fā)展和實際應用的需求，并行計算對負載平衡提出了新的要求。一方面，新的數值計算方法和高性能算法具有新的負載特征，需要構造相應的新的負載平衡算法;另一方面，許多重要的關鍵應

2、用（例如:武器物理、天氣預報、流體力學、慣性約束聚變等）需要在數百上千個處理器上進行并行模擬，而這種大規(guī)模應用對負載平衡研究提出了新的挑戰(zhàn)，很多現有的負載平衡算法無法適應。因此，結合高性能計算機系統(tǒng)的特征和實際應用特點，設計適應數百上千個處理器的負載平衡算法是當前并行計算研究的一個重要前沿課題。
　　負載平衡算法的研究需要結合實際應用的負載特征來進行。根據負載分布的特征，并行應用可分別用靜態(tài)負載模型、動態(tài)負載模型、多約束負載模型等

3、模型來描述，負載平衡算法可以針對不同的模型來進行。本文針對這些模型，在數百上千個處理器上，對負載平衡算法進行了系統(tǒng)深入的研究，取得了如下創(chuàng)新成果:
　　一、針對實際應用中具有普適性的靜態(tài)負載模型，本文使用圖排序的思想，構造了基于最小線性排序的負載平衡算法。本文算法作為一種最小線性排序算法，與現有其他算法相比，執(zhí)行速度較快，排序質量較高。在國產MPP并行機上，上千個處理器上的并行數值實驗驗證了算法的有效性。
　　二、針對復雜數

4、值模擬應用中普遍存在的動態(tài)負載不平衡問題，在現有動態(tài)負載模型的基礎上，提出了圖重排序模型，該模型能更好地描述負載的動態(tài)特征。在此基礎上，構造了基于圖重排序的負載平衡算法。新算法彌補了在處理動態(tài)負載模型時，基于最小線性排序的算法不能顯式控制數據遷移開銷這個缺點。數值試驗說明了圖重排序模型和動態(tài)負載平衡算法的有效性。
　　三、多約束負載模型來源于多個方面，一方面現代高性能計算機的多級存儲結構中速度和容量的差異要求應用程序同時平衡計算量

5、與存儲需求，另一方面多階段模擬的多個計算過程需要同時平衡計算量。本文使用迭代法的思想，構造了一維多約束負載平衡算法。理論分析和上千個處理器上的并行數值實驗驗證了算法的有效性。這種算法與圖排序算法結合，可以處理一般的多約束負載模型，從而推廣了基于圖排序的負載平衡算法的使用范圍。
　　四、自適應結構網格并行計算是科學計算中的重要方法。它的內在多尺度性造成其負載平衡問題具有巨大的難度。本文構造了一種刻畫自適應結構網格并行計算負載特征的模