Approximate algorithms scheduling parallelizable tasks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate algorithms scheduling parallelizable tasks

Full text

Pdf (1.17 MB)

Source

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

San Diego, California, United States

Pages: 323 - 332

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

John Turek
Joel L. Wolf
Philip S. Yu

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): 4, Downloads (12 Months): 52, Citation Count: 27

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/140901.141909 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.

	BB90	Belkhale, K. and P. Banerjee. Approximate Scheduling Algorithms for the Partitionable Independent Task Scheduling Problem. In Proceedings of the 1990 International Conference o/Parallel Processing, volume I, pages 72-75, August 1990.
	BCR80	Baker, B., E. Coffman, and R. Rivest. Orthogohal Packings in Two Dimensions. SIAM Journal on Computzng, 9(4)846-855, November 1980.
	BDW86	J Blazewicz , M Drabowski , J Weglarz, Scheduling multiprocessor tasks to minimize schedule length, IEEE Transactions on Computers, v.35 n.5, p.389-393, May 1986 [doi>10.1109/TC.1986.1676781]
	BS83	Baker, B. and J. Schwarz. Shelf Algorithms for Two-Dimensional Packing Problems. SIAM Journal on Computing, 12(3):508-525, August 1983.
	CGJT80	Coffman, E., M. Garey, D. Johnson, and R. Tarjan. Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms. SIAM Journal on Computing, 9(4):808-826, November 1980.
	Cof76	Coffman, E., Editor. Computer and Job-Shop Scheduling Theory. Wiley, New York, 1976.
	CYW92	Ming-Syan Chen , Philip S. Yu , Kun-Lung Wu, Scheduling and Processor Allocation for Parallel Execution of Multi-Join Queries, Proceedings of the Eighth International Conference on Data Engineering, p.58-67, February 03-07, 1992
	DL89	J. Du , J. Y.-T. Leung, Complexity of scheduling parallel task systems, SIAM Journal on Discrete Mathematics, v.2 n.4, p.473-487, Nov. 1989 [doi>10.1137/0402042]
	Fox66	Fox, B. Discrete Optimization via Marginal Analysis. Management Sczence, 13:210-216, November 1966.
	GG75	Garey, M. and R. Graham. Bounds for Multiprocessor Scheduling with Resource Constraints. SIAM Journal on Computing, 4(2):187-200, June 1975.
	IK88	Toshihide Ibaraki , Naoki Katoh, Resource allocation problems: algorithmic approaches, MIT Press, Cambridge, MA, 1988
	IRV89	B. R. Iyer , G. R. Ricard , P. J. Varman, Percentile finding algorithm for multiple sorted runs, Proceedings of the 15th international conference on Very large data bases, p.135-144, July 1989, Amsterdam, The Netherlands
	Joh73	Johnson, D. Near-Optimal Bin-Packing Algorithms. Technical Report MAC TR-109, MIT, June 1973.
	KM90	Krishnamurti, R. and E. Ms. An Approximation Algorithm for Scheduling Tasks on Varying Partition Sizes in Partitionable Multiprocessor Systems. Technical Report RC 15900, IBM Research Division, July 1990.
	Sle80	Sleator, D. A 2.5 Times Optimal Algorithm for Packing in Two Dimensions. Information Processing Letters, 10(1):37-40, February 1980.
	SWT89	Harold S. Stone , John Turek , Joel L. Wolf, Optimal Partitioning of Cache Memory, IEEE Transactions on Computers, v.41 n.9, p.1054-1068, September 1992 [doi>10.1109/12.165388]
	TTW88	A. N. Tantawi , G. Towsley , J. Wolf, Optimal allocation of multiple class resources in computer systems, Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.253-260, May 24-27, 1988, Santa Fe, New Mexico, United States
	Tuk77	Tukey, J. E~ploratory Data Analys,s. Addison- Wesley, Reading, Massachusetts, 1977.
	TWPY92	John Turek , Joel L. Wolf , Krishna R. Pattipati , Philip S. Yu, Scheduling parallelizable tasks: putting it all on the shelf, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.225-236, June 01-05, 1992, Newport, Rhode Island, United States
	WC92	Qingzhou Wang , Kam Hoi Cheng, A heuristic of scheduling parallel tasks and its analysis, SIAM Journal on Computing, v.21 n.2, p.281-294, April 1992 [doi>10.1137/0221021]
	WDY90	Joel L. Wolf , Daniel M. Dias , Philip S. Yu, An effective algorithm for parallelizing sort merge joins in the presence of data skew, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.103-115, July 02-04, 1990, Dublin, Ireland [doi>10.1145/319057.319072]
	WIPT91	Joel L. Wolf , Balakrishna R. Iyer , Krishna R. Pattipati , John Turek, Optimal Buffer Partitioning for the Nested Block Join Algorithm, Proceedings of the Seventh International Conference on Data Engineering, p.510-519, April 08-12, 1991

