Recursive array layouts and fast parallel matrix multiplication

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Recursive array layouts and fast parallel matrix multiplication

Full text

Pdf (1.28 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures table of contents

Saint Malo, France

Pages: 222 - 231

Year of Publication: 1999

ISBN:1-58113-124-0

Authors

Siddhartha Chatterjee	Department of Computer Science, The University of North Carolina, Chapel Hill, NC
Alvin R. Lebeck	Department of Computer Science, Duke University, Durham, NC
Praveen K. Patnala	Department of Computer Science, The University of North Carolina, Chapel Hill, NC
Mithuna Thottethodi	Department of Computer Science, Duke University, Durham, NC

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 64, Citation Count: 28

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/305619.305645 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ioana Banicescu , Susan Flynn Hummel, Balancing processor loads and exploiting data locality in N-body simulations, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.43-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224306]
	2	T. Bially. Space-filling curves: Their generation and their application to bandwidth reduction. IEEE Transactions on Information Theory, IT-15(6):658-664, Nov. 1969.
	3	Jeff Bilmes , Krste Asanovic , Chee-Whye Chin , Jim Demmel, Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology, Proceedings of the 11th international conference on Supercomputing, p.340-347, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263662]
	4	Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
	5	Steve Carr , Kathryn S. McKinley , Chau-Wen Tseng, Compiler optimizations for improving data locality, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.252-262, October 05-07, 1994, San Jose, California, United States
	6	Larry Carter , Jeanne Ferrante , Susan Flynn Hummel, Hierarchical tiling for improved superscalar performance, Proceedings of the 9th International Symposium on Parallel Processing, p.239-245, April 25-28, 1995
	7	Siddhartha Chatterjee , John R. Gilbert , Robert Schreiber , Shang-Hua Teng, Optimal evaluation of array expressions on massively parallel machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.123-156, Jan. 1995 [doi>10.1145/200994.201004]
	8	Michał Cierniak , Wei Li, Unifying data and control transformations for distributed shared-memory machines, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.205-217, June 18-21, 1995, La Jolla, California, United States
	9	David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
	10	J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
	11	Patrick C. Fischer , Robert L. Probert, Efficient Procedures for Using Matrix Algorithms, Proceedings of the 2nd Colloquium on Automata, Languages and Programming, p.413-427, July 29-August 02, 1974
	12	Jeremy D. Frens , David S. Wise, Auto-blocking matrix-multiplication or tracking BLAS3 performance from source code, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.206-216, June 18-21, 1997, Las Vegas, Nevada, United States
	13	M. Frigo and S. G. Johnson. FFTW: An adaptive software architecture for the FFT. In Proceedings oflCASSP'98, volume 3, page 1381, Seattle, WA, 1998. IEEE.
	14	M. E Goodchild and A. W. Grandfield. Optimizing raster storage: an examination of four alternatives. In Proceedings of Auto-Carto 6, volume 1, pages 400-407, Ottawa, Oct. 1983.
	15	Manish Gupta, Automatic data partitioning on distributed memory multicomputers, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
	16	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
	17	Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996
	18	D. Hilbert. 0ber stetige Abbildung einer Linie auf ein Fl~ichensttlck. Mathematische Annalen, 38:459--460, 1891.
	19	M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
	20	Y. Charlie Hu , S. Lennart Johnsson , Shang-Hua Teng, High performance Fortran for highly irregular problems, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.13-24, June 18-21, 1997, Las Vegas, Nevada, United States
	21	S. E Hummel, I. Banicescu, C.-T. Wang, and J. Wein. Load balancing and data locality via fractiling: An experimental study. In Language, Compilers and Run- Time Systems for Scalable Computers. Kluwer Academic Publishers, 1995.
	22	H. V. Jagadish, Linear clustering of objects with multiple attributes, ACM SIGMOD Record, v.19 n.2, p.332-342, Jun. 1990
	23	Ken Kennedy , Ulrich Kremer, Automatic data layout for distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.4, p.869-916, July 1998 [doi>10.1145/291891.291901]
	24	Kathleen Knobe , Joan D. Lukas , Guy L. Stelle, Jr., Data optimization: allocation of arrays to reduce communication on SIMD machines, Journal of Parallel and Distributed Computing, v.8 n.2, p.102-118, February 1990 [doi>10.1016/0743-7315(90)90086-5]
	25	Charles H. Koelbel , David B. Loveman , Robert S. Schreiber , Guy L. Steele, Jr. , Mary E. Zosel, The high performance Fortran handbook, MIT Press, Cambridge, MA, 1994
	26	Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
	27	R. Laurini. Graphical data bases built on Peano space-filling curves. In C. E. Vandoni, editor, Proceedings of the EUROGRAPHICS'85 Conference, pages 327-338, Amsterdam, 1985. North-Holland.
	28	C. E. Leiserson. Personal communication, Aug. 1998.
	29	Mary E. Mace, Memory storage patterns in parallel processing, Kluwer Academic Publishers, Norwell, MA, 1987
	30	M. Morris Mano, Digital Design, Prentice Hall PTR, Upper Saddle River, NJ, 2001
	31	Bongki Moon , H. V. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the clustering properties of Hilbert space-filling curve, University of Maryland at College Park, College Park, MD, 1996
	32	G. Peano. Sur une courbe qui remplit toute une aire plaine. Mathematische Annalen, 36:157-160, 1890.
	33	John R. Pilkington , Scott B. Baden, Dynamic Partitioning of Non-Uniform Structured Workloads with Spacefilling Curves, IEEE Transactions on Parallel and Distributed Systems, v.7 n.3, p.288-300, March 1996 [doi>10.1109/71.491582]
	34	H. Sagan. Space-Filling Curves. Springer-Verlag, 1994. ISBN 0-387-94265-3.
	35	J. P. Singh , T. Joe , J. L. Hennessy , A. Gupta, An empirical comparison of the Kendall Square Research KSR-1 and Stanford DASH multiprocessors, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.214-225, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169699]
	36	V. Strassen. Gaussian elimination is not optimal. Numer. Math., 13:354-356, 1969.
	37	Mithuna Thottethodi , Siddhartha Chatterjee , Alvin R. Lebeck, Tuning Strassen's matrix multiplication for memory efficiency, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-14, November 07-13, 1998, San Jose, CA
	38	M. S. Warren , J. K. Salmon, A parallel hashed Oct-Tree N-body algorithm, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.12-21, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169640]
	40	Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
	41	M. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.655-664, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76337]

