陳奉賢
(蘭州大學(xué)網(wǎng)絡(luò)安全與信息化辦公室,甘肅 蘭州 730000)
高性能計(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]。
目前對(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é)果。
高性能計(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ì)信息
從表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。
數(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í)的用戶聚類,得到最終的用戶類別。
從第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í)間。
循環(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ò)模型
注意力機(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。
運(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è)效果。
實(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í)際值。
本文分別使用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)度效率。
使用回填策略等算法提升高性能集群作業(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),以提升集群的利用率。