分布式異構(gòu)集群中節(jié)點(diǎn)優(yōu)先級(jí)調(diào)優(yōu)算法*

胡亞紅，邱圓圓，毛家發(fā)

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院(軟件學(xué)院)， 浙江 杭州 310023)

Spark是專為大數(shù)據(jù)處理而設(shè)計(jì)的快速通用的計(jì)算引擎，但是它原生的資源調(diào)度策略建立在集群同構(gòu)的基礎(chǔ)之上[1-3]。隨著硬件的更迭及高性能部件的引入，集群節(jié)點(diǎn)的性能逐漸變得各不相同，集群的異構(gòu)性日漸凸顯[4-5]。Liang等[6]研究發(fā)現(xiàn)，同構(gòu)環(huán)境下的資源分配策略不能考慮負(fù)載的特性，從而導(dǎo)致原生的Spark調(diào)度策略在異構(gòu)環(huán)境中不能充分發(fā)揮集群的性能。

目前學(xué)者們針對(duì)如何提升Spark和Hadoop異構(gòu)集群性能進(jìn)行了許多研究[7-9]。鄭曉薇等[10]指出Hadoop集群采用原生的任務(wù)調(diào)度方法，負(fù)載不均衡問(wèn)題常有出現(xiàn)，因此提出了基于節(jié)點(diǎn)能力的Hadoop集群自適應(yīng)任務(wù)調(diào)度方法，即根據(jù)節(jié)點(diǎn)的歷史和當(dāng)前負(fù)載狀態(tài)，以節(jié)點(diǎn)性能、任務(wù)特征等作為節(jié)點(diǎn)任務(wù)量調(diào)度分配的依據(jù)，自動(dòng)地調(diào)整任務(wù)量。Gunasekaran等[11]考慮Hadoop異構(gòu)集群特性，提出使用時(shí)間約束啟動(dòng)模型策略以減少任務(wù)的等待和啟動(dòng)時(shí)間。Xu等[12]研究了異構(gòu)的Hadoop集群下集群節(jié)點(diǎn)的動(dòng)態(tài)變化和負(fù)載情況，提出采用動(dòng)態(tài)調(diào)整的調(diào)度算法以實(shí)現(xiàn)集群性能優(yōu)化。雖然都是大數(shù)據(jù)處理框架，但是Spark和Hadoop在性能研究方面存在著較大差異，Hadoop集群中所采用方法不完全適用于Spark集群。因此，對(duì)于提升異構(gòu)Spark集群性能的研究非常重要[13-14]。

樊森[15]考慮異構(gòu)Spark集群下的Task調(diào)度問(wèn)題,提出以最小化最大完工時(shí)間為優(yōu)化目標(biāo)，針對(duì)具有DAG偏序關(guān)系的Job和Stage以及同一Stage中并行Task之間的問(wèn)題特點(diǎn)和特征建立數(shù)學(xué)模型，優(yōu)化了Task調(diào)度算法?；赟park on Yarn模式，Wang等[16]提出了考慮作業(yè)截止日期和值密度的硬實(shí)時(shí)調(diào)度算法以提升集群性能。Kuzmanovska等[17]則基于多個(gè)數(shù)據(jù)處理框架，提出用Mesos反饋控制器動(dòng)態(tài)調(diào)整框架權(quán)重以進(jìn)行任務(wù)調(diào)度。楊志偉等[18]指出Spark集群默認(rèn)的任務(wù)調(diào)度在異構(gòu)環(huán)境中未考慮節(jié)點(diǎn)能力差異，提出了異構(gòu)Spark集群下自適應(yīng)任務(wù)調(diào)度策略。該算法監(jiān)測(cè)節(jié)點(diǎn)的負(fù)載及資源利用率，利用監(jiān)測(cè)得到的參數(shù)動(dòng)態(tài)地調(diào)整節(jié)點(diǎn)的任務(wù)分配權(quán)重。徐家俊等[19]指出現(xiàn)有的調(diào)度策略對(duì)于異構(gòu)Spark集群效果不佳，提出了綜合考慮任務(wù)復(fù)雜度、節(jié)點(diǎn)性能及節(jié)點(diǎn)資源使用情況等因素的分層調(diào)度策略?；诩寒悩?gòu)導(dǎo)致計(jì)算資源不均衡、Spark現(xiàn)有的任務(wù)調(diào)度未考慮集群的異構(gòu)性以及節(jié)點(diǎn)資源的利用情況，胡亞紅等[20]提出了基于節(jié)點(diǎn)優(yōu)先級(jí)的Spark動(dòng)態(tài)自適應(yīng)調(diào)度算法。

神經(jīng)網(wǎng)絡(luò)在特征提取和建模方面具有獨(dú)特優(yōu)勢(shì)[21-24]。Zhang等[25]將BP神經(jīng)網(wǎng)絡(luò)(back propagation neural network)應(yīng)用到云計(jì)算環(huán)境中以進(jìn)行實(shí)時(shí)調(diào)度，實(shí)驗(yàn)證明了算法的有效性。文獻(xiàn)[26-27]分別在Spark環(huán)境中使用神經(jīng)網(wǎng)絡(luò)完成了電壓偏差預(yù)測(cè)和交通網(wǎng)絡(luò)流量預(yù)測(cè)，均取得了很好的效果。越來(lái)越多的研究將Spark和深度學(xué)習(xí)連接在一起，譬如Moritz等針對(duì)現(xiàn)有流行的批處理計(jì)算框架不支持分布式深度學(xué)習(xí)系統(tǒng)和密集型工作負(fù)載的問(wèn)題，提出了專用于訓(xùn)練深度網(wǎng)絡(luò)的Spark框架SparkNet[28]。SparkNet能夠大幅提高深度網(wǎng)絡(luò)的訓(xùn)練效率。

