Efficient approximation algorithms for scheduling malleable tasks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient approximation algorithms for scheduling malleable tasks

Full text

Pdf (1.26 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures table of contents

Saint Malo, France

Pages: 23 - 32

Year of Publication: 1999

ISBN:1-58113-124-0

Authors

Gregory Mounie	IMAG, Domaine Universitaire BP 53, 38041 Grenoble cedex, France
Christophe Rapine	IMAG, Domaine Universitaire BP 53, 38041 Grenoble cedex, France
Dennis Trystram	IMAG, Domaine Universitaire BP 53, 38041 Grenoble cedex, France

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 36, Citation Count: 14

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/305619.305622 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	B.S. Baker, D.J. Brown, and H.P. Katseff. A 5/4 algorithm for two dimensional packing. Journal of Algorithms, 2:348-368, 1981.
	2	R. Baker, E.G. Coffman, and R.L. Rivest. Orthogonal packings in two dimensions. SIAM Journal on Computing, 9(4):846--855, 1980.
	3	Eric Blayo , Laurent Debreu , Gregory Mounie , Denis Trystram, Dynamic Load Balancing for Ocean Circulation Model with Adaptive Meshing, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.303-312, August 31-September 03, 1999
	4	R. Brent. The Parallel Evaluation of Arithmetic Expressions in Logarithmic Time, pages 83-102. Academic Press, New York, 1973.
	5	E.G. Coffrnan, M.R. Garey, D.S. Johnson, and R.E. Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SlAM Journal on Computing, 9(4):808- 826, 1980.
	6	M.R. Garey and D.S. Johnson. Complexity results for multiprocessor scheduling under resource constraints. SlAM Journal on Computing, 4, 1975.
	7	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
	8	R.L Graham. Bounds on multiprocessing timing anomalies. SlAM Journal on Applied Mathematics, 17(2):416--429, March 1969.
	9	Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
	10	Klaus Jansen , Lorant Porkolab, Linear-time approximation schemes for scheduling malleable parallel tasks, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.490-498, January 17-19, 1999, Baltimore, Maryland, United States
	11	D.S. Jonhson, A. Demers, J.D. tJllman, M.R. Garey, and R.L. Graham. Worst-case performance bounds for simple onedimensional packing algorithms. SIAM Journal on Computing, 3(4):299-329, December 1974.
	12	Walter T. Ludwig, Algorithms for scheduling malleable and nonmalleable parallel tasks, University of Wisconsin at Madison, Madison, WI, 1996
	13	C.H. Papadimitriou. Computational Complexity. Addison- Wesley, 1994.
	14	G. N. Srinivasa Prasanna , Bruce R. Musicus, Generalised multiprocessor scheduling using optimal control, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.216-228, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113399]
	15	G.N.S. Prasanna and B.R. Musicus. The optimal control approach to generalized multiprocessor scheduling. Algorithmica, 15(1):17--49, 1996.
	16	V. J. Rayward-Smith, UET scheduling with unit interprocessor communication delays, Discrete Applied Mathematics, v.18 n.1, p.55-71, Nov. 1987 [doi>10.1016/0166-218X(87)90042-4]
	17	A. Steinberg, A Strip-Packing Algorithm with Absolute Performance Bound 2, SIAM Journal on Computing, v.26 n.2, p.401-409, April 1997 [doi>10.1137/S0097539793255801]
	18	John Turek , Joel L. Wolf , Philip S. Yu, Approximate algorithms scheduling parallelizable tasks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.323-332, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141909]

CITED BY 14

	Pierre-François Dutot , Denis Trystram, Scheduling on hierarchical clusters using malleable tasks, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.199-208, July 2001, Crete Island, Greece
	Pierre-François Dutot , Lionel Eyraud , Grégory Mounié , Denis Trystram, Bi-criteria algorithm for scheduling jobs on cluster platforms, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Klaus Jansen , Hu Zhang, Scheduling malleable tasks with precedence constraints, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Klaus Jansen , Hu Zhang, An approximation algorithm for scheduling malleable tasks under general precedence constraints, ACM Transactions on Algorithms (TALG), v.2 n.3, p.416-434, July 2006
	T. Decker , T. Lücking , B. Monien, A 5/4-approximation algorithm for scheduling identical malleable tasks, Theoretical Computer Science, v.361 n.2, p.226-240, 1 September 2006
	John Augustine , Sudarshan Banerjee , Sandy Irani, Strip packing with precedence constraints and strip packing with release times, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Daniel C. Vanderster , Nikitas J. Dimopoulos, Sensitivity analysis of knapsack-based task scheduling on the grid, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
	Lionel Eyraud, A Pragmatic Analysis Of Scheduling Environments On New Computing Platforms, International Journal of High Performance Computing Applications, v.20 n.4, p.507-516, November 2006
	Wolf Zimmermann , Welf Lowe, Foundations for the integration of scheduling techniques into compilers for parallel languages, International Journal of Computational Science and Engineering, v.1 n.2-4, p.99-109, May 2005
	R. Parra-Hernandez , D. Vanderster , N. J. Dimopoulos, Resource Management and Knapsack Formulations on the Grid, Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing, p.94-101, November 08-08, 2004
	Amos Israeli , Dror Rawitz , Oran Sharon, On the complexity of sequential rectangle placement in IEEE 802.16/WiMAX systems, Information and Computation, v.206 n.11, p.1334-1345, November, 2008
	Daniel C. Vanderster , Nikitas J. Dimopoulos , Rafael Parra-Hernandez , Randall J. Sobie, Resource allocation on computational grids using a utility model and the knapsack problem, Future Generation Computer Systems, v.25 n.1, p.35-50, January, 2009
	Daniel Vanderster , Nikitas Dimopoulos , Randall Sobie, Metascheduling Multiple Resource Types using the MMKP, Proceedings of the 7th IEEE/ACM International Conference on Grid Computing, p.231-237, September 28-29, 2006
	John Augustine , Sudarshan Banerjee , Sandy Irani, Strip packing with precedence constraints and strip packing with release times, Theoretical Computer Science, v.410 n.38-40, p.3792-3803, September, 2009