Abstract | ||
---|---|---|
Software pipelining exploits instruction-level parallelism from loops. In static compilers, it has been one of the most efficient optimizations for wide-issue architectures. However, the compilation time is at least O(|V|3) (V: the set of operations in a loop) and in the worst-case exponential. This paper extends software pipelining to dynamic compilers. We present a novel and simple algorithm with linear time O(|V| + |E|) (E: the set of edges in the dependence graph of a loop). Preliminary experiments show the method is light-weight and generates optimal or near-optimal schedules.
|
Year | DOI | Venue |
---|---|---|
2014 | 10.1145/2544137.2544148 | CGO |
Keywords | Field | DocType |
dependence graph,preliminary experiment,just-in-time software pipelining,linear time,efficient optimizations,simple algorithm,instruction-level parallelism,dynamic compiler,compilation time,software pipelining,near-optimal schedule,scheduling,just in time compilation | Software pipelining,Scheduling (computing),Computer science,Parallel computing,Real-time computing,Compiler,Loop inversion,Schedule,SIMPLE algorithm,Just-in-time compilation,Time complexity | Conference |
ISBN | Citations | PageRank |
978-1-4503-2670-4 | 1 | 0.36 |
References | Authors | |
20 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hongbo Rong | 1 | 91 | 6.22 |
Hyunchul Park | 2 | 341 | 17.56 |
Youfeng Wu | 3 | 749 | 52.16 |
Cheng Wang | 4 | 356 | 20.10 |