現(xiàn)有研究工作在進(jìn)行集群資源分配和任務(wù)調(diào)度時(shí)多是基于節(jié)點(diǎn)的性能優(yōu)先級(jí)進(jìn)行。為了得到合理有效的節(jié)點(diǎn)優(yōu)先級(jí)，通常需要建立集群節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)體系，并確定各評(píng)價(jià)指標(biāo)的權(quán)重。指標(biāo)的權(quán)重對(duì)于計(jì)算節(jié)點(diǎn)優(yōu)先級(jí)起著至關(guān)重要的作用。理想的指標(biāo)權(quán)重能夠賦予節(jié)點(diǎn)適合的優(yōu)先級(jí)，有助于進(jìn)行有效的集群資源調(diào)度，從而提升集群性能，減少用戶作業(yè)執(zhí)行時(shí)間。為了更直觀地展示評(píng)價(jià)指標(biāo)的權(quán)重對(duì)于集群性能的影響，本文采用文獻(xiàn)[20]中的算法，進(jìn)行了一組對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)僅調(diào)整了節(jié)點(diǎn)性能指標(biāo)體系中靜態(tài)因素和動(dòng)態(tài)因素的權(quán)重，其他實(shí)驗(yàn)配置完全一致。實(shí)驗(yàn)結(jié)果如表1所示。

表1 節(jié)點(diǎn)評(píng)價(jià)指標(biāo)權(quán)重變化對(duì)任務(wù)完成時(shí)間的影響

從表1可以看出，當(dāng)節(jié)點(diǎn)評(píng)價(jià)指標(biāo)權(quán)重發(fā)生變化時(shí)，集群完成相同用戶作業(yè)的時(shí)間差距較為明顯。因此非常有必要研究如何更為合理地確定節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)體系中各指標(biāo)的權(quán)重，從而完成節(jié)點(diǎn)優(yōu)先級(jí)的優(yōu)化。

目前對(duì)于優(yōu)先級(jí)評(píng)價(jià)指標(biāo)體系中各指標(biāo)的權(quán)重進(jìn)行優(yōu)化的研究相對(duì)較少。層次分析法[29](analytic hierarchy process，AHP)是一種經(jīng)典的權(quán)重計(jì)算方法，但是它的計(jì)算結(jié)果存在主觀性較強(qiáng)的缺點(diǎn)。節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)權(quán)重的確定是比較繁雜的非線性工程，需要建立權(quán)重的學(xué)習(xí)機(jī)制，可以通過(guò)具有學(xué)習(xí)、記憶、歸納、容錯(cuò)及自適應(yīng)能力的人工神經(jīng)網(wǎng)絡(luò)[30-31](artificial neural network, ANN)予以解決。因此，本文實(shí)驗(yàn)平臺(tái)基于中央處理器(central processing unit, CPU)異構(gòu)進(jìn)行驗(yàn)證和說(shuō)明，文中將層次分析法和BP神經(jīng)網(wǎng)絡(luò)[32-33]有機(jī)地結(jié)合在一起，提出了基于AHP-BP神經(jīng)網(wǎng)絡(luò)模型[34]的集群節(jié)點(diǎn)優(yōu)先級(jí)的優(yōu)化算法。該算法首先采用AHP確定節(jié)點(diǎn)優(yōu)先級(jí)的評(píng)價(jià)指標(biāo)體系，并計(jì)算出各指標(biāo)的初始權(quán)重。然后建立BP神經(jīng)網(wǎng)絡(luò)評(píng)價(jià)模型并進(jìn)行網(wǎng)絡(luò)訓(xùn)練。訓(xùn)練好的BP神經(jīng)網(wǎng)絡(luò)能夠提供更加科學(xué)有效的指標(biāo)權(quán)重以優(yōu)化節(jié)點(diǎn)的優(yōu)先級(jí)。

1 構(gòu)建Spark集群節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)體系

AHP是一種解決多因素多目標(biāo)問(wèn)題的決策方法，由美國(guó)運(yùn)籌學(xué)家Saaty教授于20世紀(jì)70年代首先提出[35-36]。它是將定性與定量相結(jié)合的系統(tǒng)分析方法，是一種能將復(fù)雜系統(tǒng)的決策思維過(guò)程模型化、數(shù)量化的方法。AHP根據(jù)系統(tǒng)多目標(biāo)要求，把多目標(biāo)分解成多層次因素，依據(jù)因素間關(guān)系建立層次結(jié)構(gòu)，進(jìn)行因素間重要性的兩兩對(duì)比，結(jié)合專家打分進(jìn)行各因素重要性排序從而確定各因素的權(quán)重。

1.1 建立遞階層次結(jié)構(gòu)

AHP的工作流程如圖1所示。

圖1 層次分析法的工作流程Fig.1 Workflow of AHP

根據(jù)前人文獻(xiàn)進(jìn)行綜合分析，本文建立了集群節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)體系，包括2個(gè)評(píng)價(jià)因素、8個(gè)評(píng)價(jià)指標(biāo)(屬性)。

1)靜態(tài)因素(B1)：

①CPU速度(C1) : CPU的時(shí)鐘頻率。計(jì)算機(jī)的運(yùn)行速度一般可以由它決定。

②CPU核數(shù)(C2)：一個(gè)CPU核心的數(shù)目。在其他配置相同的條件下，核心數(shù)目越多，CPU的運(yùn)轉(zhuǎn)速度越快，機(jī)器的性能越好。

③內(nèi)存容量(C3)：節(jié)點(diǎn)內(nèi)存的大小會(huì)對(duì)Spark的運(yùn)行效率起到?jīng)Q定性作用。

④磁盤容量(C4)：集群運(yùn)行過(guò)程中進(jìn)行數(shù)據(jù)的存儲(chǔ)及軟件的存儲(chǔ)。

2)動(dòng)態(tài)因素(B2)：

①CPU剩余率 (C5)：表示節(jié)點(diǎn)核心的忙閑情況。CPU剩余率過(guò)低則該節(jié)點(diǎn)可用資源很少，需要等資源釋放后才可以繼續(xù)任務(wù)的運(yùn)行。

②內(nèi)存剩余率 (C6)：內(nèi)存對(duì)于集群運(yùn)行起著極其重要的作用。

③磁盤剩余率 (C7)：磁盤用于數(shù)據(jù)存儲(chǔ)。

④CPU負(fù)載 (C8)：在一段時(shí)間內(nèi)CPU正在處理及等待CPU處理的進(jìn)程數(shù)之和，即CPU使用隊(duì)列長(zhǎng)度。

節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)體系為三層結(jié)構(gòu)模型：目標(biāo)層(A)、一級(jí)指標(biāo)層(B)和二級(jí)指標(biāo)層(C)，如圖2所示。

圖2 節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)遞階層次結(jié)構(gòu)Fig.2 Hierarchical structure of node priority evaluation

1.2 計(jì)算權(quán)重

1.2.1 構(gòu)造判斷矩陣

經(jīng)過(guò)專家打分，得到各判斷矩陣，如表2～4所示。表2給出了一級(jí)指標(biāo)判斷矩陣A-B。

表2 一級(jí)指標(biāo)判斷矩陣A-B

二級(jí)指標(biāo)的判斷矩陣分別為B1-C(如表3所示)和B2-C(如表4所示)。

表3 二級(jí)指標(biāo)判斷矩陣B1-C

表4 二級(jí)指標(biāo)判斷矩陣B2-C

計(jì)算指標(biāo)單權(quán)重，求得二級(jí)指標(biāo)層C對(duì)一級(jí)指標(biāo)層B1的權(quán)重向量為：

=[0.113，0.173，0.641，0.073]T

(1)

為進(jìn)行矩陣的一致性檢驗(yàn)，計(jì)算出一致性指標(biāo)CI=0.015 3。表5給出了不同階數(shù)的矩陣所對(duì)應(yīng)的平均隨機(jī)一致性指標(biāo)RI的標(biāo)準(zhǔn)值。

表5 平均隨機(jī)一致性指標(biāo)RI

四階判斷矩陣對(duì)應(yīng)的RI為0.90，則一致性比率CR=CI/RI=0.017<0.10，滿足一致性檢驗(yàn)。同理可求得另外兩個(gè)權(quán)重向量如下：

(2)

(3)

這兩個(gè)向量都滿足一致性檢驗(yàn)。

1.2.2 計(jì)算綜合權(quán)重

使用式(1)～(3)，可以得到各評(píng)價(jià)指標(biāo)對(duì)目標(biāo)層的綜合權(quán)重向量為：

W=[0.033 9, 0.051 9,0.192 3,0.021 9,

0.109 2,0.295 4,0.054 6,0.241 5]T

(4)

此向量也滿足一致性檢驗(yàn)。

2 建立Spark集群節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)神經(jīng)網(wǎng)絡(luò)模型

由于需要通過(guò)專家打分確定判斷矩陣，AHP存在一定的主觀性和誤差?？梢岳萌斯ど窠?jīng)網(wǎng)絡(luò)對(duì)AHP得到的權(quán)重進(jìn)行優(yōu)化，從而獲得更加客觀有效的節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)體系。

2.1 BP神經(jīng)網(wǎng)絡(luò)

人工神經(jīng)網(wǎng)絡(luò)[37-38]是非線性、自適應(yīng)、自組織的網(wǎng)絡(luò)系統(tǒng)。本文采用的神經(jīng)網(wǎng)絡(luò)模型為BP神經(jīng)網(wǎng)絡(luò)[39-42]，它是一種誤差反向傳播的多層神經(jīng)網(wǎng)絡(luò)，是理論研究比較成熟、應(yīng)用最為廣泛的神經(jīng)網(wǎng)絡(luò)之一。圖3給出了BP網(wǎng)絡(luò)模型。

圖3 BP網(wǎng)絡(luò)模型Fig.3 BP network model

2.2 BP神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法

BP網(wǎng)絡(luò)的學(xué)習(xí)算法框架如圖4所示。

圖4 BP網(wǎng)絡(luò)學(xué)習(xí)算法框架Fig.4 Framework of BP network learning algorithm

