基于集群計算的任務調度算法研究

汪瑩，陳新鵬

（四川大學計算機學院，成都610065）

0 引言

近年來，高速發展中的中國航天事業取得了非常優秀的成果，例如受到全世界關注的殲十戰斗機、殲二十戰斗機等。中國的航空工業發展起步雖晚于歐美國家，但后來居上，我國在航空工業發展中對于航空發動機的研究非常關注，發動機的研究對于航空事業極其重要，航空發動機必須在高溫高壓高負荷的情況下，保持穩定高效的工作性能，同時還必須考慮到自身重量、體積、成本和安全性等條件的約束，這導致航空發動機的研究進展極為緩慢且困難。實驗中要做到對發動機燃燒室模擬的最大化，真實實驗的成本花銷極高，故眾多研究人員多采取科學計算的方法來進行仿真模擬實驗，可以說科學計算現在已經成為學術研究中必不可少的一門科學工具[1]。科學計算（Scientific Computing）目前被應用在多個學科領域中，它使用計算機的高級計算功能來建模解決現實生產環境下產生的復雜問題，涵蓋了眾多學科的科學領域。其核心是研發對應的計算模型來模擬、理解自然系統，主要針對特定的現實問題設計對應的數學簡化模型，然后通過計算模擬尋求最優解來解決現實問題。在材料、物理、氣象、醫學、航天和軍事等學科領域中對科學計算的應用非常廣泛，這一類計算任務多為CPU 密集型任務（計算密集型任務），對于計算性能和計算完成時間要求很高，常采用HPC（高性能計算）集群來完成仿真實驗，因為HPC 集群可以提供單計算機所不能提供的超強計算能力。極速增長的計算需求和精度需求給科學計算仿真模擬平臺帶來了挑戰。僅提升CPU 芯片運算速度，已不能滿足計算需求，若是能優化集群節點計算任務的調度策略，最大化集群資源利用率，這對我國航空工業發展有極大促進作用。

1 集群計算概念

集群和分布式計算不同，分布式計算主要研究的是分散式系統（Distributed System）的計算過程。分布式系統是一組計算機，通過互聯網進行通訊和數據交互。分布式計算會把結構龐大的工程計算項目切分為許多小塊計算任務（task），再分別分發給分布于世界各地的計算機進行計算，各個計算機計算完畢后上傳結構，再將匯總的結果進行統一合并。通常分布式計算項目會征用世界各地志愿者提供的閑置計算資源。分布式計算的計算任務間具有獨立性，不存在數據依賴，故個別計算任務的出錯不會影響其余任務的計算進程和分布式計算不同，集群可被看作是一臺計算機，集群中的計算機通過局域網互連，實現各個節點間的高度緊密連接。高性能計算集群會把任務分配給集群中的不同計算節點，但節點間的數據通信時延非常小，可忽略不計。

2 算法研究

2.1 Min-Min算法

Min-Min 算法作為經典的啟發式的算法之一，現在依舊作為熱門的基礎對比算法之一，Min-Min 算法的核心思想是優先給予有最短完成時間的任務較高的優先級，總是優先執行具有最短完成時間的任務。假設有m 個待處理的任務；任務集T：{T1，T2，T3，…，Tm}，且每個任務相互獨立；n 個資源節點，節點集P：{P1，P2，P3，P4，…，Pn}，n 遠遠小于任務的數量，即n＜＜m，現舉例如下：

（1）首先對任務集T 中的每一個任務Ti，計算其被分配到每個資源節點的最早計算完成時間，用矩陣Am*n記錄，當T 集不為空，則反復執行該步驟。

（2）利用得到的最小完成時間矩陣Am*n，找到每個任務的最短完成時間以及其對應的分配資源節點。在所有任務的最短完成時間中，找到最小的任務完成時間，以及其對應的任務Ti和對應的被分配主機Pj，將任務Ti分配到計算結點Pj上。并從任務集T 中刪除任務Ti，并更新時間記錄矩陣Am*n。

在實際的生產調度中，Min-Min 算法的調度效果并不理想，Min-Min 算法將計算任務盡可能分配給處理速度較快的計算節點[2]，這會造成處理速度較慢的計算節點處于饑餓狀態。計算節點的資源利用率過低，負載不平衡，造成了資源節點的浪費。Min-Min 算法只單一的考慮了時間因素，有一定的局限性，不能滿足實際生產中對各種任務不同的QoS 要求，這是它的局限性所在。

2.2 Max-Min算法

與Min-Min 算法原理類似，Max-Min 在將任務映射到計算節點前，會預先計算每個任務被分配到n 個資源節點的最早完成時間，然后會在待分配的任務集合T 中選擇長任務，即選擇最早完成時間數值最大的任務Ti，將其分配到對應的節點上。同理，假設有m 個待處理的任務；任務集T：{T1，T2，T3，…，Tm}，且每個任務間相互獨立；n 個資源節點，計算資源節點集合P：{P1，P2，P3，P4，…，Pn}，即n＜＜m，現舉例如下：

