On the complexity of list scheduling algorithms for distributed-memory systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of list scheduling algorithms for distributed-memory systems

Full text

Pdf (965 KB)

Source

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

Rhodes, Greece

Pages: 68 - 75

Year of Publication: 1999

ISBN:1-58113-164-X

Authors

Andrei Rădulescu	Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands
Arjan J. C. van Gemund	Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 26, 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/305138.305162 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	I. Ahmad and Y.-K. Kwok. A new approach to scheduling parallel programs using task duplication. In Proc. ICPP, pages 47-51, Aug. 1994.
	2	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	3	R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM J. on Applied Mathematics, 17(2):416-429, Mar. 1969.
	4	Jing-Jang Hwang , Yuan-Chieh Chow , Frank D. Anger , Chung-Yee Lee, Scheduling precedence graphs in systems with interprocessor communication times, SIAM Journal on Computing, v.18 n.2, p.244-257, April 1989 [doi>10.1137/0218016]
	5	Boontee Kruatrachue , Ted Lewis, Grain Size Determination for Parallel Processing, IEEE Software, v.5 n.1, p.23-32, January 1988 [doi>10.1109/52.1991]
	6	Benchmarking the Task Graph Scheduling Algorithms, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.531, March 30-April 03, 1998
	7	Andrei Radulescu , Arjan J. C. van Gemund , Hai-Xiang Lin, LLB: A Fast and Effective Scheduling Algorithm for Distributed-Memory Systems, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.525-530, April 12-16, 1999
	8	V. Sarkar, Partitioning and scheduling parallel programs for execution on multiprocessors, Stanford University, Stanford, CA, 1987
	9	Behrooz Shirazi , Mingfang Wang , Girish Pathak, Analysis and evaluation of heuristic methods for static task scheduling, Journal of Parallel and Distributed Computing, v.10 n.3, p.222-2232, Nov. 1990 [doi>10.1016/0743-7315(90)90014-G]
	10	M. Y. Wu , D. D. Gajski, Hypertool: A Programming Aid for Message-Passing Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.330-343, July 1990 [doi>10.1109/71.80160]
	11	T. Yang , A. Gerasoulis, DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.951-967, September 1994 [doi>10.1109/71.308533]

CITED BY 4

	Andrei Radulescu , Arjan J. C. van Gemund, Low-Cost Task Scheduling for Distributed-Memory Machines, IEEE Transactions on Parallel and Distributed Systems, v.13 n.6, p.648-658, June 2002
	Rizos Sakellariou , Henan Zhao, A low-cost rescheduling policy for efficient mapping of workflows on grid systems, Scientific Programming, v.12 n.4, p.253-262, December 2004
	Rong Deng , Changjun Jiang , Fei Yin, Ant colony optimization for precedence-constrained heterogeneous multiprocessor assignment problem, Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation, June 12-14, 2009, Shanghai, China
	T. Szepieniec , M. Bubak, Investigation of the DAG eligible jobs maximization algorithm in a grid, Proceedings of the 2008 9th IEEE/ACM International Conference on Grid Computing, p.340-345, September 29-October 01, 2008