Step1：設(shè)置初始參數(shù)wij和θ。wij表示輸入層與隱含層的權(quán)系數(shù)或隱含層與輸出層的權(quán)系數(shù)，i表示輸入層或隱含層輸入節(jié)點(diǎn)，j表示輸出節(jié)點(diǎn)，θ表示隱含層各神經(jīng)元偏置或輸出層各神經(jīng)元偏置。初始設(shè)置范圍為[0,1]。設(shè)定計(jì)算精度值ε和最大迭代次數(shù)M。

Step2：將數(shù)據(jù)樣本添加至網(wǎng)絡(luò)中，利用式(5)計(jì)算輸出值yj：

yj=(1+e-x)-1

(5)

Step3：將已知輸出數(shù)據(jù)dj與計(jì)算得到的輸出數(shù)據(jù)進(jìn)行差值計(jì)算，得到兩者之間的誤差Δj=dj-yj,再根據(jù)式(6)計(jì)算調(diào)整權(quán)系數(shù)的調(diào)整量：

Δwij=ησjxi

(6)

其中，η為比例系數(shù)，即學(xué)習(xí)率，范圍為[0,1]，一般設(shè)置為0.01或者0.05，具體取值根據(jù)實(shí)際情況決定。在神經(jīng)網(wǎng)絡(luò)中可通過(guò)逐步提高η的值進(jìn)行訓(xùn)練，以得到穩(wěn)定且精度較高的網(wǎng)絡(luò)。σj表示輸出誤差相關(guān)值。

σj=ηj(1-yj)(dj-yj)=ηjΔj(1-yj)

(7)

BP神經(jīng)網(wǎng)絡(luò)的反向誤差傳播使用式(8)進(jìn)行：

(8)

其中，m表示輸出層神經(jīng)元數(shù)。

各層神經(jīng)元的權(quán)重調(diào)整后結(jié)果用式(9)計(jì)算得到(其中t表示學(xué)習(xí)次數(shù))：

wij(t)=wij(t-1)+Δwij

(9)

BP學(xué)習(xí)算法不斷迭代，對(duì)wij值進(jìn)行調(diào)整，直到輸出的誤差小于允許的誤差值ε或是達(dá)到迭代次數(shù)M，則網(wǎng)絡(luò)模型訓(xùn)練成功。BP算法通過(guò)迭代算法求得權(quán)重。

2.3 AHP-BP神經(jīng)網(wǎng)絡(luò)模型

基于AHP-BP神經(jīng)網(wǎng)絡(luò)模型的Spark集群節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)算法包括三個(gè)部分：數(shù)據(jù)獲取和處理、三層BP神經(jīng)網(wǎng)絡(luò)模型的建立、神經(jīng)網(wǎng)絡(luò)訓(xùn)練和節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)權(quán)重的計(jì)算。

2.3.1 數(shù)據(jù)獲取和處理

1)節(jié)點(diǎn)優(yōu)先級(jí)的初步計(jì)算：利用AHP計(jì)算評(píng)價(jià)指標(biāo)體系中各指標(biāo)的初始權(quán)重。

2)節(jié)點(diǎn)實(shí)時(shí)數(shù)據(jù)的獲?。涸赟park集群中進(jìn)行任務(wù)運(yùn)行，同時(shí)利用Ganglia[43-45]實(shí)時(shí)獲取集群節(jié)點(diǎn)的資源數(shù)據(jù)。

4)初始節(jié)點(diǎn)優(yōu)先級(jí)的計(jì)算：使用初始權(quán)重和歸一化后的節(jié)點(diǎn)數(shù)據(jù)計(jì)算出節(jié)點(diǎn)對(duì)應(yīng)的優(yōu)先級(jí)，此優(yōu)先級(jí)作為神經(jīng)網(wǎng)絡(luò)訓(xùn)練樣本的輸出。

2.3.2 三層BP神經(jīng)網(wǎng)絡(luò)模型建立

本文建立的BP神經(jīng)網(wǎng)絡(luò)模型分為三層結(jié)構(gòu)，即輸入層、隱含層和輸出層。通過(guò)不斷迭代訓(xùn)練使其收斂可以得到穩(wěn)定的網(wǎng)絡(luò)結(jié)構(gòu)和參數(shù)。

1)輸入層節(jié)點(diǎn)的選擇：輸入節(jié)點(diǎn)個(gè)數(shù)與評(píng)價(jià)指標(biāo)的個(gè)數(shù)相對(duì)應(yīng)。由圖2可知，評(píng)價(jià)指標(biāo)體系共有8個(gè)評(píng)價(jià)指標(biāo)，因此神經(jīng)網(wǎng)絡(luò)的輸入層節(jié)點(diǎn)數(shù)n=8。

2)輸出層節(jié)點(diǎn)的選擇：節(jié)點(diǎn)的優(yōu)先級(jí)數(shù)值是網(wǎng)絡(luò)的唯一輸出，因此輸出層節(jié)點(diǎn)數(shù)為1，即m=1。使用式(4)給出的權(quán)重可以計(jì)算得到對(duì)應(yīng)的神經(jīng)網(wǎng)絡(luò)輸出值。

