Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6518
Title: Percolation Scheduling: A Parallel Compilation Technique
Authors: Nicolau, Alexandru
Keywords: computer science
technical report
Issue Date: May-1985
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR85-678
Abstract: Percolation Scheduling (PS) is a new technique for compiling programs into parallel code. It attempts to overcome problems that limit the effectiveness and applicability of currently available techniques. PS globally rearranges code past basic block boundaries. Its core is a small set of simple, primitive program transformations defined in terms of adjacent nodes in a program graph. These transformations constitute the lowest level in a system of transformations and guidance rules. Higher levels of this hierarchy control and enhance the applicability of the core transformations and enable us to exploit both fine grained and coarse parallelism. Unlike other, more ad hoc approaches, PS is based on rigorous definitions of the computational model and of the core transformations. The correctness and termination of the transformations is proven here. The completeness of the transformations is also discussed. As a result our implementation, which is now underway, can proceed on a sound basis. In particular, PS enjoys greater adaptability and independence between the levels than would be possible otherwise. This paper describes PS in detail. The correctness aspects as well as illustrations of the effectiveness of our techniques are presented. Architectures which may benefit from the use of PS are also discussed.
URI: http://hdl.handle.net/1813/6518
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
85-678.pdf2.73 MBAdobe PDFView/Open
85-678.ps727.59 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us