There is a rich collection of research available on the subject of software complexity. Complexity measures discussed include code size expressed in lines of code (LOC), which is used in various places such as the DARPA HPCS program;⁴ Halstead Software Science metrics⁵ based on count of operators and operands used; McCabe cyclomatic complexity measure⁶ based on the number of linearly-independent paths through a program module, and variants thereof such as design complexity.⁷ These software complexity metrics have also been applied and extended to the context of parallel computing.⁸

An active area of research within the DARPA HPCS program is productivity metrics, which focus on capturing the complexity of the task of coding itself. ^{4 9 10} The approach presented here complements research in software complexity and productivity by considering performance complexity, which represents a measure quite different from the former two as it characterizes code execution behavior in a second dimension orthogonal to performance itself. PC is based on performance model accuracy, which has the advantage of de-pending only on performance measurements and is not based on nor requires code inspection or supervision of coding itself. To my knowledge, no similar concept has been described in the literature.

Apex-MAP is a parameterized, synthetic benchmark designed to cover performance across a whole range of locality conditions. ^{2 3} Parameterized benchmarks like this have the advantage of being able to perform parameter sweeps and generating complete performance surfaces.

The HPCC benchmark suite covers a similar locality space with a collection of various benchmarks. ¹¹ This or similar set of benchmarks would provide a good basis for analyzing PC values with more realistic codes. They might however present the additional complication of containing codes, which are measured in different metrics such as TF/s and GB/s, between which meaningful averages are very hard to define properly.

In this paper, I presented a concept for a quantitative measure of performance complexity (PC). The transparency of performance behavior is linked to the complexity of optimizing for performance and can be characterized by the accuracy of performance models. I have presented a definition and detailed description on how to calculate PC based on performance numbers from a set of benchmarks and performance models.

PC is a measure characterizing code execution behavior on a system. It is independent of performance and serves as a second dimension to evaluate systems and programming paradigms.

I demonstrated my methodology by using a parameterized synthetic benchmark, Apex-MAP. The performance results from a large parameter sweep were used as a substitute for results from a suite of different benchmarks. This might limit the interpretation of final PC values, but allows me to demonstrate the methodology. Even with this simplified setup I was able to analyze serial and parallel systems in surprising detail.

I am planning on conducting similar studies based on a set of benchmarks such as HPCC. In this context, I will also research how to extend my formalism to situations involving benchmarks measured in different dimensions for which averaging is non-trivial.