3)隱含層節(jié)點(diǎn)的選擇：隱含層節(jié)點(diǎn)的選擇非常關(guān)鍵，因?yàn)樗鼤?huì)極大影響B(tài)P神經(jīng)網(wǎng)絡(luò)的精確度和學(xué)習(xí)效率[46]。然而，到目前為止并沒(méi)有可指導(dǎo)的理論，只能在總結(jié)前人文獻(xiàn)知識(shí)的基礎(chǔ)上，根據(jù)經(jīng)驗(yàn)和問(wèn)題的實(shí)際情況而定。通?？梢允褂檬?10)和式(11)來(lái)獲得隱含層神經(jīng)元數(shù)的大致范圍進(jìn)而確定隱含層的神經(jīng)元數(shù)S。

(10)

(11)

其中，n是輸入層神經(jīng)元數(shù)，m是輸出層神經(jīng)元數(shù)，α是[1,10]之間的整數(shù)。通過(guò)計(jì)算，本文建立的神經(jīng)網(wǎng)絡(luò)模型中隱含層神經(jīng)元數(shù)S的取值范圍為[5,8]。

決定系數(shù)R2能夠評(píng)判神經(jīng)網(wǎng)絡(luò)模型預(yù)測(cè)能力的好壞，因此可用來(lái)確定隱含層神經(jīng)元的數(shù)目。R2的計(jì)算方法如式(12)所示。

(12)

使用式(12)和實(shí)際樣本的實(shí)驗(yàn)測(cè)試結(jié)果，就可以確定合適的隱含層神經(jīng)元數(shù)。隱含層神經(jīng)元數(shù)取值范圍為[5,8]，因此設(shè)定隱含層神經(jīng)元數(shù)分別為5、6、7、8，依次進(jìn)行數(shù)據(jù)訓(xùn)練得到對(duì)應(yīng)網(wǎng)絡(luò)的R2。實(shí)驗(yàn)結(jié)果如表6所示。

表6 隱含層神經(jīng)元數(shù)和對(duì)應(yīng)的R2

由表6可知，當(dāng)隱含層神經(jīng)元數(shù)為5時(shí)，R2=0.89，相比其他神經(jīng)元的取值效果最好，所以本文模型最終選擇5作為隱含層神經(jīng)元數(shù)。圖5(a)為節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)BP網(wǎng)絡(luò)模型，圖5(b) 給出了可視化的網(wǎng)絡(luò)模型搭建過(guò)程。

(a) BP網(wǎng)絡(luò)模型(a) BP network model

2.3.3 網(wǎng)絡(luò)訓(xùn)練和權(quán)重計(jì)算

網(wǎng)絡(luò)模型搭建完成后，需要收集學(xué)習(xí)樣本以進(jìn)行網(wǎng)絡(luò)訓(xùn)練，樣本的選擇對(duì)于網(wǎng)絡(luò)的訓(xùn)練很重要。一般需根據(jù)實(shí)際情況和網(wǎng)絡(luò)大小來(lái)確定合適的樣本數(shù)，過(guò)多或過(guò)少都會(huì)影響訓(xùn)練結(jié)果。依據(jù)本文中BP網(wǎng)絡(luò)結(jié)構(gòu)及Ganglia得到的節(jié)點(diǎn)性能參數(shù)進(jìn)行實(shí)驗(yàn)，再根據(jù)R2的值即可確定最適合的樣本容量。實(shí)驗(yàn)結(jié)果如表7所示。

表7 樣本容量和對(duì)應(yīng)的R2

從表7可以看出，樣本數(shù)取160時(shí)BP神經(jīng)網(wǎng)絡(luò)具有較好的網(wǎng)絡(luò)模型預(yù)測(cè)能力，因此本文中選取160個(gè)樣本進(jìn)行BP網(wǎng)絡(luò)訓(xùn)練。讀取160個(gè)樣本數(shù)據(jù)進(jìn)行量化后隨機(jī)產(chǎn)生訓(xùn)練集和測(cè)試集，兩者比例為15 ∶1，即150個(gè)訓(xùn)練樣本和10個(gè)測(cè)試樣本。設(shè)置訓(xùn)練參數(shù)迭代次數(shù)為6 000，訓(xùn)練要求精度即目標(biāo)誤差為0.001，學(xué)習(xí)率為0.01，最小梯度要求為e-10。進(jìn)行網(wǎng)絡(luò)訓(xùn)練達(dá)到收斂狀態(tài)后獲取網(wǎng)絡(luò)訓(xùn)練權(quán)重?cái)?shù)據(jù)，用矩陣表示如式(13)所示。

式(13)中，權(quán)重矩陣的前8列分別對(duì)應(yīng)輸入層的8個(gè)神經(jīng)元，最后1列對(duì)應(yīng)輸出層神經(jīng)元；矩陣的各行分別對(duì)應(yīng)隱含層的5個(gè)神經(jīng)元。Wij(i=1,2,…,5；j=1,2,…,8)表示第j個(gè)輸入神經(jīng)元與第i個(gè)隱含層神經(jīng)元之間的權(quán)重；Wi9表示輸出神經(jīng)元與第i個(gè)隱含層神經(jīng)元之間的權(quán)重。

