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

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

ARMGPU的多任務(wù)調(diào)度設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

圖形處理器;多任務(wù);調(diào)度;排隊(duì)

對流暢的圖形界面和強(qiáng)大的計(jì)算能力的需求,使得當(dāng)前的嵌入式GPU應(yīng)用日趨廣泛。盡管嵌入式GPU上同時(shí)運(yùn)行著多個(gè)圖形任務(wù)和通用計(jì)算任務(wù),但是圖形任務(wù)直接面向最終用戶,決定了嵌入式系統(tǒng)的用戶體驗(yàn),是GPU上的關(guān)鍵任務(wù)。如何在多個(gè)任務(wù)競爭GPU資源的情況下保證圖形任務(wù)的響應(yīng)速度,成為GPU多任務(wù)調(diào)度的關(guān)鍵以及新的研究方向與熱點(diǎn),例如Onur Mutlu等的研究[1]。

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

本文提出一種能保證圖形任務(wù)性能的基于分類和多優(yōu)先級隊(duì)列(class priority multiple queue, CPMQ)的GPU多任務(wù)調(diào)度系統(tǒng)。在多任務(wù)環(huán)境下,CPMQ調(diào)度系統(tǒng)在保證其他任務(wù)正確執(zhí)行的前提下,有效降低了圖形任務(wù)的響應(yīng)時(shí)間,提升了應(yīng)用系統(tǒng)的圖形用戶體驗(yàn)。

1 GPU多任務(wù)調(diào)度框架與調(diào)度目標(biāo)

1.1 GPU多任務(wù)調(diào)度框架

GPU任務(wù)調(diào)度屬于操作系統(tǒng)GPU驅(qū)動程序的一部分,隨操作系統(tǒng)平臺和GPU硬件而變化,但是其核心調(diào)度框架是一致的,如圖1所示。

圖1 GPU多任務(wù)調(diào)度框架

多個(gè)任務(wù)通過驅(qū)動程序中的多任務(wù)調(diào)度模塊的調(diào)度而使用GPU,該模塊有兩個(gè)主要子模塊:排隊(duì)模塊按照一定的排隊(duì)規(guī)則將多個(gè)任務(wù)排序;分發(fā)模塊從排隊(duì)模塊中選擇下一個(gè)要運(yùn)行的任務(wù),將其發(fā)送給GPU硬件。GPU硬件由管理部件和計(jì)算核心等組成,前者負(fù)責(zé)為各個(gè)計(jì)算核心分配任務(wù),后者負(fù)責(zé)具體的計(jì)算。管理部件接收到驅(qū)動程序的多任務(wù)調(diào)度模塊發(fā)送來的任務(wù)后,會根據(jù)各個(gè)計(jì)算核心的運(yùn)行情況,將任務(wù)分配給具體的計(jì)算核心,任務(wù)執(zhí)行完后,會通過中斷通知驅(qū)動程序,多任務(wù)調(diào)度模塊會進(jìn)行下一次任務(wù)調(diào)度。

由此可見,GPU的調(diào)度分為多任務(wù)調(diào)度和多核心調(diào)度兩個(gè)階段,分別由GPU驅(qū)動程序和GPU硬件完成。

1.2 GPU多任務(wù)調(diào)度目標(biāo)

面向多任務(wù)環(huán)境的調(diào)度方案,總是在快速響應(yīng)與公平分配資源之間權(quán)衡。在智能手機(jī)、智能電視等平臺,圖形任務(wù)是關(guān)鍵應(yīng)用,能否被快速響應(yīng)與處理是評價(jià)用戶體驗(yàn)的重要因素。因此,本文的GPU多任務(wù)調(diào)度的目標(biāo)為在不顯著增加其他任務(wù)執(zhí)行時(shí)間的情況下,降低圖形任務(wù)的響應(yīng)時(shí)間,即提升圖形任務(wù)的幀率。

記T為任務(wù)的執(zhí)行時(shí)間,即響應(yīng)時(shí)間

T=Texec+Toverhead

(1)

式中:Texec為任務(wù)的真正執(zhí)行時(shí)間;Toverhead為調(diào)度開銷,包括排隊(duì)時(shí)間、任務(wù)切換時(shí)間等。

對于GPU而言,任務(wù)在計(jì)算核心之間的分配由GPU內(nèi)部的硬件完成,負(fù)責(zé)充分利用計(jì)算核心、核心間的負(fù)載均衡等工作,處于軟件層的GPU多任務(wù)調(diào)度不能直接控制計(jì)算核心的利用率,所以對于同一個(gè)任務(wù),Texec是不變的。要降低圖形任務(wù)響應(yīng)時(shí)間,就要降低其調(diào)度開銷Toverhead,對于同一個(gè)調(diào)度系統(tǒng)而言,一次調(diào)度的調(diào)度開銷Tsched為系統(tǒng)中所有任務(wù)調(diào)度開銷之和

