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

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

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

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

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

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