A genetic algorithms approach to modeling the performance of memory-bound computations

ABSTRACT

Benchmarks that measure memory bandwidth, such as STREAM, Apex-MAPS and MultiMAPS, are increasingly popular due to the "Von Neumann" bottleneck of modern processors which causes many calculations to be memory-bound. We present a scheme for predicting the performance of HPC applications based on the results of such benchmarks. A Genetic Algorithm approach is used to "learn" bandwidth as a function of cache hit rates per machine with MultiMAPS as the fitness test. The specific results are 56 individual performance predictions including 3 full-scale parallel applications run on 5 different modern HPC architectures, with various CPU counts and inputs, predicted within 10% average difference with respect to independently verified runtimes.

REFERENCES

• 1: Wm. A. Wulf , Sally A. McKee, Hitting the memory wall: implications of the obvious, ACM SIGARCH Computer Architecture News, v.23 n.1, p.20-24, March 1995 [doi>10.1145/216585.216588]
• 2: J. McCalpin, "Memory bandwidth and machine balance in current high performance computers". IEEE Technical Committee on Computer Architecture Newsletter.
• 3: Erich Strohmaier , Hongzhang Shan, Architecture Independent Performance Characterization and Benchmarking for Scientific Applications, Proceedings of the The IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, p.467-474, October 04-08, 2004
• 4: Jonathan Weinberg , Michael O. McCracken , Erich Strohmaier , Allan Snavely, Quantifying Locality In The Memory Access Patterns of HPC Applications, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.50, November 12-18, 2005 [doi>10.1109/SC.2005.59]
• 5: Allan Snavely , Laura Carrington , Nicole Wolter , Jesus Labarta , Rosa Badia , Avi Purkayastha, A framework for performance modeling and prediction, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-17, November 16, 2002, Baltimore, Maryland
• 6: Laura C. Carrington , Michael Laurenzano , Allan Snavely , Roy L. Campbell , Larry P. Davis, How Well Can Simple Metrics Represent the Performance of HPC Applications?, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.48, November 12-18, 2005 [doi>10.1109/SC.2005.33]
• 7: Department of Defense, High Performance Computing Modernization Program. Technology Insertion 07. http://www.hpcmo.hpc.mil/Htdocs/TI/.
• 8: HPC Challenge Benchmarks, http://icl.cs.utk.edu/hpcc/.
• 9: R. Bleck, An oceanic general circulation model framed in hybrid isopycnic-cartesian coordinates. Ocean Modelling, 4, 55--88. 2002.
• 10: C. C. Hoke, V. Burnley, C. G. Schwabacher, Aerodynamic Analysis of Complex Missile Configurations using AVUS (Air Vehicles Unstructured Solver). Applied Aerodynamics Conference and Exhibit. August 2004, Providence, RI.
• 11: P. G. Buning, D. C. Jespersen, T. H. Pulliam, G. H. Klopfer, W. M. Chan, J. P. Slotnick, S. E. Krist, and K. J. Renze, Overflow Users Manual, Langley Research Center, 2003. Hampton, VA.
• 12: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 13: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 14: Reference Guide for The Genetic Algorithm Utility Library. http://gaul.sourceforge.net/gaul_reference_guide.html.2005.
• 15: High Performance Computing Modernization Program, http://www.hpcmo.hpc.mil.
• 16: D. Skinner, Performance monitoring of parallel scientific applications, Lawrence Berkeley National Laboratory, LBNL/PUB---5503. May 2005. Berkeley, CA.
• 17: D. Bailey, J. Barton, T. Lasinski, H. Simon, "The NAS parallel benchmarks", International Journal of Supercomputer Applications, 1991.
• 18: SPEC, http://www.spec.org/.
• 19: John L. Gustafson , Rajat Todi, Conventional Benchmarks as a Sample of the Performance Spectrum, Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences-Volume 7, p.514, January 06-09, 1998 [doi>10.1109/HICSS.1998.649247]
• 20: J. McCalpin, "Memory bandwidth and machine balance in current high performance computers", IEEE Technical Committee on Computer Architecture Newsletter.
• 21: Gabriel Marin , John Mellor-Crummey, Cross-architecture performance predictions for scientific applications using parameterized models, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 22: R. S., Ballansc, J. A. Cocke, and H. G. Kolsky, The Lookahead Unit, Planning a Computer System, (McGraw-Hill, New York, 1962).
• 23: G. S. Tjaden , M. J. Flynn, Detection and Parallel Execution of Independent Instructions, IEEE Transactions on Computers, v.19 n.10, p.889-895, October 1970 [doi>10.1109/T-C.1970.222795]
• 24: Jack L. Lo , Joel S. Emer , Henry M. Levy , Rebecca L. Stamm , Dean M. Tullsen , S. J. Eggers, Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.322-354, Aug. 1997 [doi>10.1145/263326.263382]
• 25: Babak Falsafi , David A. Wood, Modeling cost/performance of a parallel computer simulator, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.1, p.104-130, Jan. 1997 [doi>10.1145/244804.244808]
• 26: Jeff Gibson , Robert Kunz , David Ofelt , Mark Horowitz , John Hennessy , Mark Heinrich, FLASH vs. (Simulated) FLASH: closing the simulation loop, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.49-58, November 2000, Cambridge, Massachusetts, United States
• 27: Rafael H. Saavedra , Alan J. Smith, Analysis of benchmark characteristics and benchmark performance prediction, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.344-384, Nov. 1996 [doi>10.1145/235543.235545]
• 28: Celso L. Mendes , Daniel A. Reed, Integrated Compilation and Scalability Analysis for Parallel Systems, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.385, October 12-18, 1998
• 29: Jens Simon , Jens-Michael Wierum, Accurate Performance Prediction for Assively Parallel Systems and Its Applications, Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.675-688, August 26-29, 1996
• 30: Mark E. Crovella , Thomas J. LeBlanc, Parallel performance prediction using lost cycles analysis, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C. [doi>10.1145/602770.602870]
• 31: Zhichen Xu , Xiaodong Zhang , Lin Sun, Semi-empirical multiprocessor performance predictions, Journal of Parallel and Distributed Computing, v.39 n.1, p.14-28, Nov. 25, 1996 [doi>10.1006/jpdc.1996.0151 ]
• 32: Gheith A. Abandah , Edward S. Davidson, Modeling the Communication Performance of the IBM SP2, Proceedings of the 10th International Parallel Processing Symposium, p.249-257, April 15-19, 1996
• 33: Eric L. Boyd , Waqar Azeem , Hsien-Hsin Lee , Tien-Pao Shih , Shih-Hao Hung , Edward S. Davidson, A Hierarchical Approach to Modeling and Improving the Performance of Scientific Applications on the KSR1, Proceedings of the 1994 International Conference on Parallel Processing, p.188-192, August 15-19, 1994 [doi>10.1109/ICPP.1994.30]
• 34: Adolfy Hoisie , Olaf Lubeck , Harvey Wasserman, Scalability Analysis of Multidimensional Wavefront Algorithms on Large-Scale SMP Clusters, Proceedings of the The 7th Symposium on the Frontiers of Massively Parallel Computation, p.4, February 21-25, 1999
• 35: A. Spooner and D. Kerbyson, "Identification of Performance Characteristics from Multiview Trace Analysis", Proc. Of Int. Conf. On Computational Science (ICCS), part 3 2659, pp. 936--945, 2003.
• 36: Shirley Moore , David Cronk , Felix Wolf , Avi Purkayastha , Patricia Teller , Robert Araiza , Maria Gabriela Aguilera , Jamie Nava, Performance Profiling and Analysis of DoD Applications Using PAPI and TAU, Proceedings of the 2005 Users Group Conference on 2005 Users Group Conference, p.394, June 27-30, 2005 [doi>10.1109/DOD_UGC.2005.50]
• 37: High Productivity Computer Systems, www.highproductivity.org
• 38: M. Snir, and Jing Yu, "On the Theory of Spatial and Temporal Locality", Technical Report No. UIUCDCS-R-2005-2611, University of Illinois at Urbana-Champaign, Urbana, IL, July 2005.
• 39: X. Gao. PhD Thesis. 2006. University of California Computer Science Department.
• 40: Y. Chen and A. Snavely: Metrics for Ranking the Performance of Supercomputers, Cyberinfrastructure Technology Watch Journal: Special Issue on High Productivity Computer Systems, J. Dongarra Editor, Volume 2 Number 4, February 2007.
• 41: E. Ipek, S. McKee, R. Caruana, B. R. de Supinski, and Schulz, M. 2006. Efficiently exploring architectural design spaces via predictive modeling. SIGPLAN Not. 41, 11 (Nov. 2006), 195--206. DOI= http://doi.acm.org/10.1145/1168918.1168882
• 42: A. Phansalkar, L. K. John. Performance Prediction using Program Similarity, Proceedings of SPEC Benchmark Workshop 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Algorithms, Measurement, Performance

Keywords:
cache bandwidth, genetic algorithms, machine learning, memory bound applications, performance modeling and prediction