A comparison of programming models for multiprocessors with explicitly managed memory hierarchies

ABSTRACT

On multiprocessors with explicitly managed memory hierarchies (EMM), software has the responsibility of moving data in and out of fast local memories. This task can be complex and error-prone even for expert programmers. Before we can allow compilers to handle this complexity for us, we must identify the abstractions that are general enough to allow us to write applications with reasonable effort, yet specific enough to exploit the vast on-chip memory bandwidth of EMM multi-processors. To this end, we compare two programming models against hand-tuned codes on the STI Cell, paying attention to programmability and performance. The first programming model, Sequoia, abstracts the memory hierarchy as private address spaces, each corresponding to a parallel task. The second, Cellgen, is a new framework which provides OpenMP-like semantics and the abstraction of a shared address space divided into private and shared data. We compare three applications programmed using these models against their hand-optimized counterparts in terms of abstractions, programming complexity, and performance.

REFERENCES

• 1: Ashwin M. Aji , Wu-chun Feng , Filip Blagojevic , Dimitrios S. Nikolopoulos, Cell-SWat: modeling and scheduling wavefront computations on the cell broadband engine, Proceedings of the 2008 conference on Computing frontiers, May 05-07, 2008, Ischia, Italy [doi>10.1145/1366230.1366235]
• 2: J. Balart, M. González, X. Martorell, E. Ayguadé, Z. Sura, T. Chen, T. Zhang, K. O'Brien, and K. M. O'Brien. A Novel Asynchronous Software Cache Implementation for the Cell-BE Processor. In Proc. of the 20th International Workshop on Languages and Compilers for Parallel Computing, LNCS Vol. 5234, pages 125--140, Oct. 2007.
• 3: Pieter Bellens , Josep M. Perez , Rosa M. Badia , Jesus Labarta, CellSs: a programming model for the cell BE architecture, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188546]
• 4: W. P. L. Carter. Documentation Of The Saprc-99 Chemical Mechanism For Voc Reactivity Assessment. Final Report Contract No. 92-329, California Air Resources Board, May 8 2000.
• 5: T. Chen , R. Raghavan , J. N. Dale , E. Iwata, Cell broadband engine architecture and its first implementation: a performance view, IBM Journal of Research and Development, v.51 n.5, p.559-572, September 2007
• 6: T. Chen, Z. Sura, K. M. O'Brien, and J. K. O'Brien. Optimizing the Use of Static Buffers for DMA on a CELL Chip. In Languages and Compilers for Parallel Computing, 19th International Workshop (LCPC), pages 314--329, 2006.
• 7: Catherine H. Crawford , Paul Henning , Michael Kistler , Cornell Wright, Accelerating computing with the cell broadband engine processor, Proceedings of the 2008 conference on Computing frontiers, May 05-07, 2008, Ischia, Italy [doi>10.1145/1366230.1366234]
• 8: William J. Dally , Francois Labonte , Abhishek Das , Patrick Hanrahan , Jung-Ho Ahn , Jayanth Gummaraju , Mattan Erez , Nuwan Jayasena , Ian Buck , Timothy J. Knight , Ujval J. Kapasi, Merrimac: Supercomputing with Streams, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.35, November 15-21, 2003
• 9: A. Duran, J. M. Perez, E. Ayguade, R. M. Badia, and J. Labarta. Extending the OpenMP Tasking Model to Allow Dependent Tasks. In OpenMP in a New Era of Parallelism, Proceedings of the 4th International Workshop on OpenMP, LNCS Vol. 5004, pages 111--122, July 2008.
• 10: Kayvon Fatahalian , Daniel Reiter Horn , Timothy J. Knight , Larkhoon Leem , Mike Houston , Ji Young Park , Mattan Erez , Manman Ren , Alex Aiken , William J. Dally , Pat Hanrahan, Sequoia: programming the memory hierarchy, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188543]
• 11: Xizhou Feng , Kirk W. Cameron , Duncan A. Buell, PBPI: a high performance implementation of Bayesian phylogenetic inference, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188535]
• 12: Michael I. Gordon , William Thies , Saman Amarasinghe, Exploiting coarse-grained task, data, and pipeline parallelism in stream programs, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 13: Jayanth Gummaraju , Joel Coburn , Yoshio Turner , Mendel Rosenblum, Streamware: programming general-purpose multicore processors using streams, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 14: W. Hundsdorfer. Numerical Solution of Advection-Diffusion-Reaction Equations. Technical report, Centrum voor Wiskunde en Informatica, 1996.
• 15: IBM Corporation. Software development kit for multi-core acceleration version 3.0. Oct. 2007.
• 16: D. Jimenez-Gonzalez, X. Martorell, and A. Ramirez. Performance Analysis of Cell Broadband Engine for High Memory Bandwidth Applications. Performance Analysis of Systems & Software, 2007. ISPASS 2007. IEEE International Symposium on, pages 210--219, April 2007.
• 17: John C. Linford , Adrian Sandu, Optimizing large scale chemical transport models for multicore platforms, Proceedings of the 2008 Spring simulation multiconference, April 14-17, 2008, Ottawa, Canada
• 18: Tim Mattson, Introduction to OpenMP, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188673]
• 19: Michael D. McCool , Bruce D'Amora, Programming using RapidMind on the Cell BE, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188686]
• 20: Nicholas Mitchell , Larry Carter , Jeanne Ferrante, Localizing Non-Affine Array References, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.192, October 12-16, 1999
• 21: J. D. Owens, M. Houston, D. Luebke, S. Green, J. E. Stone, and J. C. Phillips. GPU Computing. Proceedings of the IEEE, 95(6):879--899, May 2008.
• 22: B. Rose. Cellstream. http://www.cs.vt.edu/~bar234/cellstream.
• 23: Adrian Sandu , Dacian N. Daescu , Gregory R. Carmichael , Tianfeng Chai, Adjoint sensitivity analysis of regional air quality models, Journal of Computational Physics, v.204 n.1, p.222-252, 20 March 2005 [doi>10.1016/j.jcp.2004.10.011]
• 24: Perry H. Wang , Jamison D. Collins , Gautham N. Chinya , Hong Jiang , Xinmin Tian , Milind Girkar , Nick Y. Yang , Guei-Yuan Lueh , Hong Wang, EXOCHI: architecture and programming environment for a heterogeneous multi-core multithreaded system, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

General Terms:
Design, Languages

Keywords:
cell be, explicitly managed memory hierarchies, programming models