一種作業(yè)調(diào)度和計算資源動態(tài)分配方法

楊涌 潘波 鄭建 劉光文 林小光 成亮

摘要

首先概述計算資源分配和作業(yè)調(diào)度技術(shù)現(xiàn)狀，然后以當(dāng)前作業(yè)調(diào)度事務(wù)特點為基礎(chǔ)，為了解決現(xiàn)有作業(yè)調(diào)度方法中計算資源劃分不靈活、使用效率低等問題，提出了一種計算資源動態(tài)分配方法;另外，充分了考慮任務(wù)的類型或關(guān)系等因素，提出了一種基于業(yè)務(wù)信息判斷的作業(yè)調(diào)度方法，該方法能夠避免優(yōu)先級低的作業(yè)不能及時調(diào)度的問題。通過具體測試驗證，該方法對基于高性能計算集群的各種應(yīng)用有很大的參考作用。

【關(guān)鍵詞】計算資源 作業(yè)調(diào)度 動態(tài)分配

1 研究背景

隨著信息技術(shù)的飛速發(fā)展，計算機系統(tǒng)需要處理的事務(wù)量大幅度增長。在摩爾定律巔峰時期，一切相對簡單，計算機系統(tǒng)可以期待處理器指數(shù)級的性能提升。隨著摩爾定律的終結(jié)，計算機性能提升很難直接通過升級硬件獲得，信息系統(tǒng)已變得越來越復(fù)雜。

超算集群系統(tǒng)以其卓越的性能價格比和良好的可擴(kuò)展性等因素成為當(dāng)今高性能計算機系統(tǒng)的主流體系結(jié)構(gòu)。如何合理高效地使用超算集群系統(tǒng)所包含的豐富的計算資源是非常緊迫的問題。作業(yè)調(diào)度算法是作業(yè)調(diào)度系統(tǒng)的核心，調(diào)度算法的優(yōu)劣決定了作業(yè)調(diào)度系統(tǒng)本身的質(zhì)量，決定了作業(yè)運行的穩(wěn)定性、高效性等。在超算服務(wù)業(yè)務(wù)開展過程中，主要使用 FIFO（First In First Out，先入先出）調(diào)度機制分配任務(wù)，將所有的作業(yè)統(tǒng)一提交到一個隊列中，并按照提交的先后順序依次運行隊列中的作業(yè)，但隨著超算用戶、業(yè)務(wù)量、業(yè)務(wù)類型的增多，傳統(tǒng)的FIFO調(diào)度機制已經(jīng)不能滿足目前超算業(yè)務(wù)調(diào)度的需求。另外，在只考慮作業(yè)優(yōu)先級的調(diào)度方法中，由于考慮因素單一，導(dǎo)致優(yōu)先級低的業(yè)務(wù)不能及時調(diào)度，降低了作業(yè)調(diào)度的公平性和時效性。在現(xiàn)有的資源分配方法中，通常只考慮將所有計算資源作為一個統(tǒng)一的計算資源池，用戶如果有計算需求，就分配一塊固定的計算資源，導(dǎo)致計算資源劃分不靈活、使用效率低。

2 算法總體框架

作業(yè)調(diào)度程序從后備作業(yè)中選取若干個作業(yè)到內(nèi)存并投入運行。它為被選中作業(yè)建立進(jìn)程并分配必要的資源，這時，這些被選中的作業(yè)處于執(zhí)行狀態(tài)。作業(yè)調(diào)度的功能是記錄系統(tǒng)中各作業(yè)的狀況，從后備作業(yè)隊列中挑選一批作業(yè)進(jìn)入執(zhí)行狀態(tài)，以及為被選中作業(yè)分配資源建立進(jìn)程和在作業(yè)執(zhí)行結(jié)束后釋放所占用的資源等。其中最主要的是從后備作業(yè)隊列中選取一批作業(yè)進(jìn)入執(zhí)行狀態(tài)。根據(jù)不同的目標(biāo)，將會有不同的調(diào)度算法。

