Optimised Hierarchical Storage Layouts in C#

Introduction - Hierarchical Storage Layouts

Programming Languages that support multidimensional arrays normally prescribe as part of the language definition how those arrays are laid out in memory. For example, Fortran uses column-major and C/C++ use row-major. This is great when we write our code in such a way that multidimensional arrays are accessed in the same order that they are stored in memory, and very bad (up to 10 times slower) otherwise. An alternative is to store arrays in a compromise storage layout, typically using a pattern of a space-filling curve.

C# is interesting in this respect, because the language not only has multidimensional arrays, but also allows the way in which such arrays are accessed in memory to be modified by the programmer using indexers.

Aims of this project

The aim of this project is to study the performance of scientific applications written in C# when using a variety of space-filling curves as a storage layout pattern for multidimensional arrays.

• Find a suitable collection of scientific codes that use multidimensional arrays and which are either already written in C# or which can be easily translated to C#.
• Use C# indexers to study the performance characteristics of these applications when using a variety of space-filling curves to lay out arrays in memory. Use suitable tools to measure how cache misses etc are affected.
• Use Phoenix to help the compiler "understand" and optimise the use of these storage layouts. This is arguably where the project becomes really interesting and challenging, and is an instance of "domain-specific optimisation features", i.e. we want to pass to the compiler some specific knowledge which we have about our application that can help in code optimisation.

Is this project for you?

To do this project, you should not be scared by large, existing pieces of software, and have the ability to get complex pieces of code to work.

Olav Beckmann
Last modified: Wed Oct 5 18:25:33 BST 2005