作業名層次化聚類算法預測作業運行時間*

周隆放，楊文祥，韓永國，張曉蓉，喻 杰，馮景華，張 健，李宇奇，鮮 港，吳亞東，王桂娟

(1. 中國空氣動力研究與發展中心 計算空氣動力研究所， 四川 綿陽 621000；2. 西南科技大學 計算機科學與技術學院， 四川 綿陽 621010； 3. 國防科技大學 計算機學院， 湖南 長沙 410073；4. 國家超級計算天津中心， 天津 300457； 5. 四川輕化工大學 計算機科學與工程學院， 四川 自貢 643000)

在高性能計算領域中，提升系統資源的使用效率長期以來是研究的熱點[1-4]。提升硬件資源的使用率和優化作業的吞吐率會在很大程度上減少系統的開銷[5-6]。在系統作業調度策略方面，調度策略決定著作業運行的先后次序，從而很大程度地影響著系統作業的吞吐率和資源使用效率[7-8]。傳統的作業調度采用先來先服務策略，然而，在先來先服務的策略下，所有作業按照提交時間先后的順序一次進入等待隊列，不同作業請求資源的數目和運行時間都不同，當隊首作業不能分配到足夠數目的資源時，會等待其他作業運行完成后釋放資源。

為了提升系統調度性能，短作業優先策略從等待隊列中選運行時間最短的作業運行，這有利于短作業的及時運行，但容易造成長作業處于饑餓狀態；時間片輪轉策略給每個作業固定的運行時間但是會造成更長的平均等待時間[9]；回填調度策略[10-13]在不推遲隊首作業正常運行的前提下，選取運行時間最合適的作業搶占空閑資源而運行，該策略能在縮短平均等待時間的同時提升系統的吞吐量，但是作業的預計運行時間難以估計。通常，用戶提交作業時會附上該作業的預計運行時間，但是實際上，許多系統的用戶并沒有被要求去附上作業預估時間甚至用戶通常高估作業運行時間。為了回填策略的高效運行，已有大量的算法預估作業運行時間。

近幾年機器學習[14-15]的快速發展對于高性能領域的作業時間預測問題有很大的推動。機器學習可以基于大量的歷史作業，根據其作業的特征和作業運行時間建立一個作業的預測模型來預測新提交作業的運行時間。傳統的預測方法是選取作業的部分特征放入模型中訓練[16-17]，比如作業的中央處理器(central processing unit, CPU)數量、提交時刻、用戶名等。作業名具有作業的語義信息，對描述作業運行特征有重要意義。

聚類是機器學習中提升數據質量的方法之一。作業名由許多數字、字母和特殊符號組成，其結構較為復雜，傳統的聚類算法很難將相似的作業名聚類。比如作業名的字母大小寫不能區分作業名的相似程度、由相同的字母組成的作業名但字母順序不同或者字母之間被不同的符號連接、數字僅僅表示值的大小或者時間的先后但無實際的意義。因此僅通過字符串的相似度很難將相似的作業名聚類。用戶命名作業的規律：所有的作業名都由字母、特殊字符和數字三個成分組成，用戶命名作業往往用字母(英文字母或者拼音或者二者的縮寫)表示作業所執行的功能；特殊字符指的是下劃線、橫線、點和加號等，用戶往往用特殊字符連接中間兩部分內容，它起到結構化作業名的作用；數字往往被用戶用來表示作業的參數或者時間等。根據相似作業的特點，提出字母-結構-數字(letter-structure-number，LSN)的作業名聚類算法，它總共通過三層聚類作業名：第一層是通過作業名中字母的相似程度聚類；在第一層聚類的基礎上，再通過特殊字符的相似程度二次聚類；最后通過數字的相似程度聚類得到最終的作業名聚類結果。

本文采集兩個超算中心2020年9月—2021年9月一年的歷史作業數據，抽取數據特征，采用LSN作業名聚類算法將相似的作業聚類，采用經典的機器學習模型預測作業的運行時間，包括支持向量回歸(support vector regression, SVR)、隨機森林(random forest, RF)等。同時采用傳統的字符串聚類方法聚類作業，并為之訓練模型，通過對比預測精度來評估作業名聚類的效果。

