As clusters are being deployed to support a wide range of parallel workloads, scheduling becomes a challenging research issue because these workloads exhibit diverse characteristics and impose varying quality-of-service requirements. Many scheduling strategies are thus proposed, each intended for a different application/system setting. Due to the lack of a uniform simulation platform, a significant amount of research effort is spent in building a unique simulator for each algorithm, which may lead to false conclusions. This article presents ClusterSchedSim, which is a unifying simulation frame-work of cluster scheduling strategies. The core of ClusterSchedSim includes the node model and an interconnect model. ClusterSchedSim has implemented variations of popular cluster scheduling schemes, and it is flexible enough to add on new schemes. Using ClusterSchedSim, one can conveniently compare different scheduling schemes, profile their executions, and understand the impact of different application and system configuration parameters.
[1] Setia, S. K. , M. S. Squillante , and S. K. Tripathi . 1994. Analysis of processor allocation in multiprogrammed, distributed-memory parallel processing systems . IEEE Transactions on Parallel and Distributed Systems5 (4): 401-420 .
2.
[2] Leutenegger, S. T. , and M. K.Vernon . 1990. The performance of multiprogrammed multiprocessor scheduling policies . In Proceedings of the ACM SIGMETRICS 1990 Conference on Measurement and Modeling of Computer Systems, pp. 226-236 .
3.
[3] Zahorjan, J. , and C. McCann . 1990. Processor scheduling in shared memory multiprocessors . In Proceedings of the ACM SIGMETRICS 1990 Conference on Measurement and Modeling of Computer Systems, pp. 214-225 .
4.
[4] Tucker, A. 1993. Efficient scheduling on shared-memory multiprocessors. Ph.D. diss., Stanford University, Stanford, CA.
5.
[5] Ousterhout, J. K. 1982. Scheduling techniques for concurrent systems . In Proceedings of the 3rd International Conference on Distributed Computing Systems, pp. 22-30 .
6.
[6] Feitelson, D. G. , and L. Rudolph . 1992. Gang scheduling performance benefits for fine-grained synchronization . Journal of Parallel and Distributed Computing16 (4): 306-318 .
7.
[7] Feitelson, D. G. , and L. Rudolph . 1992. Coscheduling based on run-time identification of activity working sets. Technical Report Research Report RC 18416(80519), IBMT. J. Watson Research Center .
[9] Franke, H. , J. Jann , J. E. Moreira , P. Pattnaik , and M. A. Jette . 1999. Evaluation of parallel job scheduling for ASCI Blue-Pacific . In Proceedings of Supercomputing, November.
10.
[10] Nagar, S. , A. Banerjee , A. Sivasubramaniam , and C. R. Das . 1999. A closer look at coscheduling approaches for a network of work-stations . In Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures, June, pp. 96-105 .
11.
[11] Nagar, S. , A. Banerjee , A. Sivasubramaniam , and C. R. Das . 1999. Alternatives to coscheduling a network of workstations . Journal of Parallel and Distributed Computing59 (2): 302-327 .
12.
[12] Arpaci-Dusseau, A. C. , D. E. Culler , and A. M. Mainwaring . 1998. Scheduling with implicit information in distributed systems . In Proceedings of the ACM SIGMETRICS 1998 Conference on Measurement and Modeling of Computer Systems.
13.
[13] Sobalvarro, P. G. 1997. Demand-based coscheduling of parallel jobs on multiprogrammed multiprocessors. Ph.D. diss., Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA.
14.
[14] Buchanan, M. , and A. Chien . 1997. Coordinated thread scheduling for workstation clusters under Windows NT . In Proceedings of the USENIX Windows NT Workshop, August.
15.
[15] Zhang, Y. , A. Sivasubramaniam , J. Moreira , and H. Franke . 2000. A simulation-based study of scheduling mechanisms for a dynamic cluster environment . In Proceedings of the ACM 2000 International Conference on Supercomputing, May, pp. 100-109 .
16.
[16] Zhang, Y. , A. Sivasubramaniam , J. Moreira , and H. Franke . 2001. Impact of workload and system parameters on next generation cluster scheduling mechanisms . IEEE Transactions on Parallel and Distributed Systems12 (9): 967-985 .
17.
[17] Crovella, M. , P. Das , C. Dubnicki , T. LeBlanc , and E. Markatos . 1991. Multiprogramming on multiprocessors . In Proceedings of the IEEE Symposium on Parallel and Distributed Processing, pp. 590-597 .
18.
[18] Ghosal, D. , G. Serazzi , and S. K. Tripathi . 1991. The processor working set and its use in scheduling multiprocessor systems . IEEE Transactions on Software Engineering17 (5): 443-453 .
19.
[19] Herlihy, M. , B.-H. Lim , and N. Shavit . 1992. Low contention load balancing on large-scale multiprocessors . In Proceedings of the Symposium on Parallel Algorithms and Architectures, June, pp. 219-227 .
20.
[20] Karlin, A. R. , K. Li , M. S. Manasse , and S. Owicki . 1991. Empirical studies of competitive spinning for a shared-memory multiprocessor . In The 13th Symposium on Operating Systems Principles, October, pp. 41-55 .
21.
[21] von Eicken, T. , A. Basu , V. Buch , and W. Vogels . 1995. U-net: A user-level network interface for parallel and distributed computing . In Proceedings of the 15th ACM Symposium on Operating System Principles, December.
22.
[22] Pakin, S. , M. Lauria , and A. Chien . 1995. High performance messaging on workstations: Illinois fast messages (FM) for Myrinet . In Proceedings of Supercomputing ’95, December.
23.
[23] Bailey, D. , J. Barton , T. Lasinski , and H. Simon . 1991. The NAS parallel benchmarks . International Journal of Supercomputer Applications5 (3): 63-73 .
24.
[24] Singh, J. P. , W.-D. Weber , and A. Gupta . 1991. SPLASH: Stanford Parallel Applications for Shared-Memory. Technical Report CSL-TR-91-469, Computer Systems Laboratory, Stanford University .
25.
[25] Microelectronics and Computer Technology Corporation . 1990. CSIM user’s guide. Austin, TX: Microelectronics and Computer Technology Corporation .
26.
[26] Zhang, Y. , H. Franke , J. Moreira , and A. Sivasubramaniam . 2000. Improving parallel job scheduling by combining gang scheduling and backfilling techniques . In Proceedings of the International Parallel and Distributed Processing Symposium, May, pp. 133-142 .
27.
[27] Lifka, D. 1995. The ANL/IBM SP scheduling system . In Proceedings of the IPPS Workshop on Job Scheduling Strategies for Parallel Processing, April, pp. 295-303 .
28.
[28] Tucker, L. W. , and G. G. Robertson . 1988. Architecture and applications of the connection machine . IEEE Computer21 (8): 26-38 .
29.
[29] Dusseau, A. C. , R. H. Arpaci , and D. E. Culler . 1996. Effective distributed scheduling of parallel workloads . In Proceedings of the ACM SIGMETRICS 1996 Conference on Measurement and Modeling of Computer Systems, pp. 25-36 .
30.
[30] Zhang, Y. , H. Franke , J. Moreira , and A. Sivasubramaniam . 2003. An integrated approach to parallel scheduling using gang-scheduling, backfilling and migration . IEEE Transactions on Parallel and Distributed Systems14 (3): 236-247 .
31.
[31] Zhang, Y. , H. Franke , J. Moreira , and A. Sivasubramaniam . 2000. The impact of migration on parallel job scheduling for distributed systems . In Proceedings of 6th International Euro-Par Conference Lecture Notes in Computer Science 1900, August/September, pp. 245-251 .
32.
[32] Zhang, Y. , and A. Sivasubramaniam . 2001. Scheduling best-effort and pipelined real-time applications on time-shared clusters . In Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, July, pp. 209-218 .
