Optimizing matrix multiply using PHiPAC

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology

Full text

Pdf (1.44 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 11th international conference on Supercomputing table of contents

Vienna, Austria

Pages: 340 - 347

Year of Publication: 1997

ISBN:0-89791-902-5

Authors

Jeff Bilmes	CS Division, University of California at Berkeley, Berkeley, CA and International Computer Science Institute, Berkeley, CA
Krste Asanovic	CS Division, University of California at Berkeley, Berkeley, CA and International Computer Science Institute, Berkeley, CA
Chee-Whye Chin	CS Division, University of California at Berkeley, Berkeley, CA and International Computer Science Institute, Berkeley, CA
Jim Demmel	CS Division, University of California at Berkeley, Berkeley, CA and International Computer Science Institute, Berkeley, CA

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 52, Citation Count: 69

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/263580.263662 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.

	ABB+92	E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
	ACF95	B. Alpern , L. Carter , J. Ferrante, Space-limited procedures: a methodology for portable high-performance, Proceedings of the conference on Programming Models for Massively Parallel Computers, p.10, October 09-12, 1995
	AGZ94	R. Agarwal, F. Gustavson, and M. Zuber. IBM Engineering and Scientific Subroutine Library Guide and Reference, 1994. Available through IBM branch offices.
	BAD+	J. Bilmes, K. Asanoic J. Demmd, D. Lain, and C.Wo Chin. The PHiPAC WWW home page. http://www.icsi.berkely.edu/~bilmes/phipac
	BAD+96	J. Bilmes , K. Asanovic , Jim Demmel , D. L %A , C. Chin, Optimizing Matrix Multiply using PHiPAC: a Portable,High-Performance, ANSI C Coding Methodology, University of Tennessee, Knoxville, TN, 1996
	BLL93	B.Kagstorm, P. Ling, and C. Van Loan. Portable high performance GEMM-based level 3 BLAS. In R.F. Sincovec et M., editor, Parallel Processing for Scientific Computing, pages 339-346, Phfladdphia, 1993. SIAM Pubficafions.
	BLS91	David H. Bailey , King Lee , Horst D. Simon, Using Strassen's algorithm to accelerate the solution of linear systems, The Journal of Supercomputing, v.4 n.4, p.357-371, 1990 [doi>10.1007/BF00129836]
	CDD+96	J. Choi , J. Demmel , I. Dhillon , J. Dongarra , S. Ostrouchov , A. Petitet , K. Staney , D. Walker , R. C. Whaley, LAPACK Working Note 95: ScaLAPACK: A Portable Linear Algebra Library for Distributed Memory Computers -- Design Issues and Performance, University of Tennessee, Knoxville, TN, 1995
	CFH95	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
	DCDH90	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]
	DCHHS88	Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
	GL89	G.H. Gdub and C.F. Van Loan. Matrix Computations. Johns Hopkins University Press, 1989.
	KHM94	Chandrika Kamath , Roy Ho , Dwight P. Manley, DXML: a high-performance scientific subroutine library, Digital Technical Journal, v.6 n.3, p.44-56, Summer 1994
	LHKK79	C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
	LRW91	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
	MS95	John McCalpin , Mark Smotherman, Automatic benchmark generation for cache optimization of matrix operations, Proceedings of the 33rd annual on Southeast regional conference, March 17-18, 1995, Clemson, South Carolina [doi>10.1145/1122018.1122054]
	SMP+96	Rafael H. Saavedra-Barrera , Weihua Mao , Daeyeon Park , Jacqueline Chame , Sungdo Moon, The Combined Effectiveness of Unimodular Transformations, Tiling, and Software Prefetching, Proceedings of the 10th International Parallel Processing Symposium, p.39-45, April 15-19, 1996
	WL91	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
	Wol96	Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995

