A job scheduling framework for large computing farms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A job scheduling framework for large computing farms

Full text

Pdf (326 KB)

Source

Conference on High Performance Networking and Computing archive
Proceedings of the 2007 ACM/IEEE conference on Supercomputing - Volume 00 table of contents

Reno, Nevada

SESSION: Scheduling table of contents

Article No. 54

Year of Publication: 2007

ISBN:978-1-59593-764-3

Authors

Gabriele Capannini	Information Science and Technologies Institute, Pisa, Italy
Ranieri Baraglia	Information Science and Technologies Institute, Pisa, Italy
Diego Puppin	Information Science and Technologies Institute, Pisa, Italy
Laura Ricci	Largo B. Pontecorvo, Pisa, Italy
Marco Pasquali	Information Science and Technologies Institute, Pisa, Italy

Sponsors

IEEE-CS\DATC : IEEE Computer Society
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 104, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/1362622.1362695 What is a DOI?

ABSTRACT

In this paper, we propose a new method, called Convergent Scheduling, for scheduling a continuous stream of batch jobs on the machines of large-scale computing farms. This method exploits a set of heuristics that guide the scheduler in making decisions. Each heuristics manages a specific problem constraint, and contributes to carry out a value that measures the degree of matching between a job and a machine. Scheduling choices are taken to meet the QoS requested by the submitted jobs, and optimizing the usage of hardware and software resources. We compared it with some of the most common job scheduling algorithms, i.e. Backfilling, and Earliest Deadline First. Convergent Scheduling is able to compute good assignments, while being a simple and modular algorithm.

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	Sanjoy Baruah , Shelby Funk , Joël Goossens, Robustness Results Concerning EDF Scheduling upon Uniform Multiprocessors, IEEE Transactions on Computers, v.52 n.9, p.1185-1195, September 2003 [doi>10.1109/TC.2003.1228513]
	2	A. Bayucan, R. L. Henderson, L. T. Jasinskyj, C. Lesiak, B. Mann, T. Proett, and D. Tweten. Portable batch system, administrator guide. Technical Report Release: 2.2, MRJ Technology Solutions, Mountain View, CA, USA, November 1999.
	3	Su-Hui Chiang , Andrea C. Arpaci-Dusseau , Mary K. Vernon, The Impact of More Accurate Requested Runtimes on Production Job Scheduling Performance, Revised Papers from the 8th International Workshop on Job Scheduling Strategies for Parallel Processing, p.103-127, July 24, 2002
	4	A. D. Techiouba, G. Capannini, R. Baraglia, D. Puppin, M. Pasquali, and L. Ricci. Backfilling strategies for scheduling streams of jobs on computational farms. In CoreGRID Workshop on Grid Programming Model, Grid and P2P Systems Architecture, Grid Systems, Tools and Environments, Heraklion-Crete, Greece, June 2007.
	5	Hesham El-Rewini , Theodore G. Lewis , Hesham H. Ali, Task scheduling in parallel and distributed systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
	6	Y. Etsion and D. Tsafrir. A short survey of commercial cluster batch schedulers. Technical Report 2005--13, School of Computer Science and Engineering, The Hebrew University of Jerusalem, May 2005.
	7	D. D. Feitelson, L. Rudolph, and U. Schwiegelshohn. Parallel job scheduling, a status report. In Job Scheduling Strategies for Parallel Processing 10th International Workshop, pages 1--16, London, UK, Lect. Notes Comput. Sci. vol. 3277, 2004. Springer-Verlag.
	8	Anja Feldmann , Jiří Sgall , Shang-Hua Teng, Dynamic scheduling on parallel machines, Theoretical Computer Science, v.130 n.1, p.49-72, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90152-X]
	9	A. Fiat and G. J. Woeginger. Online algorithms, the state of the art. In Developments from a June 1996 seminar on Online algorithms, London, UK, Lect. Notes Comput. Sci. vol. 1442, 1998. Springer-Verlag.
	10	Volker Hamscher , Uwe Schwiegelshohn , Achim Streit , Ramin Yahyapour, Evaluation of Job-Scheduling Strategies for Grid Computing, Proceedings of the First IEEE/ACM International Workshop on Grid Computing, p.191-202, December 17, 2000
	11	David B. Jackson , Quinn Snell , Mark J. Clement, Core Algorithms of the Maui Scheduler, Revised Papers from the 7th International Workshop on Job Scheduling Strategies for Parallel Processing, p.87-102, June 16, 2001
	12	Tsuyoshi Kawaguchi , Seiki Kyan, Worst case bound of an LRF schedule for the mean weighted flow-time problem, SIAM Journal on Computing, v.15 n.4, p.1119-1129, Nov. 1986 [doi>10.1137/0215081]
	13	David A. Lifka, The ANL/IBM SP Scheduling System, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.295-303, April 25, 1995
	14	Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
	15	S. Microsystems. Sun one grid engine administration and user guide. Technical Report Part No. 816-2077-12, Sun Microsystems, Inc., Santa Clara, CA, USA, October 2002.
	16	Ahuva W. Mu'alem , Dror G. Feitelson, Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling, IEEE Transactions on Parallel and Distributed Systems, v.12 n.6, p.529-543, June 2001 [doi>10.1109/71.932708]
	17	D. Puppin, M. Stephenson, W. Lee, and S. Amarasinghe. Convergent scheduling. The Journal of Instruction Level Parallelism, 6(1):1--23, September 2004.
	18	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 [doi>10.1109/TPDS.2002.1011417]
	19	Uwe Schwiegelshohn, Preemptive Weighted Completion Time Scheduling of Parallel Jobs, SIAM Journal on Computing, v.33 n.6, p.1280-1308, 2004 [doi>10.1137/S009753979731501X]
	20	Uwe Schwiegelshohn , Walter Ludwig , Joel L. Wolf , John Turek , Philip S. Yu, Smart SMART Bounds for Weighted Response Time Scheduling, SIAM Journal on Computing, v.28 n.1, p.237-253, Feb. 1999 [doi>10.1137/S0097539795286831]
	21	Uwe Schwiegelshohn , Ramin Yahyapour, Analysis of first-come-first-serve parallel job scheduling, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.629-638, January 25-27, 1998, San Francisco, California, United States
	22	Edi Shmueli , Dror G. Feitelson, Backfilling with lookahead to optimize the packing of parallel jobs, Journal of Parallel and Distributed Computing, v.65 n.9, p.1090-1107, September 2005 [doi>10.1016.j.jpdc.2005.05.003]
	23	Srividya Srinivasan , Rajkumar Kettimuthu , Vijay Subramani , P. Sadayappan, Selective Reservation Strategies for Backfill Job Scheduling, Revised Papers from the 8th International Workshop on Job Scheduling Strategies for Parallel Processing, p.55-71, July 24, 2002

CITED BY 2

	Marco Pasquali , Ranieri Baraglia , Gabriele Capannini , Laura Ricci , Domenico Laforenza, A two-level scheduler to dynamically schedule a stream of batch jobs in large-scale grids, Proceedings of the 17th international symposium on High performance distributed computing, June 23-27, 2008, Boston, MA, USA
	Youngjoo Han , Chan-Hyun Youn, A new grid resource management mechanism with resource-aware policy administrator for SLA-constrained applications, Future Generation Computer Systems, v.25 n.7, p.768-778, July, 2009