Vivek Sarkar
John Hennessy
ABSTRACT
Partitioning and scheduling techniques are necessary to implement parallel languages on multiprocessors. Multiprocessor performance is maximized when parallelism between tasks is optimally traded off with communication and synchronization overhead. We present compile-time partitioning and scheduling techniques to achieve this trade-off.
- 1.Ackerman, W. B. & Dennis, J. B. VAL-- a value-oriented algorithmic language. Preliminary reference manual. MIT/LCS/TR-218, Laboratory for Computer Science, MIT, June, 1979. Google Scholar
Digital Library
- 2.Aho, A. V., Hoperoft, J. E., Ullman, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google ScholarDigital Library
- 3.Allen, J. R. & Kennedy, K. PFC: A Program to Convert Fortran to Parallel Form. The Proceedings of the IBM Conference on Parallel Computers and Scientific Computations, March, 1982.Google Scholar
- 4.Bateher, K. E. "Sorting networks and their applications". 1968 Spring Joint Computer Conf., AFIPS Proc. 32 (1968), 307-314.Google Scholar
- 5.Campbell, M. L. Static Allocation for a Dataflow Multiprocessor. Proe. 1985 Int. Conf. Parallel Processing, 1985, pp. 511-517.Google Scholar
- 6.Celoni, J. R. & Hennessy, J. L. SAL: A Single- Assignment language for Parallel Algorithms. CIaSSiC-83-O1, Center for Large Scale Scientific Computation, Stanford University, Sept., 1983.Google Scholar
- 7.Davis, A. L. & Keller, R. M. "Data Flow Program Graphs". IEEE Computer 15, 2 (Feb. 1982).Google ScholarCross Ref
- 8.Using the Encore Multimax. Argonne National Laboratory, Mathematics and Computer Science Division, ANI./MCS-TM-65, 1986.Google Scholar
- 9.Fisher, J. A. et aL "Parallel Processing: A Smart Compiler and a Dumb Machine". SIGPIMN Notices 19, 6 (June 1984). Google ScholarDigital Library
- 10.Gottlieb, A. eta/. "The NYU Ultracomputer - Designing an MIMD Shared Memory Parallel Computer". IEEE Trans. Computers C-32, 2 (Feb. 1983).Google Scholar
- 11.Graham, R. L. "Bounds on Multiprocessing Timing Anomalies". SlAM J. Appl. Math. 17, 2 (March 1969).Google ScholarCross Ref
- 12.Jones, A. K., Gehringer, E. F. The Cm* Multiprocessor Project: A Research Review. CMU-CS-80-131, Computer Science Department, Carnegie-Mellon University, 1980.Google Scholar
- 13.Kuek, D. J. et al. Dependence Graphs and Compiler Optimizations. Proe. 8th ACM Syrup Principles Prog~mming Languages, Jan., 1981, pp. 207-218. Google ScholarDigital Library
- 14.Lenstra, J. K. & Rinnooy Kan, A. H.G. "Complexity of Scheduling under Precedence Constraints". Operations Research 26, I (Jan-Feb 1978).Google Scholar
- 15.McGraw, J. et aL SISAL: Streams and Iteration in a Single Assignment Language, Language Reference Manual, Version 1.2. M-146, LLNL, March, 1985.Google Scholar
- 16.Padua, D. A., Kuek, D. J. & Lawrie, D. H. "High-Speed Multiprocessors and Compilation Techniques". IEEE Trans. Computers C-29, 9 (1980).Google Scholar
- 17.Pfaltz, J. L. Computer Data Structures. McGraw-Hill, Inc., 1977. Google ScholarDigital Library
- 18.Seitz, C. L. "The Cosmic Cube". CACM 28, 1 (Jan. 1985). Google ScholarDigital Library
- 19.Using the Sequent Balance 8000. Argonne National Laboratory, Mathematics and Computer Science Division, ANL/MCS-TM-66, 1986.Google Scholar
- 20.Sites, R. et aL Machine-independent Pascal Optimizer Project: Final Report. UCSD/CS-79/038, University of California at San Diego, Nov., 1979.Google Scholar
- 21.Skedzielewski, S. & Glauert, J. IF1 -- An Intermediate Form for Applicative Languages, Version 1.0. M-170, I.LNL, July, 1985.Google Scholar
Index Terms
- Compile-time partitioning and scheduling of parallel programs
Recommendations
Compile-time partitioning and scheduling of parallel programs
Partitioning and scheduling techniques are necessary to implement parallel languages on multiprocessors. Multiprocessor performance is maximized when parallelism between tasks is optimally traded off with communication and synchronization overhead. We ...
Comments