Cited By
View all- Outman SMcGregor J(2009)Identifying task-level parallelism by functional transformation with side-effect domainsProceedings of the 47th annual ACM Southeast Conference10.1145/1566445.1566482(1-6)Online publication date: 19-Mar-2009
Parallelizing Subroutines in Sequential Programs
Abstract
An algorithm for making sequential programs parallel is described, which first identifies all subroutines, then determines the appropriate execution mode and restructures the code. It works recursively to parallelize the entire program. We use Fortran in our work, but many of the concepts apply to other languages. Our hardware model is a shared-memory multiprocessor system with a fixed number of identical processors, each with its own local memory connected to a common memory that is accessible to all processors equally. The model implements interprocessor synchronization and communication via special memory locations or special storage. Systems like the Cray X-MP, IBM 3090, and Alliant FX/8 fit this model. Our input is a sequential, structured Fortran program with no overlapping branches. With today's emphasis on writing structured code, this restriction is reasonable. A prototype of a system to implement the algorithm is under development on an IBM 3090 multiprocessor.
References
[1]
1. R. Triolet, "Direct Parallelization of Call Statement," SIGPlan Notices, July 1986, pp. 176-185.
[2]
2. A.V. Aho, R. Sethi, and J.D. Ullman, Compilers--Principles, Techniques, and Tools, Addison-Wesley, Reading, Mass., 1988.
[3]
3. J. Ferrante, K. Ottenstein, and J. Warren, "The Program Dependence Graph and Its Use in Optimization," ACM Trans. Programming Languages and Systems, July 1987, pp. 319-349.
[4]
4. T. Lengauer and R.E. Tarjan, "A Fast Algorithm for Finding Dominators in a Flowgraph," ACM Trans. Programming Languages and Systems, July 1979, pp. 121-141.
[5]
5. R. Cytron, M. Hind, and W. Hsieh, "Automatic Generation of DAG Parallelism," Proc. SIGPlan Conf. Programming Language Design and Implementation, ACM Press, New York, 1989, pp. 54-68.
[6]
6. H. Zima and B. Chapman, Supercompilers for Parallel and Vector Computers, ACM Press, New York, and Addison-Wesley, Reading, Mass., 1991.
[7]
7. F. Allen et al., "An Overview of the PTRAN Analysis System for Multiprocessing," Proc. Int'l Conf. Super-computing , IEEE CS Press, Los Alamitos, Calif., 1987, pp. 194-211.
[8]
8. M. Wegman and K. Zadeck, "Constant Propagation with Conditional Branches," Conf. Record ACM Symp. Principles of Programming Languages, ACM Press, New York, 1985, pp. 291-299.
[9]
9. R. Allen and K. Kennedy, "Automatic Translation of Fortran Programs to Vector Form," ACM Trans. Programming Languages and Systems, Oct. 1987, pp. 491-542.
[10]
10. C.-P. Chu and D.L. Carver, "An Analysis of Recurrence Relations in Fortran Do-Loops for Vector Processing," Proc. Fifth Parallel Processing Symp., IEEE CS Press, Los Alamitos, Calif., 1991, pp. 619-625.
Index Terms
- Parallelizing Subroutines in Sequential Programs
Recommendations
A Comparison of 12 Parallel FORTRAN Dialects
A simple program that approximates pi by numerical quadrature is rewritten to run on nine commercially available processors to illustrate the compilations that arise in parallel programming in FORTRAN. The machines used are the Alliant FX/8, BBN ...
Parallelizing Image Feature Extraction on Coarse-Grain Machines
In this paper, we present a fast parallel algorithm for feature extraction on coarse-grain MIMD machines. By maintaining algorithmic threads at each node, our algorithm enhances processor utilization and obtains large speed-ups. Our implementations show ...
Parallelizing constraint programs
DAMP '10: Proceedings of the 5th ACM SIGPLAN workshop on Declarative aspects of multicore programmingThe availability of commodity multicore and multiprocessor machines and the inherent parallelism in constraint programming search offer significant opportunities for constraint programming. Both constraint-based local search and finite-domain techniques ...
Reviews
Ann E. Kelley Sobel
The authors describe an algorithm that takes a sequential, structured FORTRAN program as input and produces parallel call-end statements for subroutines that can be executed in parallel. The presentation emphasizes the identification of those subroutines that can execute in a synchronous parallel mode. This algorithm incorporates and outlines many of the standard compiler code optimization techniques: analysis of call and program dependence graphs, inlining, intraprocedural constant propagation, and data dependency analysis of array indices. The information gathered is used to identify which subroutines can be restructured to incorporate parallel tasks and synchronization primitives. Only those procedure calls having identical control dependencies can be considered candidates for the same reasons that apply to sequential control statements. The reference list contains the important advances in compiler code optimization techniques. The extensive analysis required to identify synchronizable subroutine calls in addition to the massive overhead incurred from using library calls for synchronization management makes a potential performance increase highly unlikely.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 1994 IEEE. All Rights Reserved.
Publisher
IEEE Computer Society Press
Washington, DC, United States
Publication History
Published: 01 January 1994
Author Tags
- Alliant FX/8
- Cray X-MP
- IBM 3090 multiprocessor
- IBM computers
- code restructuring
- common memory
- execution mode
- interprocessor communication
- interprocessor synchronization
- local memory
- parallel algorithms
- parallel programming
- recursive process
- sequential programs
- shared-memory multiprocessor system
- special memory locations
- structured Fortran program
- structured programming
- subroutine parallelization
- subroutines
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Nov 2024
Other Metrics
Citations
Cited By
View all- Outman SMcGregor J(2009)Identifying task-level parallelism by functional transformation with side-effect domainsProceedings of the 47th annual ACM Southeast Conference10.1145/1566445.1566482(1-6)Online publication date: 19-Mar-2009