獲取的數(shù)據(jù)需要進(jìn)行計(jì)算以得到最終權(quán)重。神經(jīng)網(wǎng)絡(luò)訓(xùn)練后得到的神經(jīng)元權(quán)重表示各神經(jīng)元之間的關(guān)系，為了得到輸入因素和輸出因素之間的關(guān)系，需要對(duì)得到的權(quán)重系數(shù)進(jìn)行分析處理，利用以下指標(biāo)[39-40]進(jìn)行輸入因素和輸出因素關(guān)系的描述。

(13)

1)相關(guān)顯著性系數(shù)：

(14)

2)相關(guān)指數(shù)：

Rij=|(1-e-rij)(1+e-rij)|

(15)

3)絕對(duì)影響系數(shù)：

(16)

其中：i為神經(jīng)網(wǎng)絡(luò)輸入層神經(jīng)元，i=1,2,…,n；j為神經(jīng)網(wǎng)絡(luò)輸出層神經(jīng)元，j=1,2,…,m；k表示神經(jīng)網(wǎng)絡(luò)隱含層神經(jīng)元，k=1,2,…,p；ωjk表示輸出層神經(jīng)元j和隱含層神經(jīng)元k之間的權(quán)重系數(shù)。通過(guò)上述公式求出絕對(duì)影響系數(shù)Sij，即為優(yōu)化的節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)的權(quán)重。

使用式(14)～(16)，得到本文中各指標(biāo)的權(quán)重，如表8所示。

表8 優(yōu)化后的節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)權(quán)重

2.4 SDASA算法簡(jiǎn)介

實(shí)驗(yàn)采用文獻(xiàn)[20]中提出的基于節(jié)點(diǎn)優(yōu)先級(jí)的Spark動(dòng)態(tài)自適應(yīng)調(diào)度算法(Spark dynamic adaptive scheduling algorithm, SDASA) 進(jìn)行任務(wù)調(diào)度，其中集群中各個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)使用BP神經(jīng)網(wǎng)絡(luò)優(yōu)化后的節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)權(quán)重計(jì)算。為方便讀者，簡(jiǎn)要對(duì)SDASA算法進(jìn)行介紹。

SDASA算法[20]的架構(gòu)如圖6所示，圖中RPC為遠(yuǎn)程過(guò)程調(diào)用協(xié)議，是Spark使用的通信框架。

圖6 SDASA算法架構(gòu)[20]Fig.6 SDASA algorithm architecture diagram[20]

具體算法描述如下：

輸入：任務(wù)集TaskSet，任務(wù)個(gè)數(shù)為m；集群節(jié)點(diǎn)集合WorkerOffer，節(jié)點(diǎn)個(gè)數(shù)為n。

輸出：返回任務(wù)列表，即第i個(gè)任務(wù)分配到第j個(gè)節(jié)點(diǎn)。

Step1：?jiǎn)?dòng)集群，觸發(fā)監(jiān)控啟動(dòng)心跳。

Step2：利用Ganglia獲取Slave節(jié)點(diǎn)動(dòng)靜態(tài)因素信息。

Step3：Master對(duì)集群每個(gè)節(jié)點(diǎn)進(jìn)行輪詢，將得到的節(jié)點(diǎn)的動(dòng)靜態(tài)因素?cái)?shù)據(jù)存入輪詢數(shù)據(jù)庫(kù)中。

Step4：Master對(duì)收到的信息進(jìn)行處理，計(jì)算出各節(jié)點(diǎn)的動(dòng)靜態(tài)指標(biāo)值。

Step5：Master根據(jù)每個(gè)節(jié)點(diǎn)的動(dòng)靜態(tài)指標(biāo)值計(jì)算得到各節(jié)點(diǎn)優(yōu)先級(jí)。

Step6：根據(jù)各節(jié)點(diǎn)優(yōu)先級(jí)對(duì)節(jié)點(diǎn)集合WorkerOffer進(jìn)行排序，節(jié)點(diǎn)優(yōu)先級(jí)越高，排序越靠前；反之，排序越靠后。

Step7：從優(yōu)先級(jí)最高的節(jié)點(diǎn)開始，依次遍歷每個(gè)節(jié)點(diǎn)。在每個(gè)節(jié)點(diǎn)輪流遍歷TaskSet中的每個(gè)Task，循環(huán)執(zhí)行Step 8。

Step8：獲取Task在節(jié)點(diǎn)上的本地化參數(shù)并進(jìn)行判斷，如果參數(shù)是最大，執(zhí)行Step 9。

Step9：分配該任務(wù)Task給該節(jié)點(diǎn)。

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文提出的節(jié)點(diǎn)優(yōu)先級(jí)優(yōu)化算法的有效性，進(jìn)行了相應(yīng)的實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)環(huán)境

基于Spark on standalone模式，搭建兩個(gè)集群進(jìn)行實(shí)驗(yàn)。集群1中有3個(gè)節(jié)點(diǎn)，分別為主節(jié)點(diǎn)Master、從節(jié)點(diǎn)Slave1和Slave2。集群2中有5個(gè)節(jié)點(diǎn)，分別為主節(jié)點(diǎn)Master、從節(jié)點(diǎn)Slave1、Slave2、Slave3、Slave4。集群1和集群2的節(jié)點(diǎn)靜態(tài)因素指標(biāo)值分別如表9和表10所示。

表9 集群1節(jié)點(diǎn)靜態(tài)因素指標(biāo)值

表10 集群2節(jié)點(diǎn)靜態(tài)因素指標(biāo)值

