引言
流计算作为一种典型的基于任务流水线(Task Pipeline)的计算模式，由数据流(Data)和任务(Task)两部分组成。在流计算执行过程中，数据流需要按照流水线的方式依次顺序接受各个任务的处理。同时，各个任务之间存在着产生数据和消费数据(Producer-consumer)的关系，即前一个任务运算的输出数据是下一个任务的输入数据。这种计算模式广泛存在于多媒体处理、信号处理、数据挖掘、金融计算等领域。
GPU顺序执行流计算程序会造成两种问题：一是片上计算资源利用率不同，二是对片外内存的频繁访问。为了降低不同任务计算量不均匀对于GPU计算资源和存储资源的影响，本文提出了支持双任务并发执行的动态调度方法，能够支持GPU同时运行两个任务，并且动态监测每个任务的计算规模和性能扩展性，从而达到计算资源分配方式最优。
1 计算资源分配
计算资源分配的核心问题是寻找并发执行的两个任务最优的计算资源的数量分配。为此，最直接的方式是对所有的配置方式进行遍历，记录下每一种配置方式的性能，从中找出最优方案。这种基于遍历的方法过多地引入了性能很差的配置方式，所以遍历的过程会造成性能损失。因此，这里提出利用性能曲线线性插值的方法快速准确地找到最优的配置方式。在接下来的讨论中，需要调度的两个任务分別表示为K1和K2，它们共同占有计算资源的数量记为N。两个任务的执行时间分別为T1(n)和T2(n)，其中n为分配给该任务的计算资源数量。由于两个任务并发执行且两个任务在计算每个数据流时的计算量固定，因此运行两个任务的时间由最慢的任务时间决定，即：
T(n)=MAX(T1(n)，T2(N -n)) (1)
调度的目的是选择合适的n，使得Tn(n)的值最小。由于T1(n)和T2(n)都是非解析函数，因此很难通过解析的方式找到公式(1)的最小值。但是，由于时间函数T1(n)和T2(n)都是单调递减函数，因此，Tn(n)获得最小值的充分条件为：
T1(n)=T2(N -n) (2)
通过迭代计算的方法，可以得出近似的最优资源分配值，对程序性能不会带来明显损失。
2 缓存资源分配
多任务并发执行时任务间的临时数据可以存储在末级缓存中，从而减少对内存访问的次数。由于不同任务对于缓存资源的需求数量并不相同，因此设计了面向任务级流水线的缓存结构，从而给每个任务分配最优的缓存资源。在任务流水线中，前一个任务生成的数据会被下一个任务利用，一旦下一个任务使用完这些数据之后，这些数据则很少被其它任务利用。基于这种观察，对于任务生成的数据应该尽可能地存储在缓存中，而一旦这些数据被读取之后，应该立即将这些数据从缓存中替换出来，从而释放出这些缓存空间。给出了支持多任务并发执行的缓存结构和管理策略。
新的缓存结构在传统的缓存行结构上增加了两个标识符，Kernel_ID和Stream_ID。其中Kernel_ID记录访问该行数据的任务编号，Stream_ID记录该行数据所属的数椐流编号。对于一个没有存储有效数据的缓存行，两个标识位的值都初始化为-1。添加了两个标识符的缓存工作方式如下：当有访存请求从计算单元发射时，对应的Kernel_ID和Stream_ID的信息将添加到该访存请求中。新的缓存机制对于访存请求的数据处理方式与传统的缓存相同(缺失和命中的判断以及对于数据块的相应处理)，区別在于增加了对于标识符的操作：①如果访存请求是读操作，且缓存缺失，则对应缓存行的标识符初始化为访存请求中的标识符信息;②如果访存请求是读操作，且缓存命中，则对应的标识符保持不变;③如果访存请求是写操作，不论缓存缺失还是命中，对应缓存行的标识符信息都将进行更新，从而替换为访存请求中的标识符信息。因此，在新的缓存结构下，能够明确缓存中数据的来源。当有任务结束时，能够快速找到属于该任务的但不再需要的数据，从而把这些数据替换出缓存。
3 硬件开销评估
以下介绍资源动态分配的硬件开销。支持计算资源分配的硬件单元被称为动态任务分配器(Dynamic KernelAllocator，DKA)，负责计算两个任务并发执行时最优的计算资源分配方式(即分配给两个任务的计算资源数量)。该硬件单元可以集成在当前的GPU 全局任务调度单元中。
DKA主要的硬件开销来自于查找表的存储空间和插值计算单元。假设GPU中集成了24个SM，对于一对任务，需要25条存储单元来记录这对任务在各种计算资源分配时的性能。每1条存储单元需要记录3条信息，即存储NK1 需要5bits，存储K1_perf和K2_perf各需要16bits。因此，每1条存储单元需要37bits的存储空间。假设DKA可以支持任务流水线的长度为8，那么需要9组(buffer pool也需要一组查找表)查找表的存储空间，接近1KB(9x25x37bits)，这个面积开销十分微小。此外，DKA还需要一个插值计算单元和若干个组合逻辑。考虑到插值计算单元的硬件开销小于一个标准的浮点运算单元，而当前的GPU包含成百上千规模的浮点运算单元，因此，可以认为额外引入的插值计算单元的硬件开销对于系统来说是微小的。
对于支持任务并发执行的缓存结构，硬件结构只发生了很小的改动，因此额外引入的硬件开销微乎其微。由于每个缓存行增添了两个标识符，它们分別需要3bits(存储Kernel_ID，可以支持8个任务)和5bits(存储Stream_ID，可以支持32个数据流并且数据流的ID编号可以循环使用)的存储空间。当前典型的GPU缓存包含有12K个缓存行(缓存容量为768KB)，新的存储结构增加了12KB的存储空间，占现在缓存空间不到1.5%的面积开销。
4 结语
本文讨论了任务级的不规则计算模式，即以流计算为代表的程序中包含任务级流水线，但是不同任务的计算规模有着很大差异。针对这种不规则的计算模式，顺序执行各个任务会造成片上计算资源的空闲。当前典型的多任务并发机制采用基于抢占式的静态调度方式，该调度机制能够把更多任务发射到计算资源上，从而消除计算资源空闲的问题。但是，当多个任务并发执行时，该机制无法给出每个任务最优的资源分配方式。因此，本文提出了双任务的动态调度机制，该机制能够动态地分析每个任务的计算规模，从而赋予每个任务合适的计算资源和缓存资源。该机制能够改善计算性能，减少内存访问次数，并且随着未来GPU上计算资源规模的不断扩大，动态调度机制的优势将更加显著。
