Optimal Loop Parallelization
| dc.contributor.author | Aiken, Alexander | en_US |
| dc.contributor.author | Nicolau, Alexandru | en_US |
| dc.date.accessioned | 2007-04-23T17:24:50Z | |
| dc.date.available | 2007-04-23T17:24:50Z | |
| dc.date.issued | 1988-03 | en_US |
| dc.description.abstract | Parallelizing compilers promise to exploit the parallelism available in a given program, particularly parallelism that is too low-level or irregular to be expressed by hand in an algorithm. However, existing parallelization techniques do not handle loops in a satisfactory manner. Fine-grain (instruction level) parallelization, or compaction, captures irregular parallelism inside a loop body but does not exploit parallelism across loop iterations. Coarser methods, such as doacross [9], sacrifice irregular forms of parallelism in favor of pipelining iterations (software pipelining). Both of these approaches often yield suboptimal speedups even under the best conditions-when resources are plentiful and processors are synchronous. In this paper we present a new technique bridging the gap between fine-and coarse-grain loop parallelization, allowing the exploitation of parallelism inside and across loop iterations. Furthermore, we show that, given a loop and a set of dependencies between its statements, the execution schedule obtained by our transformation is time optimal: no transformation of the loop based on the given data-dependencies can yield a shorter running time for that loop. | en_US |
| dc.format.extent | 1289049 bytes | |
| dc.format.extent | 309424 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-905 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6745 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | Optimal Loop Parallelization | en_US |
| dc.type | technical report | en_US |