Factoring: a method for scheduling parallel loops

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Factoring: a method for scheduling parallel loops

Full text

Pdf (4.90 MB)

Source

Communications of the ACM archive
Volume 35 , Issue 8 (August 1992) table of contents

Pages: 90 - 101

Year of Publication: 1992

ISSN:0001-0782

Authors

Susan Flynn Hummel	Department of Computer Science, Polytechnic University, Six Metrotech Center, Brooklyn, NY
Edith Schonberg	IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, New York
Lawrence E. Flynn	Mathematics Department, Hampton University, Hampton, VA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 55, Citation Count: 46

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/135226.135232 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	Frances Allen , Michael Burke , Philippe Charles , Ron Cytron , Jeanne Ferreant, An overview for the PTRAN analysis system for multiprocessing, Journal of Parallel and Distributed Computing, v.5 n.5, p.617-640, October 1988 [doi>10.1016/0743-7315(88)90015-9]
	2	BBN Systems and Technologies Corporation, inside the Buttofly GP1000. 10 Moulton St., Cambridge, Mass. 02238, June 1985.
	3	Bryant, R. The RP3 parallel computing envirm.nnent, in Proceedings of the USENIX Supercomputing Workshop, I988, 69-85.
	4	Flvnn. L,E. and Hummel, S.F. Scheduling variable-length parallel subtasks. IBM Research Report RC 15492, Feb. 1990.
	5	Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
	6	Gumbel, E.J. The maxima of the mean of she largest value of the range. Ann. Math. Statist. 25 (1954), 76-84.
	7	Hart!ey, H.O. and Dahd, H.A. Uni-. versal bounds fbr mean range and extrema observations. Ann. Math. Smti, st. 25' (1954), 85-99.
	8	S. F. Hummel , E. Schonberg, Low-overhead scheduling of nested parallelism, IBM Journal of Research and Development, v.35 n.5-6, p.743-765, Sept./Nov. 1991
	9	D. N. Kimelman , T. A. Ngo, The RP3 program visualization environment, IBM Journal of Research and Development, v.35 n.5-6, p.635-651, Sept./Nov. 1991
	10	Clyde P. Kruskal , Alan Weiss, Allocating independent subtasks on parallel processors, IEEE Transactions on Software Engineering, v.11 n.10, p.1001-1016, Oct. 1985 [doi>10.1109/TSE.1985.231547]
	11	Pfister, G.F. et al. The IBM research, parallel processor prototype (RP3): lntroduction and architecture, in Proceedings of the International Conference on Parallel Procesing, 19t45, pp. 764-771.
	12	Polychronopoulos, C. Loop coalescing: A compiler transfi)rmation for parallel machine.s, In Proceedings of the International confernce on Parallel Processing, 1987, pp. 235-242.
	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	Tzen, T.H. and Ni, L.M. Dynamic loop scheduling for shared-memory multiprocessors. In Proceeding, lnternational Confere.nr.e on Parallel Processing, Vo.I. II, (1991), pp. 247-250.
	15	V. Sarkar, Determining average program execution times and their variance, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.298-312, June 19-23, 1989, Portland, Oregon, United States

