ARMGPU的多任務調度設計與實現

丑文龍,梅魁志,高增輝,李博良

(西安交通大學電子與信息工程學院, 710049, 西安)

ARMGPU的多任務調度設計與實現

丑文龍,梅魁志,高增輝,李博良

(西安交通大學電子與信息工程學院, 710049, 西安)

針對現有GPU任務調度系統在多任務環境下不能保證圖形任務響應時間的問題,提出基于分類和多優先級隊列(CPMQ)的調度方案,并在ARM的嵌入式GPU上實現驗證。該方案中,將GPU的多任務劃分為圖形任務、通用計算任務和實時圖形3類任務并分別建立隊列排隊,其中圖形任務和通用計算任務按照優先級在各自隊列中排隊,實時圖形按照任務截止時間排隊。面向多隊列的任務調度,優先從實時任務隊列中選擇任務,并按照加權公平算法分別在圖形任務隊列和通用計算隊列中選擇任務。實驗結果表明:相比于ARM GPU的原有調度系統,CPMQ在不顯著增加通用計算任務的執行時間和調度開銷的情況下,將實時圖形任務的幀率提升了5%～20%。

圖形處理器;多任務;調度;排隊

對流暢的圖形界面和強大的計算能力的需求,使得當前的嵌入式GPU應用日趨廣泛。盡管嵌入式GPU上同時運行著多個圖形任務和通用計算任務,但是圖形任務直接面向最終用戶,決定了嵌入式系統的用戶體驗,是GPU上的關鍵任務。如何在多個任務競爭GPU資源的情況下保證圖形任務的響應速度,成為GPU多任務調度的關鍵以及新的研究方向與熱點,例如Onur Mutlu等的研究[1]。

面對多任務環境下圖形處理,Linux操作系統的直接渲染設施[2](direct rendering infrastructure, DRI),采用了先到先服務(first come first served, FCFS)的簡單調度策略。Kato等提出了一個GPU調度框架TimeGraph[3],在DRI的基礎上實現了資源預留和調度算法,提升了任務的實時性,其不足在于只支持使用GLSL[4]實現的通用計算任務。Bautin等提出了GPU資源管理框架GERM,主要致力于公平地為各個應用分配GPU的計算、存儲資源[5],其采用優先級和GPU命令執行時間預測的方法,提升了調度的公平性,不足在于需要修改用戶空間與GPU相關的函數庫,例如OpenGL庫。微軟在Vista及其之后的操作系統中開發了GPU驅動模型WDDM[6],實現了GPU多任務調度,但是并沒有開放其設計原理和實現方式。實驗結果表明,在高負載情況下圖形任務的響應時間會顯著增加。ARM在其Mali T6系列嵌入式GPU的Linux驅動程序中實現了完全公平調度算法[7](completely fair scheduling, CFS),該算法公平地對待每一個任務以公平地共享GPU,使用任務的優先級和任務運行時間作為調度的依據,在任務的優先級相同時,下一次優先調度使用GPU時間少的任務,不足在于沒有考慮到不同類型的GPU任務對用戶的重要性不同,無法實現區別對待。

本文提出一種能保證圖形任務性能的基于分類和多優先級隊列(class priority multiple queue, CPMQ)的GPU多任務調度系統。在多任務環境下,CPMQ調度系統在保證其他任務正確執行的前提下,有效降低了圖形任務的響應時間,提升了應用系統的圖形用戶體驗。

1 GPU多任務調度框架與調度目標

1.1 GPU多任務調度框架

GPU任務調度屬于操作系統GPU驅動程序的一部分,隨操作系統平臺和GPU硬件而變化,但是其核心調度框架是一致的,如圖1所示。

圖1 GPU多任務調度框架

多個任務通過驅動程序中的多任務調度模塊的調度而使用GPU,該模塊有兩個主要子模塊:排隊模塊按照一定的排隊規則將多個任務排序;分發模塊從排隊模塊中選擇下一個要運行的任務,將其發送給GPU硬件。GPU硬件由管理部件和計算核心等組成,前者負責為各個計算核心分配任務,后者負責具體的計算。管理部件接收到驅動程序的多任務調度模塊發送來的任務后,會根據各個計算核心的運行情況,將任務分配給具體的計算核心,任務執行完后,會通過中斷通知驅動程序,多任務調度模塊會進行下一次任務調度。

由此可見,GPU的調度分為多任務調度和多核心調度兩個階段,分別由GPU驅動程序和GPU硬件完成。

1.2 GPU多任務調度目標

