Multi-threading and one-sided communication in parallel LU factorization

ABSTRACT

Dense LU factorization has a high ratio of computation to communication and, as evidenced by the High Performance Linpack (HPL) benchmark, this property makes it scale well on most parallel machines. Nevertheless, the standard algorithm for this problem has non-trivial dependence patterns which limit parallelism, and local computations require large matrices in order to achieve good single processor performance. We present an alternative programming model for this type of problem, which combines UPC's global address space with lightweight multithreading. We introduce the concept of memory-constrained lookahead where the amount of concurrency managed by each processor is controlled by the amount of memory available. We implement novel techniques for steering the computation to optimize for high performance and demonstrate the scalability and portability of UPC with Teraflop level performance on some machines, comparing favourably to other state-of-the-art MPI codes.

REFERENCES

• 1: Atul Adya , Jon Howell , Marvin Theimer , William J. Bolosky , John R. Douceur, Cooperative Task Management Without Manual Stack Management, Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, p.289-302, June 10-15, 2002
• 2: Allen E., Chase D., Hallett J., Luchangco V., Maessen J.-W., Ryu S., Steele G. L., and Tobin-Hochstadt S. The Fortress Language Specification, 2007. Available at http://research.sun.com/projects/plrg/Publications/index.html
• 3: Bailey D. Little's Law and High Performance Computing, 1997. Available at: http://crd.lbl.gov/~dhbailey/dhbpapers/little.pdf
• 4: An updated set of basic linear algebra subprograms (BLAS), ACM Transactions on Mathematical Software (TOMS), v.28 n.2, p.135-151, June 2002 [doi>10.1145/567806.567807]
• 5: Robert D. Blumofe , Charles E. Leiserson, Space-Efficient Scheduling of Multithreaded Computations, SIAM Journal on Computing, v.27 n.1, p.202-229, Feb. 1998 [doi>10.1137/S0097539793259471]
• 6: Dan Bonachea, GASNet Specification, v1.1, University of California at Berkeley, Berkeley, CA, 2002
• 7: Bonachea D. Proposal for Extending the UPC Memory Copy Library Functions and Supporting Extensions to GASNet, v1.0. Lawrence Berkeley National Laboratory Technical Report LBNL-54983, 2004.
• 8: Buttari A., Dongarra J., Kurzak J., Langou J., Luszczek P., and Tomov S. The Impact of Multicore on Math Software. In Proceedings of PARA 2006, Umeå, Sweden, June 2006.
• 9: Buttari A., Langou J., Kurzak J., and Dongarra J. Parallel Tiled QR Factorization for Multicore Architectures. Technical Report UT-CS-07-598, University of Tennessee, Computer Science Department, July 2007. Also published as LAPACK Working Note 190.
• 10: Callahan D., Chamberlain B. L., and Zima, H. P. The Cascade High Productivity Language. In Proceedings of the 9th International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS 2004), 52--60, IEEE Computer Society, 2004.
• 11: Parry Husbands , Costin Iancu , Katherine Yelick, A performance analysis of the Berkeley UPC compiler, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782825]
• 12: Jaeyoung Choi , Jack J. Dongarra , L. Susan Ostrouchov , Antoine P. Petitet , David W. Walker , R. Clint Whaley, Design and implementation of the ScaLAPACK LU, QR, and Cholesky factorization routines, Scientific Programming, v.5 n.3, p.173-184, Fall 1996
• 13: Ebcioglu K., Saraswat V., and Sarkar, V. X10: an Experimental Language for High Productivity Programming of Scalable Systems. In Proceedings of the P-PHEC 2005 Workshop, held in conjunction with HPCA 2005, 2005.
• 14: Tarek El-Ghazawi , William Carlson , Thomas Sterling , Katherine Yelick, UPC: Distributed Shared-Memory Programming, Wiley-Interscience, 2003
• 15: Ralf S. Engelschall, Portable multithreading: the signal stack trick for user-space thread creation, Proceedings of the annual conference on USENIX Annual Technical Conference, p.20-20, June 18-23, 2000, San Diego, California
• 16: Golub G. and Van Loan, C. Matrix Computations. Johns Hopkins University Press, 1996.
• 17: Goto K. and van de Geijn R. On reducing TLB misses in matrix multiplication. Technical Report TR-2002-55, The University of Texas at Austin, Department of Computer Sciences, 2002. Also published as FLAME Working Note #9.
• 18: Attila Gürsoy , Laxmikant V. Kale, Performance and modularity benefits of message-driven execution, Journal of Parallel and Distributed Computing, v.64 n.4, p.461-480, April 2004 [doi>10.1016/j.jpdc.2004.03.006]
• 19: F. G. Gustavson, Recursion leads to automatic variable blocking for dense linear-algebra algorithms, IBM Journal of Research and Development, v.41 n.6, p.737-756, Nov. 1997
• 20: HPC Challenge Benchmark Page. Available at: http://icl.cs.utk.edu/hpcc/
• 21: Laxmikant V. Kale , Sanjeev Krishnan, CHARM++: a portable concurrent object oriented system based on C++, ACM SIGPLAN Notices, v.28 n.10, p.91-108, Oct. 1, 1993
• 22: Kurzak J. and Dongarra J. Implementing Linear Algebra Routines on Multi-Core Processors with Pipelining and a Look Ahead. Technical Report UT-CS-06-581, University of Tennessee, Computer Science Department, 2006. Also published as LAPACK Working Note 178.
• 23: Lewis B. and Richards K. LU Factorization Case Study Using FAST: Dataflow Parallelism with the Forte Application Scalability Tool. 2003. Available at: http://developers.sun.com/prodtech/cc/articles/FAST/lu_content.html
• 24: Xiaoye S. Li , James W. Demmel, SuperLU_DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Transactions on Mathematical Software (TOMS), v.29 n.2, p.110-140, June 2003 [doi>10.1145/779359.779361]
• 25: Lin H.-Y. and Luszczek P. Tuning LINPACK N*N for PARISC Platforms. Presented at the 2001 High Performance Computing on Hewlett-Packard Systems Conference, 2001.
• 26: Piotr R Luszczek , David H Bailey , Jack J Dongarra , Jeremy Kepner , Robert F Lucas , Rolf Rabenseifner , Daisuke Takahashi, The HPC Challenge (HPCC) benchmark suite, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188677]
• 27: Makoto Matsumoto , Takuji Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.3-30, Jan. 1998 [doi>10.1145/272991.272995]
• 28: R. S. Nikhil, Can dataflow subsume von Neumann computing?, Proceedings of the 16th annual international symposium on Computer architecture, p.262-272, April 1989, Jerusalem, Israel
• 29: Panziera J.-P. and Baron J. A Highly Efficient Linpack Implementation Based on Shared-Memory Parallelism. In Proceedings of the 2005 International Supercomputer Conference, 2005.
• 30: Gregory M. Papadopoulos , Kenneth R. Traub, Multithreading: a revisionist view of dataflow architectures, Proceedings of the 18th annual international symposium on Computer architecture, p.342-351, May 27-30, 1991, Toronto, Ontario, Canada
• 31: Eric S. Raymond, The new hacker's dictionary (3rd ed.), MIT Press, Cambridge, MA, 1996
• 32: Marc Snir , Steve W. Otto , David W. Walker , Jack Dongarra , Steven Huss-Lederman, MPI: The Complete Reference, MIT Press, Cambridge, MA, 1995
• 33: The Top 500 Supercomputer Sites. Available at: http://www.top500.org, 2007.
• 34: UPC Consortium. UPC Language Specifications, v1.2. Available at: http://upc.lbl.gov/docs/user/upc_spec_1.2.pdf, 2005.

INDEX TERMS

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

General Terms:
Algorithms, Languages, Performance

Keywords:
dense linear algebra, latency tolerance, multithreading