Cache optimization for mixed regular and irregular computations

Many large application programs suffer from a bad utilization of cache and memory hierarchy. Known transformation techniques change loop structures and/or data layout in order to improve the performance. However, those techniques are usually adapted to either regular or irregular computations. In this paper, we investigate a combination of transformations suitable for algorithms with both irregular and regular features. The transformations are composed of computational loop reordering and data storage reorderings. We show how the different transformations interact in terms of cache utilization. Experiments on different clusters show performance gains for the sequential as well as for the parallel version.