A genetic algorithms approach to modeling the performance of memory-bound computations
The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“However, they rarely provide insights into how to improve performance of programs, compilers, or computers [1] or they can be hard to use by non-experts [27].”
From Roofline: an insightful visual performance model for multicore architectures (2009) · cites this paper as [27]
Citations
Cites
Holland, J. H. (1992) · The MIT Press eBooks · doi:10.7551/mitpress/1090.001.0001 · Cited by 47,002
Genetic Algorithms in Search, Optimization and Machine Learning
Goldberg, D. E., & Robson, D. (1988) · Cited by 18,391
Goldberg, D. E., & Shakespeare, W. (2002) · Cited by 16,088
Bailey, D. H., Barszcz, E., Barton, J. T., Browning, D. S., Carter, R. L., Dagum, L., Fatoohi, R. A., Frederickson, P. O., Lasinski, T. A., Schreiber, R. S., et al. (1991) · The International Journal of Supercomputing Applications · doi:10.1177/109434209100500306 · Cited by 2,395
Hitting the memory wall: implications of the obvious
Wulf, W. A., & McKee, S. A. (1995) · ACM SIGARCH Computer Architecture News · doi:10.1145/216585.216588 · Cited by 1,624
Hitting the Memory Wall: Implications of the Obvious
Wulf, W. A., & McKee, S. A. (1995) · Cited by 1,379
An oceanic general circulation model framed in hybrid isopycnic-Cartesian coordinates
Bleck, R. (2002) · Ocean Modelling · doi:10.1016/s1463-5003(01)00012-9 · Cited by 1,343
Efficiently exploring architectural design spaces via predictive modeling
Ïpek, E., McKee, S. A., Caruana, R., de Supinski, B. R., & Schulz, M. (2006) · Proceedings of the 12th international conference on Architectural support for programming languages and operating systems · doi:10.1145/1168857.1168882 · Cited by 323
Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading
Lo, J. L., Emer, J. S., Levy, H. M., Stamm, R. L., Tullsen, D. M., & Eggers, S. J. (1997) · ACM Transactions on Computer Systems · doi:10.1145/263326.263382 · Cited by 233
Cross-architecture performance predictions for scientific applications using parameterized models
Marin, G., & Mellor-Crummey, J. (2004) · Proceedings of the joint international conference on Measurement and modeling of computer systems · doi:10.1145/1005686.1005691 · Cited by 228
1 A Framework for Performance Modeling and Prediction
Snavely, A. E., Carrington, L., Wolter, N., Jesus Labarta, R. B., & Purkayastha, A. (2002) · Cited by 222
Self-citationAnalysis of benchmark characteristics and benchmark performance prediction
Saavedra, R. H., & Smith, A. J. (1996) · ACM Transactions on Computer Systems · doi:10.1145/235543.235545 · Cited by 209
Detection and Parallel Execution of Independent Instructions
Tjaden, G. S., & Flynn, M. J. (1970) · IEEE Transactions on Computers · doi:10.1109/t-c.1970.222795 · Cited by 198
A Framework for Performance Modeling and Prediction
Snavely, A. E., Carrington, L., Wolter, N., Labarta, J., Badia, R. M., & Purkayastha, A. (2002) · ACM/IEEE Conference on Supercomputing (SC) · doi:10.1109/sc.2002.10004 · Cited by 189
Self-citationEfficiently exploring architectural design spaces via predictive modeling
İpek, E., McKee, S. A., Caruana, R., de Supinski, B. R., & Schulz, M. (2006) · ACM SIGOPS Operating Systems Review · doi:10.1145/1168917.1168882 · Cited by 114
Quantifying Locality In The Memory Access Patterns of HPC Applications
Weinberg, J., McCracken, M. O., Strohmaier, E., & Snavely, A. E. (2005) · ACM/IEEE Conference on Supercomputing (SC) · doi:10.1109/sc.2005.59 · Cited by 113
Self-citationFLASH vs. (simulated) FLASH: closing the simulation loop
Gibson, J., Kunz, R. C., Ofelt, D., Horowitz, M., Hennessy, J. L., & Heinrich, M. A. (2000) · ACM SIGPLAN Notices · doi:10.1145/356989.356994 · Cited by 99
Parallel performance prediction using lost cycles analysis
Crovella, M. E., & LeBlanc, T. J. (1994) · ACM/IEEE Conference on Supercomputing (SC) · doi:10.1145/602770.602870 · Cited by 89
Parallel performance prediction using lost cycles analysis
Crovella, M. E., & LeBlanc, T. J. (1994) · Conference on High Performance Computing (Supercomputing) · doi:10.5555/602770.602870 · Cited by 76
FLASH vs. (Simulated) FLASH: closing the simulation loop
Gibson, J., Kunz, R. C., Ofelt, D., Horowitz, M., Hennessy, J. L., & Heinrich, M. A. (2000) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/378993.379000 · Cited by 65
How well can simple metrics represent the performance of HPC applications?
Carrington, L., Laurenzano, M. A., Snavely, A. E., Campbell, R., & Davis, L. P. (2005) · ACM/IEEE Conference on Supercomputing (SC) · doi:10.1109/sc.2005.33 · Cited by 61
Self-citationModeling cost/performance of a parallel computer simulator
Falsafi, B., & Wood, D. A. (1997) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/244804.244808 · Cited by 44
Modeling the communication performance of the IBM SP2
Abandah, G. A., & Davidson, E. S. (2002) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/ipps.1996.508066 · Cited by 41
Scalability analysis of multidimensional wavefront algorithms on large-scale SMP clusters
Hoisie, A., Lubeck, O. M., & Wasserman, H. J. (1999) · Symposium on the Frontiers of Massively Parallel Computation (Frontiers) · doi:10.1109/fmpc.1999.750452 · Cited by 41
Performance monitoring of parallel scientific applications
Skinner, D. E. (2005) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/881368 · Cited by 39
Integrated compilation and scalability analysis for parallel systems
Mendes, C. L., & Reed, D. A. (1998) · International Conference on Parallel Architectures and Compilation Techniques · doi:10.5555/522344.825710 · Cited by 37
Architecture independent performance characterization and benchmarking for scientific \napplications
Strohmaier, E., & Shan, H. (2004) · eScholarship (California Digital Library) · Cited by 33
Self-citationAccurate performance prediction for massively parallel systems and its applications
Simon, J., & Wierum, J.-M. (1996) · Lecture notes in computer science · doi:10.1007/bfb0024764 · Cited by 32
On the Theory of Spatial and Temporal Locality
Snir, M., & Yu, J. (2005) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 30
Semi-empirical Multiprocessor Performance Predictions
Xu, Z., Zhang, X., & Sun, L. J. (1996) · Journal of Parallel and Distributed Computing · doi:10.1006/jpdc.1996.0151 · Cited by 24
Boyd, E. L., Azeem, W., Hsien-Hsin Lee, H.-H. L., Tien-Pao Shih, T.-P. S., Shih-Hao Hung, S.-H. H., & Davidson, E. S. (1994) · 1994 International Conference on Parallel Processing Vol. 3 · doi:10.1109/icpp.1994.30 · Cited by 23 · cited 2×
“Abandah and Davidson [32], and Boyd et al [33] proposed hierarchical modeling methods for parallel machines that is kindred in spirit to our work, and was effective on machines in the early and mid 90’s.”
MethodConventional benchmarks as a sample of the performance spectrum
Gustafson, J. L., & Todi, R. K. (2002) · Hawaii International Conference on System Sciences (HICSS) · doi:10.1109/hicss.1998.649247 · Cited by 22
Performance Profiling and Analysis of DoD Applications Using PAPI and TAU
Moore, S., Cronk, D., Wolf, F., Purkayastha, A., Teller, P. J., Araiza, R., Aguilera, M. G., & Nava, J. (2006) · DoD High Performance Computing Modernization Program Users Group Conference (HPCMP-UGC) · doi:10.1109/dodugc.2005.50 · Cited by 15
Aerodynamic Analysis of Complex Missile Configurations Using AVUS (Air Vehicles Unstructured Solver)
Hoke, C. M., Burnley, V. S., & Schwabacher, G. (2004) · AIAA Applied Aerodynamics Conference · doi:10.2514/6.2004-5452 · Cited by 11
Identification of Performance Characteristics from Multi-view Trace Analysis
Spooner, D. P., & Kerbyson, D. J. (2003) · Lecture notes in computer science · doi:10.1007/3-540-44863-2_92 · Cited by 8
The department of defense high performance computing modernization program
Barton, J. M. (2021) · The Journal of Defense Modeling and Simulation Applications Methodology Technology · doi:10.1177/15485129211061743 · Cited by 1
Research works printed but not linked: 15
- McCalpin J., Memory bandwidth and machine balance in current high performance computers, IEEE Technical Committee on Computer Architecture Newsletter.
- 10.5555/1032659.1034232 · doi:10.5555/1032659.1034232
- Hoke C. C., 2004, Applied Aerodynamics Conference and Exhibit.
- Buning P. G., 2003, Langley Research Center
- J. H. Holland Adaptation in Natural and Artificial Systems. University of Michigan Press 1975 J. H. Holland Adaptation in Natural and Artificial Systems. University of Michigan Press 1975
- McCalpin J., Memory bandwidth and machine balance in current high performance computers, IEEE Technical Committee on Computer Architecture Newsletter.
- Ballansc R. S., 1962, New York
- Abandah G., 1996, Proceedings Int'l Parallel Processing Symposium, 249
- Hosie A., 1999, Proceedings of Frontiers of Massively Parallel Computing '99
- 10.5555/1762418.1762521 · doi:10.5555/1762418.1762521
- 10.5555/1114280.1114372 · doi:10.5555/1114280.1114372
- Snir M., 2005, Technical Report No. UIUCDCS-R-2005-2611
- X. Gao. PhD Thesis. 2006. University of California Computer Science Department. X. Gao. PhD Thesis. 2006. University of California Computer Science Department.
- Chen Y., 2007, Dongarra Editor, 2
- Phansalkar A., 2006, Proceedings of SPEC Benchmark Workshop
Cited by
Williams, S., Waterman, A., & Patterson, D. A. (2009) · Communications of the ACM · doi:10.1145/1498765.1498785 · Cited by 2,798
Williams, S., Waterman, A., & Patterson, D. (2009) · doi:10.2172/1407078 · Cited by 110
PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications
Tikir, M. M., Laurenzano, M. A., Carrington, L., & Snavely, A. E. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03869-3_16 · Cited by 94
Self-citationPerformance projection of HPC applications using SPEC CFP2006 benchmarks
Sharkawi, S., DeSota, D., Panda, R., Indukuru, R., Stevens, S., Taylor, V., & Wu, X. (2009) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2009.5161057 · Cited by 51
Meswani, M. R., Carrington, L., Unat, D., Snavely, A. E., Baden, S. B., & Poole, S. (2012) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342012468180 · Cited by 49
Self-citation
Metadata
- Authors
- Tikir, M. M., Carrington, L., Strohmaier, E., & Snavely, A.
- Affiliations
- San Diego Supercomputer Center (US)
- Lawrence Berkeley National Laboratory (US)
- Venue
- Proceedings of the 2007 ACM/IEEE conference on Supercomputing
- Publisher
- ACM
- Published
- 2007-11-10
- Pages
- 1-12
- ISSN
- 1063-9535 (ISSN-L)
- OpenAlex
- W2109811664
- Cited by
- 66
- References
- 36
- Citations by year
- 2024: 1 · 2023: 1 · 2022: 1 · 2020: 1 · 2019: 4 · 2018: 2 · 2017: 3 · 2016: 8 · 2015: 2 · 2014: 4 · 2013: 6 · 2012: 11
- FWCI
- 3.94
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM/IEEE Conference on Supercomputing (SC) (publishedVersion)
- Funders
- National Science Foundation (406312, 516162)
- Office of Science (SciDAC2)
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed and Parallel Computing Systems
- Physical Sciences › Computer Science › Computer Networks and Communications › Software System Performance and Reliability
- Keywords
- memory bandwidth, performance prediction, genetic algorithm, STREAM benchmark, cache hit rate, von Neumann bottleneck, HPC applications
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.