CITED BY 27

	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
	Minos N. Garofalakis , Yannis E. Ioannidis, Multi-dimensional resource scheduling for parallel queries, ACM SIGMOD Record, v.25 n.2, p.365-376, June 1996
	John Turek , Uwe Schwiegelshohn , Joel L. Wolf , Philip S. Yu, Scheduling parallel tasks to minimize average response time, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.112-121, January 23-25, 1994, Arlington, Virginia, United States
	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
	Walter Ludwig , Prasoon Tiwari, Scheduling malleable and nonmalleable parallel tasks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.167-176, January 23-25, 1994, Arlington, Virginia, United States
	L. Becchetti , S. Diggavi , S. Leonardi , A. Marchetti-Spaccamela , S. Muthukrishnan , T. Nandagopal , A. Vitaletti, Parallel scheduling problems in next generation wireless networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	John Turek , Walter Ludwig , Joel L. Wolf , Lisa Fleischer , Prasoon Tiwari , Jason Glasgow , Uwe Schwiegelshohn , Philip S. Yu, Scheduling parallelizable tasks to minimize average response time, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.200-209, June 27-29, 1994, Cape May, New Jersey, United States
	Soumen Chakrabarti , S. Muthukrishnan, Resource scheduling for parallel database and scientific applications, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.329-335, June 24-26, 1996, Padua, Italy
	Gregory Mounie , Christophe Rapine , Dennis Trystram, Efficient approximation algorithms for scheduling malleable tasks, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.23-32, June 27-30, 1999, Saint Malo, France
	Joel L. Wolf , John Turek , Ming-Syan Chen , Philip S. Yu, A Hierarchical Approach to Parallel Multiquery Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.6 n.6, p.578-590, June 1995
	Joel L. Wolf , John Turek , Ming-Syan Chen , Philip S. Yu, Scheduling multiple queries on a parallel machine, ACM SIGMETRICS Performance Evaluation Review, v.22 n.1, p.45-55, May 1994
	Sumit Ganguly , Akshay Goel , Avi Silberschatz, Efficient and accurate cost models for parallel query optimization (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.172-181, June 04-06, 1996, Montreal, Quebec, Canada
	Soumen Chakrabarti , James Demmel , Katherine Yelick, Modeling the benefits of mixed data and task parallelism, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.74-83, June 24-26, 1995, Santa Barbara, California, United States
	Oh-Heum Kwon , Kyung-Yong Chwa, Approximation algorithms for general parallel task scheduling, Information Processing Letters, v.81 n.3, p.143-150, 14 February 2002
	Klaus Jansen , Lorant Porkolab, Polynomial time approximation schemes for general multiprocessor job shop scheduling, Journal of Algorithms, v.45 n.2, p.167-191, November 2002
	Joel L. Wolf , Philip S. Yu , John Turek , Daniel M. Dias, A Parallel Hash Join Algorithm for Managing Data Skew, IEEE Transactions on Parallel and Distributed Systems, v.4 n.12, p.1355-1371, December 1993
	Thomas Rauber , Gudula Rünger, A Transformation Approach to Derive Efficient Parallel Implementations, IEEE Transactions on Software Engineering, v.26 n.4, p.315-339, April 2000
	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
	Berit Johannes, Scheduling parallel jobs to minimize the makespan, Journal of Scheduling, v.9 n.5, p.433-452, October 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
	Savina Bansal , Padam Kumar , Kuldip Singh, An improved two-step algorithm for task and data parallel scheduling in distributed memory machines, Parallel Computing, v.32 n.10, p.759-774, November, 2006
	Deshi Ye , Guochuan Zhang, On-line scheduling mesh jobs with dependencies, Theoretical Computer Science, v.372 n.1, p.94-102, March, 2007
	Emmanuel Jeannot , Frédéric Wagner, Scheduling Messages For Data Redistribution: An Experimental Study, International Journal of High Performance Computing Applications, v.20 n.4, p.443-454, November 2006
	Edmund K. Burke , Moshe Dror , James B. Orlin, Scheduling malleable tasks with interdependent processing rates: Comments and observations, Discrete Applied Mathematics, v.156 n.5, p.620-626, March, 2008
	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
	Frederic Suter, Scheduling ?-Critical Tasks in mixed-parallel applications on a national grid, Proceedings of the 8th IEEE/ACM International Conference on Grid Computing, p.2-9, September 19-21, 2007