Compile-time minimisation of load imbalance in loop nests

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Compile-time minimisation of load imbalance in loop nests

Full text

Pdf (997 KB)

Source

International Conference on Supercomputing archive
Proceedings of the 11th international conference on Supercomputing table of contents

Vienna, Austria

Pages: 277 - 284

Year of Publication: 1997

ISBN:0-89791-902-5

Authors

Rizos Sakellariou	Department of Computer Science, University of Manchester, Oxford Road, Manchester M13 9PL, U.K.
John R. Gurd	Department of Computer Science, University of Manchester, Oxford Road, Manchester M13 9PL, U.K.

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 16, Citation Count: 4

Additional Information:

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/263580.263811 What is a DOI?

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	A. I. Barvinok. Computing the Volume, Counting Integral Points, and Exponential Sums. Discrete & Computational Geometry, 10-2, 1993, pp. 123-141.
	2	Aart J. C. Bik , Harry A. G. Wijshoff, Iteration Space Partitioning, Proceedings of the International Conference and Exhibition on High-Performance Computing and Networking, p.475-484, April 15-19, 1996
	3	F. Bodin, M. O'Boyle. A Compiler Strategy for Shared Virtual Memories. In B. K. Szymanski, B. Sinharoy (Eds.), Languages, Compilers and Run-Time Systems for Scalable Computers, Kluwer Academic Publishers, 1996, pp. 57-69.
	4	J. Mark Bull, A hierarchical classification of overheads in parallel programs, Proceedings of the First IFIP TC10 International Workshop on Software Engineering for Parallel and Distributed Systems, p.208-219, March 01, 1996
	5	Philippe Clauss, Counting solutions to linear and nonlinear constraints through Ehrhart polynomials: applications to analyze and transform scientific programs, Proceedings of the 10th international conference on Supercomputing, p.278-285, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237617]
	6	Mark E. Crovella , Thomas J. LeBlanc, Parallel performance using lost cycles analysis, Proceedings of the 1994 conference on Supercomputing, p.600-609, December 1994, Washington, D.C., United States
	7	Thomas Fahringer, Estimating and Optimizing Performance for Parallel Programs, Computer, v.28 n.11, p.47-56, November 1995 [doi>10.1109/2.471179]
	8	Susan Flynn Hummel , Edith Schonberg , Lawrence E. Flynn, Factoring: a method for scheduling parallel loops, Communications of the ACM, v.35 n.8, p.90-101, Aug. 1992 [doi>10.1145/135226.135232]
	9	Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic Analysis: A Basis for Parallelization, Optimization, and Scheduling of Programs, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.567-585, August 12-14, 1993
	10	Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic analysis for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.477-518, July 1996 [doi>10.1145/233561.233568]
	11	David J. Lilja, Exploiting the parallelism available in loops, Computer, v.27 n.2, p.13-26, February 1994 [doi>10.1109/2.261915]
	12	Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
	13	C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987 [doi>10.1109/TC.1987.5009495]
	14	William Pugh, Counting solutions to Presburger formulas: how and why, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.121-134, June 20-24, 1994, Orlando, Florida, United States
	15	R. Sakellariou. On the Quest for Perfect Load Balance in Loop-Based Parallel Computations. PhD Thesis, Department of Computer Science, University of Manchester, 1996.
	16	Rizos Sakellariou, A Compile-Time Partitioning Strategy for Non-Rectangular Loop Nests, Proceedings of the 11th International Symposium on Parallel Processing, p.633-637, April 01-05, 1997
	17	Nadia Tawbi, Estimation of Nested Loops Execution Time by Integer Arithmetic in Convex Polyhedra, Proceedings of the 8th International Symposium on Parallel Processing, p.217-221, April 01, 1994
	18	T. H. Tzen , L. M. Ni, Trapezoid Self-Scheduling: A Practical Scheduling Scheme for Parallel Compilers, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.87-98, January 1993 [doi>10.1109/71.205655]
	19	Ko-Yang Wang, Precise compile-time performance prediction for superscalar-based computers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.73-84, June 20-24, 1994, Orlando, Florida, United States
	20	Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995

CITED BY 4

	Jialin Dou , Marcelo Cintra, Compiler Estimation of Load Imbalance Overhead in Speculative Parallelization, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.203-214, September 29-October 03, 2004
	Giuseppe Di Fatta , Michael R. Berthold, Decentralized load balancing for highly irregular search problems, Microprocessors & Microsystems, v.31 n.4, p.273-281, June, 2007
	Imam Machdi , Toshiyuki Amagasa , Hiroyuki Kitagawa, XML data partitioning strategies to improve parallelism in parallel holistic twig joins, Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication, January 15-16, 2009, Suwon, Korea
	Imam Machdi , Toshiyuki Amagasa , Hiroyuki Kitagawa, GMX: an XML data partitioning scheme for holistic twig joins, Proceedings of the 10th International Conference on Information Integration and Web-based Applications & Services, November 24-26, 2008, Linz, Austria