基于NR-Transformer的集群作業(yè)運(yùn)行時(shí)間預(yù)測(cè)*

陳奉賢

(蘭州大學(xué)網(wǎng)絡(luò)安全與信息化辦公室,甘肅 蘭州 730000)

1 引言

高性能計(jì)算發(fā)展快速，已被廣泛應(yīng)用到科學(xué)研究與工程應(yīng)用等領(lǐng)域。高性能計(jì)算由于具有計(jì)算能力強(qiáng)、并行規(guī)模大和多類型異構(gòu)計(jì)算等特點(diǎn)，在高密度計(jì)算和人工智能等領(lǐng)域得到了充分的應(yīng)用。

高性能計(jì)算通常以大規(guī)模計(jì)算集群的方式提供服務(wù)，集群上運(yùn)行的作業(yè)類型多樣，不同類型的作業(yè)占用的資源和運(yùn)行時(shí)長(zhǎng)各不相同[1]。在這種大規(guī)模的高性能集群上，作業(yè)調(diào)度一般由作業(yè)調(diào)度系統(tǒng)來(lái)實(shí)現(xiàn)。系統(tǒng)會(huì)監(jiān)控作業(yè)的資源消耗、使用時(shí)長(zhǎng)等特征，再通過(guò)相關(guān)調(diào)度算法，來(lái)確定作業(yè)在集群上的執(zhí)行順序。

常用的調(diào)度策略有先來(lái)先服務(wù)FCFS(First Come First Serve)、輪轉(zhuǎn)(Round Robin)和短作業(yè)優(yōu)先SJF(Short Job First)等[2]。作業(yè)根據(jù)這些調(diào)度算法的預(yù)定規(guī)則確定的作業(yè)順序按序執(zhí)行，例如FCFS是按照作業(yè)提交的順序調(diào)度作業(yè)運(yùn)行。當(dāng)集群上計(jì)算耗時(shí)長(zhǎng)的大作業(yè)較多時(shí)，F(xiàn)CFS調(diào)度算法難以利用集群的碎片資源，導(dǎo)致一定程度的資源浪費(fèi)[3]?；靥钏惴?Backfilling)是一種輔助調(diào)度算法，它根據(jù)當(dāng)前集群作業(yè)所需的運(yùn)行時(shí)間信息，在不改變?cè)鳂I(yè)執(zhí)行順序的情況下，將集群上的碎片資源分配出去，提高集群資源的利用率[4]。由于FCFS算法穩(wěn)定，對(duì)作業(yè)和進(jìn)程調(diào)度公平，因此現(xiàn)有的作業(yè)調(diào)度系統(tǒng)大都采用先來(lái)先服務(wù)加回填的調(diào)度方式，本文工作也是基于該方式展開(kāi)，該方式對(duì)作業(yè)運(yùn)行時(shí)間的預(yù)估有較高的要求。但用戶預(yù)估的作業(yè)運(yùn)行時(shí)間和實(shí)際運(yùn)行時(shí)間之間往往有較大誤差，結(jié)合用戶作業(yè)信息和集群作業(yè)的歷史日志分析預(yù)測(cè)的運(yùn)行時(shí)間，能較大程度地提高準(zhǔn)確率[5]。因此，要提高集群作業(yè)的運(yùn)行效率，需要有效利用用戶的歷史作業(yè)信息，對(duì)集群作業(yè)的運(yùn)行時(shí)間進(jìn)行準(zhǔn)確的預(yù)測(cè)[6,7]。

2 相關(guān)工作

目前對(duì)集群作業(yè)運(yùn)行時(shí)間的預(yù)測(cè)，大多是基于歷史日志數(shù)據(jù)的，即假定同一集群上計(jì)算模式和規(guī)模相似的作業(yè)其運(yùn)行時(shí)長(zhǎng)也較為接近。該方法雖然能一定程度上提升準(zhǔn)確率，但是，由于歷史數(shù)據(jù)中存在缺失數(shù)據(jù)和噪聲數(shù)據(jù)[8]，使得精確預(yù)測(cè)作業(yè)運(yùn)行時(shí)間成為一道難題。一種策略是利用同一用戶的歷史作業(yè)信息預(yù)測(cè)該用戶未來(lái)作業(yè)的運(yùn)行時(shí)間，例如將某用戶最近2次作業(yè)運(yùn)行時(shí)間的平均值作為其下一次作業(yè)運(yùn)行時(shí)間的預(yù)測(cè)值[1]，該算法對(duì)EASY回填(EASY-Backfilling)算法的調(diào)度系統(tǒng)性能有一定的提升，但在大規(guī)模的高性能集群上的準(zhǔn)確率和適用性都難以達(dá)到實(shí)用效果，尤其難以預(yù)測(cè)新用戶的作業(yè)。文獻(xiàn)[9]從歷史作業(yè)的特征中去衡量不同用戶、不同作業(yè)的相似度，篩選出與待預(yù)測(cè)作業(yè)最為相似的若干作業(yè)，并將這些作業(yè)的平均運(yùn)行時(shí)間作為待預(yù)測(cè)作業(yè)的運(yùn)行時(shí)間。該預(yù)測(cè)算法不依賴于單個(gè)用戶的歷史日志，通過(guò)改進(jìn)作業(yè)相似度衡量算法，對(duì)噪聲數(shù)據(jù)有一定的抗干擾能力。

