Split-path enhanced pipeline scheduling for loops with control flows
SangMin Shim, Soo Mook Moon · 1998
Software pipelining increases the loop execution throughput by overlapping the execution of successive iterations in a pipelined fashion. For loops with control flows, software pipelining is not straightforward because we need to consider the overlap of more than one execution path. Modulo scheduling simply transforms them into straight-line loops through if-conversion which, in effect, achieves a fixed, worst-case initiation interval (II) among all paths. All-path pipelining (APP) and enhanced pipeline scheduling (EPS) can achieve a variable II depending on the path that is followed through the loop at execution time. Unfortunately, APP concentrates only on the overlap within the same path, entirely losing the overlap between different paths, whereas EPS attempts to overlap all future paths together, failing to produce a tight schedule for each individual path. In this paper, we propose a new approach to EPS which splits each individual path in the loop via tail duplication, and perfo...