Name
Abstract | ||
|---|---|---|
While there are well-understood methods for detecting loops whose iterations are independent and parallelizing them, there are comparatively fewer proposals that support parallel execution of a sequence of loops or nested loops in the case where such loops have dependencies among them. This paper introduces a refined notion of independence, called eventual independence, that in its simplest form considers two loops, say loop1 and loop2, and captures the idea that for every i there exists k such that the i+1-th iteration of loop2 is independent from the j-th iteration of loop1, for all j≥k. Eventual independence provides the foundation of a semantics-preserving program transformation, called synchronized pipelining, that makes execution of consecutive or nested loops parallel, relying on a minimal number of synchronization events to ensure semantics preservation. The practical benefits of synchronized pipelining are demonstrated through experimental results on common algorithms such as sorting and Fourier transforms. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-12592-8_13 | logic based program synthesis and transformation |
Keywords | Field | DocType |
nested loops parallel,1-th iteration,parallel execution,nested loop,eventual independence,program parallelization,common algorithm,fewer proposal,j-th iteration,minimal number,nested loops,fourier transform | Pipeline (computing),Synchronization,Separation logic,Program transformation,Software pipelining,Computer science,Induction variable,Algorithm,Theoretical computer science,Sorting,Nested loop join | Conference |
Volume | ISSN | ISBN |
6037 | 0302-9743 | 3-642-12591-3 |
Citations | PageRank | References |
0 | 0.34 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Leonardo Scandolo | 1 | 0 | 0.34 |
| César Kunz | 2 | 167 | 10.81 |
| Manuel V. Hermenegildo | 3 | 2692 | 182.60 |