WestminsterResearch

Is Morton layout competitive for large two-dimensional arrays yet

Thiyagalingam, Jeyarajan and Beckmann, Olav and Kelly, Paul H.J. (2006) Is Morton layout competitive for large two-dimensional arrays yet. Concurrency and Computation: Practice & Experience, 18 (11). pp. 1509-1539. ISSN 1532-0626

Full text not available from this repository.

Official URL: http://dx.doi.org/10.1002/cpe.1018

Abstract

Two-dimensional arrays are generally arranged in memory in row-major order or column-major order. Traversing a row-major array in column-major order, or vice versa, leads to poor spatial locality. With large arrays the performance loss can be a factor of 10 or more. This paper explores the Morton storage layout, which has substantial spatial locality whether traversed in row-major or column-major order. Using a small suite of dense kernels working on two-dimensional arrays, we have carried out an extensive study of the impact of poor array layout and of whether Morton layout can offer an attractive compromise. We show that Morton layout can lead to better performance than the worse of the two canonical layouts; however, the performance of Morton layout compared to the better choice of canonical layout is often disappointing. We further study one simple improvement of the basic Morton scheme: we show that choosing the correct alignment for the base address of an array in Morton layout can sometimes significantly improve the competitiveness of this layout.

Item Type:Article
Additional Information:Online ISSN 1532-0634
Research Community:University of Westminster > Electronics and Computer Science, School of
ID Code:1494
Deposited On:08 May 2006
Last Modified:19 Oct 2009 16:09

Repository Staff Only: item control page