本文提出了一種結(jié)合作業(yè)調(diào)度和計算資源動態(tài)分配的方法，旨在通過結(jié)合作業(yè)的信息對作業(yè)進(jìn)行優(yōu)化調(diào)度，實現(xiàn)其調(diào)度公平性，另外，通過資源的動態(tài)分配，實現(xiàn)資源的合理分配和利用，該方法的總體運行流程如下：

（1）根據(jù)用戶業(yè)務(wù)需求為用戶分配計算資源;

（2）根據(jù)用戶業(yè)務(wù)需求建立作業(yè)隊列，記錄每個作業(yè)的優(yōu)先級、作業(yè)提交時間、作業(yè)要求計算完畢時間等信息，并為每個作業(yè)分配相應(yīng)的計算資源;

（3）計算各隊列中各個作業(yè)預(yù)計運行時間長度;

（4）以用戶為調(diào)度范圍，采用作業(yè)的優(yōu)先級、預(yù)計運行時間長度為依據(jù)進(jìn)行作業(yè)調(diào)度;

（5）以作業(yè)包含的任務(wù)類型和關(guān)系為依據(jù)進(jìn)行任務(wù)調(diào)度;

（6）計算完畢，釋放計算資源。

3 計算資源動態(tài)分配方法

需要針對每個用戶建立一張作業(yè)信息表，用于記錄該用戶所有作業(yè)的計算資源、作業(yè)優(yōu)先級、記錄作業(yè)提交時間、作業(yè)要求計算完畢時間、當(dāng)前是否占用計算資源等信息。

作業(yè)信息表示例如表1所示。

