Cited By
View all- Razzak ABarai ASanthi NBadawy A(2024)Static Reuse Profile Estimation for Array ApplicationsProceedings of the International Symposium on Memory Systems10.1145/3695794.3695817(235-244)Online publication date: 30-Sep-2024
LLVM Static Analysis for Program Characterization and Memory Reuse Profile Estimation
Authors: 
Atanu Barai, Nandakishore Santhi, Abdur Razzak, Stephan Eidenbenz, Abdel-Hameed A. BadawyAuthors Info & Claims
Article No.: 3, Pages 1 - 6
Abstract
Profiling various application characteristics, including the number of different arithmetic operations performed, memory footprint, etc., dynamically is time- and space-consuming. On the other hand, static analysis methods, although fast, can be less accurate. This paper presents an LLVM-based probabilistic static analysis method that accurately predicts different program characteristics and estimates the reuse distance profile of a program by analyzing the LLVM IR file in constant time, regardless of program input size. We generate the basic-block-level control flow graph of the target application kernel and determine basic-block execution counts by solving the linear balance equation involving the adjacent basic blocks’ transition probabilities. Finally, we represent the kernel memory accesses in a bracketed format and employ a recursive algorithm to calculate the reuse distance profile. The results show that our approach can predict application characteristics accurately compared to another LLVM-based dynamic code analysis tool, Byfl.
References
[1]
Atanu Barai. 2022. Scalable Performance Prediction of Parallel Applications on Multicore Processors Using Analytical Reuse Distance Modeling. Ph. D. Dissertation. New Mexico State University.
[2]
Atanu Barai, Gopinath Chennupati, Nandakishore Santhi, Abdel-Hameed Badawy, Yehia Arafa, and Stephan Eidenbenz. 2020. PPT-SASMM: Scalable Analytical Shared Memory Model: Predicting the Performance of Multicore Caches from a Single-Threaded Execution Trace. In The International Symposium on Memory Systems (Washington, DC, USA) (MEMSYS 2020). Association for Computing Machinery, New York, NY, USA, 341–351.
[3]
Antonia Bertolino. 2007. Software Testing Research: Achievements, Challenges, Dreams. In Future of Software Engineering (FOSE ’07). 85–103. https://doi.org/10.1109/FOSE.2007.25
[4]
Kristof Beyls and Erik H. D’Hollander. 2009. Refactoring for Data Locality. Computer 42, 2 (2009), 62–71. https://doi.org/10.1109/MC.2009.57
[5]
William R. Bush, Jonathan D. Pincus, and David J. Sielaff. [n. d.]. A static analyzer for finding dynamic programming errors. Software: Practice and Experience 30, 7 ([n. d.]), 775–802.
[6]
Calin Cascaval and David A. Padua. 2003. Estimating Cache Misses and Locality Using Stack Distances. In Proceedings of the 17th Annual International Conference on Supercomputing (San Francisco, CA, USA) (ICS ’03). ACM, New York, NY, USA, 150–159.
[7]
Arun Chauhan and Chun-Yu Shei. 2010. Static Reuse Distances for Locality-Based Optimizations in MATLAB. In Proceedings of the 24th ACM International Conference on Supercomputing (Tsukuba, Ibaraki, Japan) (ICS ’10). Association for Computing Machinery, New York, NY, USA, 295–304. https://doi.org/10.1145/1810085.1810125
[8]
Gopinath Chennupati, Nandakishore Santhi, Robert Bird, Sunil Thulasidasan, Abdel-Hameed A. Badawy, Satyajayant Misra, and Stephan Eidenbenz. 2018. A Scalable Analytical Memory Model for CPU Performance Prediction. In High Performance Computing Systems. Performance Modeling, Benchmarking, and Simulation, Stephen Jarvis, Steven Wright, and Simon Hammond (Eds.). Springer International Publishing, Cham, 114–135.
[9]
Patrick COUSOT, Radhia COUSOT, Jerome FERET, Antoine MINE, Laurent MAUBORGNE, David MONNIAUX, and Xavier RIVAL. 2007. Varieties of Static Analyzers: A Comparison with ASTREE. In First Joint IEEE/IFIP Symposium on Theoretical Aspects of Software Engineering (TASE ’07). 3–20. https://doi.org/10.1109/TASE.2007.55
[10]
Vijay D’Silva, Daniel Kroening, and Georg Weissenbacher. 2008. A Survey of Automated Techniques for Formal Software Verification. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 7 (2008), 1165–1178. https://doi.org/10.1109/TCAD.2008.923410
[11]
Pär Emanuelsson and Ulf Nilsson. 2008. A Comparative Study of Industrial Static Analysis Tools. Electronic Notes in Theoretical Computer Science 217 (2008), 5–21. https://doi.org/10.1016/j.entcs.2008.06.039 Proceedings of the 3rd International Workshop on Systems Software Verification (SSV 2008).
[12]
Chris Lattner and Vikram Adve. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proceedings of the International Symposium on Code Generation and Optimization: Feedback-directed and Runtime Optimization (Palo Alto, California) (CGO ’04). IEEE Computer Society, Washington, DC, USA, 75–86.
[13]
K.A. Lindlan, J. Cuny, A.D. Malony, S. Shende, B. Mohr, R. Rivenburgh, and C. Rasmussen. 2000. A Tool Framework for Static and Dynamic Analysis of Object-Oriented Software with Templates. In SC ’00: Proceedings of the 2000 ACM/IEEE Conference on Supercomputing. 49–49. https://doi.org/10.1109/SC.2000.10052
[14]
Richard L. Mattson, Jan Gecsei, D. R. Slutz, and I. L. Traiger. 1970. Evaluation Techniques for Storage Hierarchies. IBM Syst. J. 9, 2 (June 1970), 78–117.
[15]
Sri Hari Krishna Narayanan and Paul Hovland. 2016. Calculating Reuse Distance from Source Code. (1 2016). https://www.osti.gov/biblio/1366296
[16]
Qingpeng Niu, James Dinan, Qingda Lu, and Ponnuswamy Sadayappan. 2012. PARDA: A Fast Parallel Reuse Distance Analysis Algorithm. In Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium(IPDPS ’12). IEEE Computer Society, USA, 1284–1294.
[17]
S. Pakin and P. McCormick. 2013. Hardware-independent application characterization. In 2013 IEEE International Symposium on Workload Characterization (IISWC). 111–112.
[18]
Louis-Noël Pouchet. 2012. Polybench: The polyhedral benchmark suite. URL: http://www.cs.ucla.edu/pouchet/software/polybench (2012).
[19]
Rathijit Sen and David A. Wood. 2013. Reuse-based Online Models for Caches. In Proceedings of the ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems (Pittsburgh, PA, USA) (SIGMETRICS ’13). ACM, New York, NY, USA, 279–292.
[20]
Yutao Zhong, Xipeng Shen, and Chen Ding. 2009. Program Locality Analysis Using Reuse Distance. ACM Trans. Program. Lang. Syst. 31, 6 (2009), 20:1–20:39.
Recommendations
SVF: interprocedural static value-flow analysis in LLVM
CC '16: Proceedings of the 25th International Conference on Compiler ConstructionThis paper presents SVF, a tool that enables scalable and precise interprocedural Static Value-Flow analysis for C programs by leveraging recent advances in sparse analysis. SVF, which is fully implemented in LLVM, allows value-flow construction and ...
Static Reuse Profile Estimation for Array Applications
MEMSYS '24: Proceedings of the International Symposium on Memory SystemsReuse distance analysis is a widely recognized method for application characterization that illustrates cache locality. Although there are various techniques to calculate the reuse profile from dynamic memory traces, it is both time and space-consuming ...
Static memory leak detection using full-sparse value-flow analysis
ISSTA 2012: Proceedings of the 2012 International Symposium on Software Testing and AnalysisWe introduce a static detector, Saber, for detecting memory leaks in C programs. Leveraging recent advances on sparse pointer analysis, Saber is the first to use a full-sparse value-flow analysis for leak detection. Saber tracks the flow of values from ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2023
231 pages
ISBN:9798400716447
DOI:10.1145/3631882
Copyright © 2023 Owner/Author.
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 April 2024
Check for updates
Author Tags
Qualifiers
- Short-paper
- Research
- Refereed limited
Funding Sources
- Los Alamos National Laboratory is managed by Triad National Security, LLC, for the National Nuclear Security Administration of the U.S. DOE under contract 89233218CNA000001.
Conference
MEMSYS '23
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 362Total Downloads
- Downloads (Last 12 months)362
- Downloads (Last 6 weeks)58
Reflects downloads up to 27 Feb 2025
Other Metrics
Citations
Cited By
View all- Razzak ABarai ASanthi NBadawy A(2024)Static Reuse Profile Estimation for Array ApplicationsProceedings of the International Symposium on Memory Systems10.1145/3695794.3695817(235-244)Online publication date: 30-Sep-2024
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in