近年來(lái)，聚類、分類和集成學(xué)習(xí)等機(jī)器學(xué)習(xí)方法越來(lái)越多地用于集群作業(yè)運(yùn)行時(shí)間預(yù)測(cè)。文獻(xiàn)[10]先從歷史日志中篩選出與作業(yè)運(yùn)行時(shí)間相關(guān)的重要特征，再利用這些特征進(jìn)行聚類，根據(jù)聚類結(jié)果預(yù)測(cè)新作業(yè)的運(yùn)行時(shí)間。文獻(xiàn)[11]基于K-近鄰算法，先通過(guò)歷史數(shù)據(jù)訓(xùn)練KD樹(shù)，然后使用訓(xùn)練好的KD樹(shù)計(jì)算新作業(yè)與歷史作業(yè)的距離，并將新作業(yè)劃分到與之距離最近的作業(yè)類別中，以完成作業(yè)的運(yùn)行時(shí)間預(yù)測(cè)。除使用單一的機(jī)器學(xué)習(xí)算法外，有不少學(xué)者嘗試使用集成學(xué)習(xí)的方法預(yù)測(cè)運(yùn)行時(shí)間。文獻(xiàn)[12]以隨機(jī)森林回歸、支持向量回歸SVR(Support Vector Regression)和貝葉斯嶺回歸3種回歸模型為基模型來(lái)提取VASP(Vienna Ab-initio Simulation Package)的作業(yè)特征，預(yù)測(cè)作業(yè)的運(yùn)行時(shí)間，并對(duì)預(yù)測(cè)結(jié)果進(jìn)行了2次學(xué)習(xí)。同時(shí)，該文獻(xiàn)將歷史數(shù)據(jù)按運(yùn)行時(shí)間長(zhǎng)度分為多個(gè)區(qū)間，在每個(gè)區(qū)間內(nèi)分別進(jìn)行訓(xùn)練和預(yù)測(cè)，取得了較好的預(yù)測(cè)效果。文獻(xiàn)[13]將分類和學(xué)習(xí)算法相結(jié)合，提出一種GA-Sim集成學(xué)習(xí)算法。該算法先用K-近鄰搜索相似作業(yè)，然后在相似作業(yè)集上訓(xùn)練SVR模型，將訓(xùn)練好的SVR模型用于最終的預(yù)測(cè)。文獻(xiàn)[14]先探討了不同調(diào)度策略的特點(diǎn)，再按具體的調(diào)度策略，使用梯度提升樹(shù)方法來(lái)提升集群作業(yè)運(yùn)行時(shí)間預(yù)測(cè)預(yù)測(cè)的準(zhǔn)確率。隨著神經(jīng)網(wǎng)絡(luò)的飛速發(fā)展，有研究人員使用深度神經(jīng)網(wǎng)絡(luò)對(duì)集群作業(yè)日志建模，以提升作業(yè)運(yùn)行時(shí)間預(yù)測(cè)的準(zhǔn)確率。文獻(xiàn)[15]使用俄羅斯科學(xué)院聯(lián)合超級(jí)計(jì)算機(jī)中心(JSCC RAS)的超級(jí)計(jì)算機(jī)MVS-100K和MVS-10P的統(tǒng)計(jì)數(shù)據(jù)，將工作日志特征按重要性排序，確定了最重要特征的互相關(guān)，然后使用多種方法建模和預(yù)測(cè)，最后使用隨機(jī)森林取得了最佳預(yù)測(cè)效果。文獻(xiàn)[17]使用神經(jīng)網(wǎng)絡(luò)建模來(lái)預(yù)測(cè)運(yùn)行時(shí)間和I/O ，將整個(gè)作業(yè)腳本輸入深度學(xué)習(xí)模型，從而實(shí)現(xiàn)運(yùn)行時(shí)間和 I/O資源預(yù)測(cè)的完全自動(dòng)化。

本文在上述研究的基礎(chǔ)上，提出一種基于注意力機(jī)制的NR-Transformer(Non-Residual connected Transformer)網(wǎng)絡(luò)，對(duì)作業(yè)日志數(shù)據(jù)建模和預(yù)測(cè)。在具體算法中，先使用K-Means聚類算法對(duì)集群用戶進(jìn)行聚類，將用戶的類別特征作為用戶特征加入數(shù)據(jù)集中；然后根據(jù)集群作業(yè)運(yùn)行時(shí)間的長(zhǎng)度將數(shù)據(jù)集劃分為不同的作業(yè)集；同時(shí)考慮到集群上作業(yè)提交順序的時(shí)序因素，分別使用循環(huán)神經(jīng)網(wǎng)絡(luò)RNN(Recurrent Neural Network)、長(zhǎng)短期記憶LSTM(Long Short-Term Memory)網(wǎng)絡(luò)和NR-Transformer網(wǎng)絡(luò)等結(jié)構(gòu)，在各作業(yè)集上訓(xùn)練和預(yù)測(cè)，并對(duì)比分析了各網(wǎng)絡(luò)結(jié)構(gòu)下不同運(yùn)行時(shí)間區(qū)間內(nèi)的預(yù)測(cè)結(jié)果。

3 數(shù)據(jù)特征處理

高性能計(jì)算集群實(shí)際產(chǎn)生的作業(yè)日志包含多種特征，例如用戶ID、使用的CPU數(shù)量和作業(yè)等待時(shí)間等。如果將這些特征全部用于模型訓(xùn)練，一方面會(huì)使模型過(guò)于復(fù)雜，導(dǎo)致訓(xùn)練周期過(guò)長(zhǎng)，且容易出現(xiàn)過(guò)擬合現(xiàn)象；另一方面，由于部分特征包含了大量的缺失數(shù)據(jù)和噪聲數(shù)據(jù)，這部分特征用于訓(xùn)練會(huì)導(dǎo)致模型難以收斂。因此，在訓(xùn)練模型前，需要先對(duì)歷史作業(yè)日志數(shù)據(jù)的特征進(jìn)行篩選和清洗。

