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

软件流水技术通过重组循环体来挖掘指令级并行性,模调度是一类广泛使用的软件流水调度算法.传统模调度算法通常会产生变量活跃域重叠和寄存器压力增大问题,无法适用于嵌入式处理器.本文面向嵌入式处理器特性,建立了一种优化回溯模型,并基于该回溯模型提出了一种面向嵌入式处理器的无重叠模调度算法(NOn-Over-lapped Iterative Modulo Scheduling,简称NOOI).NOOI算法使用循环相关反依赖消除变量活跃域重叠,并使用依赖约束和资源约束回溯模型消解节点冲突,从而提高了模调度的有效性.实验结果表明,NOOI模调度算法能够有效改进模调度成功率和循环启动间距,并提高程序性能.

Non-overlapped Modulo Scheduling with Optimized Backtracking Model

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.