Cell GC: using the cell synergistic processor as a garbage collection coprocessor

ABSTRACT

In recent years, scaling of single-core superscalar processor performance has slowed due to complexity and power considerations. To improve program performance, designs are increasingly adopting chip multiprocessing with homogeneous or heterogeneous CMPs. By trading off features from a modern aggressive superscalar core, CMPs often offer better scaling characteristics in terms of aggregate performance, complexity and power, but often require additional software investment to rewrite, retune or recompile programs to take advantage of the new designs. The Cell Broadband Engine is a modern example of a heterogeneous CMP with coprocessors (accelerators) which can be found in supercomputers (Roadrunner), blade servers (IBM QS20/21), and video game consoles (SCEI PS3). A Cell BE processor has a host Power RISC processor (PPE) and eight Synergistic Processor Elements (SPE), each consisting of a Synergistic Processor Unit (SPU) and Memory Flow Controller (MFC).

In this work, we explore the idea of offloading Automatic Dynamic Garbage Collection (GC) from the host processor onto accelerator processors using the coprocessor paradigm. Offloading part or all of GC to a coprocessor offers potential performance benefits, because while the coprocessor is running GC, the host processor can continue running other independent, more general computations. .

We implement BDW garbage collection on a Cell system and offload the mark phase to the SPE co-processor. We show mark phase execution on the SPE accelerator to be competitive with execution on a full fledged PPE processor. We also explore object-based and block-based caching strategies for explicitly managed memory hierarchies, and explore to effectiveness of several prefetching schemes in the context of garbage collection. Finally, we implement Capitulative Loads using the DMA by extending software caches and quantify its performance impact on the coprocessor.

REFERENCES

• 1: Erik Altman, Peter Capek, Michael Gschwind, Peter Hofstee, James Kahle, Ravi Nair, Sumedh Sathaye, and John-David Wellman. Method and system for maintaining coherency in a multiprovessor system by broadcasting tlb invalidated entry instructions. U.S. Patent 6970982, November 2005.
• 2: Hans-Juergen Boehm, Space efficient conservative garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.197-206, June 21-25, 1993, Albuquerque, New Mexico, United States
• 3: Hans-J. Boehm, Reducing garbage collector cache misses, Proceedings of the 2nd international symposium on Memory management, p.59-64, October 15-16, 2000, Minneapolis, Minnesota, United States
• 4: Chen-Yong Cher , Antony L. Hosking , T. N. Vijaykumar, Software prefetching for mark-sweep garbage collection: hardware analysis and software redesign, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 5: Scott Clark, Kent Haselhorst, Kerry Imming, John Irish, Dave Krolak, and Tolga Ozguner. Cell Broadband Engine interconnect and memory interface. In Hot Chips 17, Palo Alto, CA, August 2005.
• 6: A. E. Eichenberger , J. K. O'Brien , K. M. O'Brien , P. Wu , T. Chen , P. H. Oden , D. A. Prener , J. C. Shepherd , B. So , Z. Sura , A. Wang , T. Zhang , P. Zhao , M. K. Gschwind , R. Archambault , Y. Gao , R. Koo, Using advanced compiler technology to exploit the performance of the Cell Broadband Engine^TM architecture, IBM Systems Journal, v.45 n.1, p.59-84, January 2006
• 7: Alexandre E. Eichenberger , Kathryn O'Brien , Kevin O'Brien , Peng Wu , Tong Chen , Peter H. Oden , Daniel A. Prener , Janice C. Shepherd , Byoungro So , Zehra Sura , Amy Wang , Tao Zhang , Peng Zhao , Michael Gschwind, Optimizing Compiler for the CELL Processor, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.161-172, September 17-21, 2005 [doi>10.1109/PACT.2005.33]
• 8: Michael Gschwind, The cell broadband engine: exploiting multiple levels of parallelism in a chip multiprocessor, International Journal of Parallel Programming, v.35 n.3, p.233-262, June 2007 [doi>10.1007/s10766-007-0035-4]
• 9: Michael Gschwind , David Erb , Sid Manning , Mark Nutter, An Open Source Environment for Cell Broadband Engine System Software, Computer, v.40 n.6, p.37-47, June 2007 [doi>10.1109/MC.2007.192]
• 10: Michael Gschwind, Peter Hofstee, Brian Flachs, Martin Hopkins, Yukio Watanabe, and Takeshi Yamazaki. A novel SIMD architecture for the CELL heterogeneous chip-multiprocessor. In Hot Chips 17, Palo Alto, CA, August 2005.
• 11: Michael Gschwind , H. Peter Hofstee , Brian Flachs , Martin Hopkins , Yukio Watanabe , Takeshi Yamazaki, Synergistic Processing in Cell's Multicore Architecture, IEEE Micro, v.26 n.2, p.10-24, March 2006 [doi>10.1109/MM.2006.41]
• 12: Timothy H. Heil , James E. Smith, Concurrent garbage collection using hardware-assisted profiling, Proceedings of the 2nd international symposium on Memory management, p.80-93, October 15-16, 2000, Minneapolis, Minnesota, United States
• 13: Mark Horowitz , Margaret Martonosi , Todd C. Mowry , Michael D. Smith, Informing memory operations: memory performance feedback mechanisms and their applications, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.170-205, May 1998 [doi>10.1145/279227.279230]
• 14: Wen-mei Hwu et al. Performance insights on executing non-graphics applications on CUDA on the NVIDIA GeForce 8800 GTX. In Hot Chips 19, Palo Alto, CA, 2007.
• 15: J. A. Kahle , M. N. Day , H. P. Hofstee , C. R. Johns , T. R. Maeurer , D. Shippy, Introduction to the cell multiprocessor, IBM Journal of Research and Development, v.49 n.4/5, p.589-604, July 2005
• 16: Chi-Keung Luk , Todd C. Mowry, Compiler-based prefetching for recursive data structures, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.222-233, October 01-04, 1996, Cambridge, Massachusetts, United States
• 17: Albert Noll, Andreas Gal, and Michael Franz. CellVM: A homogeneous virtual machine runtime system for a heterogeneous single-chip multiprocessor. Technical report, School of Information and Computer Science, University of California, Irvine, November 2006.
• 18: Manoj Plakal , Charles N. Fischer, Concurrent garbage collection using program slices on multithreaded processors, Proceedings of the 2nd international symposium on Memory management, p.94-100, October 15-16, 2000, Minneapolis, Minnesota, United States
• 19: Robin Garner , Stephen M. Blackburn , Daniel Frampton, Effective prefetch for mark-sweep garbage collection, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296915]
• 20: Samuel Williams , John Shalf , Leonid Oliker , Shoaib Kamil , Parry Husbands , Katherine Yelick, The potential of the cell processor for scientific computing, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128027]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Microprocessor/microcomputer applications

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Domain-specific architectures
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

General Terms:
Algorithms, Performance

Keywords:
BDW, SPE, SPU, accelerator, cell, coprocessor, explicitly managed memory hierarchies, garbage collection, local store, mark-sweep