為驗(yàn)證本文所提網(wǎng)絡(luò)的有效性和實(shí)用性，實(shí)驗(yàn)選用高性能集群日志中常用的公共數(shù)據(jù)集：ANL-2009、HPC2N和KIT[17]。這些數(shù)據(jù)集中的數(shù)據(jù)均由實(shí)際使用的高性能集群記錄產(chǎn)生，其中，ANL-2009是阿貢實(shí)驗(yàn)室超級(jí)計(jì)算機(jī)記錄的作業(yè)調(diào)度信息；HPC2N來(lái)自北瑞典高性能計(jì)算中心Seth的日志信息；KIT來(lái)自德國(guó)卡爾斯魯厄技術(shù)學(xué)院的ForHLR II系統(tǒng)一年半的作業(yè)記錄。這些數(shù)據(jù)集的數(shù)據(jù)均以標(biāo)準(zhǔn)日志格式SWF(Standard Workload Format)的形式記錄。本文將這3個(gè)數(shù)據(jù)集分別編號(hào)為1,2和3，其詳細(xì)信息如表1所示。

Table 1 Details of datasets表1 數(shù)據(jù)集詳細(xì)信息

3.1 數(shù)據(jù)特征篩選

從表1可以看出，3個(gè)數(shù)據(jù)集均來(lái)自多用戶的高性能計(jì)算集群，經(jīng)過(guò)初步整理后這些標(biāo)準(zhǔn)日志數(shù)據(jù)均包含18維作業(yè)特征。這些特征包含：作業(yè)的提交時(shí)間、等待時(shí)間和運(yùn)行時(shí)間等在內(nèi)的時(shí)間類特征；占用CPU數(shù)、內(nèi)存大小等資源類特征：用戶ID、用戶組等用戶類特征。這些作業(yè)特征均使用實(shí)際數(shù)值表示，缺失數(shù)據(jù)則用-1來(lái)表示。上述數(shù)據(jù)集經(jīng)過(guò)初次清洗和整理后，部分作業(yè)特征中仍存在大量缺失數(shù)據(jù)，因此需要對(duì)其進(jìn)一步地清洗和處理。

表2是各數(shù)據(jù)集上對(duì)缺失數(shù)據(jù)超過(guò)80%的特征的數(shù)量統(tǒng)計(jì)。從表2中可以看出，數(shù)據(jù)集1和數(shù)據(jù)集3有9個(gè)特征的數(shù)據(jù)缺失比例超過(guò)80%，數(shù)據(jù)集2有7個(gè)特征的缺失比例超過(guò)80%。這些特征由于缺失數(shù)據(jù)過(guò)多，屬于無(wú)效特征，因此需要將其刪除。在剩余的特征中，對(duì)包含重復(fù)信息的特征只選擇其中1維，例如作業(yè)號(hào)碼用于記錄作業(yè)提交的順序，其與作業(yè)的提交時(shí)間重疊，故只保留作業(yè)的提交時(shí)間。最終，共篩選出7維特征用于模型訓(xùn)練和預(yù)測(cè)，特征名稱和部分值見(jiàn)表3。

Table 2 Feature statistics of missing large amounts of data表2 缺失大量數(shù)據(jù)的特征統(tǒng)計(jì)

Table 3 Selected features and their values表3 篩選后的特征及其特征值

從表3可以看出，保留的作業(yè)特征仍涵蓋了上述時(shí)間類、資源類和用戶類特征，特征篩選沒(méi)有造成日志數(shù)據(jù)信息的損失。對(duì)于篩選后數(shù)據(jù)特征中仍存在的少量缺失值，本文使用均值插值法對(duì)其進(jìn)行填充。

高性能作業(yè)日志中，部分?jǐn)?shù)據(jù)來(lái)源于提交的作業(yè)參數(shù)或程序錯(cuò)誤而使作業(yè)提前終止的錯(cuò)誤作業(yè)日志，也需要將其作為噪聲數(shù)據(jù)剔除。本文將作業(yè)日志中運(yùn)行時(shí)間少于180 s的作業(yè)數(shù)據(jù)和實(shí)際運(yùn)行時(shí)間低于請(qǐng)求作業(yè)時(shí)間1%的作業(yè)數(shù)據(jù)作為噪聲數(shù)據(jù)從數(shù)據(jù)集中剔除。除此之外，極少數(shù)作業(yè)運(yùn)行時(shí)間遠(yuǎn)大于其他作業(yè)，這部分?jǐn)?shù)據(jù)作為離群點(diǎn)也被剔除出數(shù)據(jù)集外。

除此之外，7維特征中，時(shí)間類特征值在數(shù)量級(jí)上遠(yuǎn)大于其他2類特征，使各特征之間權(quán)重失衡，因此需要對(duì)數(shù)據(jù)做歸一化處理。本文使用自然對(duì)數(shù)歸一化的方式對(duì)時(shí)間類的特征進(jìn)行處理，處理后的特征值在1～15。

3.2 用戶聚類

數(shù)據(jù)經(jīng)過(guò)篩選和標(biāo)準(zhǔn)化后，可用于進(jìn)一步挖掘行為相似的用戶，優(yōu)化用戶類別的數(shù)據(jù)特征。研究表明，相類似的用戶在同一個(gè)高性能計(jì)算集群上通常會(huì)重復(fù)提交相似的作業(yè)[18,19]。由表1可知，3個(gè)數(shù)據(jù)集上用戶數(shù)均比較多，用戶ID作為離散特征變量直接用于訓(xùn)練模型，可能會(huì)因?yàn)橹颠^(guò)于分散而導(dǎo)致模型難以收斂。因此，本文使用聚類算法，首先根據(jù)歷史日志中用戶作業(yè)的計(jì)算模式和規(guī)模進(jìn)行聚類分析，得到計(jì)算模式相似的用戶類別，然后使用該特征作為用戶的類別特征，代替用戶ID，降低用戶特征的離散程度。

本文使用K-Means聚類算法，該算法具有原理簡(jiǎn)單、速度快等特點(diǎn)。在聚類前，先整理用戶的主要特征，統(tǒng)計(jì)各用戶在平臺(tái)上的作業(yè)數(shù)、平均等待時(shí)間、平均運(yùn)行時(shí)間和平均使用CPU數(shù)目等指標(biāo)，然后將其作為用戶的特征，用于用戶聚類。在訓(xùn)練時(shí),K-Means算法需要預(yù)先指定聚類的簇值K，但不同的K值對(duì)聚類效果影響較大。因此，本文首先對(duì)K值預(yù)設(shè)范圍，訓(xùn)練聚類模型時(shí)分別使用該范圍內(nèi)的K值，然后用輪廓系數(shù)(Silhouette Coefficient)衡量各K值下的聚類效果[20]。樣本i的輪廓系數(shù)和整個(gè)數(shù)據(jù)集總的輪廓系數(shù)的計(jì)算方法如式(1)和式(2)所示：

(1)

(2)

其中，a(i)為樣本i到其所在簇中其它樣本的平均距離，b(i)為樣本i到其它簇中樣本的平均距離，N為樣本數(shù)，S(i)為樣本i的輪廓系數(shù)，SC為整個(gè)數(shù)據(jù)集總的輪廓系數(shù)。

聚類的總輪廓系數(shù)越接近于1，說(shuō)明簇內(nèi)樣本之間越緊湊，簇間距離越大；反之，則說(shuō)明簇間重疊部分大，聚類效果不佳。因此，本文選取預(yù)選區(qū)間內(nèi)使輪廓系數(shù)最大的K值作為最終的聚類簇值。具體算法流程圖如圖1所示。

Figure 1 User cluser algorithm圖1 用戶聚類算法

本文預(yù)設(shè)的K值在3～18，在3個(gè)數(shù)據(jù)集上分別使用取值范圍內(nèi)的K值訓(xùn)練聚類模型，計(jì)算和統(tǒng)計(jì)不同K值下的輪廓系數(shù)。輪廓系數(shù)隨K值的變化如圖2所示。由圖2可知，在3個(gè)數(shù)據(jù)集上，隨著聚類的K值增加，輪廓系數(shù)整體呈下降趨勢(shì)，說(shuō)明數(shù)據(jù)集上的用戶類別分布差異相對(duì)較小。數(shù)據(jù)集1的輪廓系數(shù)整體高于其他2個(gè)數(shù)據(jù)集的，而數(shù)據(jù)集1的數(shù)據(jù)量小于其他2個(gè)數(shù)據(jù)集的，日志整體的時(shí)間跨度也較小，因此可以推斷出，數(shù)據(jù)采樣的時(shí)間間隔和數(shù)據(jù)量會(huì)影響數(shù)據(jù)集上用戶作業(yè)的差異性，時(shí)間間隔越久，數(shù)據(jù)量越多，用戶作業(yè)的差異性也就越大，這也符合文獻(xiàn)[18]的實(shí)驗(yàn)結(jié)論。

Figure 2 Curve of silhouette coefficient changes with K value圖2 輪廓系數(shù)隨K值的變化曲線

此外，數(shù)據(jù)集1和數(shù)據(jù)集2均在K取4時(shí)輪廓系數(shù)達(dá)到最大值，數(shù)據(jù)集3在K取6時(shí)輪廓系數(shù)達(dá)到最大值。因此,本文對(duì)數(shù)據(jù)集1和2進(jìn)行K取4時(shí)的用戶聚類，對(duì)數(shù)據(jù)集3進(jìn)行K取6時(shí)的用戶聚類，得到最終的用戶類別。

4 預(yù)測(cè)模型

從第2節(jié)對(duì)數(shù)據(jù)集的特征描述可知，作業(yè)日志中有多個(gè)特征用于記錄作業(yè)提交和執(zhí)行的時(shí)序信息?，F(xiàn)有的研究在分析作業(yè)日志時(shí)，大都沒(méi)有考慮前后作業(yè)之間的聯(lián)系。文獻(xiàn)[13]篩除時(shí)序特征，只利用了用戶特征和作業(yè)資源特征;文獻(xiàn)[21]只將作業(yè)提交時(shí)間作為作業(yè)特征信息用于訓(xùn)練模型，也未考慮作業(yè)之間的關(guān)聯(lián)。在實(shí)際的作業(yè)系統(tǒng)中，新作業(yè)的運(yùn)行狀態(tài)往往和當(dāng)前集群上正在運(yùn)行的作業(yè)有關(guān)，例如當(dāng)前系統(tǒng)上作業(yè)的運(yùn)行時(shí)間會(huì)直接影響到新作業(yè)的等待時(shí)間。

為了利用數(shù)據(jù)集上作業(yè)之間的時(shí)序性，本文在分離長(zhǎng)短作業(yè)時(shí)保留原作業(yè)的提交順序，并按照時(shí)間步長(zhǎng)L對(duì)數(shù)據(jù)進(jìn)行采樣。采樣后的一組數(shù)據(jù)長(zhǎng)度為T，訓(xùn)練時(shí)以T為基本長(zhǎng)度提取時(shí)序信息。在模型選擇上，使用能有效利用數(shù)據(jù)歷史信息的循環(huán)神經(jīng)網(wǎng)絡(luò)、長(zhǎng)短期記憶網(wǎng)絡(luò)和改進(jìn)的注意力模型Transformer等結(jié)構(gòu)，來(lái)提取作業(yè)數(shù)據(jù)的特征和時(shí)序信息。訓(xùn)練時(shí)，使用長(zhǎng)度為T的序列數(shù)據(jù)預(yù)測(cè)第T+1位置的作業(yè)運(yùn)行時(shí)間。

