Title | ||
---|---|---|
On the Optimality of Allen and Kennedy's Algorithm for Parallel Extraction in Nested Loops |
Abstract | ||
---|---|---|
We explore the link between dependence abstractions and maximal parallelism extraction in nested loops. Our goal is to find, for each dependence abstraction, the minima) transformations needed for maximal parallelism extraction. The result of this paper is that Allen and Kennedy's algorithm is optimal when dependences are approximated by dependence levels. This means that even the most sophisticated algo- rithm cannot detect more parallelism than found by Allen and Kennedy's algorithm, as long as dependence level is the only information available. |
Year | DOI | Venue |
---|---|---|
1996 | 10.1007/3-540-61626-8_50 | Parallel Algorithms Appl. |
Keywords | Field | DocType |
nested loops,parallel extraction | Abstraction,Computer science,Parallel computing,Algorithm,Cycles per instruction,Nested loop join | Conference |
Volume | Issue | ISBN |
12 | 1-3 | 3-540-61626-8 |
Citations | PageRank | References |
12 | 1.10 | 21 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alain Darte | 1 | 888 | 56.40 |
Frédéric Vivien | 2 | 101 | 7.07 |