面向多任務環境的調度方案,總是在快速響應與公平分配資源之間權衡。在智能手機、智能電視等平臺,圖形任務是關鍵應用,能否被快速響應與處理是評價用戶體驗的重要因素。因此,本文的GPU多任務調度的目標為在不顯著增加其他任務執行時間的情況下,降低圖形任務的響應時間,即提升圖形任務的幀率。

記T為任務的執行時間,即響應時間

T=Texec+Toverhead

(1)

式中:Texec為任務的真正執行時間;Toverhead為調度開銷,包括排隊時間、任務切換時間等。

對于GPU而言,任務在計算核心之間的分配由GPU內部的硬件完成,負責充分利用計算核心、核心間的負載均衡等工作,處于軟件層的GPU多任務調度不能直接控制計算核心的利用率,所以對于同一個任務,Texec是不變的。要降低圖形任務響應時間,就要降低其調度開銷Toverhead,對于同一個調度系統而言,一次調度的調度開銷Tsched為系統中所有任務調度開銷之和

(2)

式中:Tp_overhead為任務p的調度開銷。要降低圖形任務的調度開銷就需要增加其他任務的開銷,使得其他任務的執行時間增加。

2 CPMQ多任務調度設計與實現

本文提出的CPMQ結構如圖2所示,由分類器、排隊器、分發器及統計反饋器4部分組成。

圖2 CPMQ多任務調度系統整體結構圖

2.1 分類器

分類器用于將任務分類,是CPMQ排隊系統與用戶的接口,分類信息是CPMQ調度系統運行的基礎。為了保證圖形任務的響應時間,CPMQ多任務調度系統將任務分類,以實現更加細粒度的任務調度。雖然GPU上運行的任務數量多、類型廣,但作為主要面向圖形計算的處理器,其運行的任務可分為以下幾類。

(1)圖形任務,以下簡稱G任務。G任務是用戶能直接感覺到的純圖形計算類型的任務,需要較快的響應速度以保證用戶界面的流暢性,包括一般的應用程序等。

(2)通用計算任務,以下簡稱C任務。C任務是使用GPU的計算能力進行非圖形計算的任務,由于計算結果不用于顯示,所以相對于圖形計算任務而言,通用計算任務對響應時間的要求不嚴格,只要保證計算結果正確和計算時間合理,例如矩陣運算、大數據處理等。

(3)實時圖形任務,以下簡稱RT任務。這類任務是特殊的圖形任務,與一般圖形任務相比,RT任務需要更加快速的響應速度和更確定的響應時間,包括3D游戲等。

分類器由配置接口和分類配置庫兩個模塊組成,如圖3所示。在用戶提交任務之前,需要向CPMQ調度系統提交任務的類型信息,該信息將通過配置接口,保存在分類配置庫中。之后,當提交任務的時候,分類器將從分類配置庫查找任務的分類信息并輸出,作為排隊器的排隊依據之一。

圖3 分類器

2.2 排隊器

排隊器按照一定的排隊規則維護所有任務的有序性,是CPMQ排隊系統的重點。

GPU任務以GPU命令的形式使用GPU,一個任務對應多個GPU命令。按照GPU命令的有無,將任務分為就緒態和可運行態兩個狀態。當任務中的所有GPU命令執行完后,該任務處于就緒狀態;當任務中有GPU命令時,任務就處于可運行狀態。狀態之間轉換如圖4所示。

圖4 任務狀態轉換圖

CPMQ中對應就緒態隊列和可運行態隊列兩組隊列。隊列分為實時組和非實時組兩組。實時組中的隊列為實時圖形隊列,簡稱RT隊列;非實時組中有兩個隊列,分別為圖形任務隊列(簡稱G隊列)和通用計算任務隊列(簡稱C隊列),如圖5所示。

圖5 排隊器與分發器結構

常用的排隊算法有公平排隊算法(fair queuing, FQ)、加權公平排隊算法(weighted fair queuing, WFQ)[8]、優先級排隊算法(priority queuing, PQ)[9]和最早截止時間優先算法(earliest deadline first, EDF)[10]。FQ算法側重于任務調度的公平性,忽略了任務實時性需求;WFQ在FQ的基礎上加入了優先級的考慮,但不能保證任務的實時性;PQ根據任務的優先級排隊,能優先調度重要的任務;EDF加入了對于任務截止時間的考慮,適用于實時任務的調度。

因此,排隊器中的實時圖形任務按照EDF算法排隊,即按照任務的截止時間從小到大排列,截止時間最小的任務在隊首。當一個任務加入實時圖形隊列時,需要根據其截止時間信息將該任務插入到正確的位置。