(2)

式中:Tp_overhead為任務(wù)p的調(diào)度開銷。要降低圖形任務(wù)的調(diào)度開銷就需要增加其他任務(wù)的開銷,使得其他任務(wù)的執(zhí)行時(shí)間增加。

2 CPMQ多任務(wù)調(diào)度設(shè)計(jì)與實(shí)現(xiàn)

本文提出的CPMQ結(jié)構(gòu)如圖2所示,由分類器、排隊(duì)器、分發(fā)器及統(tǒng)計(jì)反饋器4部分組成。

圖2 CPMQ多任務(wù)調(diào)度系統(tǒng)整體結(jié)構(gòu)圖

2.1 分類器

分類器用于將任務(wù)分類,是CPMQ排隊(duì)系統(tǒng)與用戶的接口,分類信息是CPMQ調(diào)度系統(tǒng)運(yùn)行的基礎(chǔ)。為了保證圖形任務(wù)的響應(yīng)時(shí)間,CPMQ多任務(wù)調(diào)度系統(tǒng)將任務(wù)分類,以實(shí)現(xiàn)更加細(xì)粒度的任務(wù)調(diào)度。雖然GPU上運(yùn)行的任務(wù)數(shù)量多、類型廣,但作為主要面向圖形計(jì)算的處理器,其運(yùn)行的任務(wù)可分為以下幾類。

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

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

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

分類器由配置接口和分類配置庫兩個(gè)模塊組成,如圖3所示。在用戶提交任務(wù)之前,需要向CPMQ調(diào)度系統(tǒng)提交任務(wù)的類型信息,該信息將通過配置接口,保存在分類配置庫中。之后,當(dāng)提交任務(wù)的時(shí)候,分類器將從分類配置庫查找任務(wù)的分類信息并輸出,作為排隊(duì)器的排隊(duì)依據(jù)之一。

圖3 分類器

2.2 排隊(duì)器

排隊(duì)器按照一定的排隊(duì)規(guī)則維護(hù)所有任務(wù)的有序性,是CPMQ排隊(duì)系統(tǒng)的重點(diǎn)。

GPU任務(wù)以GPU命令的形式使用GPU,一個(gè)任務(wù)對應(yīng)多個(gè)GPU命令。按照GPU命令的有無,將任務(wù)分為就緒態(tài)和可運(yùn)行態(tài)兩個(gè)狀態(tài)。當(dāng)任務(wù)中的所有GPU命令執(zhí)行完后,該任務(wù)處于就緒狀態(tài);當(dāng)任務(wù)中有GPU命令時(shí),任務(wù)就處于可運(yùn)行狀態(tài)。狀態(tài)之間轉(zhuǎn)換如圖4所示。

圖4 任務(wù)狀態(tài)轉(zhuǎn)換圖

CPMQ中對應(yīng)就緒態(tài)隊(duì)列和可運(yùn)行態(tài)隊(duì)列兩組隊(duì)列。隊(duì)列分為實(shí)時(shí)組和非實(shí)時(shí)組兩組。實(shí)時(shí)組中的隊(duì)列為實(shí)時(shí)圖形隊(duì)列,簡稱RT隊(duì)列;非實(shí)時(shí)組中有兩個(gè)隊(duì)列,分別為圖形任務(wù)隊(duì)列(簡稱G隊(duì)列)和通用計(jì)算任務(wù)隊(duì)列(簡稱C隊(duì)列),如圖5所示。

圖5 排隊(duì)器與分發(fā)器結(jié)構(gòu)

常用的排隊(duì)算法有公平排隊(duì)算法(fair queuing, FQ)、加權(quán)公平排隊(duì)算法(weighted fair queuing, WFQ)[8]、優(yōu)先級排隊(duì)算法(priority queuing, PQ)[9]和最早截止時(shí)間優(yōu)先算法(earliest deadline first, EDF)[10]。FQ算法側(cè)重于任務(wù)調(diào)度的公平性,忽略了任務(wù)實(shí)時(shí)性需求;WFQ在FQ的基礎(chǔ)上加入了優(yōu)先級的考慮,但不能保證任務(wù)的實(shí)時(shí)性;PQ根據(jù)任務(wù)的優(yōu)先級排隊(duì),能優(yōu)先調(diào)度重要的任務(wù);EDF加入了對于任務(wù)截止時(shí)間的考慮,適用于實(shí)時(shí)任務(wù)的調(diào)度。

因此,排隊(duì)器中的實(shí)時(shí)圖形任務(wù)按照EDF算法排隊(duì),即按照任務(wù)的截止時(shí)間從小到大排列,截止時(shí)間最小的任務(wù)在隊(duì)首。當(dāng)一個(gè)任務(wù)加入實(shí)時(shí)圖形隊(duì)列時(shí),需要根據(jù)其截止時(shí)間信息將該任務(wù)插入到正確的位置。