（1）先對任務集合T 判空，若不為空，對T 中所有任務，計算每個任務被分配到所有計算節點上的最早完成時間，并將結果記錄到矩陣Am*n中；若T 集為空，則跳出此映射循環事件。

（2）利用矩陣Am*n，找到每個任務的最早完成時間以及其對應的資源節點。在所有的待分配任務中，找出最早完成時間數值最大的那個任務，Ti以及其對應的資源節點Pj，將Ti映射到資源節點上，并在任務池中刪除此任務Ti，跳回步驟（1）更新矩陣Am*n。

與MIN-MIN 類似，傳統的Max-Min 算法也具有其局限性，它會優先將長任務分配給計算節點，短任務具有較低的優先級，則會一直處于待分配狀態。當用戶的計算需求中短任務遠遠多于長任務時，會造成計算任務的調度失衡，任務的處理時延（slowdown）過長。Min-Min、Max-Min 算法單一的考慮計算任務的長短[3]，不能滿足實際生產任務中多變的QoS（服務質量）需求。隨著現實生活中的實際應用，需要處理的計算任務數據量愈發龐大，原有的傳統調度方法能提升的效率非常有限。為了處理海量計算數據，同時最小化任務完成時間和最大化資源利用率，考慮使用啟發式任務調度算法。

2.3 遺傳算法

近年來群體智能優化算法，廣泛的被應用于數值優化計算中，因其全局搜索能力強，不過分依賴于參數設置。遺傳算法也屬于啟發式進化算法的一種，任務調度問題中的一個可行解對應GA 算法中的一個染色體，染色體上有基因，對應于組成可行解的多個元素。遺傳算法運行時會進行N 次迭代，每次迭代過程中會生成多條染色體，即多個可行解。在這個過程中會由適應度函數來衡量每個可行解（任務調度方案）的優劣然后打分。得分較低的可行解會被淘汰，從而經過多次迭代后，可行解的質量會越來越優良[4]。

圖1 為遺傳算法流程圖，現將算法步驟詳細描述如下：

（1）初始化種群個體(染色體)，設置最大迭代次數為n，當前迭代次數count 為0。

（2）計算種群中每個個體的適應度函數值，并判斷當前迭代次數count 是否小于n，符合條件則跳轉到步驟3。

（3）根據步驟2 中算出的適應度函數值選擇出種群中的最優個體作為步驟4 的母體，跳轉到步驟4

（4）將步驟3 中挑選出的母體進行交叉操作，產生新個體，跳轉步驟5

（5）將上一步驟產生的新個體，在一定概率值的指導下，進行基因突變，并把當前迭代次數加一。跳轉到步驟2。

圖1 GA算法流程圖

3 實驗

在真實的系統環境中進行任務調度成本花銷過高，故而研究人員常采用模擬工具來完成仿真模擬實驗，來得到逼近最優解的可行調度方案，本文選擇了開源的仿真模擬平臺，CloudSim 進行實驗。驗證遺傳算法、Max-Min 算法、Min-Min 算法的調度性能。

CloudSim 是一個開源的仿真模擬框架[5]，有其自帶的簡單任務分配策略，若要將自己的算法引入Cloud-Sim 中進行任務分配，需要對CloudSim 中的自帶的分配策略進行重寫。實驗開始前需要對任務參數進行初始化，例如計算結點數量以及其內存大小和CPU 計算處理速率等。本次實驗設置了5 個資源結點，計算任務個數分別為25、50、100、1000，任務對于計算節點的需求，采用隨機函數隨機生成的模式，且任務之間相互獨立。由圖2 可知，遺傳算法的任務完成時間遠優于Min-Min、Max-Min 算法，且隨著任務數量的增大，遺傳算法的任務完成時間呈一個線性的緩速增長，而其余兩個算法，在任務量達到1000 時，任務完成時間激增，突破了5500ms。證明啟發式的遺傳算法性能優于傳統任務調度算法。

圖2 CloudSim實驗結果

4 結語

本文介紹了科學計算的研究意義，以及高性能計算集群的相關定義，根據待解決的問題，進行了問題定義。將啟發式優化算法中的遺傳算法和傳統的Min-Min、Max-Min 算法進行對比，分別闡述了這三個算法的問題模型及算法流程，然后基于給定的任務調度算法優化目標，在CloudSim 仿真模擬平臺上進行了模擬實驗，由最后得出的結果可知，遺傳算法相較于傳統的任務調度算法Min-Min、Max-Min 有更高的性能，完成了最小化任務完成時間，最大化資源利用率的優化目標。證明遺傳算法可用于解決實際生產環境中任務調度的相關問題，具有一定的研究意義。