Parallelizing Programs with Recursive Data Structures
| dc.contributor.author | Hendren, Laurie J. | en_US |
| dc.date.accessioned | 2007-04-23T17:46:41Z | |
| dc.date.available | 2007-04-23T17:46:41Z | |
| dc.date.issued | 1990-04 | en_US |
| dc.description.abstract | Interference estimation is a useful tool in developing parallel programs and is a key aspect of automatically parallelizing sequential programs. Interference analysis and disambiguation mechanisms for programs with simple data types and arrays have become a standard part of parallelizing and vectorizing compilers. However, efficient and implementable techniques for interference analysis in the presence of dynamic data structures have yet to be developed. This thesis addresses the problem of estimating interference and parallelizing programs in the setting of an imperative language that supports dynamic data structures. By focusing on analysis methods for recursively defined pointer data structures such as trees and DAGs, we have developed efficient and implementable interference analysis tools and parallelization techniques. The interference analysis methods are based on estimating the relationships between accessible nodes in a data structure. We define a data abstraction for estimating relationships that leads to an efficient interference analysis. Analysis functions are provided for SIL, a simple imperative language that includes conditionals, loops and recursive procedures. The analysis is proven sound with respect to the standard semantics for SIL. Based on the interference analysis tools, a collection of parallelization techniques are developed and the coarse-grain techniques are used to develop a simple system for parallelizing programs for a shared memory machine. The analysis techniques and parallelization system have been implemented, and examples illustrating the methods are provided. | en_US |
| dc.format.extent | 10342806 bytes | |
| dc.format.extent | 2703845 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/TR90-1114 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6954 | |
| 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 | Parallelizing Programs with Recursive Data Structures | en_US |
| dc.type | technical report | en_US |