Executing irregular scientific applications on stream architectures

ABSTRACT

The recent emergence of compute-intensive stream processors such as the Cell Broadband Engine, Stanford's Merrimac, and Clear-Speed's CSX600 has made them attractive platforms for scientific high-performance computing. Unstructured mesh and graph applications are an important class of numerical algorithms used in the scientific computing domain, which are particularly challenging for stream architectures. These codes have irregular structures where nodes have a variable number of neighbors, resulting in irregular memory access patterns and irregular control. We study four representative sub-classes of irregular algorithms, including finite-element and finite-volume methods for modeling physical systems, direct methods for n-body problems, and computations involving sparse algebra. We propose a framework for representing the diverse characteristics of these algorithms in the context of the unique properties of stream architectures, and demonstrate it using one representative application from each sub-class. We then develop techniques for mapping the applications onto a stream processor, placing emphasis on data-localization and parallelizations. Our simulations show that efficient stream hardware with restricted control abilities can effectively run challenging irregular applications with, for example, a finite element method and a molecular dynamic code sustaining 69GFLOP/s and 46GFLOP/s (64-bit) respectively using a single chip that measures 12mm on a side and consumes less than 70W in 90nm technology.

REFERENCES

• 1: Jung Ho Ahn , Mattan Erez , William J. Dally, Tradeoff between data-, instruction-, and thread-level parallelism in stream processors, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1274991]
• 2: Jung Ho Ahn , Mattan Erez , William J. Dally, Scatter-Add in Data Parallel Architectures, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.132-142, February 12-16, 2005 [doi>10.1109/HPCA.2005.30]
• 3: Jung Ho Ahn , Mattan Erez , William J. Dally, The design space of data-parallel memory systems, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188540]
• 4: J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
• 5: T. Barth. Simplified discontinuous Galerkin methods for systems of conservation laws with convex extension. In Cockburn, Karniadakis, and Shu, editors, Discontinuous Galerkin Methods, volume 11 of Lecture Notes in Computational Science and Engineering. Springer-Verlag, Heidelberg, 1999.
• 6: Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
• 7: Rajkumar Buyya , David Abramson , Jonathan Giddy, A Case for Economy Grid Architecture for Service Oriented Grid Computing, Proceedings of the 10th Heterogeneous Computing Workshop â"" HCW 2001 (Workshop 1), p.20083.1, April 23-27, 2001
• 8: W. W. Carlson, J. M. Draper, D. E. Culler, K. Yelick, E. Brooks, and K. Warren. Introduction to UPC and language specification. University of California-Berkeley Technical Report: CCS-TR-99-157, 1999.
• 9: John B. Carter , Wilson C. Hsieh , Leigh B. Stoller , Mark Swanson , Lixin Zhang , Sally A. McKee, Impulse: Memory system support for scientific applications, Scientific Programming, v.7 n.3-4, p.195-209, August 1999
• 10: ClearSpeed. CSX600 Datasheet. http://www.clearspeed.com/downloads/CSX600Processor.pdf, 2005.
• 11: Lucian Codrescu , D. Scott Wills , James Meindl, Architecture of the Atlas Chip-Multiprocessor: Dynamically Parallelizing Irregular Applications, IEEE Transactions on Computers, v.50 n.1, p.67-82, January 2001 [doi>10.1109/12.902753]
• 12: 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
• 13: William J. Dally , John W. Poulton, Digital systems engineering, Cambridge University Press, New York, NY, 1998
• 14: E. F. D'Azevedo, M. R. Fahey, and R. T. Mills. Vectorized sparse matrix multiply for compressed row storage format. In proceedings of the 2005 International Conference on Computational Science (ICCS'05), pages 99--106, May 2005.
• 15: Steven J. Deitz , Bradford L. Chamberlain , Sung-Eun Choi , Lawrence Snyder, The design and implementation of a parallel array operator for the arbitrary remapping of data, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 16: S. J. Deitz, B. L. Chamberlain, and L. Snyder. Abstractions for dynamic data distribution. In Ninth International Workshop on High-Level Parallel Programming Models and Supportive Environments, pages 42--51. IEEE Computer Society, 2004.
• 17: G. C. Fox, What have we learnt from using real parallel machines to solve real problems?, Proceedings of the third conference on Hypercube concurrent computers and applications, p.897-955, January 1989, Pasadena, California, United States [doi>10.1145/63047.63048]
• 18: N. Goharian, T. El-Ghazawi, D. Grossman, and A. Chowdhury. On the enhancements of a sparse matrix information retrieval approach. PDPTA, 2000.
• 19: M. Guo. Automatic parallelization and optimization for irregular scientic applications. In 18th International Parallel and Distributed Processing Symposium, 2005.
• 20: H. Han, G. Rivera, and C. Tseng. Software support for improving locality in scientic codes. In Compilers for Parallel Computation, 2000.
• 21: Judith Hippold , Gudula Rünger, Task Pool Teams for Implementing Irregular Algorithms on Clusters of SMPs, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.54.2, April 22-26, 2003
• 22: H. Peter Hofstee, Power Efficient Processor Architecture and The Cell Processor, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.258-262, February 12-16, 2005 [doi>10.1109/HPCA.2005.26]
• 23: Yuan-Shin Hwang , Bongki Moon , Shamik D. Sharma , Ravi Ponnusamy , Raja Das , Joel H. Saltz, Runtime and language support for compiling adaptive irregular programs on distributed-memory machines, Software—Practice & Experience, v.25 n.6, p.597-621, June 1995 [doi>10.1002/spe.4380250603]
• 24: Nuwan Jayasena , Mattan Erez , Jung Ho Ahn , William J. Dally, Stream Register Files with Indexed Access, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.60, February 14-18, 2004 [doi>10.1109/HPCA.2004.10007]
• 25: Ujval J. Kapasi , William J. Dally , Scott Rixner , Peter R. Mattson , John D. Owens , Brucek Khailany, Efficient conditional operations for data-parallel architectures, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.159-170, December 2000, Monterey, California, United States [doi>10.1145/360128.360145]
• 26: Ujval J. Kapasi , Scott Rixner , William J. Dally , Brucek Khailany , Jung Ho Ahn , Peter Mattson , John D. Owens, Programmable Stream Processors, Computer, v.36 n.8, p.54-62, August 2003 [doi>10.1109/MC.2003.1220582]
• 27: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 28: K. Kitagawa, S. Tagaya, Y. Hagihara, and Y. Kanoh. A hardware overview of SX-6 and SX-7 supercomputer. NEC Research and Development, 44(1):27, January 2003.
• 29: C. Koelbel , P. Mehrotra, Compiling Global Name-Space Parallel Loops for Distributed Execution, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.440-451, October 1991 [doi>10.1109/71.97901]
• 30: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 31: James Laudon , Daniel Lenoski, The SGI Origin: a ccNUMA highly scalable server, Proceedings of the 24th annual international symposium on Computer architecture, p.241-251, June 01-04, 1997, Denver, Colorado, United States
• 32: Amy W. Lim , Monica S. Lam, Maximizing parallelism and minimizing synchronization with affine transforms, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.201-214, January 15-17, 1997, Paris, France [doi>10.1145/263699.263719]
• 33: David B. Loveman, Program improvement by source to source transformation, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.140-152, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811548]
• 34: Gregory M. Papadopoulos , David E. Culler, Monsoon: an explicit token-store architecture, ACM SIGARCH Computer Architecture News, v.18 n.3a, p.82-91, June 1990
• 35: D. I. Pullin and D. J. Hill. Computational methods for shock-driven turbulence and les of the richtmyer-meshkov instability. USNCCM, 2003.
• 36: D. Roccatano, R. Bizzarri, G. Chillemi, N. Sanna, and A. D. Nola. Development of a parallel molecular dynamics code on SIMD computers: Algorithm for use of pair list criterion. Journal of Computational Chemistry, 19(7):685--694, 1998.
• 37: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• 38: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 39: Joel H. Salz , Ravi Mirchandaney , Kay Crowley, Run-Time Parallelization and Scheduling of Loops, IEEE Transactions on Computers, v.40 n.5, p.603-612, May 1991 [doi>10.1109/12.88484]
• 40: P. Sanders. Efficient emulation of MIMD behavior on SIMD machines. Technical Report iratr-1995-29, 1995.
• 41: Wei Shu , Min-You Wu, Asynchronous Problems on SIMD Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.6 n.7, p.704-713, July 1995 [doi>10.1109/71.395399]
• 42: J. E. Smith , Greg Faanes , Rabin Sugumar, Vector instruction set support for conditional operations, Proceedings of the 27th annual international symposium on Computer architecture, p.260-269, June 2000, Vancouver, British Columbia, Canada
• 43: T. Sterling, D. Savarese, D. J. Becker, J. E. Dorband, U. A. Ranawake, and C. V. Packer. BEOWULF: A parallel workstation for scientific computation. In Proceedings of the 24th International Conference on Parallel Processing, pages I:11--14, 1995.
• 44: Jimmy Su , Katherine Yelick, Automatic Support for Irregular Computations in a High-Level Language, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.53.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.118]
• 45: Michael Bedford Taylor , Jason Kim , Jason Miller , David Wentzlaff , Fae Ghodrat , Ben Greenwald , Henry Hoffman , Paul Johnson , Jae-Wook Lee , Walter Lee , Albert Ma , Arvind Saraf , Mark Seneski , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs, IEEE Micro, v.22 n.2, p.25-35, March 2002 [doi>10.1109/MM.2002.997877]
• 46: D. van der Spoel, A. R. van Buuren, E. Apol, P. J. Meulenhoff, D. P. Tieleman, A. L. T. M. Sijbers, B. Hess, K. A. Feenstra, E. Lindahl, R. van Drunen, and H. J. C. Berendsen. Gromacs User Manual version 3.1. Nijenborgh 4, 9747 AG Groningen, The Netherlands. Internet: http://www.gromacs.org, 2001.
• 47: 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]
• 48: K. Yelick, L. Semenzato, G. Pike, C. Miyamoto, B. Liblit, A. Krishnamurthy, P. Hilfinger, S. Graham, D. Gay, P. Colella, and A. Aiken. Titanium: A high-performance Java dialect. In ACM 1998 Workshop on Java for High-Performance Network Computing, Stanford, California, 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles

General Terms:
Performance

Keywords:
irregular control, scientific computing, stream processors