CTWatch
November 2006 B
High Productivity Computing Systems and the Path Towards Usable Petascale Computing
Erich Strohmaier, Lawrence Berkeley National Laboratory

7
7. Related Work

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;4 Halstead Software Science metrics5 based on count of operators and operands used; McCabe cyclomatic complexity measure6 based on the number of linearly-independent paths through a program module, and variants thereof such as design complexity.7 These software complexity metrics have also been applied and extended to the context of parallel computing.8

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. 11 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.

8. Conclusions and Future Work

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.

Acknowledgments This work was supported in part by the Department of Energy Office of Science and NSA. Computer time was provided by NERSC, LLNL, ORNL, ANL, and HLRS. I would also like to thank Hongzhang Shan for helping to collect data, and Kathy Yelick, Bob Lucas, and Jeremy Kepner for their invaluable input to this work.
References
1DARPA HPCS - www.darpa.mil/ipto/programs/hpcs/
2Strohmaier, E., Shan, H. “Apex-Map: A Global Data Access Benchmark to Analyze HPC Systems and Parallel Programming Paradigms,” Proceedings of SC|05. 2005.
3Strohmaier, E., Shan, H. “Architecture independent performance characterization and benchmarking for scientific applications. In International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, Volendam, The Netherlands, 2004.
4Funk, A., Basili, V., Hochstein, L., Kepner, J. “Application of a Development Time Pro-ductivity Metric to Parallel Software Development,” Second International Workshop on Software Engineering for High Performance Computing System Applications at the 27th International Conference on Software Engineering, May 15, St. Louis, MO
5Halstead, M. H. Elements of Software Science, Elsevier North-Holland, New York, 1977.
6McCabe, T. J. “A Complexity Measure,” IEEE Transactions on Software Engineering, SE-2 No. 4, pp. 308-320, December 1976.
7McCabe, T. J., Butler, C. “Design Complexity Measurement and Testing,” Communications of the ACM, 32, pp. 1415-1425, December 1989.
8VanderWiel, S., Nathanson, D., Lilja, D. “Performance and program complexity in contemporary network-based parallel computing systems.” Technical Report HPPC-96-02, University of Minnesota, 1996.M
9Kepner, J. “HPC Productivity Model Synthesis,” International Journal of High Performance Computing Applications: Special Issue on HPC Productivity, J. Kepner (editor), Volume 18, Number 4, Winter 2004.
10Carver, J. Asgari, S., Basili, V., Hochstein, L., Hollingsworth, J., Shull, F., Zelkowitz, M. “Studying Code Development for High Performance Computing: The HPCS Program,” Proceedings of the First International Workshop on Software Engineering for High Performance Computing System Applications at ICSE, pp. 32-36. Edinburgh, Scotland, May 2004.
11HPC Challenge Benchmark - icl.cs.utk.edu/hpcc/

Pages: 1 2 3 4 5 6 7

Reference this article
"Performance Complexity: An Execution Time Metric to Characterize the Transparency and Complexity of Performance," CTWatch Quarterly, Volume 2, Number 4B, November 2006 B. http://www.ctwatch.org/quarterly/articles/2006/11/performance-complexity-an-execution-time-metric-to-characterize-the-transparency-and-complexity-of-performance/

Any opinions expressed on this site belong to their respective authors and are not necessarily shared by the sponsoring institutions or the National Science Foundation (NSF).

Any trademarks or trade names, registered or otherwise, that appear on this site are the property of their respective owners and, unless noted, do not represent endorsement by the editors, publishers, sponsoring institutions, the National Science Foundation, or any other member of the CTWatch team.

No guarantee is granted by CTWatch that information appearing in articles published by the Quarterly or appearing in the Blog is complete or accurate. Information on this site is not intended for commercial purposes.