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

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

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

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

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

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

針對(duì)現(xiàn)有GPU任務(wù)調(diào)度系統(tǒng)在多任務(wù)環(huán)境下不能保證圖形任務(wù)響應(yīng)時(shí)間的問(wèn)題,提出基于分類(lèi)和多優(yōu)先級(jí)隊(duì)列(CPMQ)的調(diào)度方案,并在ARM的嵌入式GPU上實(shí)現(xiàn)驗(yàn)證。該方案中,將GPU的多任務(wù)劃分為圖形任務(wù)、通用計(jì)算任務(wù)和實(shí)時(shí)圖形3類(lèi)任務(wù)并分別建立隊(duì)列排隊(duì),其中圖形任務(wù)和通用計(jì)算任務(wù)按照優(yōu)先級(jí)在各自隊(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)度開(kāi)銷(xiāo)的情況下,將實(shí)時(shí)圖形任務(wù)的幀率提升了5%～20%。

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

對(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ù)競(jìng)爭(zhēng)GPU資源的情況下保證圖形任務(wù)的響應(yīng)速度,成為GPU多任務(wù)調(diào)度的關(guān)鍵以及新的研究方向與熱點(diǎn),例如Onur Mutlu等的研究[1]。

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

本文提出一種能保證圖形任務(wù)性能的基于分類(lèi)和多優(yōu)先級(jí)隊(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ū)動(dòng)程序的一部分,隨操作系統(tǒng)平臺(tái)和GPU硬件而變化,但是其核心調(diào)度框架是一致的,如圖1所示。

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

多個(gè)任務(wù)通過(guò)驅(qū)動(dòng)程序中的多任務(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ū)動(dòng)程序的多任務(wù)調(diào)度模塊發(fā)送來(lái)的任務(wù)后,會(huì)根據(jù)各個(gè)計(jì)算核心的運(yùn)行情況,將任務(wù)分配給具體的計(jì)算核心,任務(wù)執(zhí)行完后,會(huì)通過(guò)中斷通知驅(qū)動(dòng)程序,多任務(wù)調(diào)度模塊會(huì)進(jìn)行下一次任務(wù)調(diào)度。

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

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

面向多任務(wù)環(huán)境的調(diào)度方案,總是在快速響應(yīng)與公平分配資源之間權(quán)衡。在智能手機(jī)、智能電視等平臺(tái),圖形任務(wù)是關(guān)鍵應(yīng)用,能否被快速響應(yīng)與處理是評(pí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)度開(kāi)銷(xiāo),包括排隊(duì)時(shí)間、任務(wù)切換時(shí)間等。

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

(2)

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

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

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

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

2.1 分類(lèi)器

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

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

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

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

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

圖3 分類(lèi)器

2.2 排隊(duì)器

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

GPU任務(wù)以GPU命令的形式使用GPU,一個(gè)任務(wù)對(duì)應(yīng)多個(gè)GPU命令。按照GPU命令的有無(wú),將任務(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中對(duì)應(yīng)就緒態(tài)隊(duì)列和可運(yùn)行態(tài)隊(duì)列兩組隊(duì)列。隊(duì)列分為實(shí)時(shí)組和非實(shí)時(shí)組兩組。實(shí)時(shí)組中的隊(duì)列為實(shí)時(shí)圖形隊(duì)列,簡(jiǎn)稱(chēng)RT隊(duì)列;非實(shí)時(shí)組中有兩個(gè)隊(duì)列,分別為圖形任務(wù)隊(duì)列(簡(jiǎn)稱(chēng)G隊(duì)列)和通用計(jì)算任務(wù)隊(duì)列(簡(jiǎn)稱(chēng)C隊(duì)列),如圖5所示。

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

常用的排隊(duì)算法有公平排隊(duì)算法(fair queuing, FQ)、加權(quán)公平排隊(duì)算法(weighted fair queuing, WFQ)[8]、優(yōu)先級(jí)排隊(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)先級(jí)的考慮,但不能保證任務(wù)的實(shí)時(shí)性;PQ根據(jù)任務(wù)的優(yōu)先級(jí)排隊(duì),能優(yōu)先調(diào)度重要的任務(wù);EDF加入了對(duì)于任務(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ù)插入到正確的位置。

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

(3)

GPU優(yōu)先級(jí)是在任務(wù)的CPU優(yōu)先級(jí)的基礎(chǔ)上,結(jié)合運(yùn)行時(shí)間計(jì)算得到的。假設(shè)隊(duì)列中有n個(gè)任務(wù),對(duì)于任務(wù)i,CPMQ會(huì)記錄其使用GPU的累計(jì)時(shí)間Ti及其CPU優(yōu)先級(jí)Pi。Linux系統(tǒng)中,任務(wù)的CPU優(yōu)先級(jí)通過(guò)nice值表示,取值范圍為-20～19,值越小表示任務(wù)的優(yōu)先級(jí)越高;為了計(jì)算方便,令Pi=20-nice,其取值范圍為1～40,值越大任務(wù)優(yōu)先級(jí)越高。相同CPU優(yōu)先級(jí)下,任務(wù)累計(jì)執(zhí)行時(shí)間占所有任務(wù)總執(zhí)行時(shí)間的比例越小,GPU優(yōu)先級(jí)就越高,表示該任務(wù)沒(méi)有得到與其CPU優(yōu)先級(jí)相稱(chēng)的GPU時(shí)間,下次調(diào)度優(yōu)先考慮該任務(wù);相同累計(jì)執(zhí)行時(shí)間占比的情況下,CPU優(yōu)先級(jí)越高,GPU優(yōu)先級(jí)就越高,下次調(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)先級(jí)總是高于非實(shí)時(shí)組的優(yōu)先級(jí),直到RT隊(duì)列為空,分發(fā)器才在非實(shí)時(shí)組中選擇任務(wù)。非實(shí)時(shí)組中,分發(fā)器采用WFQ算法從G隊(duì)列和C隊(duì)列中選擇優(yōu)先級(jí)高的隊(duì)列并從中選擇任務(wù),兩個(gè)隊(duì)列的優(yōu)先級(jí)均使用該隊(duì)列中任務(wù)的平均優(yōu)先級(jí)

(4)

式中:Pi與式(3)中的相同。Q越大,該隊(duì)列的優(yōu)先級(jí)越高。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ù),對(duì)C隊(duì)列也采用同樣的調(diào)度方法。

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