對于圖形任務(wù)和通用計(jì)算任務(wù),優(yōu)先級決定了其在隊(duì)列中的位置,進(jìn)而決定了任務(wù)使用GPU的時(shí)機(jī)。優(yōu)先級越高,其在各自隊(duì)列中就能越早地得到調(diào)度,獲得GPU資源。圖形隊(duì)列和通用計(jì)算隊(duì)列內(nèi)部按照PQ算法在各自隊(duì)列中排隊(duì),即按照任務(wù)的優(yōu)先級從高到低排列。圖形任務(wù)和通用計(jì)算任務(wù)的GPU優(yōu)先級Gi的計(jì)算方法相同

(3)

GPU優(yōu)先級是在任務(wù)的CPU優(yōu)先級的基礎(chǔ)上,結(jié)合運(yùn)行時(shí)間計(jì)算得到的。假設(shè)隊(duì)列中有n個(gè)任務(wù),對于任務(wù)i,CPMQ會記錄其使用GPU的累計(jì)時(shí)間Ti及其CPU優(yōu)先級Pi。Linux系統(tǒng)中,任務(wù)的CPU優(yōu)先級通過nice值表示,取值范圍為-20～19,值越小表示任務(wù)的優(yōu)先級越高;為了計(jì)算方便,令Pi=20-nice,其取值范圍為1～40,值越大任務(wù)優(yōu)先級越高。相同CPU優(yōu)先級下,任務(wù)累計(jì)執(zhí)行時(shí)間占所有任務(wù)總執(zhí)行時(shí)間的比例越小,GPU優(yōu)先級就越高,表示該任務(wù)沒有得到與其CPU優(yōu)先級相稱的GPU時(shí)間,下次調(diào)度優(yōu)先考慮該任務(wù);相同累計(jì)執(zhí)行時(shí)間占比的情況下,CPU優(yōu)先級越高,GPU優(yōu)先級就越高,下次調(diào)度優(yōu)先考慮該任務(wù)。

2.3 分發(fā)器

分發(fā)器用于從排隊(duì)器的可運(yùn)行態(tài)隊(duì)列中獲取下一個(gè)要運(yùn)行的任務(wù),并將該任務(wù)發(fā)給GPU硬件執(zhí)行,是CPMQ調(diào)度系統(tǒng)與硬件的接口。

分發(fā)器分為任務(wù)選擇和任務(wù)提交兩個(gè)模塊。任務(wù)選擇模塊用于從排隊(duì)器的可運(yùn)行態(tài)隊(duì)列中選出一個(gè)可運(yùn)行任務(wù);任務(wù)提交模塊用于將任務(wù)選擇模塊選出的任務(wù)提交給GPU硬件執(zhí)行,任務(wù)將被提交給GPU的管理模塊,之后管理模塊將該任務(wù)分配給計(jì)算核心執(zhí)行。

任務(wù)選擇模塊按照PQ排隊(duì)算法在實(shí)時(shí)組和非實(shí)時(shí)組之間選擇任務(wù),實(shí)時(shí)組的優(yōu)先級總是高于非實(shí)時(shí)組的優(yōu)先級,直到RT隊(duì)列為空,分發(fā)器才在非實(shí)時(shí)組中選擇任務(wù)。非實(shí)時(shí)組中,分發(fā)器采用WFQ算法從G隊(duì)列和C隊(duì)列中選擇優(yōu)先級高的隊(duì)列并從中選擇任務(wù),兩個(gè)隊(duì)列的優(yōu)先級均使用該隊(duì)列中任務(wù)的平均優(yōu)先級

(4)

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

分發(fā)器優(yōu)先調(diào)度G隊(duì)列中的任務(wù),其中的任務(wù)被調(diào)度一次,Q值就減1,直到Q為0,或者小于通用隊(duì)列的Q值,或者隊(duì)列為空。然后再調(diào)度C隊(duì)列中的任務(wù),對C隊(duì)列也采用同樣的調(diào)度方法。

2.4 統(tǒng)計(jì)反饋器設(shè)計(jì)

統(tǒng)計(jì)反饋器負(fù)責(zé)監(jiān)測任務(wù)的執(zhí)行狀態(tài),統(tǒng)計(jì)任務(wù)的執(zhí)行結(jié)果,其由兩個(gè)模塊組成:統(tǒng)計(jì)模塊和反饋模塊,如圖6所示。

圖6 任務(wù)的執(zhí)行統(tǒng)計(jì)與反饋交互

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

