Is Morton layout competitive for large two-dimensional arrays?

Thiyagalingam, Jeyarajan and Kelly, Paul H.J. (2002) Is Morton layout competitive for large two-dimensional arrays? In: Euro-Par 2002: Parallel Processing: 8th International Euro-Par Conference Paderborn, Germany, August 27-30, 2002: proceedings. Lecture notes in computer science (2400). Springer, Berlin, Germany, pp. 280-288. ISBN 3540440496

Full text not available from this repository.
Official URL: http://springerlink.com/openurl.asp?genre=article&...

Abstract

Two-dimensional arrays are generally arranged in memory in row-major order or column-major order. Sophisticated programmers, or occasionally sophisticated compilers, match the loop structure to the language's storage layout in order to maximise spatial locality. Unsophisticated programmers do not, and the performance loss is often dramatic -- up to a factor of 20. With knowledge of how the array will be used, it is often possible to choose between the two layouts in order to maximise spatial locality. In this paper we study the Morton storage layout, which has substantial spatial locality whether traversed in row-major or column-major order. We present results from a suite of simple application kernels which show that, on the AMD Athlon and Pentium III, for arrays larger than 256 Ã?256, Morton array layout, even implemented with a lookup table with no compiler support, is always within 61% of both row-major and column-major -- and is sometimes faster.

Item Type: Book Section
Subjects: University of Westminster > Science and Technology > Electronics and Computer Science, School of (No longer in use)
Depositing User: Miss Nina Watts
Date Deposited: 08 May 2006
Last Modified: 19 Oct 2009 15:13
URI: http://westminsterresearch.wmin.ac.uk/id/eprint/1498

Actions (login required)

Edit Item (Repository staff only) Edit Item (Repository staff only)