王楚越，文萬(wàn)志

(南通大學(xué)信息科學(xué)技術(shù)學(xué)院，江蘇 南通 226000)

0 引言

如今全球高性能計(jì)算機(jī)飛速發(fā)展，由于計(jì)算任務(wù)繁重，采用一定網(wǎng)絡(luò)結(jié)構(gòu)將多臺(tái)計(jì)算機(jī)連接起來(lái)形成高性能計(jì)算機(jī)集群，在不同的計(jì)算機(jī)上運(yùn)行相同的程序，最后需要相互通信。為了提高相連計(jì)算機(jī)之間的通信效率，減少不必要的跳數(shù)，本文從相關(guān)數(shù)據(jù)基礎(chǔ)入手，以八節(jié)點(diǎn)集群環(huán)形網(wǎng)絡(luò)剖析高性能集群上的計(jì)算機(jī)程序運(yùn)行原理，高性能計(jì)算集群（MPI）程序指在每一個(gè)不同的計(jì)算節(jié)點(diǎn)上運(yùn)行同一程序，同時(shí)，每一份程序隨機(jī)分配唯一編號(hào)，每一個(gè)編號(hào)各自所帶功能各不相同。在高性能計(jì)算集群工作的過(guò)程中，編號(hào)Rank1 所屬的節(jié)點(diǎn)會(huì)與其余節(jié)點(diǎn)產(chǎn)生頻繁的通信，但是，除編號(hào)Rank1 所屬節(jié)點(diǎn)外的節(jié)點(diǎn)各自互相獨(dú)立幾乎不需要相互通信。通信過(guò)程中會(huì)產(chǎn)生延遲，節(jié)點(diǎn)與節(jié)點(diǎn)通信需要經(jīng)過(guò)中間節(jié)點(diǎn)中轉(zhuǎn)，產(chǎn)生了跳數(shù)，故延長(zhǎng)會(huì)增大。實(shí)際高性能計(jì)算程序中時(shí)延在總體時(shí)間中的比例很大，故而任務(wù)映射分配是如何合理分配編號(hào)到各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)使得全局計(jì)算代價(jià)最小的問(wèn)題。

1 相關(guān)工作

隨著計(jì)算任務(wù)的重復(fù)性增加，任務(wù)映射的分配優(yōu)化已經(jīng)成為一個(gè)重要問(wèn)題，而將其運(yùn)用到高性能計(jì)算機(jī)集群上提高數(shù)據(jù)交換效率更是一個(gè)最基礎(chǔ)的應(yīng)用。近幾年提出的有關(guān)任務(wù)映射的研究有：PENG 提出的二次雷達(dá)識(shí)別方式研究[1],LI提出的基于任務(wù)映射的暗硅芯片功耗預(yù)算方法[2],LIU 提出的一種面向電動(dòng)汽車(chē)控制的AUTOSAR 可運(yùn)行實(shí)體-任務(wù)映射方法[3]，Benazir 提出的基于滲透計(jì)算的生態(tài)系統(tǒng)高效任務(wù)映射算法[4]，Imran提出的老年患者健康監(jiān)護(hù)系統(tǒng)采用閉環(huán)醫(yī)療環(huán)境下的智能任務(wù)映射機(jī)制[5]。本文提出的基于整數(shù)規(guī)劃的任務(wù)映射研究是研究基于八節(jié)點(diǎn)環(huán)形網(wǎng)絡(luò)，并計(jì)算了當(dāng)多加一條邊之后的最優(yōu)節(jié)點(diǎn)分配方案，對(duì)比其他方式，通信的效率有所提升，并檢驗(yàn)了本文模型具有普適性，這與當(dāng)前的技術(shù)是有所不同的。

2 數(shù)據(jù)分析模型框架

本文的數(shù)據(jù)分析模型框架圖如圖1 所示，本模型主要包含了五個(gè)模塊：數(shù)據(jù)預(yù)處理、最小二乘法擬合、驗(yàn)證擬合結(jié)果、計(jì)算全局最小代價(jià)、迪杰斯特拉算法計(jì)算增加一條邊之后的情況。本文使用excel 軟件對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，利用mastlab語(yǔ)言對(duì)處理好的數(shù)據(jù)進(jìn)行最小二乘法[6]擬合，并窮舉可能的連接方式，根據(jù)得到的某一程序不同Rank之間的通信頻次數(shù)據(jù)，建立數(shù)學(xué)模型設(shè)計(jì)合理的任務(wù)映射策略，利用matlab 語(yǔ)言計(jì)算全局最小代價(jià)，最后通過(guò)迪杰斯特拉算法計(jì)算出增加一條連接邊之后的最優(yōu)的方案，使得網(wǎng)絡(luò)的最大跳數(shù)（直徑）最小。