反饋模塊會檢測一個(gè)任務(wù)是否是問題程序,判斷標(biāo)準(zhǔn)為:如果一個(gè)任務(wù)不斷產(chǎn)生大量的GPU命令,同時(shí),這些命令執(zhí)行時(shí)間很短,那么就認(rèn)為該任務(wù)是問題程序。CPMQ系統(tǒng)會給該類型任務(wù)兩次機(jī)會:當(dāng)該任務(wù)是第1次被認(rèn)定是問題程序時(shí),降低該任務(wù)所在的進(jìn)程的優(yōu)先級,來降低任務(wù)發(fā)送GPU命令的速率,從而降低該任務(wù)對GPU資源的占用,同時(shí),記錄警告次數(shù);若是第2次被認(rèn)定是問題程序,就將該任務(wù)的GPU優(yōu)先級置為最低,讓其他任務(wù)先執(zhí)行;若第3次被認(rèn)定是問題程序,就直接結(jié)束該任務(wù)。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境與過程

3.1.1 硬件平臺 實(shí)驗(yàn)使用基于三星Exynos 5420芯片的Arndale Octa開發(fā)板作為平臺,操作系統(tǒng)為Android 4.2。GPU為ARM的Mali T628,其中有6個(gè)計(jì)算核心。使用CPMQ替代Mali T628內(nèi)核驅(qū)動中的調(diào)度模塊。

3.1.2 實(shí)驗(yàn)測試程序

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

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

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

3.1.3 實(shí)驗(yàn)過程 實(shí)驗(yàn)中,同時(shí)運(yùn)行NenaMark2、4個(gè)GLCube和matrix_mul,然后通過調(diào)整matrix_mul的參數(shù),逐漸增加系統(tǒng)的負(fù)載,觀測并記錄NenaMark2和GLCube的FPS變化情況,以及matrix_mul的執(zhí)行時(shí)間變化情況,當(dāng)matrix_mul執(zhí)行完畢時(shí),結(jié)束本次實(shí)驗(yàn)并記錄數(shù)據(jù)。在Mali T628自帶的多任務(wù)調(diào)度系統(tǒng)和CPMQ多任務(wù)調(diào)度系統(tǒng)上分別運(yùn)行。

實(shí)驗(yàn)之前,通過CPMQ系統(tǒng)的分類器配置接口為任務(wù)分類,NenaMark2設(shè)置為實(shí)時(shí)圖形任務(wù),超時(shí)時(shí)間為5 ms,各個(gè)GLCube設(shè)置為圖形任務(wù),matrix_mul設(shè)置為通用計(jì)算任務(wù)。

3.2 實(shí)驗(yàn)數(shù)據(jù)分析

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

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

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

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

3.2.3 通用計(jì)算任務(wù)性能 通用計(jì)算任務(wù)如圖9所示。實(shí)驗(yàn)結(jié)果表明,在相同條件下,kernel單次循環(huán)平均執(zhí)行時(shí)間都處于上升趨勢,由于CPMQ降低了通用計(jì)算任務(wù)對GPU的占用,導(dǎo)致計(jì)算時(shí)間加長,性能下降3%～25%。

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

4 結(jié) 論

本文針對現(xiàn)有GPU多任務(wù)調(diào)度不能保證圖形任務(wù)響應(yīng)時(shí)間的問題,在嵌入式GPU平臺上設(shè)計(jì)并實(shí)現(xiàn)了基于CPMQ排隊(duì)算法的GPU多任務(wù)調(diào)度系統(tǒng)。CPMQ算法是本文在現(xiàn)有排隊(duì)算法的基礎(chǔ)上,結(jié)合GPU任務(wù)分類而提出的新算法。實(shí)驗(yàn)表明,在多任務(wù)環(huán)境下,該調(diào)度方案相比于ARM GPU的原有調(diào)度系統(tǒng)，CPMQ在不顯著增加通用計(jì)算任務(wù)的執(zhí)行時(shí)間和調(diào)度開銷的情況下,將實(shí)時(shí)圖形任務(wù)的幀率提升了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.

[本刊相關(guān)文獻(xiàn)鏈接]

張虹,鄭霄,趙丹.GPU加速竇房結(jié)計(jì)算機(jī)仿真的實(shí)現(xiàn)及優(yōu)化.2014,48(7):60-64.[doi:10.7652/xjtuxb201407011]

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

李亮,王恩東,朱正東,等.應(yīng)用動態(tài)生成樹的GPU顯存數(shù)據(jù)復(fù)用優(yōu)化.2013,47(10):44-50.[doi:10.7652/xjtuxb2013 10008]

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

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

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

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

趙保華,張煒,林華輝,等.一種通信有限狀態(tài)機(jī)的被動測試及其錯(cuò)誤診斷.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—),男,碩士生;梅魁志(通信作者),男,副教授。

國家高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2012AA010904);國家自然科學(xué)基金資助項(xiàng)目(61375023)。

時(shí)間:2014-10-31

10.7652/xjtuxb201412014

TP316

:A

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

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20141031.1642.016.html