Principles of runtime support for parallel processors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Principles of runtime support for parallel processors

Full text

Pdf (1.32 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 2nd international conference on Supercomputing table of contents

St. Malo, France

Pages: 140 - 152

Year of Publication: 1988

ISBN:0-89791-272-1

Authors

R. Mirchandaney	Yale Univ., New Haven, CT
J. H. Saltz	Yale Univ., New Haven, CT
R. M. Smith	Yale Univ., New Haven, CT
D. M. Nico	College of William and Mary, Williamsburg, VA
K. Crowley	Yale Univ., New Haven, CT

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 41, Citation Count: 32

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/55364.55378 What is a DOI?

ABSTRACT

There exists substantial data level parallelism in scientific problems. The PARTY runtime system is an attempt to obtain efficient parallel implementations for scientific computations, particularly those where the data dependencies are manifest only at runtime. This can preclude compiler based detection of certain types of parallelism. The automated system is structured as follows: An appropriate level of granularity is first selected for the computations. A directed acyclic graph representation of the program is generated on which various aggregation techniques may be employed in order to generate efficient schedules. These schedules are then mapped onto the target machine. We describe some initial results from experiments conducted on the Intel Hypercube and the Encore Multimax that indicate the usefulness of our approach.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Sudhir Ahuja , Nicholas Carriero , David Gelernter, Linda and friends, Computer, v.19 n.8, p.26-34, Aug. 1986 [doi>10.1109/MC.1986.1663305]
	2	Scott Benjamin Baden, Run-time partitioning of scientific continuum calculations running on multiprocessors, 1987
	3	M. J. Berger and S. Bokhari. A Partitioning Strategy for Non-Uniform Problems on Multiprocessors. Report 85-55, ICASE, November 1985. Shortened version appeared in Proceedings ICPP 1985.
	4	Chen. Can Data Parallel Machines be Made Easy to Program. Technical Report YALEU/DCS/RR-556, Department of Computer Science, Yale University, August 1987.
	5	G. C. Fox and S. W. Otto. Concurrent Computation and the Theory of Complex Systems. Report CALT-68-1343, Caltech, 1986.
	6	G. A. Geist and M. T. lIeath. Matrix factorization on a hypercube multiprocessor, in The Proceedings of the Hypercube Microprocessors Conf., Knoxville, TN, pages 161-180, September 1986.
	7	Paul Hudak, Para-functional programming, Computer, v.19 n.8, p.60-69, Aug. 1986 [doi>10.1109/MC.1986.1663309]
	8	I. Ipsen, Y. Sa~d, and M.tI. Schultz. Complexity of dense linear system solution on a multiprocessor ring. Lin. Algebra Appl., 77:205-239, 1986.
	9	J. F. Jordan, M. S. Benten, and N. S. Arenstori'. Force User's Manual. Department of Electrical and Computer Engineering 80309-0425, University of Colorado, October 1986.
	10	K. Kennedy. Compilation for n-processor architectures, in Proceedings of the IEEE International Conference on Computer Design: VLSI in Computers, page 15, October 1985.
	11	Ewing Lusk , James Boyle , Ralph Butler , Terrence Disz , Barnett Glickfeld , Ross Overbeek , James Patterson , Rick Stevens, Portable programs for parallel processors, Holt, Rinehart & Winston, Austin, TX, 1988
	12	D. M. Nicol and J. H. Saltz. Principles for Problem Aggregation and Assignment in Medium Scale Multiprocessors. Report 87-39, ICASE, September 1987.
	13	David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
	14	PCGPAK User's Guide. 1984.
	15	Y. Saad. Communication complexity of the gaussian elimination algorithm on multipiocessors. Lin. Algebra Appl., 77:315-340, 1986.
	16	Y. Saad and M. H. Schultz. Topological Properties of Hypercubes. Department of Computer Science YALEU/DCS/RR-389, Yale, June 1986.
	17	J. S~ltz. Automated Problem Scheduling and Reduction of Communication Delay Effects; submitted for publication. Report 87-22, ICASE, May 1987.
	18	J. H. Saltz, R. Mirchandaney, R. Smith, and D. Nicol. The Automated Crystal Runtime System: A Framework. Technical Report 588, Department of Computer Science, Yale University, Nov: 1987.
	19	M. Schultz, D. Baxter, S. Eisenstat, and J. Saltz. Building Software Packages for Large Sparse Linear Systems of Equations on Shared Memory Multiprocessors. Technical Report SCA-115, Scientific Computing Associates, 1987.

CITED BY 32

	Shamik D. Sharma , Ravi Ponnusamy , Bongki Moon , Yuan-Shin Hwang , Raja Das , Joel Saltz, Run-time and compile-time support for adaptive irregular problems, Proceedings of the 1994 conference on Supercomputing, p.97-106, December 1994, Washington, D.C., United States
	Jhy-Chun Wang , Sanjay Ranka, Scheduling of unstructured communication on the Intel iPSC/860, Proceedings of the 1994 conference on Supercomputing, p.360-369, December 1994, Washington, D.C., United States
	M. C. Rinard , D. J. Scales , M. S. Lam, Heterogeneous parallel programming in Jade, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.245-256, November 16-20, 1992, Minneapolis, Minnesota, United States
	Manuel Ujaldon , Emilio L. Zapata, Efficient resolution of sparse indirections in data-parallel compilers, Proceedings of the 9th international conference on Supercomputing, p.117-126, July 03-07, 1995, Barcelona, Spain
	D. J. Mavriplis , R. Das , R. E. Vermeland , J. Saltz, Implementation of a parallel unstructured Euler solver on shared and distributed memory architectures, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.132-141, November 16-20, 1992, Minneapolis, Minnesota, United States
	Dhruva R. Chakrabarti , Nagaraj Shenoy , Alok Choudhary , Prithviraj Banerjee, An efficient uniform run-time scheme for mixed regular-irregular applications, Proceedings of the 12th international conference on Supercomputing, p.61-68, July 1998, Melbourne, Australia
	Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiling Fortran D for MIMD distributed-memory machines, Communications of the ACM, v.35 n.8, p.66-80, Aug. 1992
	Wei Li , Keshav Pingali, Access normalization: loop restructuring for NUMA computers, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.353-375, Nov. 1993
	Andrew S. Grimshaw , Jon B. Weissman , W. Timothy Strayer, Portable run-time support for dynamic object-oriented parallel processing, ACM Transactions on Computer Systems (TOCS), v.14 n.2, p.139-170, May 1996
	Siddhartha Chatterjee , John R. Gilbert , Fred J. E. Long , Robert Schreiber , Shang-Hua Teng, Generating local addresses and communication sets for data-parallel programs, ACM SIGPLAN Notices, v.28 n.7, p.149-158, July 1993
	Karen A. Tomko , Santosh G. Abraham, Data and program restructuring of irregular applications for cache-coherent multiprocessor, Proceedings of the 8th international conference on Supercomputing, p.214-225, July 11-15, 1994, Manchester, England
	David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994
	Raja Das , Paul Havlak , Joel Saltz , Ken Kennedy, Index array flattening through program transformation, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.70-es, December 04-08, 1995, San Diego, California, United States
	Wei Li , Keshav Pingali, Access normalization: loop restructuring for NUMA compilers, ACM SIGPLAN Notices, v.27 n.9, p.285-295, Sept. 1992
	Shamik D. Sharma , Ravi Ponnusamy , Bongki Moon , Yuan Shin Hwang , Raja Das , Joel Saltz, Run-time and compile-time support for adaptive irregular problems, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
	Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiler optimizations for Fortran D on MIMD distributed-memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.86-100, November 18-22, 1991, Albuquerque, New Mexico, United States
	Steven J. Deitz , Bradford L. Chamberlain , Sung-Eun Choi , Lawrence Snyder, The design and implementation of a parallel array operator for the arbitrary remapping of data, ACM SIGPLAN Notices, v.38 n.10, October 2003
	Jhy Chun Wang , Sanjay Ranka, Scheduling of unstructured communication on the Intel iPSC/860, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
	Michelle Mills Strout , Paul D. Hovland, Metrics and models for reordering transformations, Proceedings of the 2004 workshop on Memory system performance, June 08-08, 2004, Washington, D.C.
	C. Koelbel , P. Mehrotra, Compiling Global Name-Space Parallel Loops for Distributed Execution, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.440-451, October 1991
	R. Ponnusamy , J. Saltz , A. Choudhary, Runtime compilation techniques for data partitioning and communication schedule reuse, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.361-370, December 1993, Portland, Oregon, United States
	Yuan-Shin Hwang , Raja Das , Joel H. Saltz , Milan Hodoscek , Bernard R. Brooks, Parallelizing Molecular Dynamics Programs for Distributed-Memory Machines, IEEE Computational Science & Engineering, v.2 n.2, p.18-29, June 1995
	Sanjay Ranka , Jhy-Chun Wang , Geoffrey C. Fox, Static and Run-Time Algorithms for All-to-Many Personalized Communication on Permutation Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.12, p.1266-1274, December 1994
	Raja Das , Janet Wu , Joel Saltz , Harry Berryman , Seema Hiranandani, Distributed Memory Compiler Design For Sparse Problems, IEEE Transactions on Computers, v.44 n.6, p.737-753, June 1995
	Joel H. Salz , Ravi Mirchandaney , Kay Crowley, Run-Time Parallelization and Scheduling of Loops, IEEE Transactions on Computers, v.40 n.5, p.603-612, May 1991
	Ravi Ponnusamy , Joel Saltz , Alok Choudhary , Yuan-Shin Hwang , Geoffrey Fox, Runtime Support and Compilation Methods for User-Specified Irregular Data Distributions, IEEE Transactions on Parallel and Distributed Systems, v.6 n.8, p.815-831, August 1995
	Michelle Mills Strout , Larry Carter , Jeanne Ferrante , Barbara Kreaseck, Sparse Tiling for Stationary Iterative Methods, International Journal of High Performance Computing Applications, v.18 n.1, p.95-113, February 2004
	Dhruva R. Chakrabarti , Prithviraj Banerjee, Static Single Assignment Form for Message-Passing Programs, International Journal of Parallel Programming, v.29 n.2, p.139-184, April 2001
	Manuel Ujaldón , Shamik D. Sharma , Emilio L. Zapata , Joel Saltz, Experimental evaluation of efficient sparse matrix distributions, Proceedings of the 10th international conference on Supercomputing, p.78-85, May 25-28, 1996, Philadelphia, Pennsylvania, United States
	Wei Li , Keshav Pingali, Loop transformations for NUMA machines, ACM SIGPLAN Notices, v.28 n.1, p.9-12, Jan. 1993
	D. Baxter , R. Mirchandaney , J. H. Saltz, Run-time parallelization and scheduling of loops, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.303-312, June 18-21, 1989, Santa Fe, New Mexico, United States
	Seung-Jai Min , Rudolf Eigenmann, Optimizing irregular shared-memory applications for clusters, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece