基于八節(jié)點環(huán)形網(wǎng)絡(luò)的任務(wù)映射方法研究＊

王楚越，文萬志

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

0 引言

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

1 相關(guān)工作

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

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

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

圖1 最小二乘法擬合曲線

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

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

表1 節(jié)點Node與Rank對應(yīng)情況

根據(jù)圖2、圖3 及8 節(jié)點環(huán)形網(wǎng)絡(luò)不考慮往返性的特點，可以分析出各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。

求平均值公式如下：

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

最終擬合曲線函數(shù)表達式：

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

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

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

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

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

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

圖2 求最小代價流程圖

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

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

表2 各個節(jié)點分配Rank情況

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

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

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

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

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

圖3 分配方案例圖

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

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

圖4 求解流程圖

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

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

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

表3 原始值與測試值對比

5 結(jié)論

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

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