4.1 循環(huán)神經(jīng)網(wǎng)絡(luò)

循環(huán)神經(jīng)網(wǎng)絡(luò)RNN通常用于序列數(shù)據(jù)的建模，在語(yǔ)音序列、自然語(yǔ)言和時(shí)間序列等數(shù)據(jù)上有廣泛的使用。RNN通過(guò)有向循環(huán)連接，在計(jì)算當(dāng)前隱藏層的狀態(tài)時(shí)，同時(shí)考慮了當(dāng)前的輸入向量和上一時(shí)間步的隱藏層狀態(tài)，使神經(jīng)網(wǎng)絡(luò)能夠?qū)W習(xí)歷史信息[22]。但是，RNN在輸入序列過(guò)長(zhǎng)時(shí)，通過(guò)循環(huán)連接累積的梯度容易造成梯度的消失/爆炸，致使RNN無(wú)法獲取序列的長(zhǎng)期依賴。為了解決上述梯度問(wèn)題，文獻(xiàn)[23]在RNN細(xì)胞結(jié)構(gòu)中引入門控單元，通過(guò)輸入門、遺忘門和輸出門等結(jié)構(gòu)構(gòu)建了長(zhǎng)短期記憶LSTM網(wǎng)絡(luò)[24]。通過(guò)門控單元對(duì)每次輸入進(jìn)行非線性變換，避免了梯度消失/爆炸，解決了序列數(shù)據(jù)的長(zhǎng)期依賴問(wèn)題。

本文以RNN和LSTM網(wǎng)絡(luò)作為基準(zhǔn)模型，驗(yàn)證對(duì)作業(yè)日志數(shù)據(jù)進(jìn)行時(shí)序建模和預(yù)測(cè)的有效性。

圖3是循環(huán)神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型。其中，輸入為第2節(jié)中處理后的作業(yè)特征數(shù)據(jù)；神經(jīng)網(wǎng)絡(luò)部分是3層的RNN/LSTM網(wǎng)絡(luò)，每層均包含64個(gè)神經(jīng)元;輸出是一個(gè)全連接網(wǎng)絡(luò)層，用于調(diào)整預(yù)測(cè)值的維度。在激活函數(shù)的選擇上，RNN選用ReLU函數(shù)，以避免梯度問(wèn)題；LSTM根據(jù)各個(gè)門限結(jié)構(gòu)的特點(diǎn)，使用Sigmoid函數(shù)和Tanh函數(shù)。

Figure 3 Recurrent neural network model圖3 循環(huán)神經(jīng)網(wǎng)絡(luò)模型

4.2 NR-Transformer網(wǎng)絡(luò)

注意力機(jī)制AM(Attention Mechanism)通常應(yīng)用于Seq2Seq結(jié)構(gòu)中，用于處理輸入端和輸出端序列長(zhǎng)度不等的數(shù)據(jù)。在編碼端，對(duì)于每一時(shí)刻的輸入，AM都計(jì)算該時(shí)刻基神經(jīng)網(wǎng)絡(luò)的輸出狀態(tài)值，并將該狀態(tài)值用于解碼端的輸入?；窠?jīng)網(wǎng)絡(luò)一般選擇RNN或LSTM，使用注意力機(jī)制的Seq2Seq網(wǎng)絡(luò)可以獲取比LSTM更長(zhǎng)的序列歷史信息，在自然語(yǔ)言處理和部分時(shí)間序列上都取得了較好的效果。但是，由于RNN和LSTM無(wú)法并行化，使得模型的訓(xùn)練速度較為緩慢。

Transformer是Google提出的基于自注意力機(jī)制的Seq2Seq結(jié)構(gòu)[25]。由于自注意力結(jié)構(gòu)計(jì)算時(shí)不依賴前一時(shí)刻的輸出值，因此可以通過(guò)并行化來(lái)加速模型的訓(xùn)練速度。該網(wǎng)絡(luò)使用位置編碼PE(Positional Encoding)計(jì)算序列中數(shù)據(jù)的相對(duì)位置，以獲取數(shù)據(jù)的時(shí)序關(guān)聯(lián)信息。編碼端和解碼端都使用多頭自注意力結(jié)構(gòu)，每層之間使用殘差連接，并進(jìn)行了層正則化處理[26]。

使用原始的Transformer在作業(yè)日志數(shù)據(jù)上訓(xùn)練時(shí)，模型收斂速度較慢，其預(yù)測(cè)準(zhǔn)確率和基準(zhǔn)模型的有較大差距。因此，本文根據(jù)Transformer和日志作業(yè)數(shù)據(jù)的特點(diǎn)，提出一種改進(jìn)的NR-Transformer結(jié)構(gòu)：在注意力計(jì)算上，使用縮放點(diǎn)積的計(jì)算方式；在層與層的連接上，去除各子層之間的殘差連接，并只對(duì)部分層進(jìn)行層正則化處理；在輸出端，使用全連接層對(duì)模型的狀態(tài)向量進(jìn)行映射變換。NR-Transformer的結(jié)構(gòu)如圖4所示。

Figure 4 NR-Transformer structure圖4 NR-Transformer結(jié)構(gòu)

輸入數(shù)據(jù)先經(jīng)過(guò)由單層全連接網(wǎng)絡(luò)組成的嵌入層，將輸入數(shù)據(jù)特征編碼為向量表示。位置編碼模塊提取輸入向量的時(shí)序信息，具體計(jì)算如式(3)所示：

(3)

