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

摘要

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

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

1 研究背景

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

超算集群系統(tǒ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)定性、高效性等。在超算服務業(yè)務開展過程中，主要使用 FIFO（First In First Out，先入先出）調(diào)度機制分配任務，將所有的作業(yè)統(tǒng)一提交到一個隊列中，并按照提交的先后順序依次運行隊列中的作業(yè)，但隨著超算用戶、業(yè)務量、業(yè)務類型的增多，傳統(tǒng)的FIFO調(diào)度機制已經(jīng)不能滿足目前超算業(yè)務調(diào)度的需求。另外，在只考慮作業(yè)優(yōu)先級的調(diào)度方法中，由于考慮因素單一，導致優(yōu)先級低的業(yè)務不能及時調(diào)度，降低了作業(yè)調(diào)度的公平性和時效性。在現(xiàn)有的資源分配方法中，通常只考慮將所有計算資源作為一個統(tǒng)一的計算資源池，用戶如果有計算需求，就分配一塊固定的計算資源，導致計算資源劃分不靈活、使用效率低。

2 算法總體框架

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實驗與分析

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

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

6 結(jié)束語

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

參考文獻

[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]張愛科，謝翠蘭.基于公平性和負載均衡的云計算任務調(diào)度算法[J]，計算機應用與軟件，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)中的應用[J].計算機應用，1999（08）.

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

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