A Performance Model for the Analysis of OpenMP Programs

Abstract

This work attempts to build a bridge between theoretical complexity models and the performance analysis and tuning of OpenMP programs. It starts from the assumption that the theoretical analysis of an OpenMP code produces a complexity function that gives an approach to the asymptotic number of operations performed by the algorithm. The shared memory platform is characterized through a number of parameters that are computed through a benchmarking program. We propose an algorithm that determines the algorithmic constants associated with the complexity formula in term of the architecture parameters. To predict the performance for a new computing platform, we just need to know the parameters characterizing this new platform and to solve a random linear equation system.

Due to the hierarchical design of current shared memory systems, the performance behavior of most algorithms varies in a small number of large regions corresponding to small size, medium size and large size inputs. The constants involved in the complexity formula usually have different values for these regions. We propose an algorithm that, assuming a complexity formula for the memory resources is known, proposes a partition of the algorithm input size space in a small number of regions and gives the values of the algorithmic constants for such regions. This way, though the complexity formula is the same, the family of constants provides the adaptability of the formula to the different memory use stationary states. All these tasks are automatically accomplished by the accompanying software tool that gives support to the proposed analytical model.