Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1911))
Included in the following conference series:
350Accesses
Abstract
A workload characteristic on a parallel computer depends on an administration policy or a user community for the computer system. An administrator of a parallel computer system needs to select an appropriate scheduling algorithm that schedules multiple jobs on the computer system efficiently. The goal of the work presented in this paper is to investigate mechanisms how job size characteristics affect job scheduling performance. For this goal, this paper evaluates the performance of job scheduling algorithms under various workload models, each of which has a certain characteristic related to the number of processors requested by a job, and analyzes the mechanism for job size characteristics that affect job scheduling performance significantly in the evaluation. The results showed that: (1) most scheduling algorithms classified into the first-fit scheduling showed best performance and were not affected by job size characteristics, (2) certain job size characteristics affected performance of priority scheduling significantly. The analysis of the results showed that the LJF algorithm, which dispatched the largest job first, would perfectly pack jobs to idle processors at high load, where all jobs requested powerof- two processors and the number of processors on a parallel computer was power-of-two.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K. Li and K. Cheng. Job Scheduling in a Partitionable Mesh Using a Two-Dimensional Buddy System Partitioning Scheme. IEEE Trans. on Parallel and Distributed Systems, 2(4):413– 422, 1991.
D. A. Lifka. The ANL/IBM SP Scheduling System. In Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 949, pages 295– 303. Springer-Verlag, 1995.
J. S. Skovira, W. Chan, and H. Zhou. The EASY-LoadLev eler API Project. In Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1162, pages 41– 47. Springer-Verlag, 1996.
P. Krueger, T. Lai, and V. A. Dixit-Radiya. Job Scheduling Is More Important than Processor Allocation for Hypercube Computers. IEEE Trans. on Parallel and Distributed Systems, 5(5):488– 497, 1994.
D. G. Feitelson. Packing Scheme for Gang Scheduling. In Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1162, pages 89– 110. Springer-Verlag, 1996.
J. Subhlok, T. Gross, and T Suzuoka. Impact of Job Mix on Optimizations for Space Sharing Scheduler. In Proc. of Supercomputing ’96, 1996.
A. B. Downey. A parallel workload model and its implications for processor allocation. In Proc. the 6th International Symposium of High Performance Distributed Computing, pages 112– 123, 1997.
V. Lo, J. Mache, and K. Windisch. A Comparative Study of Real Workload Traces and Synthetic Workload. In Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1459, pages 25– 46. Springer-Verlag, 1998.
D. G. Feitelson and L. Rudolph. Toward Convergence in Job Schedulers for Parallel Supercomputers. In Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1162, pages 1– 26. Springer-Verlag, 1996.
R. Gibbons. A Historical Application Profiler for Use by Parallel Schedulers. In Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1291, pages 58– 77. Springer-Verlag, 1997.
K. Aida, H. Kasahara, and S. Narita. Job Scheduling Scheme for Pure Space Sharing Among Rigid Jobs. In Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1459, pages 98– 121, 1998.
H. Franke, J. Jann, J. E. Moreira, P. Pattnaik, and M. A. Jette. An Evaluation of Parallel Job Scheduling for ASCI Blue-Pacific. In Proc. SC99, 1999.
E. G. Coffman, M. R. Garey, and D. S. Johnson. Approximation Algorithms for Bin-packing-An Updated Survey. In Algorithm Design for Computer System Design, pages 49– 106. Springer-Verlag, 1984.
E. G. Coffman, M. R. Garey, and D. S. Johnson. Bin Packing with Divisible Item Sizes. Journal of Complexity, 3:406– 428, 1987.
Author information
Authors and Affiliations
Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology, 4259, Nagatsuta, Midori-ku, Yokohama-shi, 226-8502, Japan
Kento Aida
- Kento Aida
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
The Hebrew University School of Computer Science and Engineering, 91904, Jerusalem, Israel
Dror G. Feitelson
Massachusetts Institute of Technology Laboratory for Computer Science, Cambridge, MA, 02139, USA
Larry Rudolph
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aida, K. (2000). Effect of Job Size Characteristics on Job Scheduling Performance. In: Feitelson, D.G., Rudolph, L. (eds) Job Scheduling Strategies for Parallel Processing. JSSPP 2000. Lecture Notes in Computer Science, vol 1911. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39997-6_1
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-41120-8
Online ISBN:978-3-540-39997-1
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative