Enabling scalability and performance in a large scale CMP environment

ABSTRACT

Hardware trends suggest that large-scale CMP architectures, with tens to hundreds of processing cores on a single piece of silicon, are iminent within the next decade. While existing CMP machines have traditionally been handled in the same way as SMPs, this magnitude of parallelism introduces several fundamental challenges at the architectural level and this, in turn, translates to novel challenges in the design of the software stack for these platforms. This paper presents the "Many Core Run Time" (McRT), a software prototype of an integrated language runtime that was designed to explore configurations of the software stack for enabling performance and scalability on large scale CMP platforms. This paper presents the architecture of McRT and discusses our experiences with the system, including experimental evaluation that lead to several interesting, non-intuitive findings, providing key insights about the structure of the system stack at this scale. A key contribution of this paper is to demonstrate how McRT enables near linear improvements in performance and scalability for desktop workloads such as the popular XviD encoder and a set of RMS (recognition, mining, and synthesis) applications. Another key contribution of this work is its use of McRT to explore non-traditional system configurations such as a light-weight executive in which McRT runs on "bare metal" and replaces the traditional OS. Such configurations are becoming an increasingly attractive alternative to leverage heterogeneous computing uints as seen in today's CPU-GPU configurations.

REFERENCES

• 1: Brian D. Marsh , Michael L. Scott , Thomas J. LeBlanc , Evangelos P. Markatos, First-class user-level threads, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.110-121, October 13-16, 1991, Pacific Grove, California, United States
• 2: Bil Lewis , Daniel J. Berg, Multithreaded programming with Pthreads, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 3: Next Generation POSIX Threading. http://www-124.ibm.com/pthreads/
• 4: U. Drepper, and I. Molnar. The native POSIX thread library for Linux, Jan 2003. http://people.redhat.com/drepper/nptl-design.pdf.
• 5: D. Vianney, Hyper-Threading speeds Linux, Jan 2003. http://www-128.ibm.com/developerworks/linux/library/l-htl/
• 6: Microsoft Corp, Windows Support for Hyper-Threading technology, 2002. download.microsoft.com/download/5/7/7/577a5684-8a83-43ae-9272-ff260a9c20e2/Hyper-thread_Windows.doc
• 7: Edouard Bugnion , Scott Devine , Mendel Rosenblum, Disco: running commodity operating systems on scalable multiprocessors, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.143-156, October 05-08, 1997, Saint Malo, France
• 8: Rob von Behren , Jeremy Condit , Feng Zhou , George C. Necula , Eric Brewer, Capriccio: scalable threads for internet services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 9: N. Nagarajaya, Improving Application Efficiency Through Chip Multi-Threading, Sun Developer Network, Mar 2005. developers.sun.com/solaris/articles/chip_multi_thread.html
• 10: Vivek S. Pai , Peter Druschel , Willy Zwaenepoel, Flash: an efficient and portable web server, Proceedings of the Annual Technical Conference on 1999 USENIX Annual Technical Conference, p.15-15, June 06-11, 1999, Monterey, California
• 11: Matt Welsh , David Culler , Eric Brewer, SEDA: an architecture for well-conditioned, scalable internet services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 12: S. Gribble, M. Welsh, R. von Behren, E. Brewer, D. Culler, N. Borisov, S. Czerwinski, R. Gummadi, J. Hill, A. Josheph, R. Katz, Z. Mao, S. Ross, and B. Zhao. The Ninja Architecture for Robust Internet-Scale Systems and Services. Sp. lss.: Computer Networks on Pervasive Computing 2000.
• 13: Mohan Rajagopalan , Saumya K. Debray , Matti A. Hiltunen , Richard D. Schlichting, Profile-directed optimization of event-based programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 14: J. Liedtke, On micro-kernel construction, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.237-250, December 03-06, 1995, Copper Mountain, Colorado, United States
• 15: D. R. Engler , M. F. Kaashoek , J. O'Toole, Jr., Exokernel: an operating system architecture for application-level resource management, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.251-266, December 03-06, 1995, Copper Mountain, Colorado, United States
• 16: Bryan Ford , Godmar Back , Greg Benson , Jay Lepreau , Albert Lin , Olin Shivers, The Flux OSKit: a substrate for kernel and language research, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.38-51, October 05-08, 1997, Saint Malo, France
• 17: John K. Ousterhout , Andrew R. Cherenson , Frederick Douglis , Michael N. Nelson , Brent B. Welch, The Sprite Network Operating System, Computer, v.21 n.2, p.23-36, February 1988 [doi>10.1109/2.16]
• 18: Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.53-79, Feb. 1992 [doi>10.1145/146941.146944]
• 19: T. E. Anderson , E. D. Lazowska , H. M. Levy, The Performance Implications of Thread Management Alternatives for Shared-Memory Multiprocessors, IEEE Transactions on Computers, v.38 n.12, p.1631-1644, December 1989 [doi>10.1109/12.40843]
• 20: Michael B. Jones , Richard F. Rashid, Mach and Matchmaker: kernel and language support for object-oriented distributed systems, Conference proceedings on Object-oriented programming systems, languages and applications, p.67-77, September 29-October 02, 1986, Portland, Oregon, United States
• 21: Edouard Bugnion , Scott Devine , Mendel Rosenblum, Disco: running commodity operating systems on scalable multiprocessors, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.143-156, October 05-08, 1997, Saint Malo, France
• 22: The K42 project, IBM Research. http://www.research.ibm.com/k42/
• 23: The K42/Tornado Operating System. http://www.eecg.toronto.edu/~tornado/
• 24: T. G. Mattson and G. Henry. An overview of the Intel TFLOPS supercomputer. Intel Technology Journal, 1, 1998.
• 25: Sharad Garg, Robert Godley, Richard Griffiths, Andrew Pfiffer, Terry Prickett, David Robboy, Stan Smith, T. Mack Stallcup, and Stephen Zeisset. Achieving large scale parallelism through operating system resource management on the Intel TFLOPS supercomputer. Intel Technology Journal, 1st quarter 1998.
• 26: Ron Brightwell, Rolf Riesen, Keith D. Underwood, Trammell Hudson, Patrick G. Bridges, Arthur B. Maccabe: A Performance Comparison of Linux and a Lightweight Kernel. CLUSTER 2003: 251--258
• 27: IBM Research Hypervisor. http://www.research.ibm.com/hypervisor/.
• 28: Boris Dragovic, Keir Fraser, Steve Hand, Tim Harris, Alex Ho, Ian Pratt, Andrew Warfield, Paul Barham, and Rolf Neugebauer. Xen and the Art of Virtualization. SOSP, 2003.
• 29: B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
• 30: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
• 31: Honghui Lu , Y. Charlie Hu , Willy Zwaenepoel, OpenMP on networks of workstations, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-15, November 07-13, 1998, San Jose, CA
• 32: J. Rattner. Platform 2015. Intel Dev. Forum, Spring 2005.
• 33: J. Rattner. Tera-Scale Research Program. Intel Dev. Forum, Spring 2006.
• 34: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 35: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 36: Ali-Reza Adl-Tabatabai , Brian T. Lewis , Vijay Menon , Brian R. Murphy , Bratin Saha , Tatiana Shpeisman, Compiler and runtime support for efficient software transactional memory, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 37: Bratin Saha , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Chi Cao Minh , Benjamin Hertzberg, McRT-STM: a high performance software transactional memory system for a multi-core runtime, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1123001]
• 38: Richard L. Hudson , Bratin Saha , Ali-Reza Adl-Tabatabai , Benjamin C. Hertzberg, McRT-Malloc: a scalable transactional memory allocator, Proceedings of the 5th international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada [doi>10.1145/1133956.1133967]
• 39: Ed Grochowski , Ronny Ronen , John Shen , Hong Wang, Best of Both Latency and Throughput, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.236-243, October 11-13, 2004
• 40: Michal Cierniak , Marsha Eng , Neal Glew , Brian Lewis , James Stichnoth, The Open Runtime Platform: a flexible high-performance managed runtime environment: Research Articles, Concurrency and Computation: Practice & Experience, v.17 n.5-6, p.617-637, April 2005 [doi>10.1002/cpe.v17:5/6]
• 41: P. Dubey. Recognition, Mining, and Synthesis moves computers to the era of tera. Technology@Intel, Feb 2005.
• 42: Craig, T. S. Building FIFO and priority-queueing spin locks from atomic swap. Technical Report TR 93-02-02, Dept of Computer Science, University of Washington, Feb. 1993.
• 43: Peter S. Magnusson , Anders Landin , Erik Hagersten, Queue Locks on Cache Coherent Multiprocessors, Proceedings of the 8th International Symposium on Parallel Processing, p.165-171, April 01, 1994
• 44: Michael L. Scott , William N. Scherer, Scalable queue-based spin locks with timeout, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.44-52, June 2001, Snowbird, Utah, United States
• 45: Doug Lea, The java.util.concurrent synchronizer framework, Science of Computer Programming, v.58 n.3, p.293-309, December 2005 [doi>10.1016/j.scico.2005.03.007]
• 46: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 47: B. So, A. M. Ghuloum, Y. Wu. Optimizing data parallel operations on many-core platforms. STMCS 2006.
• 48: Poonacha Kongetira , Kathirgamar Aingaran , Kunle Olukotun, Niagara: A 32-Way Multithreaded Sparc Processor, IEEE Micro, v.25 n.2, p.21-29, March 2005 [doi>10.1109/MM.2005.35]
• 49: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 50: Per-Åke Larson , Murali Krishnan, Memory allocation for long-running server applications, Proceedings of the 1st international symposium on Memory management, p.176-185, October 17-19, 1998, Vancouver, British Columbia, Canada
• 51: IA-32 Intel Architecture Software Developer's Manual. Intel Corporation.
• 52: Bradski, G.; Kaehler, A.; Pisarevsky, V. "Learning-Based Computer Vision with Intel's Open Source Computer Vision Library." Intel Technology Journal. http://developer.intel.com/technology/itj/2005/volume09issue02/art03_learning_vision/p01_abstract.htm. May 2005.
• 53: Steve Muir , Jonathan Smith, Functional divisions in the Piglet multiprocessor operating system, Proceedings of the 8th ACM SIGOPS European workshop on Support for composing distributed applications, p.255-260, September 1998, Sintra, Portugal [doi>10.1145/319195.319234]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
  D.4 OPERATING SYSTEMS
      D.4.0 General

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
memory management, multi-core processors, parallel programming, runtime design, scheduler design, sequestered mode, synchronization primitives, transactional memory