1 相關工作

已經有很多文獻提出了作業運行時間預測算法。其中文獻[18]在Mira 和 Intrepid 兩臺超算上根據用戶的提交作業的習慣和特點預測用戶新提交作業的運行時間。文獻[19]將作業運行時長按照長度區間離散化，然后再綜合支持向量回歸、貝葉斯嶺回歸和隨機森林回歸三種模型，最后通過貝葉斯分類實現運行時間的二次預測；同時該文獻還基于徑向基的神經網絡方法預測作業運行時長。文獻[20]通過自定義的特征集合，即模板，預測與之相似的作業的運行時長。文獻[21]挖掘半結構的歷史作業日志并用隱馬爾可夫模型預測作業的剩余運行時間。文獻[22]用K近鄰(Knearest neighbors, KNN)算法預測作業的運行時長并且用留一法和十字交叉驗證和統計學的方法為其查找相關系數。文獻[23]以用戶提交最近的兩次作業的平均時長預測作業的運行時間。文獻[24]用多項式模型提高作業運行時間預測的精度，它也是通過機器學習的方法，期望通過預測時間從而優化回填調度算法。文獻[25]基于KNN算法用模板找尋相似的歷史作業，并用遺傳算法為模型尋找最佳的參數。文獻[26]預測特定類型的應用，預測精度有一定的提升。文獻[27]提出為避免異常，當預測時間嚴重偏離應該提醒管理員。文獻[28]總結了機器學習的應用，提出了多種表征特征的方法。

作業名由用戶命名，用以指征作業的特征，通常表述作業所執行的功能和運行參數等，擁有相同作業名的作業執行的功能類似，所以運行時間可能相近。文獻[20]通過作業名將長短作業分離，進一步定義模板訓練機器學習模型，但同一作業名下也有可能同時出現長作業和短作業。Last-2[23]算法簡單高效地尋找相同歷史作業名的最近兩次提交的平均時間作為預測時間，但預測精度到60%后存在瓶頸。有大量的文獻對數據的新特征進行探索：文獻[29]在預測有關原子應用時加入原子的庫倫矩陣特征從而提高特定應用的預測效果；文獻[30]在輸入的特征中加入作業運行的路徑從而提高的預測效果。

有大量的研究將作業名按照字符串的距離[25]或者僅保留字母信息的手段將相似的作業名歸類，再利用機器學習的手段預測作業的運行時間，但對于命名復雜的作業名，難以通過以上的方法將相似的作業名聚類。本文通過分析用戶的命名習慣，將作業名分為三種組成成分，不同成分的聚類方式不同且成分之間的聚類順序也不同，最后實驗表明所提出的LSN聚類方法能有效地將作業名更好地聚類，從而提升了數據質量，進一步地提高了預測的精度。

2 作業時間預測框架

數據來源于兩臺高性能計算機器：國家超級計算天津中心(天津超算中心)和中國空氣動力研究與發展中心(CARDC)。兩臺機器的數據都是由Slurm[31]記錄的真實作業數據。數據處理流程如圖1所示。

圖1 實驗流程概覽Fig.1 Overview of experiment process

步驟1：數據預處理階段是清洗作業日志中的臟數據，比如空值、運行時間為0的作業、Linux腳本文件等少部分對預測時間沒有效果的作業，詳情見表1。

表1 被過濾的作業名稱

步驟2：僅僅保留作業狀態為“Completed”的作業。其他狀態(“Canceled”“Node_fail”“Pending”等)的作業無作業完整的生命周期，所以不考慮預測它們的運行時間。

步驟3：根據提出的LSN聚類算法聚類相似的作業名。

步驟4：過濾小量作業的用戶，因為機器學習模型的良好性能得益于大規模的訓練數據。小量的作業對提升模型性能沒有幫助且不預測小量作業的時間對系統的性能影響較小。

步驟5：過濾相似作業集合中的小作業集，相似作業集來源于LSN作業名聚類的結果。為了取得較為規整的作業數據，保留所有含有100條以上作業的集合。