圖1 最小二乘法擬合曲線(xiàn)

3 優(yōu)化模型建立

Rank間的時(shí)延與hops數(shù)量正相關(guān)，故希望構(gòu)造數(shù)學(xué)模型分析時(shí)延與跳數(shù)的關(guān)系。利用最小二乘法擬合函數(shù)可以清晰地得知時(shí)延與跳數(shù)的函數(shù)關(guān)系。分析各節(jié)點(diǎn)間時(shí)延測(cè)試的原始數(shù)據(jù)記錄數(shù)據(jù)，在原數(shù)據(jù)表中利用Execl 表自帶的函數(shù)TRIMMEAN()將相同對(duì)應(yīng)的Rank的不同循環(huán)次數(shù)所得的時(shí)延去掉最大值、最小值，加和求平均，保證數(shù)據(jù)的準(zhǔn)確性和科學(xué)性，并且做相應(yīng)的保存，為最小二乘法擬合做準(zhǔn)備（見(jiàn)表1）。

表1 節(jié)點(diǎn)Node與Rank對(duì)應(yīng)情況

根據(jù)圖2、圖3 及8 節(jié)點(diǎn)環(huán)形網(wǎng)絡(luò)不考慮往返性的特點(diǎn)，可以分析出各Rank間跳數(shù)：R1-R4、R1-R2、R4-R3、R2-R6、R3-R7、R6-R8、R8-R5、R7-R5 的跳數(shù)為1，R1-R3、R1-R6、R4-R7、R4-R2、R3-R5、R7-R8、R5-R6、R8-R2 的跳數(shù)為2，R1-R7、R1-R8、R4-R5、R4-R6、R3-R8、R3-R2、R7-R6、R5-R2 的跳數(shù)為3，R1-R5、R4-R8、R3-R6、R7-R2的跳數(shù)為4。

求平均值公式如下：

利用最小二乘法對(duì)已求得的平均值及其所對(duì)應(yīng)的跳數(shù)進(jìn)行擬合，最小二乘法原理的公式如下：

最終擬合曲線(xiàn)函數(shù)表達(dá)式：

在直觀(guān)判斷的基礎(chǔ)上，選幾種曲線(xiàn)分別擬合，然后比較，選取最小二乘指標(biāo)J 最小的函數(shù)作為最終的數(shù)學(xué)模型。

根據(jù)已得數(shù)據(jù)進(jìn)行代碼求解，通過(guò)對(duì)擬合次數(shù)的調(diào)整，本文進(jìn)行四次擬合，最終選擇最小的最小二乘指標(biāo)值，經(jīng)檢驗(yàn)其誤差為最小，接著借助代碼求解得到結(jié)果和一個(gè)最合適的最小二乘法擬合曲線(xiàn)。

根據(jù)輸出結(jié)果可以得出時(shí)延(L)與跳數(shù)(H)的關(guān)系為：

在實(shí)際的高性能計(jì)算程序中，數(shù)據(jù)交換產(chǎn)生的延遲占據(jù)總體計(jì)算時(shí)間比例是非常大的，如果兩個(gè)頻繁通信Rank所屬的節(jié)點(diǎn)之間延遲較大，而兩個(gè)較少產(chǎn)生通信Rank所屬的節(jié)點(diǎn)之間延遲較小，就會(huì)導(dǎo)致整個(gè)計(jì)算過(guò)程變長(zhǎng)，因此，為了盡可能地減少計(jì)算代價(jià)，本文建立以下數(shù)學(xué)模型。

由于數(shù)據(jù)規(guī)模的有限性，所以選擇用窮舉法對(duì)每一種Rank 的分配情況進(jìn)行對(duì)比求出最小，計(jì)算代價(jià)(cost)=通信頻次×跳數(shù)，公式如下：

考慮到通信頻次往返的相同性，首先根據(jù)計(jì)算代價(jià)（cost）與通信頻次和跳數(shù)的函數(shù)關(guān)系運(yùn)用窮舉法，得出編號(hào)和節(jié)點(diǎn)合理的任務(wù)映射策略，使得全局計(jì)算代價(jià)最小，提高程序的計(jì)算速度。圖2 為求最小代價(jià)rank分配的流程圖。

圖2 求最小代價(jià)流程圖

求解前，先總結(jié)出基于八節(jié)點(diǎn)環(huán)形網(wǎng)絡(luò)各節(jié)點(diǎn)Node 到其他節(jié)點(diǎn)的跳數(shù),利用窮舉法，代碼實(shí)現(xiàn)數(shù)學(xué)模型，得出編號(hào)和節(jié)點(diǎn)合理的任務(wù)映射策略。

