Linear-time matrix transpose algorithms using vector register file with diagonal registers
B. Hanounik, Xiaobo Sharon Hu · 2002
Matrix transpose operation (MT) is used frequently in many multimedia and high performance applications. Therefore, using a faster MT operation results in a shorter execution time of these applications. In this paper we propose two new MT algorithms. The algorithms exploit diagonal register properties to achieve a linear-time execution of MT operation using vector processor that supports diagonal registers. We demonstrate the algorithms as well as proofs, examples, and various enhancements to the proposed algorithms A performance evaluation shows that the proposed algorithms are at least twice as fast as one of the leading MT algorithms such as an algorithm that is implemented using Motorola's AltiVec architecture (n/spl ges/16). We believe that our work opens new doors to improve the execution time of many two-dimensional operations such as DCT, DFT, and Shearsort.