根據(jù)每個用戶的業(yè)務(wù)需求，為其分配分配計算資源Ki（i=1，2，"""n，i為用戶編號）;管理節(jié)點將分配給節(jié)點i的計算資源分成兩部分：一部份為Ki*P，作為該用戶實際的計算資源，另外一部份為Ki*（1-P），作為該用戶的預(yù)留計算資源，其中，P為該用戶實際使用的計算資源與該用戶分配的總計算資源的比值，0≤P≤1。

另外，為了保證整個系統(tǒng)超算業(yè)務(wù)調(diào)度的順利進(jìn)行，在為每個用戶分配預(yù)留資源外，系統(tǒng)還將預(yù)留一部份資源備用。資源分配原理如圖1所示。

根據(jù)用戶需求建立作業(yè)隊列，并為每個作業(yè)分配計算資源，確定作業(yè)優(yōu)先級、記錄作業(yè)提交時間。

4 作業(yè)調(diào)度算法分析

為了優(yōu)化作業(yè)調(diào)度機制，提高作業(yè)調(diào)度的公平性和實時性，方法通過考慮計算時長估計和用戶設(shè)定的計算時長因素，提出的一種計算資源動態(tài)分配方法，具體作業(yè)調(diào)度算法如下：

（1）計算各隊列中各個作業(yè)預(yù)計運行時間;

其中，S為當(dāng)前作業(yè)的計算量，S'為歷史作業(yè)的計算量，T₀為歷史作業(yè)的運行時間。

（2）進(jìn)行作業(yè)調(diào)度;作業(yè)調(diào)度示意如圖2所示。

步驟1，以用戶為單位，對本用戶的所有作業(yè)優(yōu)先級進(jìn)行排序;

步驟2.對于每個用戶，以每個作業(yè)的預(yù)計完成時間長度為依據(jù)，判斷是否立即處理;計算作業(yè)要求計算完畢時間一當(dāng)前時間的值，并判斷作業(yè)要求計算完畢時間一當(dāng)前時間與作業(yè)的預(yù)計完成時間長度的關(guān)系;

步驟3，如果作業(yè)要求計算完畢時間一當(dāng)前時間>作業(yè)的預(yù)計完成時間長度，則不作處理，按作業(yè)優(yōu)先級順序進(jìn)行調(diào)度;

步驟4，如果作業(yè)要求計算完畢時間一當(dāng)前時間≤作業(yè)的預(yù)計完成時間長度，立即進(jìn)行作業(yè)調(diào)度，將該作業(yè)分配到本用戶的預(yù)留計算資源進(jìn)行調(diào)度;如果本用戶的預(yù)留計算資源不夠用，則申請系統(tǒng)獨立的計算資源進(jìn)行調(diào)度。

（3）以該作業(yè)的所有任務(wù)的關(guān)系為依據(jù)進(jìn)行任務(wù)調(diào)度，如圖3所示;

步驟1，在任務(wù)調(diào)度過程中，首先判斷該作業(yè)的所有任務(wù)的類型和關(guān)系;

步驟2，如果任務(wù)間是串行關(guān)系，則將任務(wù)按FIFO順序，分配該作業(yè)的全部資源進(jìn)行計算;

步驟3，如果任務(wù)間是并行關(guān)系，則需要確定該并行關(guān)系的任務(wù)數(shù)M，然后將該作業(yè)的計算資源分成M份，每個任務(wù)對應(yīng)其中1份計算資源，最后進(jìn)行并行計算。

（4）計算資源使用完畢，釋放計算資源。

當(dāng)作業(yè)使用資源完畢，更新作業(yè)信息表中占用資源信息為空，即釋放資源，并更新作業(yè)信息表中相關(guān)信息。

5 實驗與分析

通過將該算法應(yīng)用到超算平臺作業(yè)調(diào)度系統(tǒng)中，驗證該方法在不同業(yè)務(wù)類型作業(yè)調(diào)度中的運行情況，圖4為應(yīng)用了該算法的超算平臺實際作業(yè)調(diào)度情況。

通過一段時間的應(yīng)用驗證，能夠保障不同優(yōu)先級的業(yè)務(wù)能夠被及時調(diào)度，優(yōu)化了作業(yè)調(diào)度的公平性問題，說明了該方法是實用可行的。

6 結(jié)束語

本文提出的一種作業(yè)調(diào)度和計算資源動態(tài)分配方法，將計算資源按用戶需求進(jìn)行劃分，在每個用戶劃分的計算資源中預(yù)留計算資源，并在每個用戶劃分的計算資源外預(yù)留系統(tǒng)的計算資源：在作業(yè)調(diào)度時以用戶為單位進(jìn)行作業(yè)調(diào)度，充分考慮作業(yè)的優(yōu)先級、預(yù)計運行時間長度等因素進(jìn)行作業(yè)調(diào)度，充分了考慮任務(wù)的類型和關(guān)系等因素進(jìn)行任務(wù)調(diào)度，能夠避免優(yōu)先級低的作業(yè)不能及時調(diào)度的問題，保障所有作業(yè)在規(guī)定的時間能夠完成計算，提高了作業(yè)調(diào)度的公平性和時效性。該方法在超算平臺業(yè)務(wù)調(diào)度系統(tǒng)中具有較強的可操作性和一定的實用價值。

參考文獻(xiàn)

[1]Esmaeilzadeh H，Blem E，Amant R St，etal.Dark Silicon and the End ofMulticore Scaling[C].InternationalSymposium on Computer Architecture.IEEE，2012：122-134.

[2]Corujo A，Almeida B.Dynamic loadbalancing on heteroge-neousmulticore，multi GPU systems[C].International Conference on HighPerformance Computing&Simulation;（HPCS 2010），2010.

[3]張愛科，謝翠蘭.基于公平性和負(fù)載均衡的云計算任務(wù)調(diào)度算法[J]，計算機應(yīng)用與軟件，2015，32（02）：268-271.

[4]余祖峰，蔡啟先.基于工SM的動態(tài)優(yōu)先級調(diào)度算法[J].計算機工程，2011，7（04）：8-9.

[5]張登銀，許揚揚.基于時延的動態(tài)優(yōu)先級調(diào)度算法[J].計算機技術(shù)與發(fā)展，2011，33（02）：7-9.

[6]韓建民，鹿玲杰，王傳斌，賈莉抑.作業(yè)調(diào)度機制在計算機控制系統(tǒng)中的應(yīng)用[J].計算機應(yīng)用，1999（08）.

[7]叢龍水.動態(tài)優(yōu)先級作業(yè)調(diào)度算法與實現(xiàn)[J].計算機工程與應(yīng)用，2013，49（10）：267-270.

[8]涂剛，陽富民.基于動態(tài)優(yōu)先級策略的最優(yōu)軟非周期任務(wù)調(diào)度算法[J].計算機研究與發(fā)展，2004，12（11）：23-24.