基于整数线性规划的VLIW DSP指令分簇调度  

Integer linear programming based instruction cluster assignment schedule of VLIW DSP

作　　者：周鹏 刘纯纲[1,2] 郑启龙 Zhou Peng;Liu Chungang;Zheng Qilong(School of Computer Science&Technology,University of Science&Technology of China,Hefei 230026,China;Key Laboratory of High Performance Computing of Anhui Province,University of Science&Technology of China,Hefei 230026,China)

机构地区：[1]中国科学技术大学计算机科学与技术学院,合肥230026 [2]中国科学技术大学高性能计算安徽省重点实验室,合肥230026

出　　处：《计算机应用研究》2022年第10期3078-3083,共6页Application Research of Computers

基　　金：国家核高基重大专项资助项目(2012ZX01034-001-001)。

摘　　要：在分簇VLIW DSP上,指令分簇是一项对程序性能有重要影响的编译优化,但现有的指令分簇算法只能处理顺序的程序区域,且难以获得最佳的分簇方案。针对这些问题,提出一种基于整数线性规划的统一指令分簇与指令调度的方法。该方法使用0-1决策变量表示函数中指令的分簇、指令的局部调度以及簇间传输指令的全局调度,并将指令之间的依赖关系和对处理器资源的竞争关系构造为线性约束,最终得到一个以最小化函数的估计执行时间为目标的整数线性规划模型。实验结果表明,求解该模型得到的分簇调度方案对程序性能的优化显著强于现有算法,并且求解模型所耗费的时间是可接受的。Cluster assignment is a compiler optimization that plays an important role in performance of programs.However,the existing algorithms only work on straight-line program area,and is difficult to be optimal.Aiming at these problems,this paper proposed a unified cluster assignment and instruction scheduling method based on integer linear programming.This method used 0-1 decision variables to represent cluster assignment,local instruction scheduling and global scheduling of inter-cluster transfer instructions,and formulated dependency and processor resources competition between instructions into linear constraints,eventually got an integer linear programming model whose objective was to minimize the estimated execution time of the function.Experimental results show that the cluster assignment and scheduling scheme from solving the model significantly outperforms the existing algorithms on accelerating programs,and the time required to solve the model is acceptable.

关 键 词：数字信号处理器 超长指令字 指令分簇 指令调度 整数线性规划 

分 类 号：TP314[自动化与计算机技术—计算机软件与理论]