针对递归函数的高级综合编译优化算法  

High-Level Synthesis Compile Optimization Algorithm for Recursive Functions

作　　者：张茉莉[1,2] 杨海钢[1] 刘峰[1] 黄娟[1] 崔秀海[1] 

机构地区：[1]中国科学院电子学研究所可编程芯片与系统研究室北京100190 [2]中国科学院大学北京100049

出　　处：《计算机辅助设计与图形学学报》2013年第10期1557-1565,共9页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家“九七三”重点基础研究发展计划项目(2011CB933202);国家自然科学基金(61106033)

摘　　要：为了消除高级综合中的递归函数调用,提出一种基于函数调用图(FCG)和分支决策的编译优化算法.首先在LLVM编译器架构下给出FCG的中间结构,将递归调用转换为非递归函数的嵌套调用,然后借助决策树的构造规则去除函数体中的分支判断及未调用的子支,最后采用子函数复用、资源预评估的方法控制实现电路的规模.实验结果表明,与内联展开算法RecursionHW相比,采用该算法综合后的逻辑单元数平均减少63%,时钟频率平均提高3.2倍,并且高级综合的总时长随递归深度的增大而呈指数级减少.Based on function call graph （FCG） and branch decision strategy, this paper presents an optimization algorithm during high-level synthesis （HLS） to handle recursion. Firstly, FCG is proposed to eliminate the recursive calls within the LLVM compiler infrastructure, then construction rules of the decision tree is introduced to remove branch condition judgment and non-called branch. Finally sub-function reuse and dynamic resource pre-evaluation is adopted to prevent code explosion. Compared with the inline algorithm RecursionHW, experimental results show that the presented algorithm can get an average resource reduction by 63%, and the maximum clock frequency can be increased 3.2 times averagely. Moreover, the HLS time is reduced exponentially with the increase of recursion depth.

关 键 词：高级综合 递归函数 编译优化 函数调用图 决策树 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]