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.

Chapter titleMinimizing associativity conflicts in Morton layout
AuthorsThiyagalingam, J., Beckmann, O. and Kelly, P.H.J.
EditorsWyrzykowski, R., Dongarra, J., Meyer, N. and Wasniewski, J.
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.

Book titleParallel Processing and Applied Mathematics: 6th International Conference, PPAM 2005, Poznan, Poland, September 11-14, 2005, revised selected papers
Year2006
PublisherSpringer
Publication dates
Published2006
Place of publicationBerlin, Germany
SeriesLecture notes in computer science
ISBN3540341412
Digital Object Identifier (DOI)doi:10.1007/11752578_131
Journal citation(3911), pp. 1082-1088

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.

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.

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

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/927v7/minimizing-associativity-conflicts-in-morton-layout


Share this
Tweet
Email