本文通過(guò)模型求解可知，全局最小計(jì)算代價(jià)min為2.9514，各節(jié)點(diǎn)分配Rank情況如表2。

表2 各個(gè)節(jié)點(diǎn)分配Rank情況

從前面所得結(jié)論中，我們發(fā)現(xiàn)由于環(huán)形網(wǎng)絡(luò)跳數(shù)與效率呈負(fù)相關(guān)關(guān)系，因此為尋求效率高的最優(yōu)方案，本文建立以下模型。

考慮到要在每個(gè)節(jié)點(diǎn)上增加額外一條邊并保持節(jié)點(diǎn)的數(shù)目不變的條件下可以假設(shè)0-1 變量，xij表示節(jié)點(diǎn)i與節(jié)點(diǎn)j是否相連，構(gòu)造0-1整數(shù)規(guī)劃模型，利用Dijkstra算法，找尋某一網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中某一點(diǎn)到其他所有點(diǎn)的最短路徑中的最大跳數(shù)，并對(duì)比每一個(gè)結(jié)構(gòu)找到每一張圖的最短路徑中的最大跳數(shù)中的最小值，以尋求最優(yōu)方案，得到網(wǎng)絡(luò)的最大跳數(shù)的最小數(shù)學(xué)模型。

由于所求為跳數(shù)的最小值，首先基于0-1 整數(shù)規(guī)劃模型創(chuàng)建如下表達(dá)式：

此題可抽象為尋找圖中從某一點(diǎn)到其他所有點(diǎn)的最短路徑求解的圖論問(wèn)題，因此本文選擇基于Dijkstra算法，計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。以起始點(diǎn)為中心，向外層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止，其時(shí)間復(fù)雜度為O（n2），并采用貪心算法的策略求解此類(lèi)問(wèn)題。

根據(jù)上述表達(dá)式構(gòu)建鄰接矩陣，本文取其中一種情況作為例子展現(xiàn)鄰接矩陣的構(gòu)造，如圖3所示。

圖3 分配方案例圖

其鄰接矩陣對(duì)應(yīng)如下：

圖4為求解流程圖，首先，通過(guò)窮舉法依次列出所有鄰接矩陣的情況，此時(shí)在已知鄰接矩陣的條件下，通過(guò)遍歷已知圖的所有路徑，運(yùn)用dis 數(shù)組記錄到第i點(diǎn)的最短路徑，然后在循環(huán)中進(jìn)行大小的比較判定。同時(shí)，利用已初始化為零的mark 數(shù)組作為標(biāo)記數(shù)組，判斷是否已經(jīng)遍歷過(guò)，最終輸出最優(yōu)分配方案。

圖4 求解流程圖

從中可以得出在八節(jié)點(diǎn)集群環(huán)形網(wǎng)絡(luò)中，最大跳數(shù)（直徑）的最小值為2。

4 結(jié)果分析與檢驗(yàn)

基于已歸納完成的數(shù)學(xué)模型，將原始數(shù)據(jù)輸入測(cè)試模型的準(zhǔn)確性，測(cè)試結(jié)果數(shù)據(jù)見(jiàn)表3。

表3 原始值與測(cè)試值對(duì)比

5 結(jié)論

本文提出了一種基于八節(jié)點(diǎn)環(huán)形網(wǎng)絡(luò)的任務(wù)映射分配優(yōu)化問(wèn)題，使用了最小二乘法、數(shù)據(jù)擬合、迪杰斯特拉算法、整數(shù)規(guī)劃等方法，對(duì)所搜集到的數(shù)據(jù)進(jìn)行整合計(jì)算，并給出網(wǎng)絡(luò)節(jié)點(diǎn)的最優(yōu)分配方案，最終通過(guò)將原本已知數(shù)據(jù)帶入求出的表達(dá)式對(duì)比原始數(shù)據(jù)，發(fā)現(xiàn)數(shù)據(jù)吻合度高達(dá)99%，驗(yàn)證了本文的模型具有普適性，網(wǎng)絡(luò)節(jié)點(diǎn)的最優(yōu)方案求得全局最小計(jì)算代價(jià)min 為2.9514，對(duì)比原本其他方案有明顯提升，驗(yàn)證了本文方法的有效性。

本文的實(shí)驗(yàn)雖然具有一定的實(shí)際數(shù)據(jù)的支撐，但是基于八節(jié)點(diǎn)環(huán)形網(wǎng)絡(luò)還有更為復(fù)雜的計(jì)算過(guò)程，本文的全局最小計(jì)算代價(jià)還有進(jìn)一步提升空間，下一步將著手于提升整體方法的簡(jiǎn)化性，進(jìn)一步提升八節(jié)點(diǎn)環(huán)形網(wǎng)絡(luò)計(jì)算效率，從而使此方法具有普適性。