On multiprocessor system scheduling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On multiprocessor system scheduling

Full text

Pdf (823 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: 82 - 88

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

Xiaotie Deng	Department of Computer Science, York University, North York, Ontario, Canada M3J 1P3
Patrick Dymond	Department of Computer Science, York University, North York, Ontario, Canada M3J 1P3

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): 38, Citation Count: 6

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.237510 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	David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
	2	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215403]
	3	Su-Hui Chiang , Rajesh K. Mansharamani , Mary K. Vernon, Use of application characteristics and limited preemption for run-to-completion parallel processor scheduling policies, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.33-44, May 16-20, 1994, Nashville, Tennessee, United States
	4	Xiaotie Deng , Patrick W. Dymond, Efficient routing and message bounds for optimal parallel algorithms, Proceedings of the 9th International Symposium on Parallel Processing, p.556, April 25-28, 1995
	5	Xiaotie Deng , Nian Gu , Tim Brecht , KaiCheng Lu, Preemptive scheduling of parallel jobs on multiprocessors, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.159-167, January 28-30, 1996, Atlanta, Georgia, United States
	6	Xiaotie Deng , Elias Koutsoupias, Competitive implementation of parallel programs, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.455-461, January 25-27, 1993, Austin, Texas, United States
	7	Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, April 1995
	8	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]
	9	M. R. Garey, R. L. Graham, "Bounds for Multiprocessor Scheduling with Resource Constraints", SIAM Journal of Computing, Vol. #,, No. 2, pp. 187-200, June, 1975.
	10	Leslie Ann Goldberg , Mark Jerrum , Philip D. MacKenzie, An Ω(√ log log n) lower bound for routing in optical networks, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.147-156, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181093]
	11	R. L. Graham, "Bounds for Certain Multiprocessor Timing Anomalies", Bell System Technical Journal, Vol. #5, pp. 1563-1581, 1966.
	12	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
	13	A.R. Karlin, M.S. Manasse, L. Rudolph, and D.D. Sleator. "Competitive Snoopy Caching", Algorithmica 3 pp. 79-119, 1988.
	14	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]
	15	M. Kumar, Measuring Parallelism in Computation-Intensive Scientific/Engineering Applications, IEEE Transactions on Computers, v.37 n.9, p.1088-1098, September 1988 [doi>10.1109/12.2259]
	16	S. T. Leutenegger and R. D. Nelson, "Analysis of Spatial and Temporal Scheduling Policies for Semi-Static and Dynamic Multiprocessor Environments", Technical Report RC 17086 (No. 7559#), IBM T. J. Watson Research Center, Yorktown Heights, NY, August, 1991.
	17	W. Ludwig and P. Tiwari, "The Power of Choice in Scheduling Parallel Tasks", Computer Science Department, University of W#scons#n, Madison, Report US TRI190, Madison, WI, November, t993.
	18	Scott T. Leutenegger , Mary K. Vernon, The performance of multiprogrammed multiprocessor scheduling algorithms, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.226-236, April 1990, Univ. of Colorado, Boulder, Colorado, United States
	19	R. M ansharamani and M. K. Vernon, "Qualitative Behavior of the EQS Parallel Processor Allocation Policy", Technzcal Report CS TR 1192, Computer Sciences Department. University of Wisconsin, Madison, Madison, WI. November, 1993.
	20	Mark Manasse , Lyle McGeoch , Daniel Sleator, Competitive algorithms for on-line problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.322-333, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62243]
	21	Rajeev Motwani , Steven Phillips , Eric Torng, Non-clairvoyant scheduling, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.422-431, January 25-27, 1993, Austin, Texas, United States
	22	Cathy McCann , Raj Vaswani , John Zahorjan, A dynamic processor allocation policy for multiprogrammed shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.11 n.2, p.146-178, May 1993 [doi>10.1145/151244.151246]
	23	Cathy McCann , John Zahorjan, Scheduling memory constrained jobs on distributed memory parallel computers, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.208-219, May 15-19, 1995, Ottawa, Ontario, Canada
	24	K. C. Sevcik, Application scheduling and processor allocation in multiprogrammed parallel processing systems, Performance Evaluation, v.19 n.2-3, p.107-140, March 1994 [doi>10.1016/0166-5316(94)90036-1]
	25	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
	26	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]
	27	A. Tucker , A. Gupta, Process control and scheduling issues for multiprogrammed shared-memory multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.159-166, November 1989
	28	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]
	29	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
	30	J. Turek, U. Schwiegelshohn, J. L. Wolf, P. S. Yu, "A Significantly Smarter Bound for a Slightly Smarter SMART Algorithm", IBM Research Division, T. J. Watson Research Center, Report RC19#22 (84#162), Yorktown Heights, NY 10598, February, 1994.
	31	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
	32	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	33	John Zahorjan , Cathy McCann, Processor scheduling in shared memory multiprocessors, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.214-225, April 1990, Univ. of Colorado, Boulder, Colorado, United States

CITED BY 6

	Jeff Edmonds, Scheduling in the dark, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.179-188, May 01-04, 1999, Atlanta, Georgia, United States
	Jeff Edmonds , Donald D. Chinn , Tim Brecht , Xiaotie Deng, Non-clairvoyant multiprocessor scheduling of jobs with changing execution characteristics (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.120-129, May 04-06, 1997, El Paso, Texas, United States
	Kunal Agrawal , Yuxiong He , Wen Jing Hsu , Charles E. Leiserson, Adaptive scheduling with parallelism feedback, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
	Kunal Agrawal , Yuxiong He , Charles E. Leiserson, Adaptive work stealing with parallelism feedback, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
	Kunal Agrawal , Charles E. Leiserson , Yuxiong He , Wen Jing Hsu, Adaptive work-stealing with parallelism feedback, ACM Transactions on Computer Systems (TOCS), v.26 n.3, p.1-32, September 2008
	Rajkumar Kettimuthu , Vijay Subramani , Srividya Srinivasan , Thiagaraja Gopalsamy , D. K. Panda , P. Sadayappan, Selective preemption strategies for parallel job scheduling, International Journal of High Performance Computing and Networking, v.3 n.2/3, p.122-152, November 2005