3.2 BP神經(jīng)網(wǎng)絡(luò)優(yōu)化的性能評(píng)價(jià)體系之權(quán)重

利用AHP計(jì)算得到的各指標(biāo)初始權(quán)重如式(4)所示。實(shí)驗(yàn)中通過(guò)BP神經(jīng)網(wǎng)絡(luò)優(yōu)化后的節(jié)點(diǎn)優(yōu)先級(jí)計(jì)算的各影響因素權(quán)重分別為:

1)各因素綜合權(quán)重如表8所示。

2)靜、動(dòng)態(tài)因素權(quán)重為0.371 5和0.628 5。

3)各靜態(tài)因素CPU速度、CPU核數(shù)、內(nèi)存容量和磁盤容量的權(quán)重分別為0.135 7、0.268 1、0.549 9和0.046 3。

4)各動(dòng)態(tài)因素CPU剩余率、內(nèi)存剩余率、磁盤剩余率、CPU負(fù)載的權(quán)重分別為0.284 6、0.507 0、0.145 4和0.062 8。

表11和表12分別給出了集群2中各節(jié)點(diǎn)的動(dòng)態(tài)因素指標(biāo)值隨著任務(wù)運(yùn)行的變化情況。實(shí)驗(yàn)使用了數(shù)據(jù)量為4 GB的工作負(fù)載Sort，表中CPU負(fù)載顯示的是該節(jié)點(diǎn)任務(wù)隊(duì)列的長(zhǎng)度。優(yōu)先級(jí)計(jì)算使用的是BP神經(jīng)網(wǎng)絡(luò)優(yōu)化后的權(quán)重。由表可以看到，隨著任務(wù)的執(zhí)行，各個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)均發(fā)生了變化。

表11 任務(wù)開始時(shí)動(dòng)態(tài)數(shù)據(jù)采集及節(jié)點(diǎn)優(yōu)先級(jí)初始狀態(tài)

表12 系統(tǒng)運(yùn)行28 s后采集的各節(jié)點(diǎn)動(dòng)態(tài)數(shù)據(jù)及節(jié)點(diǎn)優(yōu)先級(jí)

3.3 BP神經(jīng)網(wǎng)絡(luò)權(quán)重優(yōu)化調(diào)度算法實(shí)驗(yàn)結(jié)果及分析

本節(jié)展示節(jié)點(diǎn)權(quán)重優(yōu)化算法的有效性，對(duì)比算法為Spark默認(rèn)調(diào)度算法[47-49]和2.4節(jié)描述的基于AHP權(quán)重的SDASA算法。采用的負(fù)載是中國(guó)科學(xué)院計(jì)算技術(shù)研究所研發(fā)的基于大數(shù)據(jù)基準(zhǔn)測(cè)試的開源性程序集BigDataBench[50-51]。實(shí)驗(yàn)選擇了三種工作負(fù)載，分別為WordCount、Sort和K-means。

實(shí)驗(yàn)分別在包含3個(gè)節(jié)點(diǎn)的集群1和包含5個(gè)節(jié)點(diǎn)的集群2上進(jìn)行。選取兩個(gè)集群進(jìn)行實(shí)驗(yàn)的目的是考查隨著集群中節(jié)點(diǎn)數(shù)目的增多，節(jié)點(diǎn)權(quán)重優(yōu)化算法對(duì)于集群性能提升的影響。兩個(gè)集群上所進(jìn)行的實(shí)驗(yàn)相同，均為相同數(shù)據(jù)量不同工作負(fù)載實(shí)驗(yàn)和相同工作負(fù)載不同數(shù)據(jù)量實(shí)驗(yàn)。為了實(shí)驗(yàn)數(shù)據(jù)的準(zhǔn)確性，每種實(shí)驗(yàn)進(jìn)行5次并記錄時(shí)間，以5次的平均值為最終實(shí)驗(yàn)結(jié)果。

3.3.1 相同工作負(fù)載不同數(shù)據(jù)量的實(shí)驗(yàn)

本實(shí)驗(yàn)處理的工作負(fù)載是WordCount，實(shí)驗(yàn)使用不同數(shù)量的數(shù)據(jù)集，分別為2 GB、4 GB、6 GB、8 GB和10 GB。圖7給出了集群1上的實(shí)驗(yàn)結(jié)果，圖8給出了集群2上的實(shí)驗(yàn)結(jié)果。

圖7 集群1上不同數(shù)據(jù)量執(zhí)行時(shí)間對(duì)比Fig.7 Comparison of execution time under different data sizes for Cluster 1

圖8 集群2上不同數(shù)據(jù)量執(zhí)行時(shí)間對(duì)比Fig.8 Comparison of execution time under different data sizes for Cluster 2

由圖7和圖8可以得到，運(yùn)行相同工作負(fù)載時(shí)，使用BP神經(jīng)網(wǎng)絡(luò)優(yōu)化權(quán)重的SDASA與使用Spark默認(rèn)算法和AHP初始權(quán)重的SDASA相比，任務(wù)的執(zhí)行時(shí)間大幅縮減。表13給出了具體的對(duì)比結(jié)果。

從表13可以看到，負(fù)載相同、工作量不同時(shí)，集群1環(huán)境下，與Spark默認(rèn)算法相比性能平均提升12.72%；與SDASA算法相比平均提升6.57%。集群2中，與Spark默認(rèn)算法相比性能平均提升16.64%；與SDASA算法相比平均提升9.76%。隨著集群中節(jié)點(diǎn)數(shù)目的增加，節(jié)點(diǎn)優(yōu)先級(jí)優(yōu)化后，集群的性能提升也更加顯著。

