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.

Chapter titleIs Morton layout competitive for large two-dimensional arrays?
AuthorsThiyagalingam, J. and Kelly, P.H.J.
EditorsMonien, B. and Feldman, R.
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.

Book titleEuro-Par 2002: Parallel Processing: 8th International Euro-Par Conference Paderborn, Germany, August 27-30, 2002: proceedings
Year2002
PublisherSpringer
Publication dates
Published2002
Place of publicationBerlin, Germany
SeriesLecture notes in computer science
ISBN3540440496
Web address (URL)http://springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2400&spage=280
Journal citation(2400), pp. 280-288

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. https://doi.org/CoreGRIDTechnicalReportNumberTR-0068

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. https://doi.org/10.1002/cpe.1018

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. https://doi.org/CoreGRIDTechnicalReportNumberTR-0020

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.

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/93y83/is-morton-layout-competitive-for-large-two-dimensional-arrays


Share this

Usage statistics

69 total views
0 total downloads
These values cover views and downloads from WestminsterResearch and are for the period from September 2nd 2018, when this repository was created.