The potential of the cell processor for scientific computing

ABSTRACT

The slowing pace of commodity microprocessor performance improvements combined with ever-increasing chip power demands has become of utmost concern to computational scientists. As a result, the high performance computing community is examining alternative architectures that address the limitations of modern cache-based designs. In this work, we examine the potential of using the forthcoming STI Cell processor as a building block for future high-end computing systems. Our work contains several novel contributions. First, we introduce a performance model for Cell and apply it to several key scientific computing kernels: dense matrix multiply, sparse matrix vector multiply, stencil computations, and 1D/2D FFTs. The difficulty of programming Cell, which requires assembly level intrinsics for the best performance, makes this model useful as an initial step in algorithm design and evaluation. Next, we validate the accuracy of our model by comparing results against published hardware results, as well as our own implementations on the Cell full system simulator. Additionally, we compare Cell performance to benchmarks run on leading superscalar (AMD Opteron), VLIW (Intel Itanium2), and vector (Cray X1E) architectures. Our work also explores several different mappings of the kernels and demonstrates a simple and effective programming model for Cell's unique architecture. Finally, we propose modest microarchitectural modifications that could significantly increase the efficiency of double-precision calculations. Overall results demonstrate the tremendous potential of the Cell architecture for scientific computations in terms of both raw performance and power efficiency.

REFERENCES

• 1: Guy E. Blelloch , Michael A. Heroux , Marco Zagha, Segmented Operations for Sparse Matrix Computation on Vector Multiprocessors, Carnegie Mellon University, Pittsburgh, PA, 1993
• 2: Cactus homepage. http://www.cactuscode.org.
• 3: Lynn Elliot Cannon, A cellular computer to implement the kalman filter algorithm, 1969
• 4: Cell broadband engine architecture and its first implementation. http://www-128.ibm.com/developerworks/power/library/pa-cellperf/.
• 5: Chombo homepage. http://seesar.lbl.gov/anag/chombo.
• 6: E. D'Azevedo, M. R. Fahey, and R. T. Mills. Vectorized sparse matrix multiply for compressed row storage format. In International Conference on Computational Science (ICCS), pages 99--106, 2005.
• 7: FFTW speed tests. http://www.fftw.org.
• 8: B. Flachs, S. Asano, S. Dhong, et al. A streaming processor unit for a cell processor. ISSCC Dig. Tech. Papers, pages 134--135, February 2005.
• 9: Poletti Francesco , Paul Marchal , David Atienza , Luca Benini , Francky Catthoor , Jose M. Mendias, An integrated hardware/software approach for run-time scratchpad management, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996634]
• 10: Ibm cell specifications. http://www.research.ibm.com/cell/home.html.
• 11: Eun-Jin Im , Katherine Yelick , Richard Vuduc, Sparsity: Optimization Framework for Sparse Matrix Kernels, International Journal of High Performance Computing Applications, v.18 n.1, p.135-158, February 2004 [doi>10.1177/1094342004041296]
• 12: The Berkeley Intelligent RAM (IRAM) Project. http://iram.cs.berkeley.edu.
• 13: Guohua Jin , John Mellor-Crummey , Robert Fowler, Increasing temporal locality with skewing and recursive blocking, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.43-43, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582077]
• 14: 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
• 15: Shoaib Kamil , Parry Husbands , Leonid Oliker , John Shalf , Katherine Yelick, Impact of modern memory subsystems on cache optimizations for stencil computations, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois [doi>10.1145/1111583.1111589]
• 16: M. Kandemir , J. Ramanujam , J. Irwin , N. Vijaykrishnan , I. Kadayif , A. Parikh, Dynamic management of scratch-pad memory space, Proceedings of the 38th conference on Design automation, p.690-695, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379049]
• 17: P. Keltcher, S. Richardson, S. Siu, et al. An equal area comparison of embedded dram and sram memory architectures for a chip multiprocessor. Technical report, HP Laboratories, April 2000.
• 18: Brucek Khailany , William J. Dally , Ujval J. Kapasi , Peter Mattson , Jinyung Namkoong , John D. Owens , Brian Towles , Andrew Chang , Scott Rixner, Imagine: Media Processing with Streams, IEEE Micro, v.21 n.2, p.35-46, March 2001 [doi>10.1109/40.918001]
• 19: M. Kondo, H. Okawara, H. Nakamura, et al. Scima: A novel processor architecture for high performance computing. In 4th International Conference on High Performance Computing in the Asia Pacific Region, volume 1, May 2000.
• 20: Atsushi Kunimatsu , Nobuhiro Ide , Toshinori Sato , Yukio Endo , Hiroaki Murakami , Takayuki Kamei , Masashi Hirano , Fujio Ishihara , Haruyuki Tago , Masaaki Oka , Akio Ohba , Teiji Yutaka , Toyoshi Okada , Masakazu Suzuoki, Vector Unit Architecture for Emotion Synthesis, IEEE Micro, v.20 n.2, p.40-47, March 2000 [doi>10.1109/40.848471]
• 21: Zhiyuan Li , Yonghong Song, Automatic tiling of iterative stencil loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.6, p.975-1028, November 2004 [doi>10.1145/1034774.1034777]
• 22: Christian Jacobi , Hwa-Joon Oh , Kevin D. Tran , Scott R. Cottier , Brad W. Michael , Hiroo Nishikawa , Yonetaro Totsuka , Tatsuya Namatame , Naoka Yano, The Vector Floating-Point Unit in a Synergistic Processor Element of a CELL Processor, Proceedings of the 17th IEEE Symposium on Computer Arithmetic, p.59-67, June 27-29, 2005 [doi>10.1109/ARITH.2005.45]
• 23: Masaaki Oka , Masakazu Suzuoki, Designing and Programming the Emotion Engine, IEEE Micro, v.19 n.6, p.20-28, November 1999 [doi>10.1109/40.809374]
• 24: L. Oliker, R. Biswas, J. Borrill, et al. A performance evaluation of the Cray X1 for scientific applications. In Proc. 6th International Meeting on High Performance Computing for Computational Science, 2004.
• 25: Ornl cray x1 evaluation. http://www.csm.ornl.gov/~dunigan/cray.
• 26: Neungsoo Park , Bo Hong , Viktor K. Prasanna, Analysis of Memory Hierarchy Performance of Block Data Layout, Proceedings of the 2002 International Conference on Parallel Processing (ICPP'02), p.35, August 18-21, 2002
• 27: D. Pham, S. Asano, M. Bollier, et al. The design and implementation of a first-generation cell processor. ISSCC Dig. Tech. Papers, pages 184--185, February 2005.
• 28: Sony press release. http://www.scei.co.jp/corporate/release/pdf/050517e.pdf.
• 29: M. Suzuoki et al. A microprocessor with a 128-bit cpu, ten floating point macs, four floating-point dividers, and an mpeg-2 decoder. IEEE Solid State Circuits, 34(1), November 1999.
• 30: Use of Local Memory for Efficient Java Execution, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.468, September 23-26, 2001
• 31: Richard Wilson Vuduc , James W. Demmel, Automatic performance tuning of sparse matrix kernels, 2003
• 32: Using Time Skewing to Eliminate Idle Time due to Memory Bandwidth and Network Limitations, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.171, May 01-05, 2000

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Heterogeneous (hybrid) systems
      C.1.4 Parallel Architectures
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Design studies; Modeling techniques

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

General Terms:
Design, Performance

Keywords:
FFT, GEMM, SpMV, cell processor, sparse matrix, stencil, three level memory