Recursive array layouts and fast matrix multiplication

Submitted for publication to IEEE TPDS The performance of both serial and parallel implementations of matrix multiplication is highly sensitive to memory system behavior. False sharing and cache conflicts cause tradi-tional column-major or row-major array layouts to incur high variability in memory system performance as matrix size varies. This paper investigates the use of recursive array layouts to improve performance and reduce variability. Previous work on recursive matrix multiplication is extended to examine several recursive array layouts and three recursive algorithms: standard matrix multiplication, and the more complex algorithms of Strassen and Winograd. While recursive layouts significantly outper-form traditional layouts (reducing execution times by a factor of 1.2–2.5) for the standard al-gorithm, they offer little improvement for Strassen’s and Winograd’s algorithms. For a purely sequential implementation, it is possible to reorder computation to conserve memory space and improve performance between 10 % and 20%. Carrying the recursive layout down to the level of individual matrix elements is shown to be counter-productive; a combination of recursiv