統(tǒng)計(jì)反饋器負(fù)責(zé)監(jiān)測(cè)任務(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í)間)識(shí)別并處理問(wèn)題程序。對(duì)于在排隊(duì)的RT型任務(wù),更新其deadline值,即減去自上次調(diào)度以來(lái)的毫秒數(shù)值,并重新排隊(duì);對(duì)于非RT任務(wù),根據(jù)優(yōu)先級(jí)計(jì)算公式重新計(jì)算優(yōu)先級(jí),然后重新排隊(duì)。

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

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

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

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

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

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

(2)圖形任務(wù)GLCube。雖然Android系統(tǒng)是多任務(wù)的,但是Android圖形應(yīng)用程序在運(yùn)行時(shí)會(huì)獨(dú)占屏幕,同時(shí)只有一個(gè)圖形應(yīng)用程序能在屏幕上顯示。為了測(cè)試調(diào)度系統(tǒng)對(duì)多個(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è)圖形類(lèi)測(cè)試應(yīng)用。同時(shí)為了便于獲取FPS數(shù)據(jù),4個(gè)進(jìn)程會(huì)將每秒的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)過(guò)程 實(shí)驗(yàn)中,同時(shí)運(yùn)行NenaMark2、4個(gè)GLCube和matrix_mul,然后通過(guò)調(diào)整matrix_mul的參數(shù),逐漸增加系統(tǒng)的負(fù)載,觀測(cè)并記錄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)之前,通過(guò)CPMQ系統(tǒng)的分類(lèi)器配置接口為任務(wù)分類(lèi),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所示。相同條件下,二者的幀率都會(huì)下降,CPMQ對(duì)于實(shí)時(shí)圖形任務(wù)的調(diào)度比原驅(qū)動(dòng)要好,整體幀率都高于原驅(qū)動(dòng)。原驅(qū)動(dòng)中,當(dāng)通用計(jì)算的矩陣相乘次數(shù)大于3時(shí),圖形任務(wù)的幀率已經(jīng)降低到20幀/s以下,能明顯感覺(jué)到畫(huà)面的延遲和卡頓;而CPMQ調(diào)度系統(tǒng)中,當(dāng)矩陣相乘次數(shù)達(dá)到5時(shí),也基本能保證24幀/s的幀率。相比原驅(qū)動(dòng),CPMQ使實(shí)時(shí)圖形任務(wù)的整體性能提升5%～20%。

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

3.2.2 圖形任務(wù)性能 圖形任務(wù)如圖8所示。由于GLCube比NenaMark2簡(jiǎn)單,計(jì)算量較小,其幀率均比相同條件下的NenaMark2的幀率高。隨著矩陣相乘次數(shù)的增長(zhǎng),二者的幀率都會(huì)下降,CPMQ對(duì)于圖形任務(wù)的調(diào)度比原驅(qū)動(dòng)要好,但是由于有實(shí)時(shí)圖形任務(wù)的爭(zhēng)搶,圖形任務(wù)的整體性能提升沒(méi)有實(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í)間都處于上升趨勢(shì),由于CPMQ降低了通用計(jì)算任務(wù)對(duì)GPU的占用,導(dǎo)致計(jì)算時(shí)間加長(zhǎng),性能下降3%～25%。

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

4 結(jié) 論

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

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

李亮,王恩東,朱正東,等.應(yīng)用動(dòng)態(tài)生成樹(shù)的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]

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

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

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

國(guó)家高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2012AA010904);國(guó)家自然科學(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