Computing Publications

Publications Home » Minimizing Associativity Conflict...

Minimizing Associativity Conflicts in Morton Layout

Olav Beckmann, Thiyagalingam Jeyarajan, Paul Kelly

Conference or Workshop Paper
PPAM 2005 Workshop on HPC Linear Algebra Libraries for Computers with Multilevel Memories
September, 2005
Lecture Notes in Computer Science
Volume 3911
Springer
Abstract

Hierarchically-blocked non-linear storage layouts, such as the Morton ordering, have been shown to be a potentially attractive compromise between row-major and column-major for two-dimensional arrays. When combined with appropriate optimizations,Morton layout offers some spatial locality whether traversed row- or column-wise. However, for linear algebra routines with larger problem sizes, the layout shows diminishing returns. It is our hypothesis that associativity conflicts between Morton blocks cause this behavior and we show that carefully arranging the Morton blocks can minimize this effect. We explore one such arrangement and report our preliminary results.

BibTEX file for the publication
 

pubs.doc.ic.ac.uk: built & maintained by Ashok Argent-Katwala.