對于圖形任務和通用計算任務,優先級決定了其在隊列中的位置,進而決定了任務使用GPU的時機。優先級越高,其在各自隊列中就能越早地得到調度,獲得GPU資源。圖形隊列和通用計算隊列內部按照PQ算法在各自隊列中排隊,即按照任務的優先級從高到低排列。圖形任務和通用計算任務的GPU優先級Gi的計算方法相同

(3)

GPU優先級是在任務的CPU優先級的基礎上,結合運行時間計算得到的。假設隊列中有n個任務,對于任務i,CPMQ會記錄其使用GPU的累計時間Ti及其CPU優先級Pi。Linux系統中,任務的CPU優先級通過nice值表示,取值范圍為-20～19,值越小表示任務的優先級越高;為了計算方便,令Pi=20-nice,其取值范圍為1～40,值越大任務優先級越高。相同CPU優先級下,任務累計執行時間占所有任務總執行時間的比例越小,GPU優先級就越高,表示該任務沒有得到與其CPU優先級相稱的GPU時間,下次調度優先考慮該任務;相同累計執行時間占比的情況下,CPU優先級越高,GPU優先級就越高,下次調度優先考慮該任務。

2.3 分發器

分發器用于從排隊器的可運行態隊列中獲取下一個要運行的任務,并將該任務發給GPU硬件執行,是CPMQ調度系統與硬件的接口。

分發器分為任務選擇和任務提交兩個模塊。任務選擇模塊用于從排隊器的可運行態隊列中選出一個可運行任務;任務提交模塊用于將任務選擇模塊選出的任務提交給GPU硬件執行,任務將被提交給GPU的管理模塊,之后管理模塊將該任務分配給計算核心執行。

任務選擇模塊按照PQ排隊算法在實時組和非實時組之間選擇任務,實時組的優先級總是高于非實時組的優先級,直到RT隊列為空,分發器才在非實時組中選擇任務。非實時組中,分發器采用WFQ算法從G隊列和C隊列中選擇優先級高的隊列并從中選擇任務,兩個隊列的優先級均使用該隊列中任務的平均優先級

(4)

式中:Pi與式(3)中的相同。Q越大,該隊列的優先級越高。Q的取值范圍為1～40。

分發器優先調度G隊列中的任務,其中的任務被調度一次,Q值就減1,直到Q為0,或者小于通用隊列的Q值,或者隊列為空。然后再調度C隊列中的任務,對C隊列也采用同樣的調度方法。

2.4 統計反饋器設計

統計反饋器負責監測任務的執行狀態,統計任務的執行結果,其由兩個模塊組成:統計模塊和反饋模塊,如圖6所示。

圖6 任務的執行統計與反饋交互

統計模塊統計任務的執行時間等參數,將更新后的執行時間代入式(3)并重新為任務排序;反饋模塊根據任務的行為(例如命令數量和命令執行時間)識別并處理問題程序。對于在排隊的RT型任務,更新其deadline值,即減去自上次調度以來的毫秒數值,并重新排隊;對于非RT任務,根據優先級計算公式重新計算優先級,然后重新排隊。

反饋模塊會檢測一個任務是否是問題程序,判斷標準為:如果一個任務不斷產生大量的GPU命令,同時,這些命令執行時間很短,那么就認為該任務是問題程序。CPMQ系統會給該類型任務兩次機會:當該任務是第1次被認定是問題程序時,降低該任務所在的進程的優先級,來降低任務發送GPU命令的速率,從而降低該任務對GPU資源的占用,同時,記錄警告次數;若是第2次被認定是問題程序,就將該任務的GPU優先級置為最低,讓其他任務先執行;若第3次被認定是問題程序,就直接結束該任務。

3 實驗及結果分析

3.1 實驗環境與過程

3.1.1 硬件平臺 實驗使用基于三星Exynos 5420芯片的Arndale Octa開發板作為平臺,操作系統為Android 4.2。GPU為ARM的Mali T628,其中有6個計算核心。使用CPMQ替代Mali T628內核驅動中的調度模塊。

3.1.2 實驗測試程序

(1)實時圖形任務。NenaMark2是用于GPU評測的軟件,其提供了3D渲染測試場景,包含了圖形計算中的常用操作,例如光照、粒子系統、紋理、動態陰影等,能比較全面地評價GPU。NenaMark2在測試完后會報告渲染過程中的平均幀率(frame per second, FPS),同時在運行過程中,也會顯示實時幀率。