CITED BY 28

	Siddhartha Chatterjee , Erin Parker , Philip J. Hanlon , Alvin R. Lebeck, Exact analysis of the cache behavior of nested loops, ACM SIGPLAN Notices, v.36 n.5, p.286-297, May 2001
	Valerio Pascucci , Randall J. Frank, Global static indexing for real-time exploration of very large regular grids, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.2-2, November 10-16, 2001, Denver, Colorado
	Sandeep Sen , Siddhartha Chatterjee, Towards a theory of cache-efficient algorithms, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.829-838, January 09-11, 2000, San Francisco, California, United States
	José E. Moreira , Samuel P. Midkiff , Manish Gupta, A comparison of three approaches to language, compiler, and library support for multidimensional arrays in Java, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.116-125, June 2001, Palo Alto, California, United States
	Siddhartha Chatterjee , Vibhor V. Jain , Alvin R. Lebeck , Shyam Mundhra , Mithuna Thottethodi, Nonlinear array layouts for hierarchical memory systems, Proceedings of the 13th international conference on Supercomputing, p.444-453, June 20-25, 1999, Rhodes, Greece
	Radu Rugina , Martin Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, ACM SIGPLAN Notices, v.35 n.5, p.182-195, May 2000
	G. Almasi , F. G. Gustavson , J. E. Moreira, Design and evaluation of a linear algebra package for Java, Proceedings of the ACM 2000 conference on Java Grande, p.150-159, June 03-04, 2000, San Francisco, California, United States
	Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive Array Layouts and Fast Matrix Multiplication, IEEE Transactions on Parallel and Distributed Systems, v.13 n.11, p.1105-1123, November 2002
	Eunice E. Santos, Parallel Complexity of Matrix Multiplication, The Journal of Supercomputing, v.25 n.2, p.155-175, June 2003
	Chun-Yuan Lin , Yeh-Ching Chung , Jen-Shiuh Liu, Efficient Data Parallel Algorithms for Multidimensional Array Operations Based on the EKMR Scheme for Distributed Memory Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.14 n.7, p.625-639, July 2003
	Venkata K. Pingali , Sally A. McKee , Wilson C. Hseih , John B. Carter, Computation regrouping: restructuring programs for temporal data cache locality, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
	David S. Wise , Jeremy D. Frens , Yuhong Gu , Gregory A. Alexander, Language support for Morton-order matrices, ACM SIGPLAN Notices, v.36 n.7, p.24-33, July 2001
	Sandeep Sen , Siddhartha Chatterjee , Neeraj Dumir, Towards a theory of cache-efficient algorithms, Journal of the ACM (JACM), v.49 n.6, p.828-858, November 2002
	Venkata K. Pingali , Sally A. McKee , Wilson C. Hsieh , John B. Carter, Restructuring computations for temporal data cache locality, International Journal of Parallel Programming, v.31 n.4, p.305-338, August 2003
	Hossam ElGindy , George Ferizis, On improving the memory access patterns during the execution of Strassen's matrix multiplication algorithm, Proceedings of the 27th Australasian conference on Computer science, p.109-115, January 01, 2004, Dunedin, New Zealand
	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
	Radu Rugina , Martin C. Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.2, p.185-235, March 2005
	Chun-Yuan Lin , Jen-Shiuh Liu , Yeh-Ching Chung, Efficient Representation Scheme for Multidimensional Array Operations, IEEE Transactions on Computers, v.51 n.3, p.327-345, March 2002
	Guohua Jin , John Mellor-Crummey, SFCGen: A framework for efficient generation of multi-dimensional space-filling curves by recursion, ACM Transactions on Mathematical Software (TOMS), v.31 n.1, p.120-148, March 2005
	Evangelia Athanasaki , Nectarios Koziris, Fast indexing for blocked array layouts to reduce cache misses, International Journal of High Performance Computing and Networking, v.3 n.5/6, p.417-433, March 2005
	Paolo D'Alberto , Alexandru Nicolau, Adaptive Strassen's matrix multiplication, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington
	Peter Gottschling , David S. Wise , Michael D. Adams, Representation-transparent matrix algorithms with scalable performance, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington
	Kamen Yotov , Tom Roeder , Keshav Pingali , John Gunnels , Fred Gustavson, An experimental comparison of cache-oblivious and cache-conscious programs, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Rezaul Alam Chowdhury , Vijaya Ramachandran, The cache-oblivious gaussian elimination paradigm: theoretical framework, parallelization and experimental evaluation, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Nico Galoppo , Naga K. Govindaraju , Michael Henson , Dinesh Manocha, LU-GPU: Efficient Algorithms for Solving Dense Linear Systems on Graphics Hardware, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.3, November 12-18, 2005
	Chris H. Hamilton , Andrew Rau-Chaplin, Compact Hilbert indices: Space-filling curves for domains with unequal side lengths, Information Processing Letters, v.105 n.5, p.155-163, February, 2008
	Masood Ahmed , Shahid Bokhari, Mapping with Space Filling Surfaces, IEEE Transactions on Parallel and Distributed Systems, v.18 n.9, p.1258-1269, September 2007
	Francesco Silvestri, On the limits of cache-oblivious rational permutations, Theoretical Computer Science, v.402 n.2-3, p.221-233, August, 2008