步驟6：將過濾后的數據用于時間預測，將整體的數據按照3 ∶1的比例分成訓練集和測試集，訓練集訓練時間預測模型，測試集用訓練好的模型來預測時間。

3 LSN聚類算法

3.1 作業名的相似性

傳統的時間預測方法是選取能表示作業運行的特征放入機器學習模型中訓練，比如作業的CPU數量、作業提交的時刻、用戶的名稱、隊列名稱等。作業名是作業重要的特征之一，它由用戶命名，并且含有作業運行的語義信息。作業名的樣例如表2所示。

表2 超算中真實作業名的樣例

如圖2所示，集群中的作業名種類繁多，結構豐富。雖然難以歸納作業名的命名規律，但是許多作業名之間彼此相似,相似的作業往往有相似的運行時間。為提高數據的質量，可聚類擁有相似作業名的作業。

圖2 作業名的樣例和彼此相似的作業名Fig.2 Sample of job names and job names that are similar to each other

3.2 LSN聚類詳細內容

根據集群中作業名的相似性提出LSN聚類算法，目的是將相似的作業名聚類。LSN聚類的流程如圖3所示。LSN算法由字母聚類、結構聚類和數字聚類三個聚類層級組成，如算法1所示。作業名集合經過第一層字母聚類后，其中的作業名被聚合成若干個子集1；每個子集1經過第二層結構聚類后被聚合成若干個子集2；每個子集2經過第三層數字聚類后被聚合成若干個子集3。整個作業名集合經過LSN聚類后生成若干個子集3，聚類的結果輸出為所有子集3的集合。

圖3 LSN聚類算法Fig.3 LSN clustering algorithm

3.2.1 作業名的成分特征

作業名實際上是字符的集合，如圖2所示。作業名的組成成分可被歸納為字母、數字和特殊字符。作業名的主體為字母和數字，而特殊字符連接字母序列或數字序列，凸顯字母或數字序列的層次關系，起著結構化作業名這一重要作用。

算法1 LSN作業名聚類算法

作業名的相似性可歸納為字母、結構和數字這三個成分特征的相似性。因為相似作業名的成分特征極為相似，所以LSN算法以聚類作業名的成分特征為主要思想，根據各個成分的重要性，構造出字母-結構-數字的層級聚類算法。

3.2.2 LSN聚類層級1：字母聚類

因為作業名中所包含的語義信息很大程度上來源于字母，所以LSN層級聚類的第一層為字母聚類。字母聚類的流程如圖4所示。首先僅保留作業名中的英文字母，緊接著統一大小寫，剩余的字母序列為該作業名的特征，最后將含有相同特征的作業名聚合為一類得到若干個圖3中的子集1。字母聚類能聚合具有一定相似度的作業名，并且在CARDC的數據集中取得了較好的聚類效果。作業名中包含的字母個數越多，字母聚類的效果就越好，但是當作業名中字母個數較少甚至沒有字母的時候，子集1內容易存在大量互不相似的作業名。如表3所示，含有相同的字母在結構上或者參數類別上有較大的差異。

圖4 字母聚類流程Fig.4 Letter clustering algorithm flowchart

表3 作業名的字母聚類算法的結果

3.2.3 LSN聚類層級2：結構聚類

LSN聚類的第二層是結構聚類，因為作業名中含有結構化的語義信息。作業名集群中含有的特殊字符如表4所示，其中被標紅字符常被用戶用來連接字母或數字序列，包括“+”“=”“-”“_”和空格(稱之為結構字符)。LSN中由此提出“結構聚類”的概念，因為在擁有相同的字母特征的作業名集合里，作業名之間仍然存在明顯的差異，這個差異主要來源于作業名的命名結構，如表5所示，這9個作業名經過字母聚類后屬于3個類別，但每一類的內部作業彼此之間結構不同又可以進一步細分成更小子集。結構聚類的方法是將每個字母聚類子集里的作業名以結構字符分節分成若干小節，若小節之間的連接方式相同，則聚為一類。連接方式的相同包括結構字符的數量相同、種類相同、順序相同。

表4 作業名的字符組成

表5 有著不同結構的相似作業名