(2)圖形任務GLCube。雖然Android系統是多任務的,但是Android圖形應用程序在運行時會獨占屏幕,同時只有一個圖形應用程序能在屏幕上顯示。為了測試調度系統對多個圖形任務的調度情況,本文實現了一個3D應用,其在屏幕上繪制4個旋轉著的立方體,顯示每個立方體的FPS,并且能和其他圖形應用程序同時運行。4個立方體屬于4個不同的進程,所以GLCube代表了4個圖形類測試應用。同時為了便于獲取FPS數據,4個進程會將每秒的FPS值保存在4個不同的文件中。

(3)通用計算任務。matrix_mul是使用OpenCL實現的矩陣相乘程序,其在kernel中計算1000×1000的兩個浮點矩陣的乘法運算。matrix_mul接收一個數字參數,表示矩陣相乘的次數,次數越大,則計算量越大,例如matrix_mul 2表示運行兩次高維矩陣相乘。單獨運行matrix_mul時,每一次矩陣相乘大概需要5 s。

3.1.3 實驗過程 實驗中,同時運行NenaMark2、4個GLCube和matrix_mul,然后通過調整matrix_mul的參數,逐漸增加系統的負載,觀測并記錄NenaMark2和GLCube的FPS變化情況,以及matrix_mul的執行時間變化情況,當matrix_mul執行完畢時,結束本次實驗并記錄數據。在Mali T628自帶的多任務調度系統和CPMQ多任務調度系統上分別運行。

實驗之前,通過CPMQ系統的分類器配置接口為任務分類,NenaMark2設置為實時圖形任務,超時時間為5 ms,各個GLCube設置為圖形任務,matrix_mul設置為通用計算任務。

3.2 實驗數據分析

3.2.1 實時圖形任務性能 實時圖形任務如圖7所示。相同條件下,二者的幀率都會下降,CPMQ對于實時圖形任務的調度比原驅動要好,整體幀率都高于原驅動。原驅動中,當通用計算的矩陣相乘次數大于3時,圖形任務的幀率已經降低到20幀/s以下,能明顯感覺到畫面的延遲和卡頓;而CPMQ調度系統中,當矩陣相乘次數達到5時,也基本能保證24幀/s的幀率。相比原驅動,CPMQ使實時圖形任務的整體性能提升5%～20%。

圖7 NenaMark2的幀率隨matrix_mul矩陣相乘次數的變化

3.2.2 圖形任務性能 圖形任務如圖8所示。由于GLCube比NenaMark2簡單,計算量較小,其幀率均比相同條件下的NenaMark2的幀率高。隨著矩陣相乘次數的增長,二者的幀率都會下降,CPMQ對于圖形任務的調度比原驅動要好,但是由于有實時圖形任務的爭搶,圖形任務的整體性能提升沒有實時圖形任務明顯,在1%～15%之間。

圖8 GLCube程序的幀率隨matrix_mul矩陣相乘次數的變化

3.2.3 通用計算任務性能 通用計算任務如圖9所示。實驗結果表明,在相同條件下,kernel單次循環平均執行時間都處于上升趨勢,由于CPMQ降低了通用計算任務對GPU的占用,導致計算時間加長,性能下降3%～25%。

圖9 matrix_mul隨其自身矩陣相乘次數的變化

4 結 論

本文針對現有GPU多任務調度不能保證圖形任務響應時間的問題,在嵌入式GPU平臺上設計并實現了基于CPMQ排隊算法的GPU多任務調度系統。CPMQ算法是本文在現有排隊算法的基礎上,結合GPU任務分類而提出的新算法。實驗表明,在多任務環境下,該調度方案相比于ARM GPU的原有調度系統，CPMQ在不顯著增加通用計算任務的執行時間和調度開銷的情況下,將實時圖形任務的幀率提升了5%～20%。

[1] JOG A, KAYIRAN O, NACHIAPPAN N C, et al. OWL: cooperative thread array aware scheduling techniques for improving GPGPU performance [C]∥ Proceedings of the 18th International Conference on Architectural Support for Programming Languages and Operating Systems. New York, NY, USA: ACM, 2013: 395-406.

[2] PAUL B. Introduction to the direct rendering infrastructure [EB/OL]. (2000-08-10) [2014-03-23]. http:∥dri.sourceforge.net/doc/DRIintro.html.

[3] KATO S, LAKSHMANAN K, RAJKUMAR R, et al. TimeGraph: GPU scheduling for real-time multi-tasking environments [C]∥ Proceedings of the 2011USENIX Conference on USENIX Annual Technical Conference. Berkeley, CA, USA: USENIX Association, 2011: 17-30.

