Is Morton layout competitive for large two-dimensional arrays yet

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

TitleIs Morton layout competitive for large two-dimensional arrays yet
AuthorsThiyagalingam, J., Beckmann, O. and Kelly, P.H.J.
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.

JournalConcurrency and Computation: Practice & Experience
Journal citation18 (11), pp. 1509-1539
ISSN1532-0626
YearSep 2006
Digital Object Identifier (DOI)doi:10.1002/cpe.1018
Publication dates
PublishedSep 2006

Related outputs

Advanced Grid programming with components: a biometric identification case study
Weigold, T., Buhler, P., Thiyagalingam, J., Basukoski, A. and Getov, Vladimir 2008. Advanced Grid programming with components: a biometric identification case study. in: Proceedings of the 32nd Annual IEEE International Computer Software and Applications Conference, 28 July - 1 August 2008, Turku, Finland: COMPSAC 2008 Los Alamitos, USA IEEE . pp. 401-408

Domain-specific metadata for model validation and performance optimisation
Thiyagalingam, J., Getov, Vladimir, Penagiotidi, S., Beckmann, O. and Darlington, J. 2008. Domain-specific metadata for model validation and performance optimisation. in: Gorlatch, S., Bubak, M. and Priol, T. (ed.) Achievements in European Research on Grid Systems: Proceedings of the CoreGRID Integration Workshop 2006, October 19-20, Krakow, Poland Berlin, Germany Springer. pp. 165-177

Design and implementation of a hybrid P2P-based Grid resource discovery system
Basukoski, A., Getov, Vladimir, Thiyagalingam, J. and Isaiadis, S. 2008. Design and implementation of a hybrid P2P-based Grid resource discovery system. in: Danelutto, M., Fragopoulou, P. and Getov, Vladimir (ed.) Making grids work: Proceedings of the CoreGRID Workshop on Programming Models Grid and P2P System Architecture Grid Systems, Tools and Environments 12-13 June 2007, Heraklion, Crete, Greece Springer.

Domain-specific metadata for model validation and performance optimisation
Thiyagalingam, J., Getov, Vladimir, Panagiotidi, S., Beckmann, O. and Darlington, J. 2007. Domain-specific metadata for model validation and performance optimisation. CoreGRID.

Lightweight grid platform: design methodology
Badia, R.M., Beckmann, O., Bubak, M., Caromel, D., Getov, Vladimir, Henrio, L., Isaiadis, S., Lazarov, V., Malawski, M., Panagiotidi, S., Parlavantzas, N. and Thiyagalingam, J. 2006. Lightweight grid platform: design methodology. CoreGRID.

A metadata extracting tool for software components in grid applications
Thiyagalingam, J. and Getov, Vladimir 2006. A metadata extracting tool for software components in grid applications. in: IEEE John Vincent Atanasoff 2006 International Symposium on Modern Computing (JVA'06) Los Alamitos, USA IEEE . pp. 189-196

Minimizing associativity conflicts in Morton layout
Thiyagalingam, J., Beckmann, O. and Kelly, P.H.J. 2006. Minimizing associativity conflicts in Morton layout. in: Wyrzykowski, R., Dongarra, J., Meyer, N. and Wasniewski, J. (ed.) Parallel Processing and Applied Mathematics: 6th International Conference, PPAM 2005, Poznan, Poland, September 11-14, 2005, revised selected papers Berlin, Germany Springer.

Towards building a generic grid services platform: a components-oriented approach
Thiyagalingam, J., Isaiadis, S. and Getov, Vladimir 2005. Towards building a generic grid services platform: a components-oriented approach. in: Getov, Vladimir and Kielmann, T. (ed.) Component models and systems for grid applications: proceedings of the Workshop on Component Models and Systems for Grid Applications held June 26, 2004 in Saint Malo, France New York, USA Springer. pp. 39-56

An exhaustive evaluation of row-major, column-major and Morton layouts for large two-dimensional arrays
Thiyagalingam, J., Beckmann, O. and Kelly, P.H.J. 2003. An exhaustive evaluation of row-major, column-major and Morton layouts for large two-dimensional arrays. in: Jarvis, S.A. (ed.) Performance Engineering: 19th Annual UK Performance Engineering Workshop, University of Warwick, July 2003 UKPEW. pp. 340-351

Improving the performance of Morton layout by array alignment and loop unrolling: reducing the price of naivety
Thiyagalingam, J., Beckmann, O. and Kelly, P.H.J. 2003. Improving the performance of Morton layout by array alignment and loop unrolling: reducing the price of naivety. in: Rauchwerger, L. (ed.) Languages and Compilers for Parallel Computing: 16th International Workshop, LCPC 2003, College Station, TX, USA, October 2-4, 2003: revised papers London, UK Springer.

Is Morton layout competitive for large two-dimensional arrays?
Thiyagalingam, J. and Kelly, P.H.J. 2002. Is Morton layout competitive for large two-dimensional arrays? in: Monien, B. and Feldman, R. (ed.) Euro-Par 2002: Parallel Processing: 8th International Euro-Par Conference Paderborn, Germany, August 27-30, 2002: proceedings Berlin, Germany Springer.

Optimising concurrent processing efficiency: a practical methodology
Lea, R.M., Tetnowski, P.T. and Thiyagalingam, J. 2001. Optimising concurrent processing efficiency: a practical methodology. in: Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, (PDPTA), June 25 - 28, 2001 CSREA Press. pp. 362-368

Programming languages, models, and methods
Kelly, P.H.J., Gorlatch, S., Baden, S. and Getov, Vladimir 2000. Programming languages, models, and methods. in: Bode, A., Ludwig, T., Karl, W. and Wismuller, R. (ed.) Euro-Par 2000 Parallel Processing Springer.

Permalink - https://westminsterresearch.westminster.ac.uk/item/921y9/is-morton-layout-competitive-for-large-two-dimensional-arrays-yet


Share this
Tweet
Email