Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1459))
Included in the following conference series:
207Accesses
Abstract
This paper evaluates the performance of job scheduling schemes for pure space sharing among rigid jobs. Conventional job scheduling schemes for the pure space sharing among rigid jobs have been achieved by First Come First Served (FCFS). However, FCFS has a drawback such that it can not utilize processors efficiently. This paper evaluates the performance of job scheduling schemes that are proposed to alleviate the drawback of FCFS by simulation, performance analysis and experiments on a real multiprocessor system. The results showed that Fit Processors First Served (FPFS), which searches the job queue and positively dispatches jobs that fit idle processors, was more effective and more practical than others.
This is a preview of subscription content,log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
High Performance Fortran Forum. High Performance Fortran Language Specification Version 1.0, 1993.
H. Kasahara, H. Honda, K. Aida, M. Okamoto, and S. Narita. OSCAR Fortran Compiler. InProc. Workshop on Compilation of Languages for Parallel Computers, pages 30–37, 1991.
D. G. Feitelson and L. Rudolph. Toward Convergence in Job Schedulers for Parallel Supercomputers. InJob Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1162, pages 1–26. Springer-Verlag, 1996.
S. T. Leutenegger and M. K. Vernon. The Performance of Multiprogrammed Multiprocessor Scheduling Policies. InProc. of 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pages 226–236, 1990.
A. Gupta, A. Tucker, and S. Urushibara. The Impact of Operating System Scheduling Policies and Synchronization Methods on the Performance of Parallel Applications. InProc. of 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pages 120–132, 1991.
C. McCann, R. Vaswani, and J. Zahorjan. A Dynamic Processor Allocation Policy for Multiprogrammed Shared-Memory Multiprocessors.ACM Trans. on Computer Systems, 11(2):146–178, 1993.
K. Li and K. Cheng. A Two-Dimensional Buddy System for Dynamic Resource Allocation in a Partitionable Mesh Connected System.J. Parallel and Distributed Computing, 12:79–83, 1991.
P. Chuang and N. Tzeng. An Efficient Submesh Allocation Strategy for Mesh Computer Systems. InProc. of International Conference on Distributed Computing Systems, pages 256–263, 1991.
Y. Zhu. Efficient Processor Allocation Strategies for Mesh-Connected parallel Computers.J. Parallel and Distributed Computing, 16:328–337, 1992.
V. Lo, K. J. Windisch, W. Liu, and B. Nitzberg. Noncontiguous Processor Allocation Algorithms for Mesh-Connected Multicomputers.IEEE Trans. on Parallel and Distributed Systems, 8(7):712–726, 1997.
D. G. Feitelson and L. Rudolph. Parallel Job Scheduling: Issues and Approaches. InJob Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 949, pages 1–18. Springer-Verlag, 1995.
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.
J. Subhlok, T. Gross, and T Suzuoka. Impact of Job Mix on Optimizations for Space Sharing Scheduler. InProc. of Supercomputing '96, 1996.
K. Aida, H. Kasahara, and S. Narita. A Scheduling Scheme of Parallel Jobs to Processor Groups on a Multiprocessor System.Trans. of IEICE, J80-D-I(6):463–473, 1997, (in Japanese).
R. Gibbons. A Historical Application Profiler for Use by Parallel Schedulers. InJob Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1291, pages 58–77. Springer-Verlag, 1997.
E. W. Parsons and K. C. Sevcik. Implementing Multiprocessor Scheduling Disciplines. InJob Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1291, pages 166–192. Springer-Verlag, 1997.
D. A. Lifka. The ANL/IBM SP Scheduling System. InJob 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 — LoadLeveler API Project. InJob Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1162, pages 41–47. Springer-Verlag, 1996.
T. Maruyama, Y. Kanoh, T. Hirose, T. Nakata, K. Muramatsu, Y. Asano, and Y. Inamura. Architecture of a Parallel Machine: Cenju-3.IEICE Trans. The Institute of Electronics, Information and Communication Engineers, J78-D-I(2):59–67, 1995, (in Japanese).
E. G. Coffman, M. R. Garey, and D. S. Johnson. Approximation Algorithms for Bin-packing — An Updated Survey. InAlgorithm Design for Computer System Design, pages 49–106. Springer-Verlag, 1984.
S. Hotovy. Workload Evolution on the Cornell Theory Center IBM SP2. InJob Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science 1162, pages 27–40. Springer-Verlag, 1996.
R. Jain.The Art of Computer Systems Performance Analysis. Wiley, 1991.
Y. Zhu and M. Ahuja. On Job Scheduling on a Hypercube.IEEE Trans. on Parallel and Distributed Systems, 4(1):62–69, 1993.
E. G. Coffman and G. S. Lueker.Probabilistic Analysis of Packing and Partitioning Algorithms. Wiley, 1991.
P. W. Shor. The Average-case Analysis of Some On-line Algorithms for Bin Packing.Combinatorial, 6(2):179–200, 1986.
NEC.NEC Parallel Computer Cenju-3 User's Manual, 1994, (in Japanese).
T. Sakamoto, Y. Maekawa, S. Wakao, T. Onuki, and H. Kasahara. Parallelization of the Electro-magnetic Field Analysis Application Using Hybrid Finite Element and Boundary Element Method. InProc. 52th Annual Convention IPSJ, pages 4L-8, 1996, (in Japanese).
D. Bailey, E. Barszcz, J. Barton, D. Browningand R. Carter, L. Dagum, R. Fatoohi, S. Fineberg, P. Frederickson, T. Lasinski, R. Schreiber, H. Simon, V. Venkatakrishnan, and S. Weeratunga. The NAS Parallel Benchmarks. Technical Report BNR-94-007, NASA Ames Research Center, 1994.
Author information
Authors and Affiliations
Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1, O-okayama, Meguro-ku, 152, Tokyo, Japan
Kento Aida
Department of Electrical, Electronics and Computer Engineering, Waseda University, 3-4-1, Ohkubo, Shinjuku-ku, 169, Tokyo, Japan
Hironori Kasahara & Seinosuke Narita
- Kento Aida
You can also search for this author inPubMed Google Scholar
- Hironori Kasahara
You can also search for this author inPubMed Google Scholar
- Seinosuke Narita
You can also search for this author inPubMed Google Scholar
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aida, K., Kasahara, H., Narita, S. (1998). Job scheduling scheme for pure space sharing among rigid jobs. In: Feitelson, D.G., Rudolph, L. (eds) Job Scheduling Strategies for Parallel Processing. JSSPP 1998. Lecture Notes in Computer Science, vol 1459. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0053983
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-64825-3
Online ISBN:978-3-540-68536-4
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