如圖3所示，每個子集1在結構聚類層級上聚類分成若干個子集2。經過結構聚類后，字母量較少的相似作業名在結構聚類層級能被較好地聚類。但在無字母的作業名集合中，每個子集2仍然包含相互之間存在明顯差異的作業名。因此LSN針對無字母的作業集合，附加額外的聚類層級——數字聚類。

3.2.4 LSN聚類層級3：數字聚類

LSN聚類的第三層級是數字聚類。作業名集合中含有大量的無字母的作業名，該類作業僅僅由數字和特殊字符組成。由于字母不能為該類作業提供豐富的語義信息，LSN將該類作業名在結構聚類后附加數字聚類。在結構聚類層級上，每個作業名被結構字符分割成若干個子節，LSN抽去子節中的非結構特殊字符(“.”除外)，所有的子節由數字組成。由于數字的差異無實際意義，因此LSN將數字歸類。數字可歸為4個類別——小數、自然數、編號、長序列，如表6所示。LSN判別小數的依據是子節帶有“.”；判別編號的依據是子節以0開頭并且長度大于2；若非0開頭但是字符長度大于3，則屬于長序列類別，并且不同的子節長度對應不同的長序列子類別，此時日期就被分為長序列中的四位數的類別，比如2020；最后LSN將不屬于上述所有類別的數字類型歸為自然數類別。LSN將每個子節的數字類別都相同的作業名聚類，如圖3所示，每個子集2在數字聚類層級上聚類為若干個子集3。

若字母僅存在作業名的后綴中，該類作業同樣也無語義信息，將后綴名為“.sh”和“.txt”類型的作業名也納入數字聚類。

表6 數字類別

3.3 聚類結果評估

與傳統的聚類算法對比，LSN算法具有較強的作業名聚類效果。分別以近鄰傳播(affinity propagation, AP)聚類算法和最大相似長度聚類算法與LSN聚類算法進行對比驗證。

3.3.1 AP傳播聚類算法

AP傳播算法無須先指定類別的數量，從而達到自動化聚類的效果[32]。它將樣本中所有的數據點視為潛在的聚類中心，在表示樣本之間相互距離的矩陣中，對角線上的值越大，則對應該位置的樣本就越有可能成為聚類的中心。AP算法迭代所有的點，判斷該點和中心點的吸引度、歸屬度，直到產生所有的高質量的聚類中心停止。采用字符串之間的編輯距離表示兩個作業名之間的相似度，距離越大相似度越低。

AP算法聚類作業名后，每個類別的作業名稱都較為相似，但是類別的數量過多且相似的作業名分散在不同的類別里，如表7所示。AP算法的聚類效果較差。

表7 AP算法聚類結果

3.3.2 最大相似長度聚類算法

相似的作業名之間包含相同的子字符串，如表8所示。最長公共子序列[33](longest common sequence, LCS)可衡量兩個作業名的相似度。

表8 含有公共子序列的作業名集合

由于作業名的長短差異很大，相似的短作業名的公共子序列也較短。因此用公共子序列的長度與作業名的總長度的比值來判斷相似。作業名之間若含有公共子序列并且子序列的長度超過各自作業總長度的75%則聚為一類。

LCS聚類結果與AP聚類算法相比有明顯的改善，類別的數量有明顯的減少，并且每類別的作業名都有公共的子序列。聚類的效果如表9所示。雖然每個類別的作業名都有公共的子序列，但是每個類別的作業名的相似程度有所降低。

表9 LCS聚類結果

3.3.3 LSN算法聚類結果

LSN聚類算法由字母聚類、結構聚類、數字聚類三個層級組成。聚類結果如表10所示。雖然不同類別的作業名之間存在一定的相似性，但是同一類別下的作業名相似度極高。

表10 LSN算法聚類結果

4 實驗結果與分析

4.1 實驗流程和評估方法

本實驗從CARDC的機器得到的歷史數據集一共57 064條，從天津超算中心得到的數據集一共67 821條。只保留完成狀態的作業，經過作業狀態和作業名的篩選后，CARDC數據集中共有有效數據53 332條以及2 000余種作業名，天津超算中心數據集共有有效數據62 073條以及7 285種作業名。將以上兩個有效作業數據集合作為實驗的輸入。經過LSN聚類后，每個作業名都對應一個所屬類別的編號。將用戶名和作業名類號進行哈希編碼。

由于機器學習模型只接受數值型的輸入字段，因此在輸入的作業字段中，用UID代替用戶名；相對時間戳代替作業提交時刻，其計算方法如式(1)所示；作業名所屬聚類編號代替作業名；用戶所申請的CPU字段表示CPU數量，因為用戶申請的CPU數目實際上是申請的核數，其數值等于或者小于作業占用CPU字段的核數，因此用戶申請CPU更加能準確表示作業的資源占有數目。

trelative_i=ti-min(t1,t2,…,tn)

(1)

式中，trelative_i表示相對時間，ti表示第i個作業的真實時間。

將歷史作業數據集按作業提交時間的先后排序，以3 ∶1的比例分成訓練集和測試集，訓練集中作業的UID、提交時間、申請CPU和作業名類別作為訓練特征，作業的實際運行時間作為訓練的目標。以預測精度評估預測的準確性，如式(2)所示。Acc指的是預測精度，tpredict是預測的時間值，treal是該作業實際運行時間的真實值，時間單位是s，精度用百分位表示。

(2)

4.2 時間預測模型

時間預測的方法采用機器學習的經典預測模型：SVR[34]、決策樹[35](decision tree, DT)和RF[36]。

SVR是一種監督機器學習方法，它在n維輸入變量之間構建線性回歸函數，計算綜合損失函數的值，并且將特征通過核函數映射到高維空間，是非線性回歸預測。

DT是一個樹形的模型，它內部的節點在訓練的時候根據信息熵分裂，選取基尼系數評判信息增益，是監督機器學習的經典模型之一。

RF是構造多顆決策樹并且最終的輸出值由多個決策樹共同決定，在很多的預測算法上都體現了其優勢性，其也是經典的機器學習方式之一。

4.3 預測結果

基于兩臺機器2020年9月—2021年9月一年的真實歷史作業數據，采用同樣的實驗方法，包括數據預處理、作業名聚類、時間預測。以預測精度評估預測的準確性。

4.3.1 作業名有無聚類對比

將未被聚類的作業數據集和經過LSN聚類的數據集分別放入模型中訓練。在CARDC的數據集中一共獲得53 332條有效數據，其中近40 000條數據作為訓練集，剩下的近13 000條作業作為測試集。分別用SVR、DT和RF的機器學習模型預測作業運行時間，實驗結果如圖5所示。在CARDC的數據中，在無作業名聚類的情況下，所有模型的預測精度在69%～79%之間；SVR模型的預測精度較低僅為69.2%，DT和RF的預測精度差距較小，都在78%左右。在LSN作業名聚類的情況下，這三個模型的預測精度均有1%～3%的提升，預測精度在71%～80%之間。

圖5 CARDC的作業運行時間預測結果Fig.5 CARDC′s job running time prediction result

在天津超算中心的數據集中，一共獲得了62 073條有效數據，同樣以3 ∶1的比例分成近47 000條作業作為訓練集、近15 000條作業作為測試集。SVR、DT和RF的模型的預測結果如圖6所示。在無作業名的聚類情況下，三個機器學習模型的預測精度是62%～74%，天津超算中心的作業預測精度整體較低于CARDC的預測精度，主要原因是天津超算中心的作業種類更多、數據量大、用戶多，作業的時間較難預測；經過LSN聚類后，SVR預測精度由62.8%上升至74.6%，DT預測精度由70.2%上升至75.7%，RF預測精度由73.5%上升至76.8%。相比于CARDC的數據，天津超算中心經過作業名LSN聚類后時間提升精度更大。天津超算中心的數據中含有7 000多種作業名而CARDC的數據中僅含有2 000多種作業名。天津超算中心的作業數據種類更豐富，應用LSN算法的聚類效果更明顯，時間的預測精度提升更大。

圖6 天津超算中心的作業運行時間預測結果Fig.6 Job running time prediction result of Tianjin supercomputer center

