0 引言

    3D引擎是圖形處理器(Graphics Processing Unit，GPU)的關鍵和核心，GPU技術經過十多年發展，其硬件架構和圖形流水線經歷了從固定功能、分離渲染到統一渲染的三個發展階段，實現復雜圖形高效繪制，滿足日益多樣的圖形處理應用需求。統一渲染架構3D引擎內單個統一染色器具備分時復用處理頂點或像素渲染任務的能力，可有效提升3D引擎計算核心的資源利用效率，是目前主流GPU廠商廣泛采用的3D引擎架構。

    圖形處理器的處理性能、吞吐量和資源利用效率與實施不同的任務調度實現策略密切相關。任務調度策略是統一渲染架構3D引擎設計的關鍵及核心，通過對統一染色器執行狀態的統一管理、執行時間和執行資源的統一調度，實現渲染任務的分配和染色器的狀態監控功能。目前統一架構3D引擎的調度策略設計面臨眾多挑戰，而國內相關領域的研究仍處于初級階段，許多關鍵技術需要進一步探索和研究。

    本文在分析統一架構GPU的圖形繪制特點及現有調度策略的基礎上，提出了基于染色器預先分配的避免圖形繪制流水線死鎖策略，基于隊列統計的資源分配及負載均衡策略，實現染色器資源有限條件下多類型任務（頂點任務、像素任務等）的合理分配和統一管理，降低了調度方案硬件實現的復雜度，同時確保了高效的調度性能。論文給出基于負載均衡調度策略相關電路設計，各類復雜渲染場景的仿真結果表明這種負載均衡調度策略可有效地降低染色器資源的空閑時長和調度時間，提升染色器資源的利用率和3D引擎的處理效率。

1 統一渲染架構3D引擎任務調度技術概述

    基于對3D引擎圖形流水線的研究，統一渲染架構之前的性能瓶頸主要在于像素渲染階段，即使分離渲染架構中將1：3作為頂點與像素渲染引擎的黃金比例，依然無法適應復雜多變的渲染場景的需求，因此資源利用率不足成為限制GPU性能提升的關鍵^[1]。作為支持多任務的計算平臺，統一渲染架構3D引擎中每個計算單元的任務處理效率可能不同，為充分利用系統資源，需要3D引擎具備監控以及動態調度計算核心的能力。同時，統一渲染架構3D引擎的核心處理性能主要由其任務調度能力和各個流處理器核的執行能力表征，因而兼顧靈活、高效以及可靠的任務調度與資源分配方案是統一渲染架構的3D引擎研究重點和關鍵技術。

    根據任務性質將任務調度問題劃分為靜態和動態的調度。某些具有確定處理時間、可預測的數據同步問題，甚至是各個任務數據之間確定依賴關系的問題，屬于靜態調度問題^[2]。相較而言，某些需要適應性更強的調度方案方能充分解決的問題，屬于動態調度問題。動態調度避免了因資源浪費導致的利用率不足和因資源過度利用造成的漫長響應時間，但是動態調度中良好的適應性往往需要更復雜的調度設計才能實現^[3]，因此減少調度開銷和調度時間成為動態調度設計的關鍵。目前更為常見的調度策略使用靜態和動態調度相結合的方式，尋求調度性能與調度開銷之間的平衡。

    任務調度問題根據負載是否均衡分為基于負載均衡和負載非均衡的調度。負載均衡的調度能夠通過均衡各核心負載減少任務的平均響應時間；負載非均衡通過減少調度一組任務的調度器和調度資源來降低能耗。通常認為負載非均衡算法更適合于實時任務分配^[4]，基于負載均衡的調度策略具有通用性和良好的局部性。

    基于目前對GPU的任務調度策略的研究，Video Core采用優先向頂點任務分配資源的策略^[5]，AMD的GCN系列芯片在僅剩最后一個執行單元中的最后一個warp空位時作特殊均衡處理，其余資源充足場景啟用資源硬件調度^[6]。對調度資源管理功能的設計策略，文獻[7]提出資源的預先分配和資源調度的順序性維護。

    針對統一渲染架構3D引擎的任務調度策略，文獻[8]提出兩級循環warp任務分配策略，策略中首先將所有支持并行執行的warp拆分為小組（例如32個warp任務可以分成4組，每組8個warp），同組warp在同一SM內并行執行，對每組內的warp按優先級排序。兩級循環即組內的調度策略采用輪詢，組間的切換也采用輪詢的循環策略，每級調度均使用公平輪詢策略。如圖1所示，采用兩級調度的優勢在于減少了空閑執行單元的循環周期，提高資源利用率與計算性能。

    國內對統一渲染架構的研究和探索起步較晚，主要集中于GPU架構研究、算法優化、功耗分析以及統一染色器設計等方面，但針對統一架構染色器資源的管理與調度方面的研究資料較少。

