基于优化回溯模型的无重叠模调度算法  

Non-overlapped Modulo Scheduling with Optimized Backtracking Model

作　　者：谭明星[1,2,3] 刘先华[1,2] 张吉豫[1,2] 程旭[1,2,3] 

机构地区：[1]北京大学信息科学技术学院,北京100871 [2]微处理器及系统教育部工程研究中心,北京100871 [3]北京大学深圳研究生院,广东深圳518055

出　　处：《电子学报》2012年第8期1681-1686,共6页Acta Electronica Sinica

基　　金：国家核高基重大专项(No.2009ZX01029-001-002;No.2009ZX01036-001-003);北京市自然科学基金(No.4123098)

摘　　要：软件流水技术通过重组循环体来挖掘指令级并行性,模调度是一类广泛使用的软件流水调度算法.传统模调度算法通常会产生变量活跃域重叠和寄存器压力增大问题,无法适用于嵌入式处理器.本文面向嵌入式处理器特性,建立了一种优化回溯模型,并基于该回溯模型提出了一种面向嵌入式处理器的无重叠模调度算法(NOn-Over-lapped Iterative Modulo Scheduling,简称NOOI).NOOI算法使用循环相关反依赖消除变量活跃域重叠,并使用依赖约束和资源约束回溯模型消解节点冲突,从而提高了模调度的有效性.实验结果表明,NOOI模调度算法能够有效改进模调度成功率和循环启动间距,并提高程序性能.Software pipelining exploits instruction level parallelism by reconstructing loops, while modulo scheduling is a kind of widely used scheduling algorithms for software pipelining. Traditional modulo scheduling algorithms usually cause overlapping register lifetimes and increase register pressure, and thus are not applicable to embedded processors. This paper presents the NOn- Overlapped Iterative （NOOI） modulo scheduling algorithm based on an optimized backtracking model for embedded processors. NOOI algorithm avoids the register lifetime overlap by adding loop-carried anti-dependence and resolves the scheduling conflicts using dependence-constrained and resource-constrained backtracking model. Our evaluations show that NOOI can significantly improve the success ratio and loop initial interval, which leads to better program performance.

关 键 词：嵌入式处理器 软件流水 模调度 回溯模型 

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