Abstract
Automatic process partitioning is the operation of automatically rewriting an algorithm as a collection of tasks, each operating primarily on its own portion of the data, to carry out the computation in parallel. Hybrid shared memory systems provide a hierarchy of globally accessible memories. To achieve high performance on such machines one must carefully distribute the work and the data so as to keep the workload balanced while optimizing the access to nonlocal data. In this paper we consider a semi-automatic approach to process partitioning in which the compiler, guided by advice from the user, automatically transforms programs into such an interacting set of tasks. This approach is illustrated with a picture processing example written in BLAZE, which is transformed by the compiler into a task system maximizing locality of memory reference.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. T. Schwartz, Ultracomputers,ACM Transactions on Programming Languages and Systems 2(4):484–521 (1980).
Multimax Multiprocessor System, Encore Computer Corporation, Marlboro, Massachusetts.
S. Thakkar, P. Gifford, and G. Fielland, Balance: A Shared Memory Multiprocessor, InProceedings of the Second International Conference on Supercomputing, Santa Clara, California (May 1987).
G. F. Pfister, W. C. Brantley, D. A. George, S. L. Harvey, W. J. Kleinfelder, K. P. McAuliffe, E. A. Melton, V. A. Norton, and J. Weiss, The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture,In Proceedings of the 1985 International Conference on Parallel Processing ed.,D. DeGroot, pp. 764–771, Computer Society Press (August 1985).
Butterfly Parallel Processor Overview, BBN Laboratories, Inc. (June 1985).
Reference Manual for the Ada Programming Language, American National Standards Institute, Inc., ANSI/MIL-STD-1815A-1983 edition (February 1983).
H. Jordan, Structuring Parallel algorithms in an MIMD, Shared Memory Environment,Parallel Computing 3(2):93–110 (May 1986).
T. W. Pratt, Pisces: An Environment for Parallel Scientific Computation,IEEE Software 2:7–20 (1985).
P. Hudak, Parafunctional Programming,IEEE Computer 19:60–71 (1986).
J. McGraw, S. Skedzielewski, S. Allan, R. Oldenhoeft, J. Glauert, C. Kirkham, W. Noyce, and R. Thomas,SISAL: Streams and Iteration in a Single Assignment Language: Language Reference Manual, Report M-146, Lawrence Livermore National Laboratory (March 1985).
P. Mehrotra and J. Van Rosendale, The BLAZE Language: A Parallel Language for Scientific Programming,Parallel Computing 5:339–361 (1987).
F. Allen, M. Burke, P. Charles, R. Cytron, and J. Ferrante,An Overview of the PTRAN Analysis System for Multiprocessing, Research Report RC 13115 (#56866), IBM T. J. Watson Research Center, Yorktown Heights, New York (September 1987).
J. R. Allen and K. Kennedy,Automatic Translation of Fortran Programs to Vector Form, Technical Report 476-029-4, Rice University, Houston, Texas (October 1980).
D. A. Padua, D. J. Kuck, and D. H. Lawrie, High-speed Multiprocessors and Compilation Techniques,IEEE Transactions on Computers C-29(9): 763–776 (September 1980).
D. Reed, L. Adams, and M. Patrick, Stencils and Problem Partitioning: Their Influence on Performance of Multiprocessor Systems,IEEE Transactions on Computers C-367): 845–858 (July 1987).
H. J. Siegel, L. J. Siegel, F. C. Kemmerer, P. T. Mueller, Jr., H. E. Smalley, Jr., and S. D. Smith, Pasm: A Partitionable SIMD/MIMD System for Image Processing and Pattern Recognition,IEEE Transactions on Computers C-30(12):934–947 (December 1981).
M. Mace,Globally Optimal Selection of Memory Storage Patterns, PhD thesis, Duke University, Durham, North Carolina (May 1983).
R. Allen, D. Callahan, and K. Kennedy,Automatic Decomposition of Scientific Programs for Parallel Execution, Computer Science Technical Report TR86-42, Rice University, Houston, Texas (November 1986).
M. J. Wolfe,Optimizing Supercompilers for Supercomputers, PhD thesis, University of Illinois, Urbana, Illinois (October 1982).
Additional information
Research supported by an IBM Graduate Fellowship.
Research supported under NASA Contract No. 520-1398-0356.
Research supported by NASA Contract No. NAS1-18107 while the last two authors were in residence at ICASE, NASA, Langley Research Center.
Rights and permissions
About this article
Cite this article
Koelbel, C., Mehrotra, P. & Van Rosendale, J. Semi-automatic process partitioning for parallel computation. Int J Parallel Prog 16, 365–382 (1987). https://doi.org/10.1007/BF01407902
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01407902