Improving the Scalability of Parallel Jobs by adding Parallel Awareness to the Operating System

ABSTRACT

A parallel application benefits from scheduling policies that include a global perspective of the application's process working set. As the interactions among cooperating processes increase, mechanisms to ameliorate waiting within one or more of the processes become more important. In particular, collective operations such as barriers and reductions are extremely sensitive to even usually harmless events such as context switches among members of the process working set. For the last 18 months, we have been researching the impact of random short-lived interruptions such as timer-decrement processing and periodic daemon activity, and developing strategies to minimize their impact on large processor-count SPMD bulk-synchronous programming styles. We present a novel co-scheduling scheme for improving performance of fine-grain collective activities such as barriers and reductions, describe an implementation consisting of operating system kernel modifications and run-time system, and present a set of empirical results comparing the technique with traditional operating system scheduling. Our results indicate a speedup of over 300% on synchronizing collectives.

REFERENCES

• 1: [ASCI_White] ASCI White Information. http://www.llnl.gov/asci/platforms/white
• 2: [Barbosa da Silva99] Barbosa da Silva FA, Scherson ID. Concurrent gang: Towards a flexible and scalable gang scheduler. Proceedings 11th Symposium on Computer Architecture and High Performance Computing. Univ. Federal do Rio Grande do Sul. 1999, pp. 243-7. Porto Alegre, Brazil.
• 3: R. M. Bryant , H.-Y. Chang , B. S. Rosenburg, Operating system support for parallel programming on RP3, IBM Journal of Research and Development, v.35 n.5-6, p.617-634, Sept./Nov. 1991
• 4: Douglas C. Burger , Rahmat S. Hyder , Barton P. Miller , David A. Wood, Paging tradeoffs in distributed-shared-memory multiprocessors, Proceedings of the 1994 conference on Supercomputing, p.590-599, December 1994, Washington, D.C., United States
• 5: [Dawson03] Shawn Dawson, Mike Collette, Performance of Ares. LLNL Technical Report UCRL-, January 21, 2003.
• 6: Andrea C. Dusseau , Remzi H. Arpaci , David E. Culler, Effective distributed scheduling of parallel workloads, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.25-36, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 7: [Feitelson89] Dror G. Feitelson and Larry Rudolph. Gang Scheduling Performance Benefits for Fine-Grain Synchronization. Journal of Parallel and Distributed Computing, 16(4), 1992.
• 8: [Feitelson97] Feitelson, D.: Job Scheduling in Multiprogrammed Parallel Systems IBM Research Report RC 19970, Second Revision (1997).
• 9: Anoop Gupta , Andrew Tucker , Shigeru Urushibara, The impact of operating system scheduling policies and synchronization methods of performance of parallel applications, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.120-132, May 21-24, 1991, San Diego, California, United States
• 10: Robert L. Henderson, Job Scheduling Under the Portable Batch System, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.279-294, April 25, 1995
• 11: [Hoisie03] Adolfy Hoisie, Darren Kerbyson, Scott Pakin, Fabrizio Petrini, Harvey Wasserman, Juan Fernandez-Peinador, Identifying and Eliminating the performance Variability on the ASCI Q Machine, LANL Technical Report UCRL-yyyyy. January 2, 2003.
• 12: [IBM 01] IBM Corp - IBM Parallel Environment for AIX: Installation, GA22-7418
• 13: [IBM 03] IBM Cluster solutions. http://www-1.ibm.com/servers/eserver/clusters
• 14: [Jones02] Terry Jones, "A Scaling Investigation on IBM SPs", ScicomP 6, Aug. 2002, Berkeley, CA.
• 15: [Jones03] Terry Jones, Jeff Fier, Larry Brenner, Observed Impacts of Operating Systems on the Scalability of Applications. LLNL Technical Report UCRL-, March 5, 2003.
• 16: [Karl97] Holger Karl - Co-scheduling through synchronized Scheduling servers - A prototype and experiments (unpublished).
• 17: W. T. C. Kramer , J. M. Crawer, Effective use of Cray supercomputers, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.721-731, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76345]
• 18: [Litzkow88] M. Litzkow, M. Livny, and M. Mutka. Condor - a hunter of idle workstations. In Proceedings of the 8th International Conference on Distributed Computing Systems (ICDCS'88), pages 108--111. IEEE Computer Society Press, June 1988.
• 19: [MHPCC] MHPCC, The Maui Scheduler, http://www.hpc2n.umu.se/doc/maui/index.html
• 20: José E. Moreira , Hubertus Franke , Waiman Chan , Liana L. Fong , Morris A. Jette , Andy Yoo, A Gang-Scheduling System for ASCI Blue-Pacific, Proceedings of the 7th International Conference on High-Performance Computing and Networking, p.831-840, April 12-14, 1999
• 21: [MPICH02] Abstract Device Interface Version 3.3 Reference Manual Draft of October 17, 2002.
• 22: [Mraz94] R. Mraz, Reducing the Variance of Point to Point Transfers in the IBM 9076 Parallel Computer, July, 1994. IBM Research Report RC-19675.
• 23: Shailabh Nagar , Ajit Banerjee , Anand Sivasubramaniam , Chita R. Das, A closer look at coscheduling approaches for a network of workstations, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.96-105, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305630]
• 24: [Ousterhout82] John K. Ousterhout - Scheduling Techniques for Concurrent Systems. In Third International Conference on Distributed Computing Systems, pp. 22-30, May 1982.
• 25: [Sobalvarro97] Patrick G. Sobalvarro, Scott Pakin, William E. Weihl, and Andrew A. Chien - Dynamic Co-scheduling on Workstation Clusters. Digital Systems Research Center Technical Note 1997-017, March, 1997.
• 26: Dennis M. Ritchie , Ken Thompson, The UNIX time-sharing system, Communications of the ACM, v.17 n.7, p.365-375, July 1974 [doi>10.1145/361011.361061]
• 27: [Top500] Top 500 Supercomputer sites. http://www.top500.org/lists/2002/11/