CITED BY 46

	Girija J. Narlikar , Guy E. Blelloch, Space-efficient implementation of nested parallelism, ACM SIGPLAN Notices, v.32 n.7, p.25-36, July 1997
	Girija J. Narlikar , Guy E. Blelloch, Space-efficient scheduling of nested parallelism, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.1, p.138-173, Jan. 1999
	J. Liu , V. A. Saletore, Self-scheduling on distributed-memory machines, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.814-823, December 1993, Portland, Oregon, United States
	Srikat Subramaniam , Derek L. Eager, Affinity scheduling of unbalanced workloads, Proceedings of the 1994 conference on Supercomputing, p.214-226, December 1994, Washington, D.C., United States
	Robert Bernecky, The role of APL and J in high-performance computation, ACM SIGAPL APL Quote Quad, v.24 n.1, p.17-32, Aug. 1993
	Hannah Bast, Dynamic scheduling with incomplete information, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.182-191, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Susan Flynn Hummel , Jeanette Schmidt , R. N. Uma , Joel Wein, Load-sharing in heterogeneous systems via weighted factoring, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.318-328, June 24-26, 1996, Padua, Italy
	Salvatore Orlando , Raffaele Perego, A template for non-uniform parallel loops based on dynamic scheduling and prefetching techniques, Proceedings of the 10th international conference on Supercomputing, p.117-124, May 25-28, 1996, Philadelphia, Pennsylvania, United States
	Perry Fizzano , David Karger , Clifford Stein , Joel Wein, Job scheduling in rings, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.210-219, June 27-29, 1994, Cape May, New Jersey, United States
	Ioana Banicescu , Susan Flynn Hummel, Balancing processor loads and exploiting data locality in N-body simulations, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.43-es, December 04-08, 1995, San Diego, California, United States
	E. P. Markatos , T. J. LeBlanc, Using Processor Affinity in Loop Scheduling on Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.4, p.379-400, April 1994
	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
	Srikant Subramaniam , Derek L. Eager, Affinity scheduling of unbalanced workloads, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
	Cécile Germain-Renaud , Nathalie Playez, Result checking in global computing systems, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
	R. L. Cariño , I. Banicescu , R. K. Vadapalli , C. A. Weatherford , J. Zhu, Message-passing parallel adaptive quantum trajectory method, High performance scientific and engineering computing: hardware/software support, Kluwer Academic Publishers, Norwell, MA, 2004
	Rizos Sakellariou , John R. Gurd, Compile-time minimisation of load imbalance in loop nests, Proceedings of the 11th international conference on Supercomputing, p.277-284, July 07-11, 1997, Vienna, Austria
	Oscar Plata , Francisco F. Rivera, Combining static and dynamic scheduling on distributed-memory multiprocessors, Proceedings of the 8th international conference on Supercomputing, p.186-195, July 11-15, 1994, Manchester, England
	Susan Flynn Hummel , Doug Kimelman , Edith Schonberg , Marsha Tennenhouse , Dror Zernik, Using Program Visualization for Tuning Parallel-Loop Scheduling, IEEE Parallel & Distributed Technology: Systems & Technology, v.5 n.1, p.26-40, January 1997
	Susan Flynn Hummel , Doug Kimelman , Edith Schonberg , Marsha Tennenhouse , Dror Zernik, Using Program Visualization for Tuning Parallel-Loop Scheduling, IEEE Parallel & Distributed Technology: Systems & Technology, v.5 n.1, p.26-40, January 1997
	Olivier Beaumont , Arnaud Legrand , Yves Robert, Scheduling divisible workloads on heterogeneous platforms, Parallel Computing, v.29 n.9, p.1121-1152, September 2003
	Naraig Manjikian , Tarek S. Abdelrahman, Exploiting Wavefront Parallelism on Large-Scale Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.12 n.3, p.259-271, March 2001
	Babak Hamidzadeh , Lau Ying Kit , David J. Lilja, Dynamic Task Scheduling Using Online Optimization, IEEE Transactions on Parallel and Distributed Systems, v.11 n.11, p.1151-1163, November 2000
	Shashi Shekhar , Sivakumar Ravada , Vipin Kumar , Douglas Chubb , Greg Turner, Declustering and Load-Balancing Methods for Parallelizing Geographic Information Systems, IEEE Transactions on Knowledge and Data Engineering, v.10 n.4, p.632-655, July 1998
	Mary W. Hall , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Monica S. Lam, Interprocedural parallelization analysis in SUIF, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.4, p.662-731, July 2005
	Ioana Banicescu , Ricolindo L. Cariño , Jaderick P. Pabico , Mahadevan Balasubramaniam, Design and implementation of a novel dynamic load balancing library for cluster computing, Parallel Computing, v.31 n.7, p.736-756, July 2005
	Tatiana Tabirca , Len Freeman , Sabin Tabirca , Laurence Tianruo Yang, Feedback guided dynamic loop scheduling: convergence of the continuous case, The Journal of Supercomputing, v.30 n.2, p.151-178, November 2004
	Yang Yang , Krijn van der Raadt , Henri Casanova, Multiround Algorithms for Scheduling Divisible Loads, IEEE Transactions on Parallel and Distributed Systems, v.16 n.11, p.1092-1102, November 2005
	Yong Yan , Canming Jin , Xiaodong Zhang, Adaptively Scheduling Parallel Loops in Distributed Shared-Memory Systems, IEEE Transactions on Parallel and Distributed Systems, v.8 n.1, p.70-81, January 1997
	Chao-Tung Yang , Kuan-Wei Cheng , Kuan-Ching Li, An Enhanced Parallel Loop Self-Scheduling Scheme for Cluster Environments, The Journal of Supercomputing, v.34 n.3, p.315-335, December 2005
	Marcelo S. Sousa , Alba Cristina M. A. Melo, PackageBLAST: an adaptive multi-policy grid service for biological sequence comparison, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Lutz Prechelt, Exploiting Domain-Specific Properties: Compiling Parallel Dynamic Neural Network Algorithms into Efficient Code, IEEE Transactions on Parallel and Distributed Systems, v.10 n.11, p.1105-1117, November 1999
	Chao-Tung Yang , Wen-Chung Shih , Shian-Shyong Tseng, Dynamic partitioning of loop iterations on heterogeneous PC clusters, The Journal of Supercomputing, v.44 n.1, p.1-23, April 2008
	Ricolindo L. Cariño , Ioana Banicescu, Dynamic load balancing with adaptive factoring methods in scientific applications, The Journal of Supercomputing, v.44 n.1, p.41-63, April 2008
	Sabin Tabirca , Tatiana Tabirca , Lawrence Tianruo Yang , Andrea Unger , Thomas Steube, A practical application of FGDLS to birds flock trajectory, Proceedings of the 9th WSEAS International Conference on Computers, p.1-6, July 14-16, 2005, Athens, Greece
	E. Cesar , A. Moreno , J. Sorribes , E. Luque, Modeling master/worker applications for automatic performance tuning, Parallel Computing, v.32 n.7, p.568-589, September 2006
	Mahmut Kandemir , Taylan Yemliha , Seung Woo Son , Ozcan Ozturk, Memory bank aware dynamic loop scheduling, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Chao-Tung Yang , Kuan-Wei Cheng , Wen-Chung Shih, On development of an efficient parallel loop self-scheduling for grid computing environments, Parallel Computing, v.33 n.7-8, p.467-487, August, 2007
	Ioana Banicescu , Ricolindo L. Cariòo , Jane L. Harvill , John Patrick Lestrade, Vector nonlinear time-series analysis of gamma-ray burst datasets on heterogeneous clusters, Scientific Programming, v.13 n.2, p.67-77, April 2005
	Wen-Chung Shih , Chao-Tung Yang , Shian-Shyong Tseng, A performance-based parallel loop scheduling on grid environments, The Journal of Supercomputing, v.41 n.3, p.247-267, September 2007
	Florina M. Ciorba , Ioannis Riakiotakis , Theodore Andronikos , George Papakonstantinou , Anthony T. Chronopoulos, Enhancing self-scheduling algorithms via synchronization and weighting, Journal of Parallel and Distributed Computing, v.68 n.2, p.246-264, February, 2008
	Ricolindo L. Cariño , Ioana Banicescu, A Load Balancing Tool for Distributed Parallel Loops, Cluster Computing, v.8 n.4, p.313-321, October 2005
	Clemens Grelck, Shared memory multiprocessor support for functional array processing in SAC, Journal of Functional Programming, v.15 n.3, p.353-401, May 2005
	Ioana Banicescu , Ricolindo L. Carino , Jaderick P. Pabico , Mahadevan Balasubramaniam, Performance evaluation of a dynamic load-balancing library for cluster computing, International Journal of Computational Science and Engineering, v.1 n.2-4, p.118-133, May 2005
	Diego R. Llanos , David Orden , Belen Palop, New Scheduling Strategies for Randomized Incremental Algorithms in the Context of Speculative Parallelization, IEEE Transactions on Computers, v.56 n.6, p.839-852, June 2007
	A. Moreno , E. Cesar , J. Sorribes , T. Margalef , E. Luque, Task distribution using factoring load balancing in Master--Worker applications, Information Processing Letters, v.109 n.16, p.902-906, July, 2009
	Javier Díaz , Sebastián Reyes , Alfonso Niño , Camelia Muñoz-Caro, Derivation of self-scheduling algorithms for heterogeneous distributed computer systems: Application to internet-based grids of computers, Future Generation Computer Systems, v.25 n.6, p.617-626, June, 2009