其中，PE(t,2i)表示輸入向量中t時(shí)刻第i維的位置編碼向量，dmodel表示輸入向量的維度大小。通過(guò)位置編碼模塊，得到包含作業(yè)數(shù)據(jù)時(shí)序信息的位置編碼向量，再將位置編碼向量和輸入向量相加得到新向量，作為編碼器和解碼器的輸入。

編碼器和解碼器的核心模塊是多頭注意力(Multi-Head Attention)，它是Transformer中提出的一種注意力計(jì)算算法。該算法通過(guò)降維映射和縮放點(diǎn)積多次計(jì)算輸入的注意力，并將這些計(jì)算結(jié)果拼接起來(lái)，計(jì)算公式如式(4)所示：

MultiHead(Q,K,V)=

Concat(head1,…,headh)Wo

(4)

其中，h是頭的個(gè)數(shù)，即計(jì)算次數(shù);headi通過(guò)縮放點(diǎn)積求得,如式(5)所示：

(5)

Feed Forward層是編碼器和解碼器中的最后一個(gè)模塊，該部分對(duì)多頭注意力的輸出進(jìn)行非線性變換。它由2個(gè)全連接網(wǎng)絡(luò)和激活函數(shù)組成。解碼器的輸出經(jīng)過(guò)1層全連接網(wǎng)絡(luò)得到最終的預(yù)測(cè)結(jié)果。在本文中，激活函數(shù)使用ReLU函數(shù)，編碼器和解碼器的層數(shù)n均為3，頭的個(gè)數(shù)h為8。

5 實(shí)驗(yàn)與結(jié)果

5.1 數(shù)據(jù)集劃分

運(yùn)行時(shí)間相差較大的作業(yè)，其特征差異也往往較大，如果不加區(qū)分地使用全部數(shù)據(jù)訓(xùn)練模型，模型難以很好地學(xué)習(xí)數(shù)據(jù)集的特征，導(dǎo)致模型難以收斂到最優(yōu)點(diǎn)?，F(xiàn)有的研究通常按照作業(yè)的實(shí)際運(yùn)行時(shí)間將數(shù)據(jù)集中的長(zhǎng)短作業(yè)分離，分別在各作業(yè)集上進(jìn)行訓(xùn)練和預(yù)測(cè)。

本文先對(duì)3個(gè)數(shù)據(jù)集的運(yùn)行時(shí)間區(qū)間進(jìn)行統(tǒng)計(jì)，然后根據(jù)各區(qū)間的樣本數(shù)，劃分各數(shù)據(jù)集上的長(zhǎng)短作業(yè)集。圖5～圖7分別是數(shù)據(jù)集1,2和3的區(qū)間頻數(shù)統(tǒng)計(jì)圖。從圖中可以看出，3個(gè)數(shù)據(jù)集上運(yùn)行時(shí)間在0～5 000 s的短作業(yè)樣本最多，大于40 000s的長(zhǎng)作業(yè)樣本較少。本文按照運(yùn)行時(shí)間的區(qū)間和各區(qū)間的樣本數(shù)，將3個(gè)數(shù)據(jù)集分別劃分成長(zhǎng)、中、短3類作業(yè)集，具體劃分如表4所示。

Figure 5 Runtime interval distribution on Dataset1圖5 數(shù)據(jù)集1運(yùn)行時(shí)間區(qū)間分布

Figure 6 Runtime interval distribution on Dataset2圖6 數(shù)據(jù)集2運(yùn)行時(shí)間區(qū)間分布

Figure 7 Runtime interval distribution on Dataset3圖7 數(shù)據(jù)集3運(yùn)行時(shí)間區(qū)間分布

表4 長(zhǎng)短作業(yè)劃分

從表4中可知，3個(gè)數(shù)據(jù)集中，數(shù)據(jù)集2的作業(yè)日志數(shù)最多，在各作業(yè)集上的樣本數(shù)也均多于數(shù)據(jù)集1和數(shù)據(jù)集3的；數(shù)據(jù)集1主要由短作業(yè)樣本組成，中長(zhǎng)作業(yè)樣本遠(yuǎn)少于短作業(yè)樣本；數(shù)據(jù)集2和數(shù)據(jù)集3上各作業(yè)集的樣本數(shù)則較為均衡。

在后續(xù)實(shí)驗(yàn)中，各作業(yè)集按照8∶1∶1的比例劃分訓(xùn)練集、驗(yàn)證集和測(cè)試集。其中，訓(xùn)練集和驗(yàn)證集用于模型的訓(xùn)練，測(cè)試集用于評(píng)估模型的預(yù)測(cè)效果。

5.2 實(shí)驗(yàn)參數(shù)和評(píng)價(jià)方式

實(shí)驗(yàn)中網(wǎng)絡(luò)參數(shù)的選擇按照第3節(jié)中的預(yù)設(shè)為主：RNN和LSTM均使用3層網(wǎng)絡(luò)，神經(jīng)元個(gè)數(shù)為64；NR-Transformer使用的編碼器和解碼器均為3層，多頭注意力中的h為8;優(yōu)化器均使用Adam優(yōu)化算法[27]，初始學(xué)習(xí)率為0.001，Batch Size為128，時(shí)間步長(zhǎng)為20。在訓(xùn)練時(shí)，使用Dropout來(lái)防止過(guò)擬合[28]。模型使用PyTorch框架實(shí)現(xiàn)，計(jì)算使用單塊的NVIDIA Tesla V100顯卡。

本文使用Huber函數(shù)作為目標(biāo)函數(shù)[29]。該函數(shù)對(duì)平均絕對(duì)誤差MAE(Mean Absolute Error)函數(shù)進(jìn)行了平滑，避免訓(xùn)練時(shí)出現(xiàn)梯度爆炸的情況。