在兩臺機器的數據集中，三個預測時間的模型里，SVR的預測精度相對低于DT和RF的預測精度，這主要是因為不同的模型訓練的算法不同，SVR屬于非線性回歸預測，DT和RF屬于分類預測。由于作業的運行時間范圍差異較大，從數秒到數十萬秒不等，回歸算法建立所有數據之間總損失最小的超平面，因此容易在時間范圍差異較大的數據集中產生與真實值偏離較大的預測值，從而降低作業時間的預測精度。分類算法的預測值從真實值中產生，因此分類預測更適用于時間范圍差異大的數據集合。

4.3.2 不同聚類算法的對比

將AP聚類算法、LCS聚類算法和LSN聚類算法得出的三種聚類結果分別放入相同的模型中預測時間。CARDC的作業的三種聚類算法的預測結果如圖7所示。在AP傳播算法的聚類結果中，三個模型的預測精度在69%～79%；在LCS的聚類結果中，三個模型的預測精度在68%～80%；在LSN算法的聚類結果中，三個模型的預測精度在71%～80%。仍然是DT和RF算法的預測精度整體上較高于SVR，而且經過LSN聚類后的數據集的預測精度在每個模型上都高于經過其他算法聚類后的數據集，主要是由于LSN聚類的效果相對于其他聚類算法更好，數據的質量更高。

圖7 CARDC作業不同聚類算法運行時間預測結果Fig.7 Runtime prediction results of different clustering algorithms for CARDC jobs

圖8 天津超算中心作業不同聚類算法運行時間預測結果Fig.8 Runtime prediction results of different clustering algorithms for Tianjin supercomputer center jobs

天津超算中心的作業的三種聚類算法的預測結果如圖8所示。在AP傳播算法的聚類結果中，三個模型的預測精度在62%～75%之間；在LCS的聚類結果中，三個模型的預測精度在70%～74%之間；在LSN算法的聚類結果中，三個模型的預測精度在74%～77%之間。不同聚類算法對SVR的精度影響較大，對DT和RF的精度影響較小，但是聚類的質量對時間預測的準確性均有一定的影響。在每個模型中，LSN聚類算法的數據均比其他兩種聚類算法的數據預測精度高，因為LSN的作業名聚類效果更好，相應的數據質量更高。于是采取基于LSN聚類算法的分類模型預測的結果作為時間預測的最終結果，即79.8%的平均精度。

4.3.3 LSN聚類的特征重要性對比

DT模型的訓練過程是通過基尼系數判斷信息增益最大的特征，分裂新的分支而形成的一個樹形結構的預測模型。分裂次數多的特征在整個決策樹模型的構建過程中起到了相對重要的作用。對比DT模型下的各個特征在LSN聚類前后的重要性。如圖9(a)所示，在CARDC的數據中提交時間特征的重要性達到91.5%，作業名的重要性僅為2.7%。如圖9(b)所示，數據經過LSN聚類后，所有其他特征的重要性變化均很小但作業名特征的重要性有升高。如圖10(a)所示，在天津超算中心的數據中提交時間特征重要性仍然最高，但相較于CARDC的數據其重要性降低，作業名的重要性上升為12.3%。如圖10(b)所示，經過LSN聚類后作業名特征的重要性上升至15.3%，上升程度明顯，因為LSN聚類的特征在模型構建過程中的貢獻度有所提升。

(a) 作業名聚類前各個特征的重要性(a) Importance of each feature before job name clustering

(a) 作業名聚類前各個特征的重要性(a) Importance of each feature before job name clustering

5 結論

本文的數據來自CARDC和天津超算中心2020年的真實歷史數據，通過數據清洗整理出較高質量的作業數據。為提升時間預測效果，提出LSN算法聚類作業名。該算法在CARDC和天津超算中心的作業名聚類中獲得了顯著的聚類效果。將預處理后的數據分別放在SVR、DT和RF的機器學習模型上訓練和預測。實驗證明經過作業名聚類的數據在這3個模型上都取得了時間預測精度的提升，能達到79.8%的精度。在未來的工作中將進一步改進作業名聚類算法，深入挖掘作業名包含的語義信息，關聯作業名和作業運行時間，提高作業運行時間的預測精度。