About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Theoretical Computer Science
Paper
A theory of compaction-based parallelization
Abstract
We present a simple and uniform transformational system for extracting parallelism from programs. The transformations are studied as a formal system. We define a measure of program improvement, and show that the transformations improve programs with respect to the measure. We show that it is possible to compute limits of infinite sequences of the transformations; this allows our system to implement software pipelining, and leads to a general solution to the problem of software pipelining in the presence of tests. Using the primitive transformations and the limit-taking transformation, it is possible to express the classical parallelization techniques for vector, multiprocessor, and VLIW machines. Thus, our transformational system can be viewed as a formal foundation for the area of parallelization. We present implementations of two techniques, doacross and a simple form of vectorization. © 1990.