Combining analytical and empirical approaches in tuning matrix transposition

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Combining analytical and empirical approaches in tuning matrix transposition

Full text

Pdf (274 KB)

Source

PACT archive
Proceedings of the 15th international conference on Parallel architectures and compilation techniques table of contents

Seattle, Washington, USA

SESSION: Application-specific optimizations table of contents

Pages: 233 - 242

Year of Publication: 2006

ISBN:1-59593-264-X

Authors

Qingda Lu	The Ohio State University, Columbus, OH
Sriram Krishnamoorthy	The Ohio State University, Columbus, OH
P. Sadayappan	The Ohio State University, Columbus, OH

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 30, Citation Count: 0

Additional Information:

abstract references 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/1152154.1152190 What is a DOI?

ABSTRACT

Matrix transposition is an important kernel used in many applications. Even though its optimization has been the subject of many studies, an optimization procedure that targets the characteristics of current processor architectures has not been developed. In this paper, we develop an integrated optimization framework that addresses a number of issues, including tiling for the memory hierarchy, effective handling of memory misalignment, utilizing memory subsystem characteristics, and the exploitation of the parallelism provided by the vector instruction sets in current processors. A judicious combination of analytical and empirical approaches is used to determine the most appropriate optimizations. The absence of problem information until execution time is handled by generating multiple versions of the code - the best version is chosen at runtime, with assistance from minimal-overhead inspectors. The approach highlights aspects of empirical optimization that are important for similar computations with little temporal reuse. Experimental results on PowerPC G5 and Intel Pentium 4 demonstrate the effectiveness of the developed framework.

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	Martin F. Berman, A Method for Transposing a Matrix, Journal of the ACM (JACM), v.5 n.4, p.383-384, Oct. 1958 [doi>10.1145/320941.320952]
	2	N. Brenner, ACM Algorithm 467: Matrix Transposition in Place, Communications of the ACM, v.16 n.11, p.692-694, Nov. 1973 [doi>10.1145/355611.355612]
	3	Aaron B. Brown , Margo I. Seltzer, Operating system benchmarking in the wake of lmbench: a case study of the performance of NetBSD on the Intel x86 architecture, Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.214-224, June 15-18, 1997, Seattle, Washington, United States
	4	Larry Carter , Kang Su Gatlin, Towards an Optimal Bit-Reversal Permutation Program, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.544, November 08-11, 1998
	5	S. Chatterjee and S. Sen. Cache-efficient matrix transposition. In HPCA '00: Proceedings of the Sixth International Symposium on High-Performance Computer Architecture, pages 195--205, 2000.
	6	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 [doi>10.1109/CGO.2005.10]
	7	Chris H. Q. Ding, An Optimal Index Reshuffle Algorithm for Multidimensional Arrays and Its Applications for Parallel Architectures, IEEE Transactions on Parallel and Distributed Systems, v.12 n.3, p.306-315, March 2001 [doi>10.1109/71.914776]
	8	Alexandre E. Eichenberger , Peng Wu , Kevin O'Brien, Vectorization for SIMD architectures with alignment constraints, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
	9	K. S. Gatlin , L. Carter, Memory Hierarchy Considerations for Fast Transpose and Bit-Reversals, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.33, January 09-12, 1999
	10	Mahmut Kandemir , Prithviraj Banerjee , Alok Choudhary , J. Ramanujam , Eduard Ayguadé, Static and Dynamic Locality Optimizations Using Integer Linear Programming, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.922-941, September 2001 [doi>10.1109/TPDS.2001.1184186]
	11	M. Kandemir , J. Ramanujam , A. Choudhary , P. Banerjee, A Layout-Conscious Iteration Space Transformation Technique, IEEE Transactions on Computers, v.50 n.12, p.1321-1336, December 2001 [doi>10.1109/TC.2001.970571]
	12	Alexei Kudriavtsev , Peter Kogge, Generation of permutations for SIMD processors, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
	13	Rick Kufrin, Measuring and improving application performance with PerfSuite, Linux Journal, v.2005 n.135, p.4, July 2005
	14	Susan Laflin , M. A. Brebner, Algorithm 380: in-situ transposition of a rectangular matrix [F1], Communications of the ACM, v.13 n.5, p.324-326, May 1970 [doi>10.1145/362349.362368]
	15	J. McCalpin. Memory bandwidth and machine balance in current high performance computers. IEEE Computer Society TCCA Newsletter, Dec. 1995.
	16	Gang Ren , Peng Wu , David Padua, Optimizing data permutations for SIMD devices, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
	17	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
	18	R. C. Whaley, A. Petitet, and J. J. Dongarra. Automated empirical optimization of software and the ATLAS project. Parallel Computing, 27(1-2):3--35, 2001.
	19	David B. Whalley, Tuning High Performance Kernels through Empirical Compilation, Proceedings of the 2005 International Conference on Parallel Processing, p.89-98, June 14-17, 2005 [doi>10.1109/ICPP.2005.77]
	20	K. Yotov, X. Li, G. Ren, M.J.S.Garzaran, D. Padua, K. Pingali, and P. Stodghill. Is search really necessary to generate high-performance BLAS? Proceedings of the IEEE, 93(2):358--386, 2005.
	21	Kamen Yotov , Keshav Pingali , Paul Stodghill, Automatic measurement of memory hierarchy parameters, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
	22	Kamen Yotov , Keshav Pingali , Paul Stodghill, Think globally, search locally, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088168]
	23	Zhao Zhang , Xiaodong Zhang, Fast Bit-Reversals on Uniprocessors and Shared-Memory Multiprocessors, SIAM Journal on Scientific Computing, v.22 n.6, p.2113-2134, 2000 [doi>10.1137/S1064827599359709]