[4] MARROQUIM R, MAXIMO A. Introduction to GPU programming with GLSL [C]∥ Proceedings of the 2009 Tutorials of the 22nd Brazilian Symposium on Computer Graphics and Image Processing. Washington, DC, USA: IEEE Computer Society, 2009: 3-16.

[5] BAUTIN M, DWARAKINATH A, CHIUEH T. Graphic engine resource management [C]∥Proceedings of the International Society for Optics and Photonics. Bellingham, WA, USA: SPIE, 2008: 68180O.

[6] PRONOVOST S. Windows display driver model (WDDM) v2 and beyond [C/OL]∥ Proceedings of the Windows Hardware Engineering Conference.[2014-03-23].http:∥ci.nii.ac.jp/naid/10018383501/.

[7] WONG C S, TAN I, KUMARI R D, et al. Towards achieving fairness in the Linux scheduler [J]. Operating Systems Review, 2008, 42(5): 34-43.

[8] BENNETT J C, ZHANG Hui. WF2Q: worst-case fair weighted fair queuing [C]∥ Proceedings of the 15th Annual Joint Conference of the IEEE Computer Societies on Networking the next Generation. Piscataway, NJ, USA: IEEE, 1996: 120-128.

[9] WONG H T. Packet scheduling using dual weight single priority queue: USA, 6570883 [P]. 2003-05-27.

[10]DOYTCHINOV B, LEHOCZKY J, SHREVE S. Real-time queues in heavy traffic with earliest-deadline-first queue discipline [J]. The Annals of Applied Probability, 2001, 11(2): 332-378.

[本刊相關文獻鏈接]

張虹,鄭霄,趙丹.GPU加速竇房結計算機仿真的實現及優化.2014,48(7):60-64.[doi:10.7652/xjtuxb201407011]

周秦武,隋芳芳,白平,等.嵌入式無接觸視頻心率檢測方法.2013,47(12):55-60.[doi:10.7652/xjtuxb201312010]

李亮,王恩東,朱正東,等.應用動態生成樹的GPU顯存數據復用優化.2013,47(10):44-50.[doi:10.7652/xjtuxb2013 10008]

張保,董小社,白秀秀,等.CPU-GPU系統中基于剖分的全局性能優化方法.2012,46(2):17-23.[doi:10.7652/xjtuxb 201202004]

向坤,陳娟,張安學,等.提高喇叭天線增益的超介質構建方法.2011,45(2):92-96.[doi:10.7652/xjtuxb201102019]

鄒華,高新波,呂新榮.一種八叉樹編碼加速的3D紋理體繪制算法.2008,42(12):1490-1494.[doi:10.7652/xjtuxb2008 12012]

劉曉東,尋亮,馬棟,等.基于球體追蹤的動態視差遮擋映射算法.2007,41(12):1401-1405.[doi:10.7652/xjtuxb200712 004]

趙保華,張煒,林華輝,等.一種通信有限狀態機的被動測試及其錯誤診斷.2007,41(6):640-644.[doi:10.7652/xjtuxb 200706003]

(編輯 武紅江)

DesignandImplementationofMultitaskSchedulingforEmbeddedARMGPU

CHOU Wenlong,MEI Kuizhi,GAO Zenghui,LI Boliang

(School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

A scheduling solution of class priority multiple queue (CPMQ) is proposed to solve the problem that the response time to graphic tasks is not ensured by existing task scheduling systems of GPU under multitask conditions, and the schedule is implemented on an embedded system. Multiple tasks on GPU are firstly classified into three classes of tasks, that is, graphic tasks, real-time graphic tasks and general purpose computing tasks. These three classes of tasks then queued respectively with different queuing policy. Graphic tasks and general purpose computing tasks are queued by their priorities, while real-time graphic tasks are queued by their deadlines. When the multi-class tasks are scheduled, real-time graphic tasks are selected at first, and then graphic tasks and general purpose computing tasks are selected out using a weighted fair queuing algorithm. Experimental results and comparisons with the original scheduling system of ARM’s GPU show that CPMQ increases the frame rate of reel time graphic tasks by 5%-20% without significant increase in execution time of general purpose computing tasks and scheduling expense.

graphic processing unit(GPU); multitask; scheduling; queuing

2014-06-23。

丑文龍(1989—),男,碩士生;梅魁志(通信作者),男,副教授。

國家高技術研究發展計劃資助項目(2012AA010904);國家自然科學基金資助項目(61375023)。

時間:2014-10-31

10.7652/xjtuxb201412014

TP316

:A

:0253-987X(2014)12-0087-06

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20141031.1642.016.html