Resource scheduling for parallel database and scientific applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Resource scheduling for parallel database and scientific applications

Full text

Pdf (984 KB)

Source

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

Padua, Italy

Pages: 329 - 335

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

Soumen Chakrabarti	Computer Science Division, U. C. Berkeley, CA
S. Muthukrishnan	University of Warwick, UK

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): 1, Downloads (12 Months): 26, Citation Count: 12

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/237502.237577 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	N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
	2	K. Brown et al. Resource allocation and scheduling for mixed database workloads. Technical Report 1095, Umversity of Wisconsin at Madison, July 1992.
	3	Soumen Chakrabarti , Cynthia A. Phillips , Andreas S. Schulz , David B. Shmoys , Clifford Stein , Joel Wein, Improved Scheduling Algorithms for Minsum Criteria, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.646-657, July 08-12, 1996
	4	C. Chekuri, R. Motwani, and B. Natarajan. Scheduling to minimize weighted completion time. Manuscript, 1995.
	5	K. Ekanadham, J. E. Moreira, and V. K. Naik. Application oriented resource management on large scale parallel systems. Technical Report RC 20151, IBM Research, Yorktown Heights, Aug. 1995.
	6	Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, April 1995
	7	Anja Feldmann , Ming-Yang Kao , Jiří Sgall , Shang-Hua Teng, Optimal online scheduling of parallel jobs with dependencies, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.642-651, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167254]
	8	M. R,. Garey and R. L. Graham. Bounds for multiprocessor scheduling with resource constraints. SIAM Journal on Computing, 4(2):187-200, June 1975.
	9	Minos N. Garofalakis , Yannis E. Ioannidis, Multi-dimensional resource scheduling for parallel queries, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.365-376, June 04-06, 1996, Montreal, Quebec, Canada
	10	R. L. Graham. Bounds on multiprocessor timing anomalies. SIAM Journal of Apphed Mathematzcs, 17(2):416-429, March 1969.
	11	Susan L. Graham , Steven Lucco , Oliver Sharp, Orchestrating interactions among parallel computations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.100-111, June 21-25, 1993, Albuquerque, New Mexico, United States
	12	J. Gray. A survey of parallel database techniques and systems, September 1995. Tutorial at VLDB.
	13	Leslie A. Hall , David B. Shmoys , Joel Wein, Scheduling to minimize average completion time: off-line and on-line algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.142-151, January 28-30, 1996, Atlanta, Georgia, United States
	14	Wei Hong , Michael Stonebraker, Optimization of parallel query execution plans in XPRS, Distributed and Parallel Databases, v.1 n.1, p.9-32, Jan. 1993 [doi>10.1007/BF01277518]
	15	D. S. Johnson and K. A. Niemi. On knapsacks, partitions, and a new dynamic programming technique for trees. Mathematics of Operations Research, 8(1):1-14, February 1983.
	16	Hans Kellerer , Thomas Tautenhahn , Gerhard J. Woeginger, Approximability and nonapproximability results for minimizing total flow time on a single machine, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.418-426, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237989]
	17	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
	18	Manish Mehta , David J. DeWitt, Dynamic Memory Allocation for Multiple-Query Workloads, Proceedings of the 19th International Conference on Very Large Data Bases, p.354-367, August 24-27, 1993
	19	J. E. Moreira, V. K. Naik, and R. B. Konuru. A system for dynamic resource allocation and data distribution. Technical Report RC 20257, IBM Research, Yorktown Heights, Oct. 1995.
	20	Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1]
	21	P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
	22	David B. Shmoys , Clifford Stein , Joel Wein, Improved Approximation Algorithms for Shop Scheduling Problems, SIAM Journal on Computing, v.23 n.3, p.617-632, June 1994 [doi>10.1137/S009753979222676X]
	23	David B. Shmoys , Joel Wein , David P. Williamson, Scheduling parallel machines on-line, Proceedings of the 32nd annual symposium on Foundations of computer science, p.131-140, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185361]
	24	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 [doi>10.1145/181014.181331]
	25	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
	26	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]
	27	J. Wolf, J. Turek, M. Chen, and P. Yu. The optimal scheduling of multiple queries in a parallel database machine. Technical Report RC 18595 (81362) 12/17/92, IBM, 1992.

CITED BY 12

	Sachin More , S. Muthukrishnan , Elizabeth Shriver, Efficiently sequencing tape-resident jobs, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.33-43, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Arvind Arasu , Junghoo Cho , Hector Garcia-Molina , Andreas Paepcke , Sriram Raghavan, Searching the Web, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.2-43, Aug. 2001
	Sergey Melnik , Sriram Raghavan , Beverly Yang , Hector Garcia-Molina, Building a distributed full-text index for the Web, Proceedings of the 10th international conference on World Wide Web, p.396-406, May 01-05, 2001, Hong Kong, Hong Kong
	Sergey Melink , Sriram Raghavan , Beverly Yang , Hector Garcia-Molina, Building a distributed full-text index for the web, ACM Transactions on Information Systems (TOIS), v.19 n.3, p.217-241, July 2001
	Stefan Bischof , Ernst W. Mayr, On-line scheduling of parallel jobs with runtime restrictions, Theoretical Computer Science, v.268 n.1, p.67-90, 10/06/2001
	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
	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
	Ameet S. Talwadker, Survey of performance issues in parallel database systems, Journal of Computing Sciences in Colleges, v.18 n.6, p.5-9, June 2003
	Junghoo Cho , Hector Garcia-Molina , Taher Haveliwala , Wang Lam , Andreas Paepcke , Sriram Raghavan , Gary Wesley, Stanford WebBase components and applications, ACM Transactions on Internet Technology (TOIT), v.6 n.2, p.153-186, May 2006
	Nicole Megow , Marc Uetz , Tjark Vredeveld, Models and Algorithms for Stochastic Online Scheduling, Mathematics of Operations Research, v.31 n.3, p.513-525, August 2006
	Marek Chrobak , Claire Kenyon-Mathieu, SIGACT news online algorithms column 10: competitiveness via doubling, ACM SIGACT News, v.37 n.4, December 2006
	Minos N. Garofalakis , Yannis E. Ioannidis, Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.296-305, August 25-29, 1997