在模型預(yù)測(cè)效果的評(píng)測(cè)方式上，本文使用平均絕對(duì)百分比誤差MAPE(Mean Absolute Percent Error)和平均預(yù)測(cè)準(zhǔn)確率APA(Average Predictive Accuracy)2個(gè)指標(biāo)。

在對(duì)模型預(yù)測(cè)的誤差評(píng)估上，由于本文使用多種不同運(yùn)行時(shí)間長(zhǎng)度的數(shù)據(jù)集，因此難以直接用平均絕對(duì)誤差衡量。平均絕對(duì)百分比誤差則能較好地衡量預(yù)測(cè)值相比于實(shí)際值的偏離程度，其值越小，說(shuō)明預(yù)測(cè)模型的預(yù)測(cè)精度越好。記測(cè)試集樣本數(shù)為N，其MAPE計(jì)算如式(6)所示：

(6)

平均預(yù)測(cè)準(zhǔn)確率是測(cè)試集上所有作業(yè)的預(yù)測(cè)準(zhǔn)確率的平均值，單個(gè)作業(yè)的預(yù)測(cè)準(zhǔn)確率計(jì)算如式(7)所示：

(7)

在整個(gè)測(cè)試集上的平均預(yù)測(cè)準(zhǔn)確率如式(8)所示：

(8)

APA的值在0～1，其值越接近于1，說(shuō)明預(yù)測(cè)值越接近于實(shí)際值。

5.3 實(shí)驗(yàn)結(jié)果

本文分別使用BP神經(jīng)網(wǎng)絡(luò)BPNN(Back Propagation Neural Network)、RNN、LSTM和NR-Transformer 4種神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行實(shí)驗(yàn)。其中，BP神經(jīng)網(wǎng)絡(luò)用于和時(shí)序神經(jīng)網(wǎng)絡(luò)對(duì)比，其網(wǎng)絡(luò)層數(shù)和神經(jīng)元數(shù)與RNN的相同。

數(shù)據(jù)集分別使用4.1節(jié)中劃分的各長(zhǎng)短作業(yè)集，在每個(gè)作業(yè)集上，分別使用上述4種神經(jīng)網(wǎng)絡(luò)訓(xùn)練模型。在實(shí)際訓(xùn)練中，為防止訓(xùn)練時(shí)出現(xiàn)過(guò)擬合現(xiàn)象，本文使用了早停法，即在5個(gè)連續(xù)的訓(xùn)練周期中，如果驗(yàn)證集的損失函數(shù)沒(méi)有下降，則提前結(jié)束訓(xùn)練。

由4.1節(jié)可知，數(shù)據(jù)集2上的作業(yè)樣本數(shù)最多，且各作業(yè)集的樣本量也較為均衡，因此本文對(duì)數(shù)據(jù)集2上的實(shí)驗(yàn)結(jié)果進(jìn)行詳細(xì)分析，再驗(yàn)證結(jié)論在數(shù)據(jù)1和數(shù)據(jù)集3上是否具有一致性。

圖8和圖9分別是4種神經(jīng)網(wǎng)絡(luò)在各測(cè)試集上的預(yù)測(cè)結(jié)果。由圖可知，BP神經(jīng)網(wǎng)絡(luò)和其它3種時(shí)序網(wǎng)絡(luò)相比，在各作業(yè)集上誤差率較高，準(zhǔn)確率較低。NR-Transformer網(wǎng)絡(luò)則在各作業(yè)集上都有較低的百分比誤差和較高的準(zhǔn)確率，在長(zhǎng)作業(yè)集上平均預(yù)測(cè)準(zhǔn)確率達(dá)0.905。在該數(shù)據(jù)集上，NR-Transformer預(yù)測(cè)的結(jié)果和文獻(xiàn)[13]中使用SVR等機(jī)器學(xué)習(xí)算法預(yù)測(cè)的結(jié)果相比，平均預(yù)測(cè)準(zhǔn)確率提升了近0.2。

Figure 8 MAPE of each job set on Dataset2圖8 數(shù)據(jù)集2上各作業(yè)集MAPE

Figure 9 APA of each job set on Dataset2圖9 數(shù)據(jù)集2上各作業(yè)集APA

圖10和圖11分別是BPNN和NR- Transformer在中作業(yè)集上的部分預(yù)測(cè)值和實(shí)際值的對(duì)比。從圖中可以看出，BPNN沒(méi)有充分學(xué)習(xí)到作業(yè)運(yùn)行時(shí)間的變化規(guī)律，其預(yù)測(cè)值大部分為該作業(yè)集上運(yùn)行時(shí)間的中值，也沒(méi)有預(yù)測(cè)出作業(yè)運(yùn)行時(shí)間的變化趨勢(shì)；NR-Transformer則較好地從歷史作業(yè)信息中學(xué)習(xí)到了作業(yè)之間的時(shí)序信息，對(duì)部分運(yùn)行時(shí)間變化較大的點(diǎn)也有較高的預(yù)測(cè)準(zhǔn)確率。

Figure 10 Comparison of values predicted by BPNN and the actual value圖10 BPNN預(yù)測(cè)值與實(shí)際值對(duì)比

Figure 11 Comparison of values predicted by NR-Transformer and the actual value圖11 NR-Transformer預(yù)測(cè)值與實(shí)際值對(duì)比

由上述分析可知，BPNN在實(shí)際預(yù)測(cè)中，難以學(xué)習(xí)到作業(yè)數(shù)據(jù)中的時(shí)序信息，因而平均準(zhǔn)確率較低。而在時(shí)序網(wǎng)絡(luò)中，LSTM通過(guò)門控結(jié)構(gòu)、NR-transformer通過(guò)位置編碼模塊和自注意力機(jī)制都能獲取到較長(zhǎng)的作業(yè)歷史信息，在平均預(yù)測(cè)準(zhǔn)確率上高于RNN。