表13 不同數(shù)據(jù)量時(shí)集群性能對(duì)比

3.3.2 不同工作負(fù)載相同數(shù)據(jù)量的實(shí)驗(yàn)

為了考察節(jié)點(diǎn)性能優(yōu)先級(jí)評(píng)價(jià)指標(biāo)的權(quán)重對(duì)于不同性質(zhì)任務(wù)的影響，對(duì)三種不同工作負(fù)載進(jìn)行了實(shí)驗(yàn)，所選負(fù)載分別為WordCount、Sort和K-means，實(shí)驗(yàn)使用的數(shù)據(jù)量均為2 GB。使用Spark默認(rèn)的任務(wù)調(diào)度算法、基于AHP權(quán)重的SDASA和本文基于AHP-BP權(quán)重的SDASA得到的實(shí)驗(yàn)結(jié)果分別如圖9和圖10所示。

圖9 集群1上不同工作負(fù)載執(zhí)行時(shí)間對(duì)比Fig.9 Comparison of execution time under different workloads for Cluster 1

圖10 集群2上不同工作負(fù)載執(zhí)行時(shí)間對(duì)比Fig.10 Comparison of execution time underdifferent workloads for Cluster 2

由圖9和圖10可以看出，進(jìn)行節(jié)點(diǎn)優(yōu)先級(jí)優(yōu)化后的SDASA與Spark默認(rèn)調(diào)度算法和使用AHP初始權(quán)重的SDASA相比，運(yùn)行WordCount、Sort和K-means三種工作負(fù)載時(shí)，系統(tǒng)性能都有提升。具體數(shù)據(jù)見表14。

表14 不同工作負(fù)載時(shí)集群性能對(duì)比

從表14可以看到，當(dāng)處理相同工作量的不同負(fù)載時(shí)，集群1環(huán)境下，與Spark默認(rèn)算法相比性能平均提升11.90%，與SDASA算法相比平均提升4.30%；集群2中，與Spark默認(rèn)算法相比性能平均提升12.49%，與SDASA算法相比平均提升6.54%。同樣地，集群的性能提升會(huì)隨著集群中節(jié)點(diǎn)數(shù)目的增加而增加。因此可以看出，隨著集群規(guī)模的進(jìn)一步加大，本文提出的優(yōu)先級(jí)調(diào)優(yōu)算法能夠更好地提高集群性能。

4 結(jié)論

為了解決分布式異構(gòu)集群性能優(yōu)化問(wèn)題，本文對(duì)集群節(jié)點(diǎn)的優(yōu)先級(jí)進(jìn)行了優(yōu)化。本文建立了AHP-BP神經(jīng)網(wǎng)絡(luò)模型，利用AHP和BP神經(jīng)網(wǎng)絡(luò)來(lái)確定集群節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)體系中各因素的權(quán)重。實(shí)驗(yàn)結(jié)果表明，使用所提出的節(jié)點(diǎn)優(yōu)先級(jí)調(diào)優(yōu)算法能夠得到合理的集群節(jié)點(diǎn)優(yōu)先級(jí)，提升Spark集群系統(tǒng)性能。

下一步的研究工作將從以下幾個(gè)方面展開：

1) 本文模型考慮的異構(gòu)集群的復(fù)雜度主要體現(xiàn)在同一集群的多個(gè)節(jié)點(diǎn)之間在磁盤容量、CPU核數(shù)和速度以及內(nèi)存容量等方面存在較大差異，從而導(dǎo)致節(jié)點(diǎn)計(jì)算能力的不同。本文提出的基于AHP-BP神經(jīng)網(wǎng)絡(luò)的節(jié)點(diǎn)優(yōu)先級(jí)評(píng)價(jià)模型具有較強(qiáng)的通用性。目前文中的AHP層次結(jié)構(gòu)是針對(duì)上述的異構(gòu)模型所建立的。當(dāng)考慮更為復(fù)雜的異構(gòu)集群，如CPU-GPU-NPU等不同類型的異構(gòu)時(shí)，可以將GPU及NPU的速度、核數(shù)、剩余率、負(fù)載等因素也作為影響節(jié)點(diǎn)性能的因素加以考慮，建立新的AHP層次結(jié)構(gòu)模型。同時(shí)根據(jù)新的節(jié)點(diǎn)性能影響因素調(diào)整BP神經(jīng)網(wǎng)絡(luò)的輸入，訓(xùn)練符合新AHP模型的BP網(wǎng)絡(luò)模型。因此后續(xù)將研究本文提出的算法對(duì)于其他種類異構(gòu)集群的有效性。

2) 研究更好的學(xué)習(xí)樣本選擇方法。

3) 選用更合適的神經(jīng)網(wǎng)絡(luò)或深度學(xué)習(xí)方法進(jìn)行實(shí)驗(yàn)研究。

4) 搭建大型集群，針對(duì)大數(shù)據(jù)量和多種負(fù)載進(jìn)行更多的實(shí)驗(yàn)，以進(jìn)一步驗(yàn)證優(yōu)先級(jí)優(yōu)化算法的有效性。