Name
Abstract | ||
|---|---|---|
Loop alignment is a classical program transformation that can enable the fusion of parallel loops, thereby increasing locality and reducing the number of synchronizations. Although the problem is quite old in the one-dimensional case (i.e., no nested loops), it came back recently - with a multi-dimensional form - when trying to refine parallelization algorithms based on multi-dimensional schedules. The main result of this paper is that, unlike the problem in 1D, finding a multi-dimensional shift of statements that makes an innermost loop parallel is strongly NP-complete. Nevertheless, we identify some polynomially-solvable cases that can occur in practice and we show that the general problemcan be stated as a systemof integer linear constraints. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/3-540-45841-7_14 | STACS |
Keywords | Field | DocType |
main result,multi-dimensional loop alignment,loop alignment,parallel loop,multi-dimensional form,general problemcan,multi-dimensional schedule,nested loop,multi-dimensional shift,innermost loop parallel,classical program transformation,complexity,loop optimization,automatic parallelization,retiming,nested loops | Loop fusion,Retiming,Discrete mathematics,Locality,Combinatorics,Program transformation,Computer science,Loop fission,Loop optimization,Algorithm,Nested loop join,Automatic parallelization | Conference |
ISBN | Citations | PageRank |
3-540-43283-3 | 8 | 0.52 |
References | Authors | |
20 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alain Darte | 1 | 888 | 56.40 |
| Guillaume Huard | 2 | 135 | 11.10 |