文献标识码：A
DOI：10.16157/j.issn.0258-7998.2017.05.013
中文引用格式：邓艺，田泽，韩立敏. 一种基于负载均衡的3D引擎任务调度策略[J].电子技术应用，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)的关键和核心，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统一标识，S0中执行的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）