A Novel Triangular Space-Filling Curve for Cache-Oblivious In-Place Transposition of Square Matrices

This paper proposes a novel cache-oblivious blocking scheme based on a new triangular space-filling curve which preserves data locality. The proposed blocking-scheme reduces the movement of data within the host memory hierarchy for triangular matrix traversals, which inherently exhibit poor data locality, such as the in-place transposition of square matrices. We show that our cache-oblivious blocking-scheme can be generated iteratively in linear time and constant memory with regard to the number of entries present in the lower, or upper, triangle of the input matrix. In contrast to classical recursive cache-oblivious solutions, the iterative nature of our blocking-scheme does not inhibit other essential optimizations such as software prefetching. In order to assess the viability of our blocking-scheme as a cache-oblivious strategy, we applied it to the in-place transposition of square matrices. Extensive experiments show that our cache-oblivious transposition algorithm generally outperforms the cache-aware state-of-the-art algorithm in terms of throughput and energy efficiency in sequential as well as parallel environments.

I. Introduction

The in-place transposition of square matrices is a well-explored problem in scientific computing [1]–[3]. In-place transposition routines are widely used to optimize the memory access patterns of different FFT methods. In some cases, such as in the "six-step" FFT variant, the transposition steps are found to represent the most significant performance bottle-neck [4]. The in-place transposition of square matrices is also an important building block for methods that compute the in-place transposition of rectangular matrices, where the input matrix is partitioned into square sub-matrices that must be transposed in-place, such as the Euclid's GCD method proposed by Gustavson et al. [5].