Figure 12 MAPE and APA on Dataset1圖12 數(shù)據(jù)集1上的MAPE和APA

Figure 13 MAPE and APA on Dataset3圖13 數(shù)據(jù)集3上的MAPE和APA

圖12和圖13是上述神經(jīng)網(wǎng)絡(luò)在數(shù)據(jù)集1和數(shù)據(jù)集3上的測(cè)試結(jié)果?？梢钥闯?，由于數(shù)據(jù)集上樣本數(shù)量的差異，這2個(gè)數(shù)據(jù)集上各神經(jīng)網(wǎng)絡(luò)的整體預(yù)測(cè)效果均差于數(shù)據(jù)集2的。這說(shuō)明深度神經(jīng)網(wǎng)絡(luò)往往需要較大量的數(shù)據(jù)，才能訓(xùn)練出較優(yōu)的模型。在各作業(yè)集的具體表現(xiàn)上，各神經(jīng)網(wǎng)絡(luò)的性能和數(shù)據(jù)集2上的結(jié)果基本一致，BPNN和RNN的性能略差于LSTM和NR-Transformer的。數(shù)據(jù)集1的長(zhǎng)作業(yè)集樣本只有3 964個(gè)，在該作業(yè)集上，BPNN預(yù)測(cè)準(zhǔn)確率只有0.67?？梢钥闯?，在樣本量較小時(shí)，結(jié)構(gòu)簡(jiǎn)單的BPNN難以學(xué)習(xí)到作業(yè)數(shù)據(jù)的特征；NR-Transformer的結(jié)果和RNN和LSTM的相比有較為明顯的提升，說(shuō)明該網(wǎng)絡(luò)同樣適用于小樣本量數(shù)據(jù)。

圖14是訓(xùn)練好的各模型在數(shù)據(jù)集2的測(cè)試集上預(yù)測(cè)所用時(shí)間的對(duì)比。從圖14中可以看出，由于各區(qū)間的測(cè)試集數(shù)據(jù)量相近，因此模型在這3個(gè)作業(yè)集上的預(yù)測(cè)時(shí)間相一致。其中，BPNN由于結(jié)構(gòu)簡(jiǎn)單，在3 000組測(cè)試數(shù)據(jù)上預(yù)測(cè)所用時(shí)間最少，最短時(shí)間只有0.15 s；LSTM結(jié)構(gòu)較為復(fù)雜，且不能并行化執(zhí)行，所用時(shí)間最長(zhǎng)；NR-Transformer和RNN所用時(shí)間相近，預(yù)測(cè)3 000組測(cè)試數(shù)據(jù)用時(shí)在0.5 s左右，但在平均預(yù)測(cè)準(zhǔn)確率上，NR-Transformer高于RNN的。在實(shí)際預(yù)測(cè)新作業(yè)的運(yùn)行時(shí)間時(shí)，NR-Transformer能在較短時(shí)間內(nèi)預(yù)測(cè)出準(zhǔn)確的作業(yè)運(yùn)行時(shí)間。

Figure 14 Prediction time of test dataset on Dataset2圖14 數(shù)據(jù)集2上的測(cè)試集預(yù)測(cè)所需時(shí)間

綜上所述，本文分別使用4種不同的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)在3個(gè)數(shù)據(jù)集上的不同作業(yè)集上進(jìn)行了訓(xùn)練和預(yù)測(cè)。本文提出的NR-Transformer結(jié)構(gòu)在多個(gè)作業(yè)集上的預(yù)測(cè)性能優(yōu)于RNN和LSTM的，最高平均預(yù)測(cè)準(zhǔn)確率達(dá)0.9，同時(shí)在樣本數(shù)較少的作業(yè)集上也有較好的預(yù)測(cè)準(zhǔn)確率，說(shuō)明NR- Transformer能較好地用于作業(yè)數(shù)據(jù)的運(yùn)行時(shí)間預(yù)測(cè)。在實(shí)際作業(yè)調(diào)度系統(tǒng)中，可以在考慮誤差率的情況下，將NR-Transformer預(yù)測(cè)的運(yùn)行時(shí)間作為作業(yè)的估計(jì)運(yùn)行時(shí)間，配合回填算法提高集群的調(diào)度效率。

6 結(jié)束語(yǔ)

使用回填策略等算法提升高性能集群作業(yè)調(diào)度效率，需要準(zhǔn)確的作業(yè)運(yùn)行時(shí)間估計(jì)。本文從歷史作業(yè)數(shù)據(jù)的相似性出發(fā)，先對(duì)集群用戶進(jìn)行聚類，將類別信息添加到作業(yè)特征中；再使用多種神經(jīng)網(wǎng)絡(luò)，在各作業(yè)集上進(jìn)行訓(xùn)練和預(yù)測(cè)。實(shí)驗(yàn)結(jié)果顯示，時(shí)序性神經(jīng)網(wǎng)絡(luò)在作業(yè)運(yùn)行時(shí)間預(yù)測(cè)上有較高的平均預(yù)測(cè)準(zhǔn)確率和較低的預(yù)測(cè)百分比誤差。其中，本文提出的NR-Transformer結(jié)構(gòu)在多個(gè)作業(yè)集上較RNN和LSTM網(wǎng)絡(luò)都有更準(zhǔn)確和更穩(wěn)定的預(yù)測(cè)結(jié)果。

今后將在實(shí)際的高性能集群上試用NR-Transformer來(lái)預(yù)測(cè)作業(yè)的運(yùn)行時(shí)間，并進(jìn)一步改進(jìn)，以提升集群的利用率。