Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (29): 8-12.

Previous Articles     Next Articles

Analytic method of loop run-time information based on edge profiling

NIU Xiaoxia, WU Yanxia, GU Guochang, ZHANG Bowei, LI Jingmei   

  1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001 China
  • Online:2012-10-11 Published:2012-10-22

基于edge profiling的循环运行时信息分析方法

牛晓霞,吴艳霞,顾国昌,张博为,李静梅   

  1. 哈尔滨工程大学 计算机科学与技术学院,哈尔滨 150001

Abstract: The loop structure is always considered as the main time-consuming part in most computationally intensive applications. Since the FPGA-based reconfigurable computing systems emerge in recent years, the static techniques for analyzing loop structures are not able to meet the requirement of specific optimization according to the current behavior of programs. To address the lack of directly accessing the run-time information by using the dynamic techniques for analyzing loops, a new loop-analysis method is proposed. In this method which is implemented on the Low Level Virtual Machine(LLVM), the loop structures obtained from the Control Flow Graph(CFG) are recognized according to the dominating relationship, then the result of the edge profiling before the frequency of loop-calling, the average frequency of iteration and time of running are calculated. Experimental results manifest that the proposed method can recognize all the loop structure and collect the loop run-time information accurately, which can support hardware/software partitioning work of reconfigurable computing.

Key words: computer architecture, loop run-time information, edge profiling

摘要: 应用程序中循环部分往往是计算密集型应用的主要工作负载,随着基于FPGA的可重构计算系统的出现,循环的静态分析技术已不能满足可重构计算系统根据程序当前行为模式进行特定优化的要求。针对现有的程序动态分析技术无法直接获取循环动态信息的问题,提出一种循环信息分析算法,根据支配关系在控制流图中识别循环,通过edge profiling的结果分析计算得到循环调用次数、循环平均迭代次数及循环运行时间等关键信息,并在LLVM(Low Level Virtual Machine)平台上实现该算法。实验结果表明,该算法能够自动识别所有循环结构,并对循环部分进行精确分析,分析结果能够为可重构计算系统待加速计算密集型循环的选择提供较全面、精确的信息支持,对程序员进行可重构系统中软硬件划分技术的研究具有重要作用。

关键词: 计算机系统结构, 循环运行时信息, edge profiling