Parallel and Cache-Efficient In-Place Matrix Storage Format Conversion
Authors:
Open Access
- 1 April 2012
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 38 (3) , 1-32
Abstract
Techniques and algorithms for efficient in-place conversion to and from standard and blocked matrix storage formats are described. Such functionality is required by numerical libraries that use different data layouts internally. Parallel algorithms and a software package for in-place matrix storage format conversion based on in-place matrix transposition are presented and evaluated. A new algorithm for in-place transposition which efficiently determines the structure of the transposition permutation a priori is one of the key ingredients. It enables effective load balancing in a parallel environment.Keywords
Funding Information
- Vetenskapsrådet (2008-5243)
This publication has 20 references indexed in Scilit:
- Distributed SBP Cholesky factorization algorithms with near-optimal schedulingACM Transactions on Mathematical Software, 2009
- Tiling, block data layout, and memory hierarchy performanceIEEE Transactions on Parallel and Distributed Systems, 2003
- The cache performance and optimizations of blocked algorithmsACM SIGARCH Computer Architecture News, 1991
- Impact of Hierarchical Memory Systems On Linear Algebra Algorithm DesignThe International Journal of Supercomputing Applications, 1988
- Algorithm 513: Analysis of In-Situ Transposition [F1]ACM Transactions on Mathematical Software, 1977
- Algorithm 380: in-situ transposition of a rectangular matrix [F1]Communications of the ACM, 1970
- Algorithm 302: Transpose vector stored arrayCommunications of the ACM, 1967
- A problem in abelian groups, with application to the transposition of a matrix on an electronic computerMathematics of Computation, 1960
- Transposing Matrices in a Digital ComputerThe Computer Journal, 1959
- A Method for Transposing a MatrixJournal of the ACM, 1958