2022, Vol. 31
2. 中国科学技术大学 高性能计算安徽省重点实验室, 合肥 230027
2. Key Laboratory of High Performance Computing of Anhui Province, University of Science and Technology of China, Hefei 230027, China
实践证明, CPU架构在面对海量数据和特殊计算时存在性能瓶颈, 依靠增加主频或堆积核心数量会使硬件结构复杂, 计算功耗增加, 且不能解决性能瓶颈[1]. 一种解决方案是搭建异构计算系统, 异构计算系统定义为由不同指令集和基础架构计算资源构成的系统, 计算资源包含CPU, GPU, DSP, FPGA等芯片. 异构系统协调硬件设备间计算, 从而提升系统的性能[2].
HXDSP是中国电子科技集团公司第38研究所研制BWDSP[3, 4]系列处理器下的一款国产DSP处理器芯片. HXDSP芯片通常搭配CPU芯片, 构成HXDSP异构系统. HXDSP异构计算框架选取OpenCL作为载体.
OpenCL是异构并行编程模型, 异构编程模型还有CUDA, Merge[5], C++AMP[6], Lime[7]. OpenCL将计算任务抽象为3个层次: 内核, 工作组, 工作项. 当研究对象为内核在设备上的分配策略时, 问题为异构系统下的任务调度问题. 该问题被证明是NP-hard问题[8], 可通过启发式或元启发式算法解决, 启发式调度算法包括: 基于优先级列表调度算法[9], 基于聚类调度算法[10], 基于任务复制调度算法[11]; 元启发式算法包括: 遗传算法[12], 粒子群优化算法[13], 蚁群优化算法[14]. 基于优先级列表的调度算法HEFT[15]被实践证明简单高效, 被选取为研究对象.
基于OpenCL执行模型特性的任务调度存在大量研究, 如文献[16]通过机器学习方式通过代码文件判断内核在CPU和GPU间的最优分配, 文献[17]通过内核代码特征, 选择CPU执行, GPU执行或在两者之间划分任务的策略, 文献[18]在多DSP架构针对OpenCL工作组和工作项两个粒度设计了一种双层调度器, 文献[19]研究了在多设备协同执行同一个内核的有效性.
现有OpenCL任务调度研究局限于开发平台闭源性质, 研究点侧重于内核中工作组粒度上任务分配, 或在内核粒度上的研究不同处理器间选择问题, 并未从不同粒度对计算任务进行规划. 内核间的任务调度符合传统任务调度模型, 而OpenCL内核内符合单指令多线程, 本文算法综合考虑两种粒度提出新的思路.
本文从特定的HXDSP硬件结构出发, 针对异构编程模型OpenCL展开运行时的自动化任务调度研究, 设计了一种通过任务队列在OpenCL运行时获取任务图的方法, 通过将内核分解与调度算法HEFT结合, 得到一种更加高效的静态任务调度算法. 本文组织如下: 第1节介绍异构计算中相关问题研究现状. 第2节介绍HXDSP硬件平台和OpenCL抽象模型. 第3节介绍在OpenCL应用中获取任务图方法. 第4节介绍在HXDSP异构系统中的OpenCL运行时任务调度算法设计. 第5节通过实验验证算法的可行性和有效性. 最后对本文工作进行总结和展望.
2 OpenCL和HXDSP相关知识 2.1 HXDSP结构HXDSP1042设备内部集成了2个eC104处理核心, 6组serdes接口, 2个DDR控制器, 1个以太网接口, 一些低速外设接口. 在性能上, eC104包含4个执行宏, 支持SIMD和VLIW, 工作时的核心频率为500 Mhz, 达到30 GOPS和8 GFMACS的运算能力. 在存储空间上, 程序空间和数据空间在物理上分离, 单核心含32 KB字指令cache及1536 KB字数据存储器, 数据存储器被划分为6个block, 每个block大小为256 KB, 双内核共享256 KB字指令存储器. HXDSP数据存储空间通过统一地址空间NUMA方式实现互访, 用户可访问程序存储空间主要包括共享指令存储器, 内核私有程序存储器, 加载核ROM存储空间和DDR空间.
研究对象HXDSP异构计算平台抽象为图1所示硬件结构, FPGA板卡上搭载1张DSP加速板卡, DSP加速板卡包含4个HXDSP1042芯片和1块DDR存储, FPGA充当主设备, 也可视为CPU, 运行主机端管理程序, 驱动DSP进行计算和DDR上数据的存取.
|
图 1 HXDSP异构系统结构图 |
2.2 OpenCL抽象模型
OpenCL框架可分为4个模型: 平台模型, 执行模型, 存储模型, 编程模型.
OpenCL执行模型分为两个模块: 主机端执行的管理程序, 设备端执行的内核. 内核是计算任务的描述, 通过OpenCL C语言进行编写. 内核代码在执行时会创建索引空间NDRange, N的维度可取{1, 2, 3}, 索引空间中的点有独特的全局ID, 用于实例化工作项, 实现单指令多数据. 由于硬件限制, 索引空间中的工作项不能同时实例化, 工作项间被组织为工作组, 工作组是工作项实例化的集合. 在HXDSP异构系统中, 内核被映射到HXDSP1042芯片上, 工作组被映射到芯片上的eC104处理核心集合, 工作项映射到单个处理核心.
OpenCL存储模型将设备中的存储器抽象为4层结构. 全局内存: 索引空间中所有节点可读写; 全局常量: 索引空间中所有节点可读不可写; 本地内存: 工作组内的工作节点可读写, 对其他工作组不可见; 私有内存: 只属于工作节点. 软件层面的内存模型是建立在硬件存储系统之上, 在HXDSP硬件模型中, 芯片内部只有1536 KB 字数据存储器, 所以全局存储和全局常量可能不能全部加载到DSP内部, 全局存储和全局常量被映射到DDR, 本地内存映射到数据存储器block, 私有内存映射到DSP核心中的寄存器组.
3 OpenCL任务图获取OpenCL规范明确了计算中涉及到的概念对象和操作对应的API接口, 框架具体行为由提供商依据规范实提供. OpenCL规范不包含任务调度概念, 由用户管理全部计算流程, 复杂的过程导致用户承担巨大工作量, 且程序在并行性上往往存在优化空间. 文献[20]发现目前供应商不能发现顺序队列中内核任务级并行性, 对内核重新调度能实现更优的执行效果, 这也证明了HXDSP异构计算平台上OpenCL运行时任务调度系统的可行性和必要性.
实现OpenCL的运行时自动化任务调度抽象为两个关键问题: 在OpenCL应用程序中获取任务图, 节点映射到计算设备上的策略. 本节讨论问题1: OpenCL任务图建立的依据和方法, 这是进行任务调度必需的前驱条件, 第4节讨论问题2.
3.1 OpenCL任务同步机制OpenCL任务图的建立在对OpenCL同步机制的正确理解之上. OpenCL的同步机制分为主机端同步和设备端同步. 主机端同步机制描述命令队列中各个命令之间的同步关系, 包含内核间的相关依赖关系. 设备端的同步机制描述工作组内部的同步关系, 内核内部的同步机制与任务图获取无关. 主机端的同步机制分为3种: 命令队列执行模式, 基于事件的同步方式, 显式的同步命令.
命令队列有两种执行模式: 顺序执行和乱序执行. 默认情况下, 命令队列中的命令是FIFO操作, 先发送的命令先执行, 在创建命令队列对象时, 选择参数属性CL_QUEUE_OUT_OF_ORDER_EXEC_MODE_ENABLE, 目标设备将不定序的执行其接受到的命令.
第2种方式是基于事件的同步方式, 每一个OpenCL命令在入队列时都可以关联一个事件对象以及一个等待事件列表, 前者代指当前命令执行完成与否, 可被用于其他等待事件列表, 后者描述了该命令需要等待的事件集合, 只有事件集合中的命令全部执行完毕, 当前命令才能执行.
第3种方式是通过显式同步命令进行同步. OpenCL中的同步命令包括标记命令, 栅栏命令和等待命令. 标记命令是对一组事件的标签, 用来记录事件的状态. 栅栏命令入队之后, 后续入队的命令等待栅栏命令执行完成. 等待命令会暂停命令队列执行, 直到其等待的事件列表执行完成.
3.2 任务图构造方法任务图通常通过有向无环图DAG表示, 形式化表示为G={T, E, W, C}, T指任务节点集合, E指节点间的有向边集合, E中的边表示依赖关系, W指任务在处理器上的执行开销, C指节点间的通信开销, 当节点在同一个处理器上时, 通信开销为0.
对于任务在处理器上的处理开销, 可通过测量一小部分工作组的执行开销推算完成内核需要的全部时间. 前沿研究的方法是性能建模[21], 例如通过深度神经网络对基本块在时钟周期级别进行预测[22], 通过随机森林预测内核在GPU上执行时间[23], 通过卷积神经网络预测嵌入式GPU上程序执行效率[24].
对于任务节点间的通信开销, 通过硬件IO通道传输速度和传输的数据量的比值进行估算.
对于节点间和节点与数据间的依赖关系, 可以通过在OpenCL运行时添加任务调度模块实现, 任务调度模块负责构造任务图和调度任务执行. 在OpenCL中, 用户对设备发送的命令请求通过命令队列传递, 命令队列相关接口API中接受命令队列对象, 数据对象, 内核对象, 事件对象等, 完成命令的提交. 通过在命令对象接口API下添加额外操作, 在API入口处完成对传入对象的关系分析, 并将有效信息提交至任务调度模块, 即可构造运行时的任务图信息.
任务节点之间的依赖关系通过两个部分进行确定, 通过OpenCL任务同步机制确定命令之间的控制依赖关系, 然后在控制依赖图的基础上分析任务内存对象之间的依赖获得任务图. 根据OpenCL任务同步机制, 命令之间的控制依赖分析应该从命令队列执行模式, 命令依赖的事件集和显式的同步点3个方面进行分析. 情况1, 命令对象为顺序执行模式时, 后入队列的命令对象逻辑上依赖于先入队列的命令, 当命令队列被设置为无序状态时, 队列中的命令逻辑上是并行的. 情况2, 一个命令在入队列时可以显式的关联一个事件列表, 命令对象和事件列表对象一起被传递给命令队列, 事件列表中的对象集合的命令被当前命令依赖. 情况3, 当显式的同步命令被提交给命令队列时, 同步命令前的命令集合被同步点后入队的命令所依赖. 在命令队列接口下建立控制流图的过程如算法1所示.
算法1. 命令队列构造控制流图
输入: command_queue
输出: control_flow_graph
1. if command_queue_type==inorder then
2. for command in command_queue do
3. add edge from prev(command) to cur(command)
4. for command in command_queue do
5. if command_type==kernel or
6. command_type==transmission or
7. command_type==wait then
8. if wait_event_list!=NULL then
9. for event in wait_event_list do
10. command_waited=getCommand(event)
11. add edge from command_waited to command
12. if command_type==barrier or
13. command_type==marker then
14. if wait_event_list!=NULL then
15. for event in wait_event_list do
16. command_waited=getCommand(event)
17. add edge from command_waited to command
18. else
19. command_waited=getExitCommandBefore(command)
20. add edge from command_waited to command
由控制流图构造任务图还需要边的权值, 即明确内核间数据传输量. OpenCL用户习惯使用顺序队列简化操作, 这种行为导致不必要的依赖关系被加入到控制流图中, 为此需要在控制依赖的基础上进行数据依赖分析, 分析被内核对象修改的参数, 结合内核对象间的依赖关系, 可确定内核对象间数据的交换量. 数据依赖分析对内核参数的读写属性进行确认, OpenCL中参数的读写属性体现在内存对象的参数修饰符上, 通过以下3种情况确定命令对数据的访问方式.
1)若内核程序的参数的地址空间修饰符为CL_MEM_READ_ONLY, 则所有命令对该内存对象的访问权限为只读, 若内存对象的访问类型为CL_MEM_WRITE_ONLY, 则所有命令对该内存对象的访问权限为只写.
2)若内核程序的参数的地址空间修饰符为CL_MEM_READ_WRITE, 此时命令对该内存对象既可读可写, 根据内核程序的参数修饰符进一步确定命令对该内存对象的访问权限: 如果参数修饰符为read_only, 那么内核程序对该数据的访问权限为只读, 如果参数修饰符为write_only, 那么内核程序对该数据的访问权限为只写, 如果参数修饰符为read_write, 那么内核程序对该数据即可读可写.
3)若内核程序的参数的地址空间修饰符为constant, 那么内核程序对该数据的访问是只读的.
在控制流图的基础上, 根据内核对象对内存对象的访问权限可以确定内核任务间的数据依赖关系, 建立任务图的过程如算法2所示.
算法2. 构造任务图
输入: control_flow_graph
输出: task_graph
1. for command in control_flow_graph do
2. if command in control_flow_graph then
3. for mem_obj in command_mo_list do
4. if mem_obj_type==CL_MEM_READ_ONLY |
5. Cl_MEM_COPY_HOST_PTR then
6. input_command=createCommand(mem_obj)
7. add edge from input_command to command
8. if mem_obj_type==CL_MEM_READ_WRITE &&
9. command_access_mo_type!=__write_only then
10. for command_prev_type==kernel do
11. if command_prev_type==kernel then
12. if mem_obj in command_prev_mo_list&&
13. command_prev_access_mo_type!=__read_only
14. then
15. add edge from command_prev to command
16. else if command_prev_type==input then
17. if mem_obj==getMemObj(input) then
18. add edge from command_prev to command
19. else
20. traverse command of prev(command_prev)
矩阵分块乘加是矩阵乘法的加速实现, 将输入矩阵平分为4个子矩阵, 然后对4个子块分别进行矩阵乘法, 最后将各个子块运算结果合并. 使用OpenCL实现矩阵分块乘加, 并依据算法对矩阵分块乘进行任务图提取操作, 将结果进行可视化后得到如图2的计算任务图, 节点上的数字代表HXDSP执行时间开销, 边上的数字代表数据传输开销.
|
图 2 OpenCL提取矩阵分块乘加任务图 |
4 HDGEFT调度算法
本节依据HXDSP架构特征和OpenCL计算任务特性, 基于异构调度算法HEFT, 结合OpenCL内核分解技术, 改进得到新的调度算法HDGEFT (heterogeneous double-granularity earliest finish time)异构双粒度最早完成时间优先调度算法.
4.1 HEFT算法异构调度算法HEFT包含两个步骤.
1) 任务选择阶段. 计算每个任务的向上权值ranku, 根据该值对任务节点降序排序, 得到任务分配的优先级序列, 任务优先级一经确定不再改变.
2) 任务分配阶段. 依据步骤1)得到的ranku序列进行任务分配, 计算任务ti在不同处理器pj上最早执行完成的时间EFT(ti, pj), 选择能最早完成任务的处理器并将任务分配到该处理器上.
HEFT算法中涉及的相关公式及符号定义如下.
任务节点ti的向上权值ranku定义为从出口节点向上遍历到任务节点ti的最长距离, 计算公式如下:
| $ ran{k_u}\left( {{t_i}} \right) = {\bar {w_i}} + \mathop {\max }\limits_{{t_j} \in succ\left( {{t_i}} \right)} \left( {ran{k_u} + {c_{ij}}} \right) $ | (1) |
其中,
EFT(ti, pj)表示任务节点ti在处理器pj上最早完成时间, 计算公式如下:
| $ \begin{split} &{\textit{EST}}\left( {{t_i}, {p_j}} \right) \\ &= \max \left( \begin{gathered} avail\left[ j \right], \mathop {\max }\limits_{{t_m} \in pred\left( {{t_i}} \right)} \left( {AFT\left( {{t_m}} \right) + {c_{m, i}}} \right) \end{gathered} \right) \end{split} $ | (2) |
| $ EFT\left( {{t_i}, {p_j}} \right) = {w_{i, j}} + {\textit{EST}}\left( {{t_i}, {p_j}} \right) $ | (3) |
其中, EST表示任务节点ti在处理器pj上最早可执行时间; avail[j]表示处理器pj的最早空闲时间, 即任务节点可以被处理器pj处理的最早时间; pred(ti)={tj | eji∈E}代表任务节点ti的前驱节点集合, 若任务节点ti的前驱节点集合为空, 则ti也是入口节点, 记为tentry; AFT(ti)表示任务节点ti的实际完成时间; cm,i表示当前任务节点ti与前驱任务节点tm的通讯开销; wi,j表示任务节点ti在处理器节点pj上的执行开销.
4.2 HDGEFT算法设计本小节阐述算法思路的出发点和算法具体步骤.
1) 调度结果中会存在如图3情况, 某DSP处理器在处理一个任务时, 从任务开始执行到结束执行期间, 旁边的DSP处理器都处于空闲状态. 如任务Tj被调度在0号DSP处理器上执行, 而在Tj的执行时间段内, 其余3块DSP处理器并未执行计算任务, 理论上, 如果空闲DSP的计算能力能够正向辅助当前的计算任务, 那么运行时系统有理由采取优化设计去利用空闲设备进行计算.
|
图 3 HXDSP调度图 |
2) OpenCL的执行模型特性使内核索引空间中的工作组是并行执行的, 工作组之间没有约束条件, 内核执行结果不依赖于工作组的执行顺序, 每一个输出数据由唯一的工作组产生, 工作组可以作为被调度的单位.
3) 内核执行过程可分为数据传输, 创建执行环境和内核任务执行3个过程, 观察HXDSP异构计算平台下的基本性能评测数据(表1)[25], 可以发现, 数据传输时间对比内核任务执行时间有着巨大差距, 创建内核执行环境的开销较低, 这意味着数据传输开销不是性能瓶颈, 额外的计算核心可以产生正向作用.
|
表 1 基本性能评测表 |
基于以上3点原因, 在依据HEFT调度算法在内核粒度上产生调度结果后, 可依据调度结果对符合条件的内核任务在工作组粒度上再进行一次任务调度, 新算法HDGEFT的具体步骤如下:
输入: 任务流图
输出: 任务在DSPs上的调度策略
1) 任务选择阶段.
2) 任务分配阶段. 前两步与HEFT算法相同.
3) 任务分解阶段. 在任务分配阶段得到分配结果后, 从前到后扫描, 寻找分配在DSP处理器上且满足任务执行期间存在空闲DSP计算资源的任务, 对该任务在空闲DSP集合上执行计算分解, 由于该操作使当前任务执行完成时间和当前处理器空闲时间这两个指标改变, 而任务在一个处理器上最早执行时间EST由处理器可用时间avail和依赖项执行结束时间AFT决定, 内核分解操作可能会对后续任务的最早执行完成时间EFT产生影响, 从而影响分配决策, 见式(3).
因此对原分配序列应重新执行任务分配阶段和任务分解阶段, 迭代执行直至分配完最后一个任务.
4.3 工作组划分文献[19]研究了1CPU-2GPUs架构上单OpenCL内核多设备协同计算相关问题, 通过方案设计和测试数据证明了使用多设备对单个内核计算实现加速的可行性, 其运行时设计为DSPs架构上的内核协同计算运行时设计提供了思路启发.
工作组划分方式需要满足每个工作组都被计算且仅计算一次, 划分工作组有简单可行的方式, 即从最高维度对工作组区间进行划分. 图4展示三维划分, 工作组索引具有连续性, 且整个工作空间被完全覆盖, 通过4个数据对象可以描述进行划分操作后各个DSP负责的工作空间: 数据的维度work_dims, 各个维度上全局ID偏移量global_work_offset, 各个维度上工作项的数量global_work_size, 各个维度上一个工作组中工作项的数量local_work_size. 不同的DSP设备从各自的全局偏移处开始计算, 在各个维度计算一定的步长, 每个DSP的工作区间不重叠, 所有DSP工作组的并集构成完整的任务空间.
|
图 4 三维工作组划分 |
内核划分的另一个关键问题是内存一致性, 内核被分解到不同设备上执行计算, 输出数据存储在不同物理介质上, 最终输出由各部分整合得到. 由于工作组之间的独立性, 某一个输出数据由唯一确定工作组输出, 对不同设备输出数据做线性扫描可得到最终输出数据. 在HXDSP硬件系统上, DSP设备的全局存储被映射到DDR存储上, DSP可操作同一块物理介质, 可避免数据整合问题, 但会引入对DDR资源的竞争, 这种现象可通过工作组的preload-poststore buffer优化.
利用多个DSP设备协同计算一个内核任务的运行时流程如下: 编译内核环节, 使用目标编译器编译内核并将编译后机器码发送到参与计算的DSP; 创建数据环节, 创建作为输入输出参数的数据对象, 将其发送到DDR上, 获得数据对象在DDR上的物理起始地址; 设置内核参数环节, 将参与计算的DSPs上内核参数地址设置为上一步中获得的物理地址, 不同DSP指向相同的DDR地址; 执行内核环节, 划分内核任务工作空间, 确定每个DSP设备全局偏移量和各个维度上工作项的工作项数目, 并驱动DSP的RTOS执行内核; 执行完成环节, 主机端监听设备信号, 在所有参与计算的DSP都向主机端发送子内核执行完成信号, 内核进入完成状态, 可进行下一步数据处理或后续任务调度.
5 实验 5.1 实验环境本文相关研究及实验基于实验室前期搭建的HXDSP异构计算平台[21], 该平台实现参考一种开源的面向CPU处理器的OpenCL实现-PoCL, 在其基础上面向HXDSP平台进行修改和调整, 其中充当从设备HXDSP有相关的开发工具链和模拟运行器, 可以完成kernel任务模拟计算. 实验中涉及的多HXDSP环境, 数据传输, 并行计算, 任务调度等环节都通过软件模拟实时系统实现了相应功能.
实验数据采用随机生成的任务图进行测试, 随机任务图的关键参数变量设置如下, 其中, V指任务图中的节点数目, CCR指计算通信比, out_degree指任务图中的平均出度值, q指参与计算的处理器集合, 固定为1CPU加4HXDSP:
SETV = {20, 40, 60, 80, 100, 120, 140, 160}
SETCCR = {0.1, 0.2, 0.3}
SETout_degree = {1, 3, 5, 7, 9}
SETq = {1, 4}
组合不同的参数获得实例, 在每一个不同的实例下生成10个随机任务图, 计算并对结果取算术平均值. 实验评价指标采用SLR和加速比Speedup, 相关的指标和计算公式如下.
1)调度总长度makespan: 调度总长度等于出口节点的执行结束时间, 当有多个出口节点时, 调度总长度等于出口节点执行结束时间中的最大值, 定义如下:
| $ {\textit{makespan}} = \max \left( {AFT\left( {{v_{\rm{{exit}}}}} \right)} \right) $ | (4) |
2) SLR (schedule length ratio): 调度总长度与关键路径上的节点分别在最快处理器上执行时间之和的比. SLR为一个无单位实数, SLR值与算法性能成反比, 值越接近1效果越好, 定义如下:
| $ {\textit{SLR}} = \frac{{{\textit{makespan}}}}{{\displaystyle\sum\nolimits_{{n_i} \in {{\textit{CP}}_{\min }}} {{{\min }_{{p_j} \in Q}}\left( {{w_{i, j}}} \right)} }} $ | (5) |
3)加速比Speedup: 在各个处理器上分别串行执行任务图中所有节点产生的执行开销之和, 取其中的最小值与调度总长度的比值. Speedup为一个无单位实数, Speedup与算法的效率成正比, Speedup数值不会大于处理器数量, 定义如下:
| $ {\textit{Speedup}} = \frac{{{{\min }_{{p_j} \in Q}}\left( {\displaystyle\sum\nolimits_{{n_i} \in V} {{w_{i, j}}} } \right)}}{{{\textit{makespan}}}} $ | (6) |
实验使用HEFT, CPOP算法进行对比, 使用SLR和加速比Speedup作为评价指标, 实验结果如图5.
|
图 5 调度算法实验结果 |
由图5实验数据可得, 改进的HDGEFT算法在OpenCL任务调度中有明显的效率优势. 在部分结果中, SLR在HDGEFT优化算法下的值能小于1, 这意味着对关键路径上满足条件的节点进行内核任务分解, 算法正向效率提升大于通信开销.
在节点数目确定的情况下, 与HDGEFT调度效果最相关的参数是图节点的平均出度值, 出度值越大, 节点的依赖关系越多, 串行性增强, 并行性减弱, DAG图中的节点会获得更大深度, 这也导致依据HEFT算法产生的调度结果中出现更多的处理器空闲间隙, 为HDGEFT算法提供了更多可分解的节点. 在节点数设置为80, 选取Speedup作为评价指标的情况下, 测试不同依赖数目下的优化效果, 实验结果如表2, 观察可得, 算法优化效果与出度值有明显正相关, 即内核间的串行性越强, 应用越能从HDGEFT算法中获得收益.
|
|
表 2 出度值性能评测表 |
使用OpenCL应用任务图进行测试: MapReduce, 矩阵分块乘法, 特征融合. 在HXDSP异构计算平台上, 应用在不同策略下的执行时间如图6, 观察可得, HDGETF算法有不同程度的优化效果.
|
图 6 调度长度实验评估 |
测试应用中的矩阵分块乘法的任务图如图2所示, 该任务图使用HDGEFT算法调度后得到的调度图如图7所示, 任务图中的split1和merge内核任务满足内核任务分解条件, 被执行内核分解操作, 获得了仅靠HEFT任务调度无法获得的额外性能收益. split1和split2任务是并发关系, 由于split1在分配列表中优先, 所以空闲DSP资源全部被分配给split1, 但仅分解split1并不能加速mul_add任务, 因为mul_add也依赖于split2, 观察可得, 将空闲的DSP资源平分给split1和split2是更优的行为, 可以使计算任务更快完成, 获得更大收益, 这为算法进一步改进提供了方向.
|
图 7 矩阵分块乘调度图 |
6 总结和展望
本文面向异构环境下的OpenCL运行时中任务调度问题, 给出一种获取OpenCL任务计算图的工程方法, 并结合HXDSP硬件架构, 基于HEFT算法提出了一种针对OpenCL任务进行优化调度的HDGEFT算法, 通过设计实验, 使用随机生成的任务图和具体的应用任务图验证了该算法的有效性.
在运行时进行OpenCL任务调度系统设计有许多改进方向, 下一步可添加机制完善运行时任务调度系统, 如其他类型处理器和DSPs之间对同一个内核的协同计算, 基于内核可分解特性的先验条件设计出更加完备的调度策略, 重叠计算操作和数据传输操作以获得更大的并发性, 这些措施可通过自动化实施提高异构系统的效能.
| [1] |
Kwok YK, Ahmad I. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys, 1999, 31(4): 406-471. DOI:10.1145/344588.344618 |
| [2] |
Shan A. Heterogeneous processing: A strategy for augmenting Moore’s law. Linux Journal, 2006, 2006(142): 80-82. |
| [3] |
邓文齐. 基于BWDSP的众核深度学习加速器的研究[硕士学位论文]. 合肥: 中国科学技术大学, 2018.
|
| [4] |
蔡恒雨, 宁成明, 侯璇, 等. 国产BWDSP的并行通信接口设计. 小型微型计算机系统, 2021, 42(5): 897-904. DOI:10.3969/j.issn.1000-1220.2021.05.001 |
| [5] |
Piccardi M. Background subtraction techniques: A review. Proceedings of 2004 IEEE International Conference on Systems, Man and Cybernetics. The Hague: IEEE, 2004. 3099–3104.
|
| [6] |
Gregory K, Miller A. C++ AMP: Accelerated massive parallelism with Microsoft Visual C++. Microsoft Press, 2012.
|
| [7] |
Auerbach J, Bacon DF, Cheng P, et al. Lime: A Java-compatible and synthesizable language for heterogeneous architectures. ACM SIGPLAN Notices, 2010, 45(10): 89-108. DOI:10.1145/1932682.1869469 |
| [8] |
Ruan YL, Liu G, Li QH, et al. An efficient scheduling algorithm for dependent tasks. Proceedings of the 4th International Conference on Computer and Information Technology. Wuhan: IEEE, 2004. 456–461.
|
| [9] |
Abbasi SI, Kamal S, Gochoo M, et al. Affinity-based task scheduling on heterogeneous multicore systems using CBS and QBICTM. Applied Sciences, 2021, 11(12): 5740. DOI:10.3390/app11125740 |
| [10] |
Kwok YK, Ahmad I. Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors. Proceedings of the International Workshop on Languages & Compilers for Parallel Computing. Berlin: Springer, 2011.
|
| [11] |
Zhou L, Sun SX. Scheduling algorithm based on critical tasks in heterogeneous environments. Journal of Systems Engineering and Electronics, 2008, 19(2): 398-405. DOI:10.1016/S1004-4132(08)60099-7 |
| [12] |
Ma JT, Li WT, Fu T, et al. A novel dynamic task scheduling algorithm based on improved genetic algorithm in cloud computing. Wireless Communications, Networking and Applications. New Delhi: Springer, 2016. 829–835.
|
| [13] |
Hasan MZ, Al-Rizzo H. Task scheduling in Internet of Things cloud environment using a robust particle swarm optimization. Concurrency and Computation: Practice and Experience, 2020, 32(2): e5442. |
| [14] |
Kumar AMS, Venkatesan M. Multi-objective task scheduling using hybrid genetic-ant colony optimization algorithm in cloud environment. Wireless Personal Communications, 2019, 107(4): 1835-1848. DOI:10.1007/s11277-019-06360-8 |
| [15] |
Topcuoglu H, Hariri S, Wu MY. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274. DOI:10.1109/71.993206 |
| [16] |
Grewe D, Wang Z, O’Boyle MFP. OpenCL task partitioning in the presence of GPU contention. Proceedings of the 26th International Workshop on Languages and Compilers for Parallel Computing. San Jose: Springer, 2013. 87–101.
|
| [17] |
Ravi VT, Ma WJ, Chiu D, et al. Compiler and runtime support for enabling generalized reduction computations on heterogeneous parallel configurations. Proceedings of the 24th ACM International Conference on Supercomputing. Ibaraki: ACM, 2010. 137–146.
|
| [18] |
Tian L, Meng C, Zhou FG. A two-level task scheduler on multiple DSP system for OpenCL. Advances in Mechanical Engineering, 2014, 6: 1-10. |
| [19] |
Lee J, Samadi M, Park Y, et al. SKMD: Single kernel on multiple devices for transparent CPU-GPU collaboration. ACM Transactions on Computer Systems, 2015, 33(3): 9. |
| [20] |
Jääskeläinen P, Korhonen V, Koskela M, et al. Exploiting task parallelism with OpenCL: A case study. Journal of Signal Processing Systems, 2019, 91(1): 33-46. DOI:10.1007/s11265-018-1416-1 |
| [21] |
彭云峰. 高性能计算应用程序的静态性能分析和建模方法研究. 计算机应用研究, 2021, 38(1): 204-208, 222. |
| [22] |
Mendis C, Renda A, Amarasinghe SP, et al. Ithemal: Accurate, portable and fast basic block throughput estimation using deep neural networks. Proceedings of the 36th International Conference on Machine Learning. Long Beach: PMLR, 2019. 4505–4515.
|
| [23] |
Braun L, Nikas S, Song C, et al. A simple model for portable and fast prediction of execution time and power consumption of GPU kernels. ACM Transactions on Architecture and Code Optimization, 2021, 18(1): 7. |
| [24] |
Bouhali N, Ouarnoughi H, Niar S, et al. Execution time modeling for CNN inference on embedded GPUs. Proceedings of the 2021 Drone Systems Engineering and Rapid Simulation and Performance Evaluation: Methods and Tools Proceedings. Budapest: ACM, 2021. 59–65.
|
| [25] |
宁成明, 蔡恒雨, 郑启龙, 等. HXDSP异构计算框架的设计与优化. 小型微型计算机系统, 2022, 43(1): 179-185. DOI:10.3969/j.issn.1000-1220.2022.01.028 |