CITED BY 69

	Jianxin Xiong , Jeremy Johnson , Robert Johnson , David Padua, SPL: a language and compiler for DSP algorithms, ACM SIGPLAN Notices, v.36 n.5, p.298-308, May 2001
	Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive array layouts and fast parallel matrix multiplication, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.222-231, June 27-30, 1999, Saint Malo, France
	R. Clint Whaley , Jack J. Dongarra, Automatically tuned linear algebra software, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-27, November 07-13, 1998, San Jose, CA
	Bjarne Stig Andersen , Jerzy Waśniewski , Fred G. Gustavson, A recursive formulation of Cholesky factorization of a matrix in packed storage, ACM Transactions on Mathematical Software (TOMS), v.27 n.2, p.214-244, June 2001
	Enrique S. Quintana-Ortí , Robert A. van de Geijn, Formal derivation of algorithms: The triangular sylvester equation, ACM Transactions on Mathematical Software (TOMS), v.29 n.2, p.218-243, June 2003
	Richard Vuduc , James W. Demmel , Katherine A. Yelick , Shoaib Kamil , Rajesh Nishtala , Benjamin Lee, Performance optimizations and bounds for sparse matrix-vector multiply, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-35, November 16, 2002, Baltimore, Maryland
	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
	Thomas Rauber , Gudula Rüger, Optimizing locality for ODE solvers, Proceedings of the 15th international conference on Supercomputing, p.123-132, June 2001, Sorrento, Italy
	Shigeo Itou , Satoshi Matsuoka , Hirokazu Hasegawa, AJaPACK: experiments in performance portable parallel Java numerical libraries, Proceedings of the ACM 2000 conference on Java Grande, p.140-149, June 03-04, 2000, San Francisco, California, United States
	Michael A. Bender , Giridhar Pemmasani , Steven Skiena , Pavel Sumazin, Finding least common ancestors in directed acyclic graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.845-854, January 07-09, 2001, Washington, D.C., United States
	Christian Weiß , Wolfgang Karl , Markus Kowarschik , Ulrich Rüde, Memory characteristics of iterative methods, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.31-es, November 14-19, 1999, Portland, Oregon, United States
	Bryan Singer , Manuela Veloso, Stochastic search for signal processing algorithm optimization, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.22-22, November 10-16, 2001, Denver, Colorado
	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
	Geoff Pike , Paul N. Hilfinger, Better tiling and array contraction for compiling scientific programs, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-12, November 16, 2002, Baltimore, Maryland
	Gerald Baumgartner , David E. Bernholdt , Daniel Cociorva , Robert Harrison , So Hirata , Chi-Chung Lam , Marcel Nooijen , Russell Pitzer , J. Ramanujam , P. Sadayappan, A high-level approach to synthesis of high-performance codes for quantum chemistry, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-10, November 16, 2002, Baltimore, Maryland
	Jeremy D. Frens , David S. Wise, QR factorization with Morton-ordered quadtree matrices for memory re-use and parallelism, ACM SIGPLAN Notices, v.38 n.10, October 2003
	Zizhong Chen , Jack Dongarra , Piotr Luszczek , Kenneth Roche, Self-adapting software for numerical linear algebra and LAPACK for clusters, Parallel Computing, v.29 n.11-12, p.1723-1743, November/December 2003
	Matthias Korch , Thomas Rauber , Gudula Rünger, Performance optimization of RK methods using block-based pipelining, Performance analysis and grid computing, Kluwer Academic Publishers, Norwell, MA, 2004
	Michael A. Bender , Martín Farach-Colton , Giridhar Pemmasani , Steven Skiena , Pavel Sumazin, Lowest common ancestors in trees and directed acyclic graphs, Journal of Algorithms, v.57 n.2, p.75-94, November 2005
	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
	Sato Hiroyuki, Array form representation of idiom recognition system for numerical programs, ACM SIGAPL APL Quote Quad, v.31 n.2, p.87-98, December 2000
	F. G. Gustavson, High-performance linear algebra algorithms using new generalized data structures for matrices, IBM Journal of Research and Development, v.47 n.1, p.31-55, January 2003
	Dror Irony , Gil Shklarski , Sivan Toledo, Parallel and fully recursive multifrontal sparse Cholesky, Future Generation Computer Systems, v.20 n.3, p.425-440, April 2004
	Dror Irony , Sivan Toledo , Alexander Tiskin, Communication lower bounds for distributed-memory matrix multiplication, Journal of Parallel and Distributed Computing, v.64 n.9, p.1017-1026, September 2004
	Matteo Frigo, A fast Fourier transform compiler, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Sascha Hunold , Thomas Rauber , Gudula Rünger, Multilevel hierarchical matrix multiplication on clusters, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
	Javier Cuenca , Domingo Giménez , José González, Architecture of an automatically tuned linear algebra library, Parallel Computing, v.30 n.2, p.187-210, February 2004
	Takahiro Katagiri , Kenji Kise , Hiroki Honda , Toshitsugu Yuba, Effect of auto-tuning with user's knowledge for numerical software, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy
	Steven T. Gabriel , David S. Wise, The Opie compiler from row-major source to Morton-ordered matrices, Proceedings of the 3rd workshop on Memory performance issues: in conjunction with the 31st international symposium on computer architecture, p.136-144, June 20-20, 2004, Munich, Germany
	Markus Püschel , José M. F. Moura , Bryan Singer , Jianxin Xiong , Jeremy Johnson , David Padua , Manuela Veloso , Robert W. Johnson, Spiral: A Generator for Platform-Adapted Libraries of Signal Processing Algorithms, International Journal of High Performance Computing Applications, v.18 n.1, p.21-45, February 2004
	Ahmad Faraj , Xin Yuan, Automatic generation and tuning of MPI collective communication routines, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts
	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
	Kenneth Barr , Krste Asanović, Energy aware lossless data compression, Proceedings of the 1st international conference on Mobile systems, applications and services, p.231-244, May 05-08, 2003, San Francisco, California
	Mahmut Kandemir , Alok Choudhary , J. Ramanujam , Prith Banerjee, Reducing False Sharing and Improving Spatial Locality in a Unified Compilation Framework, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.337-354, April 2003
	David Parello , Olivier Temam , Jean-Marie Verdun, On increasing architecture awareness in program optimizations to bridge the gap between peak and sustained processor performance: matrix-multiply revisited, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-11, November 16, 2002, Baltimore, Maryland
	Karin Högstedt , Larry Carter , Jeanne Ferrante, On the Parallel Execution Time of Tiled Loops, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.307-321, March 2003
	Richard Vuduc , James W. Demmel , Jeff A. Bilmes, Statistical Models for Empirical Search-Based Performance Tuning, International Journal of High Performance Computing Applications, v.18 n.1, p.65-94, February 2004
	P. M. W. Knijnenburg , T. Kisuki , M. F. P. O'Boyle, Iterative compilation, Embedded processor design challenges: systems, architectures, modeling, and simulation-SAMOS, Springer-Verlag New York, Inc., New York, NY, 2002
	Takahiro Katagiri , Kenji Kise , Hiroki Honda , Toshitsugu Yuba, ABCLibScript: a directive to support specification of an auto-tuning facility for numerical software, Parallel Computing, v.32 n.1, p.92-112, January 2006
	Takahiro Katagiri , Kenji Kise , Hiroki Honda , Toshitsugu Yuba, ABCLib_DRSSED: a parallel eigensolver with an auto-tuning facility, Parallel Computing, v.32 n.3, p.231-250, March 2006
	Matthias Korch , Thomas Rauber, Optimizing locality and scalability of embedded Runge-Kutta solvers using block-based pipelining, Journal of Parallel and Distributed Computing, v.66 n.3, p.444-468, March 2006
	J. Dongarra , G. Bosilca , Z. Chen , V. Eijkhout , G. E. Fagg , E. Fuentes , J. Langou , P. Luszczek , J. Pjesivac-Grbovic , K. Seymour , H. You , S. S. Vadhiyar, Self-adapting numerical software (SANS) effort, IBM Journal of Research and Development, v.50 n.2/3, p.223-238, March 2006
	Paweł Hitczenko , Jeremy R. Johnson , Hung-Jen Huang, Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform, Theoretical Computer Science, v.352 n.1, p.8-30, 7 March 2006
	Apan Qasem , Ken Kennedy , John Mellor-Crummey, Automatic tuning of whole applications using direct search and a performance-based transformation system, The Journal of Supercomputing, v.36 n.2, p.183-196, May 2006
	Yoon-Ju Lee , Pedro C. Diniz , Mary W. Hall , Robert Lucas, Empirical optimization for a sparse linear solver: a case study, International Journal of Parallel Programming, v.33 n.2, p.165-181, June 2005
	Paolo Bientinesi , Brian Gunter , Robert A. van de Geijn, Families of algorithms related to the inversion of a Symmetric Positive Definite matrix, ACM Transactions on Mathematical Software (TOMS), v.35 n.1, p.1-22, July 2008
	Lamia Youseff , Keith Seymour , Haihang You , Jack Dongarra , Rich Wolski, The impact of paravirtualized memory hierarchy on linear algebra computational kernels and software, Proceedings of the 17th international symposium on High performance distributed computing, June 23-27, 2008, Boston, MA, USA
	Lakshminarayanan Renganarayana , Sanjay Rajopadhye, A Geometric Programming Framework for Optimal Multi-Level Tiling, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.18, November 06-12, 2004
	Jeremy Lau , Matthew Arnold , Michael Hind , Brad Calder, Online performance auditing: using hot optimizations without getting burned, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Apan Qasem , Ken Kennedy, Profitable loop fusion and tiling using model-driven empirical search, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
	Ahmad Faraj , Xin Yuan , David Lowenthal, STAR-MPI: self tuned adaptive routines for MPI collective operations, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
	Kenneth C. Barr , Krste Asanović, Energy-aware lossless data compression, ACM Transactions on Computer Systems (TOCS), v.24 n.3, p.250-291, August 2006
	Matthew Curtis-Maury , Christos D. Antonopoulos , Dimitrios S. Nikolopoulos, A comparison of online and offline strategies for program adaptation, Proceedings of the 45th annual southeast regional conference, March 23-24, 2007, Winston-Salem, North Carolina
	Thomas Rauber , Gudula Rünger, Improving locality for ODE solvers by program transformations, Scientific Programming, v.12 n.3, p.133-154, August 2004
	Xiaoming Li , Maria Jesus Garzaran , David Padua, Optimizing Sorting with Genetic Algorithms, Proceedings of the international symposium on Code generation and optimization, p.99-110, March 20-23, 2005
	Chun Chen , Jacqueline Chame , Mary Hall, Combining Models and Guided Empirical Search to Optimize for Multiple Levels of the Memory Hierarchy, Proceedings of the international symposium on Code generation and optimization, p.111-122, March 20-23, 2005
	Nicholas Mitchell , Karin Högstedt , Larry Carter , Jeanne Ferrante, Quantifying the Multi-Level Nature of Tiling Interactions, International Journal of Parallel Programming, v.26 n.6, p.641-670, December 1998
	S. Hunold , T. Rauber , G. Rünger, Combining building blocks for parallel multi-level matrix multiplication, Parallel Computing, v.34 n.6-8, p.411-426, July, 2008
	Muthu Manikandan Baskaran , Uday Bondhugula , Sriram Krishnamoorthy , J. Ramanujam , Atanas Rountev , P. Sadayappan, Automatic data movement and computation mapping for multi-level parallel architectures with explicitly managed memories, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	DaeGon Kim , Lakshminarayanan Renganarayanan , Dave Rostron , Sanjay Rajopadhye , Michelle Mills Strout, Multi-level tiling: M for the price of one, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada
	Carsten Scholtes, A method to derive the cache performance of irregular applications on machines with direct mapped caches, International Journal of Computational Science and Engineering, v.1 n.2-4, p.157-174, May 2005
	Armando Solar-Lezama , Christopher Grant Jones , Rastislav Bodik, Sketching concurrent data structures, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Lakshminarayanan Renganarayana , Sanjay Rajopadhye, Positivity, posynomials and tile size selection, Proceedings of the 2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008, Austin, Texas
	Manman Ren , Ji Young Park , Mike Houston , Alex Aiken , William J. Dally, A tuning framework for software-managed memory hierarchies, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada
	Paolo D'Alberto , Alexandru Nicolau, Adaptive Winograd's matrix multiplications, ACM Transactions on Mathematical Software (TOMS), v.36 n.1, p.1-23, March 2009
	R. Clint Whaley , Anthony M. Castaldo, Achieving accurate and context-sensitive timing for code optimization, Software—Practice & Experience, v.38 n.15, p.1621-1642, December 2008
	Hans Zima , Mary Hall , Chun Chen , Jaqueline Chame, Model-guided autotuning of high-productivity languages for petascale computing, Proceedings of the 18th ACM international symposium on High performance distributed computing, p.151-166, June 11-13, 2009, Garching, Germany
	Jason Ansel , Cy Chan , Yee Lok Wong , Marek Olszewski , Qin Zhao , Alan Edelman , Saman Amarasinghe, PetaBricks: a language and compiler for algorithmic choice, ACM SIGPLAN Notices, v.44 n.6, June 2009
	Lamia Youseff , Keith Seymour , Haihang You , Dmitrii Zagorodnov , Jack Dongarra , Rich Wolski, Paravirtualization effect on single- and multi-threaded memory-intensive linear algebra software, Cluster Computing, v.12 n.2, p.101-122, June 2009