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

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

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

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

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

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