Abstract
Coscheduling is essential for obtaining good performance in a time-shared symmetric multiprocessor (SMP) cluster environment. The most common technique, gang scheduling, has limitations such as poor scalability and vulnerability to faults mainly due to explicit synchronization between its components. A decentralized approach called dynamic coscheduling (DCS) has been shown to be effective for network of workstations (NOW), but this technique may not be suitable for the workloads on a very large SMP-cluster with thousands of processors. Furthermore, its implementation can be prohibitively expensive for such a large-scale machine. In this paper, we propose a novel coscheduling technique which can achieve coscheduling on very large SMP-clusters in a scalable, effcient, and cost-effective way. In the proposed technique, each local scheduler achieves coscheduling based upon message trafic between the components of parallel jobs. Message trapping is carried out at the user-level, eliminating the need for unsupported hardware or device-level programming. A sending process attaches its status to outgoing messages so local schedulers on remote nodes can make more intelligent scheduling decisions. Once scheduled, processes are guaranteed some minimum period of time to execute. This provides an opportunity to synchronize the parallel job’s components across all nodes and achieve good program performance. The results from a performance study reveal that the proposed technique is a promising approach that can reduce response time significantly over uncoordinated time-sharing and batch scheduling.
This work was performed under the auspices of the U.S. Department of Energy by University of California Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
T. E. Anderson, D. E. Culler, and D. A. Patterson. A Case for NOW (Networks of Workstations). IEEE Micro, 15(1):54–64, Feb. 1995.
A. C. Arpaci-Dusseau, D. E. Culler, and A. M. Mainwaring. Scheduling with Implicit Information in Distributed Systems. In Proc. ACM SIGMETRICS 1998 Conf. on Measurement and Modeling of Computer Ssystems, 1998.
D. H. Bailey et al. The NAS Parallel Benchmarks. International Journal of Supercomputer Applications, 5:63–73, 1991.
D. H. Bailey et al. The NAS Parallel Benchmarks. Technical Report NASA Technical Memorandom 103863, NASA Ames Research Center, 1993.
D. H. Bailey et al. The NAS Parallel Benchmarks 2.0. Technical Report NAS-95-020, NASA Ames Research Center, Dec. 1995.
D. H. Bailey et al. Valuation of Ultra-Scale Computing Systems: A White Paper, Dec. 1999.
D. G. Feitelson. Memory Usage in the LANL CM-5 Workload. In Proc. IPPS’97 Workshop on Job Scheduling St rategies for Parallel Processing, pages 78–94, 1997.
D. G. Feitelson and M. Jette. Improved Utilization and Responsiveness with Gang Scheduling. In Proc. IPPS’97 Workshop on Job Scheduling Strategies for Parallel Processing, Vol. 1291 of Lecture Notes in Computer Science, pages 238–261. Springer-Verlag, Apr. 1997.
H. Franke, P. Pattnaik, and L. Rudolph. Gang Scheduling for Highly Effcient Multiprocessors. In Proc. Sixth Symp. on the Frontiers of Massively Parallel Processing, Oct. 1996.
W. Gropp and E. Lusk. A High-Performance, Portable Implementation of the MPI Message Passing Interface Standard. Parallel Computing, 22:54–64, Feb. 1995.
IBM Corporation. LoadLeveler’s User Guide, Release 2.1.
J. E. Moreira et al. A Gang-Scheduling System for ASCI Blue-Pacific. In Proc. Distributed Computing and Metacomputing (DCM) Workshop, High-Performance Computing and Networking’ 99, Apr. 1999.
M. Jette. Performance Characteristics of Gang Scheduling in Multiprogrammed Environments. In Proc. SuperComputing97, Nov. 1997.
M. Jette. Expanding Symmetric Multiprocessor Capability Through Gang Scheduling. In Proc. IPPS’98 Workshop on Job Scheduling Strategies for Parallel Processing, Mar. 1998.
M. Jette, D. Storch, and E. Yim. Timesharing the Cray T3D. In CrayUser Group, pages 247–252, Mar. 1996.
N. J. Boden et al. Myrinet: A Gigabit-per-second Local Area Network. IEEE Micro, 15(1):29–36, Feb. 1995.
S. Nagar, A. Banerjee, A. Sivasubramaniam, and C. R. Das. A Closer Look At Coscheduling Approaches for a Network of Workstations. In Proc. 11th ACM Symp. of Parallel Algorithms and Architectures, June 1999.
J. K. Ousterhout. Scheduling Technique for Concurrent Systems. In Proc. Int’l Conf. on Distributed Computing Systems, pages 22–30, 1982.
S. Pakin, M. Lauria, and A. Chien. High Performance Messaging on Workstations: Illinois Fast Meessages (FM). In Proc. Supercomputing’ 95, Dec. 1995.
S. Saini and D. H. Bailey. NAS Parallel Benchmark (Version 1.0) Results 11-96. Technical Report NAS-96-18, NASA Ames Research Center, Nov. 1996.
J. Skovira, W. Chan, H. Zhou, and D. Lifka. The Easy-LoadLeveler API Project. In Proc. IPPS’96 Workshop on Job Scheduling Strategies for Parallel Processing, Vol. 1162 of Lecture Notes in Computer Science, pages 41–47. Springer-Verlag, Apr. 1996.
P. G. Sobalvarro. Demand-based Coscheduling of Parallel Jobs on Multiprogrammed Multiprocessors. PhD thesis, Dept. of Electrical Engineering and Compuer Science, Massachusetts Institutute of Technology, 1997.
P. G. Sobalvarro and W. E. Weihl. Demand-based Coscheduling of Parallel Jobs on Multipr ogrammed Multiprocessors. In Proc. IPPS’95 Workshop on Job Scheduling Strategies for Parallel Processing, pages 63–75, Apr. 1995.
T. von Eicken and A. Basu and V. Buch and W. Vogels. U-Nnet: A User-Level Network Interface for Parallel and Distributed Computing. In Proc. 15th ACM Symp. on Operating System Principles, Dec. 1995.
T. von Eicken and D. E. Culler and S. C. Goldsten and K. E. Schauser. Active Messages: A Mechanism for Integrated Communication and Computation. In Proc. 19th Annual Int’l Symp. on Computer Architecture, Dec. 1995.
B. S. Yoo and C. R. Das. A Fast and Effcient Processor Management Scheme for k-ary n-cubes. Journal of Parallel and Distributed Computing, 55(2):192–214, Dec. 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yoo, A.B., Jette, M.A. (2001). An Efficient and Scalable Coscheduling Technique for Large Symmetric Multiprocessor Clusters. In: Feitelson, D.G., Rudolph, L. (eds) Job Scheduling Strategies for Parallel Processing. JSSPP 2001. Lecture Notes in Computer Science, vol 2221. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45540-X_3
Download citation
DOI: https://doi.org/10.1007/3-540-45540-X_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42817-6
Online ISBN: 978-3-540-45540-0
eBook Packages: Springer Book Archive