2 任務調度策略設計與實現

2.1 任務調度模塊

    本文設計的調度策略結合動態、靜態調度，實現一種基于負載均衡策略和兩級輪詢策略的任務調度電路設計，實現3D引擎中多個任務執行資源的合理分配調度問題，保證高效的資源利用率。其中3D引擎包含N個流多處理器(SM)模塊，每個SM模塊中最多支持M個warp并行執行，任務調度即調度M*N個資源以及多組頂點、像素warp任務在時間和空間上的分配問題。warp是實施任務調度的基本單位。

    任務調度模塊主要包括為避免圖形流水線死鎖設計的資源預先分配模塊、資源統計與查找模塊和負載均衡執行模塊，任務調度模塊設計如圖2所示。

2.2 資源預先分配模塊設計

    首先，為實現死鎖避免策略，模塊內部將M*N個可分配的warp計算資源采用預先分配方案，按照頂點任務和像素任務1:1的比例分配，即預先分配M*N/2個頂點warp計算資源和M*N/2個像素warp計算資源，如圖3所示。

    本文以M為8、N為4為例，闡述任務調度策略。即下文提到的系統具有支持共計4*8個warp并行計算的能力，為保障一致性和便于描述，將系統各SM中的warp執行資源由warp_ID統一標識，S₀中執行的warp任務編號0至7，SM1支持warp任務編號8至15，依此類推。

2.3 資源統計與查找模塊設計

    資源統計與查找模塊的設計策略使用隊列統計待調度warp_ID、待釋放warp_ID和待釋放資源順序性等實時信息，并依據統計信息對執行資源作統一管理和調度，實現對warp_ID和相應執行資源的分配與統計功能。資源統計信號包括：(1)可分配資源隊列統計信號queue；(2)隊列起始位置信號start；(3)隊列結束位置信號end；(4)隊列資源釋放的順序性維護指針信號release。

    設計使用兩組統計信號對頂點和像素可分配資源分別進行統計，并支持頂點與像素資源并行統計、查找。

    本文以頂點隊列統計信號為例，闡述資源分配統計信號組。

    (1)頂點可分配資源隊列統計信號queue_v統計當前所有預先分配的頂點任務執行資源，以warp_ID標識。

    (2)頂點隊列起始位置信號start_v標識下一個待分配warp任務在隊列中可分配的warp_ID，每當輪詢調度分配一次任務，start_v標識位置移動。

    (3)頂點隊列結束位置信號end_v標識下一個待釋放warp_ID在隊列中的排序位置，每當執行資源被釋放一次，end_v標識位置移動。

    (4)頂點隊列資源釋放順序維護信號release_v標識隊列中按照順序應釋放的warp_ID，順序性應保證先分配任務的執行資源優先釋放warp_ID。

    設計中隊列資源統計，使用start_v和end_v在隊列中標識位置之間的warp_ID表征當前可分配頂點warp任務的空閑資源；使用release_v與start_v在隊列中標識位置之間的warp_ID表征當前執行頂點warp任務的繁忙資源。

    頂點資源統計信號組的初始狀態、資源分配操作以及資源釋放操作如圖4所示。像素類資源統計信號組原理相同。

2.4 負載均衡模塊設計

    負載均衡策略設計中，基于像素染色器是制約渲染性能的主要因素^[9]，當染色器資源有限時，優先分配資源處理像素任務；由于負載均衡操作中可能會同時改變頂點和像素統計隊列中的統計信息，負載均衡操作中需鎖定當前隊列統計狀態，其他操作等待負載均衡結束后執行。負載均衡策略不能并行執行，每次負載均衡操作僅分配一個warp_ID資源。

    本文在負載均衡設計中將負載不均衡的場景分為三類：

    第一類場景：當頂點或者像素類型的空閑資源僅剩一個時，而另一類型預先分配資源或有效資源還有較多空閑，需要將空閑類型的執行資源由負載均衡操作轉換為繁忙類型的執行資源執行待分配的warp_ID；

    第二類場景：當頂點與像素類型的空閑資源均僅剩一個時，若頂點任務和像素任務均請求分配資源或僅頂點任務請求分配資源，則不進行負載均衡操作，各自分配隊列統計中的warp_ID；

    第三類場景：當頂點與像素類型的空閑資源均僅剩一個時，若像素任務請求分配資源，則進行負載均衡操作，將頂點分配隊列統計中的warp-ID均衡為像素隊列中待分配的warp_ID；若僅頂點任務請求分配資源，不執行負載均衡操作。

    本文以第一類場景為例，闡述負載均衡操作流程。如圖5所示，當像素隊列中可分配資源不足，而頂點可分配資源充足，將end_v信號移動至其在隊列中前一位置的warp_ID，將指向的warp_ID分配給像素類資源，則頂點隊列負載均衡操作完成；end_p信號當前位指向的隊列位置寫入頂點隊列均衡的warp_ID，隨后end_p向高位移動，指向下一組warp_ID釋放位置，像素隊列負載均衡操作完成。

