文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2017.05.013
中文引用格式： 鄧藝，田澤，韓立敏. 一種基于負載均衡的3D引擎任務(wù)調(diào)度策略[J].電子技術(shù)應(yīng)用，2017，43(5)：55-59.
英文引用格式： Deng Yi，Tian Ze，Han Limin. A task scheduling strategy for 3D engine based on load balance[J].Application of Electronic Technique，2017，43(5)：55-59.
0 引言
3D引擎是圖形處理器(Graphics Processing Unit，GPU)的關(guān)鍵和核心，GPU技術(shù)經(jīng)過十多年發(fā)展，其硬件架構(gòu)和圖形流水線經(jīng)歷了從固定功能、分離渲染到統(tǒng)一渲染的三個發(fā)展階段，實現(xiàn)復(fù)雜圖形高效繪制，滿足日益多樣的圖形處理應(yīng)用需求。統(tǒng)一渲染架構(gòu)3D引擎內(nèi)單個統(tǒng)一染色器具備分時復(fù)用處理頂點或像素渲染任務(wù)的能力，可有效提升3D引擎計算核心的資源利用效率，是目前主流GPU廠商廣泛采用的3D引擎架構(gòu)。
圖形處理器的處理性能、吞吐量和資源利用效率與實施不同的任務(wù)調(diào)度實現(xiàn)策略密切相關(guān)。任務(wù)調(diào)度策略是統(tǒng)一渲染架構(gòu)3D引擎設(shè)計的關(guān)鍵及核心，通過對統(tǒng)一染色器執(zhí)行狀態(tài)的統(tǒng)一管理、執(zhí)行時間和執(zhí)行資源的統(tǒng)一調(diào)度，實現(xiàn)渲染任務(wù)的分配和染色器的狀態(tài)監(jiān)控功能。目前統(tǒng)一架構(gòu)3D引擎的調(diào)度策略設(shè)計面臨眾多挑戰(zhàn)，而國內(nèi)相關(guān)領(lǐng)域的研究仍處于初級階段，許多關(guān)鍵技術(shù)需要進一步探索和研究。
本文在分析統(tǒng)一架構(gòu)GPU的圖形繪制特點及現(xiàn)有調(diào)度策略的基礎(chǔ)上，提出了基于染色器預(yù)先分配的避免圖形繪制流水線死鎖策略，基于隊列統(tǒng)計的資源分配及負載均衡策略，實現(xiàn)染色器資源有限條件下多類型任務(wù)（頂點任務(wù)、像素任務(wù)等）的合理分配和統(tǒng)一管理，降低了調(diào)度方案硬件實現(xiàn)的復(fù)雜度，同時確保了高效的調(diào)度性能。論文給出基于負載均衡調(diào)度策略相關(guān)電路設(shè)計，各類復(fù)雜渲染場景的仿真結(jié)果表明這種負載均衡調(diào)度策略可有效地降低染色器資源的空閑時長和調(diào)度時間，提升染色器資源的利用率和3D引擎的處理效率。
1 統(tǒng)一渲染架構(gòu)3D引擎任務(wù)調(diào)度技術(shù)概述
基于對3D引擎圖形流水線的研究，統(tǒng)一渲染架構(gòu)之前的性能瓶頸主要在于像素渲染階段，即使分離渲染架構(gòu)中將1：3作為頂點與像素渲染引擎的黃金比例，依然無法適應(yīng)復(fù)雜多變的渲染場景的需求，因此資源利用率不足成為限制GPU性能提升的關(guān)鍵[1]。作為支持多任務(wù)的計算平臺，統(tǒng)一渲染架構(gòu)3D引擎中每個計算單元的任務(wù)處理效率可能不同，為充分利用系統(tǒng)資源，需要3D引擎具備監(jiān)控以及動態(tài)調(diào)度計算核心的能力。同時，統(tǒng)一渲染架構(gòu)3D引擎的核心處理性能主要由其任務(wù)調(diào)度能力和各個流處理器核的執(zhí)行能力表征，因而兼顧靈活、高效以及可靠的任務(wù)調(diào)度與資源分配方案是統(tǒng)一渲染架構(gòu)的3D引擎研究重點和關(guān)鍵技術(shù)。
根據(jù)任務(wù)性質(zhì)將任務(wù)調(diào)度問題劃分為靜態(tài)和動態(tài)的調(diào)度。某些具有確定處理時間、可預(yù)測的數(shù)據(jù)同步問題，甚至是各個任務(wù)數(shù)據(jù)之間確定依賴關(guān)系的問題，屬于靜態(tài)調(diào)度問題[2]。相較而言，某些需要適應(yīng)性更強的調(diào)度方案方能充分解決的問題，屬于動態(tài)調(diào)度問題。動態(tài)調(diào)度避免了因資源浪費導(dǎo)致的利用率不足和因資源過度利用造成的漫長響應(yīng)時間，但是動態(tài)調(diào)度中良好的適應(yīng)性往往需要更復(fù)雜的調(diào)度設(shè)計才能實現(xiàn)[3]，因此減少調(diào)度開銷和調(diào)度時間成為動態(tài)調(diào)度設(shè)計的關(guān)鍵。目前更為常見的調(diào)度策略使用靜態(tài)和動態(tài)調(diào)度相結(jié)合的方式，尋求調(diào)度性能與調(diào)度開銷之間的平衡。
任務(wù)調(diào)度問題根據(jù)負載是否均衡分為基于負載均衡和負載非均衡的調(diào)度。負載均衡的調(diào)度能夠通過均衡各核心負載減少任務(wù)的平均響應(yīng)時間；負載非均衡通過減少調(diào)度一組任務(wù)的調(diào)度器和調(diào)度資源來降低能耗。通常認為負載非均衡算法更適合于實時任務(wù)分配[4]，基于負載均衡的調(diào)度策略具有通用性和良好的局部性。
基于目前對GPU的任務(wù)調(diào)度策略的研究，Video Core采用優(yōu)先向頂點任務(wù)分配資源的策略[5]，AMD的GCN系列芯片在僅剩最后一個執(zhí)行單元中的最后一個warp空位時作特殊均衡處理，其余資源充足場景啟用資源硬件調(diào)度[6]。對調(diào)度資源管理功能的設(shè)計策略，文獻[7]提出資源的預(yù)先分配和資源調(diào)度的順序性維護。
針對統(tǒng)一渲染架構(gòu)3D引擎的任務(wù)調(diào)度策略，文獻[8]提出兩級循環(huán)warp任務(wù)分配策略，策略中首先將所有支持并行執(zhí)行的warp拆分為小組（例如32個warp任務(wù)可以分成4組，每組8個warp），同組warp在同一SM內(nèi)并行執(zhí)行，對每組內(nèi)的warp按優(yōu)先級排序。兩級循環(huán)即組內(nèi)的調(diào)度策略采用輪詢，組間的切換也采用輪詢的循環(huán)策略，每級調(diào)度均使用公平輪詢策略。如圖1所示，采用兩級調(diào)度的優(yōu)勢在于減少了空閑執(zhí)行單元的循環(huán)周期，提高資源利用率與計算性能。
國內(nèi)對統(tǒng)一渲染架構(gòu)的研究和探索起步較晚，主要集中于GPU架構(gòu)研究、算法優(yōu)化、功耗分析以及統(tǒng)一染色器設(shè)計等方面，但針對統(tǒng)一架構(gòu)染色器資源的管理與調(diào)度方面的研究資料較少。
2 任務(wù)調(diào)度策略設(shè)計與實現(xiàn)
2.1 任務(wù)調(diào)度模塊
本文設(shè)計的調(diào)度策略結(jié)合動態(tài)、靜態(tài)調(diào)度，實現(xiàn)一種基于負載均衡策略和兩級輪詢策略的任務(wù)調(diào)度電路設(shè)計，實現(xiàn)3D引擎中多個任務(wù)執(zhí)行資源的合理分配調(diào)度問題，保證高效的資源利用率。其中3D引擎包含N個流多處理器(SM)模塊，每個SM模塊中最多支持M個warp并行執(zhí)行，任務(wù)調(diào)度即調(diào)度M*N個資源以及多組頂點、像素warp任務(wù)在時間和空間上的分配問題。warp是實施任務(wù)調(diào)度的基本單位。
任務(wù)調(diào)度模塊主要包括為避免圖形流水線死鎖設(shè)計的資源預(yù)先分配模塊、資源統(tǒng)計與查找模塊和負載均衡執(zhí)行模塊，任務(wù)調(diào)度模塊設(shè)計如圖2所示。
2.2 資源預(yù)先分配模塊設(shè)計
首先，為實現(xiàn)死鎖避免策略，模塊內(nèi)部將M*N個可分配的warp計算資源采用預(yù)先分配方案，按照頂點任務(wù)和像素任務(wù)1:1的比例分配，即預(yù)先分配M*N/2個頂點warp計算資源和M*N/2個像素warp計算資源，如圖3所示。
本文以M為8、N為4為例，闡述任務(wù)調(diào)度策略。即下文提到的系統(tǒng)具有支持共計4*8個warp并行計算的能力，為保障一致性和便于描述，將系統(tǒng)各SM中的warp執(zhí)行資源由warp_ID統(tǒng)一標識，S0中執(zhí)行的warp任務(wù)編號0至7，SM1支持warp任務(wù)編號8至15，依此類推。
2.3 資源統(tǒng)計與查找模塊設(shè)計
資源統(tǒng)計與查找模塊的設(shè)計策略使用隊列統(tǒng)計待調(diào)度warp_ID、待釋放warp_ID和待釋放資源順序性等實時信息，并依據(jù)統(tǒng)計信息對執(zhí)行資源作統(tǒng)一管理和調(diào)度，實現(xiàn)對warp_ID和相應(yīng)執(zhí)行資源的分配與統(tǒng)計功能。資源統(tǒng)計信號包括：(1)可分配資源隊列統(tǒng)計信號queue；(2)隊列起始位置信號start；(3)隊列結(jié)束位置信號end；(4)隊列資源釋放的順序性維護指針信號release。
設(shè)計使用兩組統(tǒng)計信號對頂點和像素可分配資源分別進行統(tǒng)計，并支持頂點與像素資源并行統(tǒng)計、查找。
本文以頂點隊列統(tǒng)計信號為例，闡述資源分配統(tǒng)計信號組。
(1)頂點可分配資源隊列統(tǒng)計信號queue_v統(tǒng)計當(dāng)前所有預(yù)先分配的頂點任務(wù)執(zhí)行資源，以warp_ID標識。
(2)頂點隊列起始位置信號start_v標識下一個待分配warp任務(wù)在隊列中可分配的warp_ID，每當(dāng)輪詢調(diào)度分配一次任務(wù)，start_v標識位置移動。
(3)頂點隊列結(jié)束位置信號end_v標識下一個待釋放warp_ID在隊列中的排序位置，每當(dāng)執(zhí)行資源被釋放一次，end_v標識位置移動。
(4)頂點隊列資源釋放順序維護信號release_v標識隊列中按照順序應(yīng)釋放的warp_ID，順序性應(yīng)保證先分配任務(wù)的執(zhí)行資源優(yōu)先釋放warp_ID。
設(shè)計中隊列資源統(tǒng)計，使用start_v和end_v在隊列中標識位置之間的warp_ID表征當(dāng)前可分配頂點warp任務(wù)的空閑資源；使用release_v與start_v在隊列中標識位置之間的warp_ID表征當(dāng)前執(zhí)行頂點warp任務(wù)的繁忙資源。
頂點資源統(tǒng)計信號組的初始狀態(tài)、資源分配操作以及資源釋放操作如圖4所示。像素類資源統(tǒng)計信號組原理相同。
2.4 負載均衡模塊設(shè)計
負載均衡策略設(shè)計中，基于像素染色器是制約渲染性能的主要因素[9]，當(dāng)染色器資源有限時，優(yōu)先分配資源處理像素任務(wù)；由于負載均衡操作中可能會同時改變頂點和像素統(tǒng)計隊列中的統(tǒng)計信息，負載均衡操作中需鎖定當(dāng)前隊列統(tǒng)計狀態(tài)，其他操作等待負載均衡結(jié)束后執(zhí)行。負載均衡策略不能并行執(zhí)行，每次負載均衡操作僅分配一個warp_ID資源。
本文在負載均衡設(shè)計中將負載不均衡的場景分為三類：
第一類場景：當(dāng)頂點或者像素類型的空閑資源僅剩一個時，而另一類型預(yù)先分配資源或有效資源還有較多空閑，需要將空閑類型的執(zhí)行資源由負載均衡操作轉(zhuǎn)換為繁忙類型的執(zhí)行資源執(zhí)行待分配的warp_ID；
第二類場景：當(dāng)頂點與像素類型的空閑資源均僅剩一個時，若頂點任務(wù)和像素任務(wù)均請求分配資源或僅頂點任務(wù)請求分配資源，則不進行負載均衡操作，各自分配隊列統(tǒng)計中的warp_ID；
第三類場景：當(dāng)頂點與像素類型的空閑資源均僅剩一個時，若像素任務(wù)請求分配資源，則進行負載均衡操作，將頂點分配隊列統(tǒng)計中的warp-ID均衡為像素隊列中待分配的warp_ID；若僅頂點任務(wù)請求分配資源，不執(zhí)行負載均衡操作。
本文以第一類場景為例，闡述負載均衡操作流程。如圖5所示，當(dāng)像素隊列中可分配資源不足，而頂點可分配資源充足，將end_v信號移動至其在隊列中前一位置的warp_ID，將指向的warp_ID分配給像素類資源，則頂點隊列負載均衡操作完成；end_p信號當(dāng)前位指向的隊列位置寫入頂點隊列均衡的warp_ID，隨后end_p向高位移動，指向下一組warp_ID釋放位置，像素隊列負載均衡操作完成。
3 實驗結(jié)果及性能分析
本文調(diào)度性能驗證基于虛擬仿真平臺實現(xiàn)，平臺主要包括主機接口模型、頂點任務(wù)發(fā)送模型、像素任務(wù)發(fā)送模型、CPR時鐘模塊和統(tǒng)一染色器組模型。基于負載均衡的任務(wù)調(diào)度模塊搭建的仿真驗證平臺如圖6所示。
主機接口模型通過寄存器讀寫配置整個平臺模型的各項參數(shù)信息；頂點任務(wù)和像素任務(wù)模型按照3D引擎的數(shù)據(jù)發(fā)送規(guī)則向任務(wù)調(diào)度模塊發(fā)送需要調(diào)度的數(shù)據(jù)warp信息；CPR時鐘模塊生成整個平臺的時鐘與復(fù)位信號；統(tǒng)一染色器陣列模型通過接收任務(wù)調(diào)度模塊的任務(wù)調(diào)度信息和數(shù)據(jù)信息，執(zhí)行計算warp數(shù)據(jù)（vertex_data和pixel_data）操作，操作完成后依據(jù)任務(wù)調(diào)度模塊的調(diào)度釋放執(zhí)行資源。
驗證中采用多種負載均衡策略、多種虛擬渲染場景對比驗證，其中：
(1)調(diào)度策略一為執(zhí)行資源不足時優(yōu)先分配頂點任務(wù)；
(2)調(diào)度策略二為本文提出的負載均衡策略；
(3)調(diào)度策略三為公平負載均衡策略，執(zhí)行資源不足時優(yōu)先執(zhí)行先分配的任務(wù)，若頂點資源與像素資源爭搶同一執(zhí)行資源時，使用隨機公平分配的原則。
在所有測試場景頂點與像素任務(wù)總數(shù)一定，為模擬在圖形繪制程序中不同階段頂點與像素任務(wù)比例，將各任務(wù)組中頂點和像素warp的比例分別為(a)3:1、(b)2:1、(c)1:1、(d)1:2、(e)1:3?；趯?D引擎的調(diào)度性能的評測主要由吞吐量衡量，對一定時間內(nèi)各復(fù)雜渲染場景吞吐量作歸一化處理后，調(diào)度性能對比驗證結(jié)果如圖7所示。
當(dāng)部分渲染場景中頂點類任務(wù)較多時，如任務(wù)組a、b類場景中，偏向頂點的負載均衡策略一具有相對較好的調(diào)度性能；當(dāng)部分渲染場景中像素類任務(wù)較多時，如任務(wù)組d、e類場景，本文提出的策略二具有突出的調(diào)度性能；公平的負載均衡策略三在不同場景中具有平穩(wěn)的調(diào)度性能，但均不優(yōu)越?；谙袼仡惾蝿?wù)處理性能長期成為圖形渲染的性能瓶頸，多數(shù)場景中像素類任務(wù)偏多[1，9]，如任務(wù)組c、d、e類場景在一組渲染任務(wù)中較多、占據(jù)時長較長，本文提出的任務(wù)調(diào)度策略能夠在大多數(shù)場景中具有優(yōu)越的調(diào)度性能，在部分頂點類任務(wù)較多的場景策略二調(diào)度性能良好。
綜合以上分析，經(jīng)過多種渲染場景對比驗證，本文提出的一種基于負載均衡的調(diào)度算法能夠?qū)崿F(xiàn)高效調(diào)度功能，在多種場景中較大幅度地提升調(diào)度效率，且設(shè)計簡潔、調(diào)度開銷較小并具有良好的場景適應(yīng)性，在不同渲染場景中均具有較好的負載均衡能力和調(diào)度性能。
4 結(jié)論
結(jié)合其他調(diào)度算法策略，研究并設(shè)計、實現(xiàn)了一種基于負載均衡的3D引擎的任務(wù)調(diào)度策略，通過實現(xiàn)基于預(yù)先分配的避免死鎖策略、基于隊列統(tǒng)計和隊列順序維護的資源統(tǒng)計與查找策略、基于偏向像素設(shè)計的動態(tài)負載均衡策略設(shè)計相關(guān)調(diào)度電路，實現(xiàn)調(diào)度復(fù)雜度較低且調(diào)度性能較高效的任務(wù)調(diào)度策略，經(jīng)多種渲染場景對比驗證，具有較好的負載均衡能力及調(diào)度性能。
目前3D引擎發(fā)展對任務(wù)調(diào)度策略提出了更高的要求，調(diào)度的多任務(wù)類型也從圖形類型的頂點和像素擴展到實時渲染、通用計算等任務(wù)，未來任務(wù)調(diào)度策略還應(yīng)考慮支持多種任務(wù)并行調(diào)度的復(fù)雜調(diào)度策略，更細致的負載均衡場景設(shè)計以及更完備的硬件測試與性能評測設(shè)計方法。
參考文獻
[1] Wang Po-Han，Chen Yen-Ming，Yang Chia-Lin. A predictive shutdown technique for GPU shader processors[J].IEEE Computer Architecture Letters，2009，8(1)：9-12.
[2] 賓雪蓮，楊玉海，金士堯.一種基于分組與適當(dāng)選取策略的實時多處理器系統(tǒng)的動態(tài)調(diào)度算法[J].計算機學(xué)報，2006，29(1)：81-91.
[3] LIU S，QUAN G，REN S.On-line scheduling of real-time services for cloud computing. Services[C].2010 6th World Congress on IEEE，2010.
[4] 劉加海，楊茂林，雷航.共享資源約束下多核實時任務(wù)分配算法[J].浙江大學(xué)學(xué)報，2014，48(1)：113-117.
[5] Boardcom Corporation.VideoCore IV 3D Architecture Reference Guide[EB/OL].(2013-9-16)[2016-12-31].https://www.broadcom.com/docs/support/videocore/VideoCoreIV-AG100-R.pdf.
[6] Graphics Core Next[EB/OL].(2016-12-19)[2016-12-31].https://en.wikipedia.org/wiki/Graphics_Core_Next
[7] Jonathan Ragan-Kelley.Scheduling the Graphics Pipeline[EB/OL].(2011-8-9)[2016-12-31].http://bps11.idav.ucdavis.edu/talks/05-schedulingGraphicsPipelineWithNotes-BPS2011-raganKelley.pdf.
[8] Veynu Narasiman，Michael Shebanow.Improving GPU perfor-mance via large warps and two-level warp scheduling[C].Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture ACM，2011.
[9] Pitchaya Sitthi-amorm，Jason Lawrence，Lei Yang，et al.Automated Reprojection-Based Pixel Shader Optimization[J].ACM Transactions on Graphics，2008，27(5)：127.
作者信息:
鄧 藝，田 澤，韓立敏
（中航工業(yè)西安航空計算技術(shù)研究所，陜西 西安710065）