3 實驗結果及性能分析

    本文調度性能驗證基于虛擬仿真平臺實現，平臺主要包括主機接口模型、頂點任務發送模型、像素任務發送模型、CPR時鐘模塊和統一染色器組模型。基于負載均衡的任務調度模塊搭建的仿真驗證平臺如圖6所示。

    主機接口模型通過寄存器讀寫配置整個平臺模型的各項參數信息；頂點任務和像素任務模型按照3D引擎的數據發送規則向任務調度模塊發送需要調度的數據warp信息；CPR時鐘模塊生成整個平臺的時鐘與復位信號；統一染色器陣列模型通過接收任務調度模塊的任務調度信息和數據信息，執行計算warp數據（vertex_data和pixel_data）操作，操作完成后依據任務調度模塊的調度釋放執行資源。

    驗證中采用多種負載均衡策略、多種虛擬渲染場景對比驗證，其中：

    (1)調度策略一為執行資源不足時優先分配頂點任務；

    (2)調度策略二為本文提出的負載均衡策略；

    (3)調度策略三為公平負載均衡策略，執行資源不足時優先執行先分配的任務，若頂點資源與像素資源爭搶同一執行資源時，使用隨機公平分配的原則。

    在所有測試場景頂點與像素任務總數一定，為模擬在圖形繪制程序中不同階段頂點與像素任務比例，將各任務組中頂點和像素warp的比例分別為(a)3:1、(b)2:1、(c)1:1、(d)1:2、(e)1:3。基于對3D引擎的調度性能的評測主要由吞吐量衡量，對一定時間內各復雜渲染場景吞吐量作歸一化處理后，調度性能對比驗證結果如圖7所示。

    當部分渲染場景中頂點類任務較多時，如任務組a、b類場景中，偏向頂點的負載均衡策略一具有相對較好的調度性能；當部分渲染場景中像素類任務較多時，如任務組d、e類場景，本文提出的策略二具有突出的調度性能；公平的負載均衡策略三在不同場景中具有平穩的調度性能，但均不優越。基于像素類任務處理性能長期成為圖形渲染的性能瓶頸，多數場景中像素類任務偏多^[1，9]，如任務組c、d、e類場景在一組渲染任務中較多、占據時長較長，本文提出的任務調度策略能夠在大多數場景中具有優越的調度性能，在部分頂點類任務較多的場景策略二調度性能良好。

    綜合以上分析，經過多種渲染場景對比驗證，本文提出的一種基于負載均衡的調度算法能夠實現高效調度功能，在多種場景中較大幅度地提升調度效率，且設計簡潔、調度開銷較小并具有良好的場景適應性，在不同渲染場景中均具有較好的負載均衡能力和調度性能。

4 結論

    結合其他調度算法策略，研究并設計、實現了一種基于負載均衡的3D引擎的任務調度策略，通過實現基于預先分配的避免死鎖策略、基于隊列統計和隊列順序維護的資源統計與查找策略、基于偏向像素設計的動態負載均衡策略設計相關調度電路，實現調度復雜度較低且調度性能較高效的任務調度策略，經多種渲染場景對比驗證，具有較好的負載均衡能力及調度性能。

    目前3D引擎發展對任務調度策略提出了更高的要求，調度的多任務類型也從圖形類型的頂點和像素擴展到實時渲染、通用計算等任務，未來任務調度策略還應考慮支持多種任務并行調度的復雜調度策略，更細致的負載均衡場景設計以及更完備的硬件測試與性能評測設計方法。

參考文獻

[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] 賓雪蓮，楊玉海，金士堯.一種基于分組與適當選取策略的實時多處理器系統的動態調度算法[J].計算機學報，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] 劉加海，楊茂林，雷航.共享資源約束下多核實時任務分配算法[J].浙江大學學報，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.

作者信息:

鄧  藝，田  澤，韓立敏

（中航工業西安航空計算技術研究所，陜西 西安710065）