A Case for Precise, Fine-Grained Pointer Synthesis in High-Level Synthesis
Article No.: 30, Pages 1 - 26
Abstract
This article combines two practical approaches to improve pointer synthesis within HLS tools. Both approaches focus on inefficiencies in how HLS tools treat the points-to graph—a mapping that connects each instruction to the memory locations that it might access at runtime. HLS pointer synthesis first computes the points-to graph via pointer analysis and then implements its connections in hardware, which gives rise to two inefficiencies. First, HLS tools typically favour pointer analysis that is fast, sacrificing precision. Second, they also favour centralising memory connections in hardware for instructions that can point to more than one location.
In this article, we demonstrate that a more precise pointer analysis coupled with decentralised memory connections in hardware can substantially reduce the unnecessary sharing of memory resources. We implement both flow- and context-sensitive pointer analysis and fine-grained memory connections in two modern HLS tools, LegUp and Vitis HLS. An evaluation on three benchmark suites, ranging from non-trivial pointer use to standard HLS benchmarks, indicates that when we improve both precision and granularity of pointer synthesis, on average, we can reduce area and latency by around 42% and 37%, respectively.
References
[1]
N. Ramanathan. 2020. Supplementary material on GitHub. https://github.com/nadeshr/ppa-hls.
[2]
Lars Ole Andersen. 1994. Program Analysis and Specialization for the C Programming Language. Ph.D. Dissertation. University of Cophenhagen.
[3]
Berkeley Design Technology, Inc.2010. An Independent Evaluation of: The AutoESL AutoPilot High-Level Synthesis Tool. Tech. Rep.http://www.bdti.com/MyBDTI/pubs/AutoPilot.pdf.
[4]
Michael Burke, Paul Carini, Jong-Deok Choi, and Michael Hind. 1994. Flow-insensitive interprocedural alias analysis in the presence of pointers. In International Workshop on Languages and Compilers for Parallel Computing. Springer, 234–250.
[5]
Andrew Canis, Jongsok Choi, Mark Aldham, Victor Zhang, Ahmed Kammoona, Jason Anderson, Stephen Brown, and Tomasz Czajkowski. 2011. LegUp: High-level synthesis for FPGA-based processor/accelerator systems. In Field-Programmable Gate Arrays (FPGA).
[6]
Jianyi Cheng, Shane T. Fleming, Yu Ting Chen, Jason H. Anderson, and George A. Constantinides. 2019. EASY: Efficient arbiter synthesis from multi-threaded code. In 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 142–151.
[7]
Jong-Deok Choi, Michael Burke, and Paul Carini. 1993. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 232–245.
[8]
Philippe Coussy, Daniel D. Gajski, Michael Meredith, and Andres Takach. 2009. An introduction to high-level synthesis. IEEE Design and Test of Computers 26, 4 (2009).
[9]
Maryam Emami, Rakesh Ghiya, and Laurie J. Hendren. 1994. Context-sensitive interprocedural points-to analysis in the presence of function pointers. ACM SIGPLAN Notices 29, 6 (1994), 242–256.
[10]
Nicholas V. Giamblanco and Jason H. Anderson. 2019. ASAP: Automatic sizing and partitioning for dynamic memory heaps in high-level synthesis. In 2019 International Conference on Field-Programmable Technology (ICFPT). IEEE, 275–278.
[11]
Nicholas V. Giamblanco and Jason H. Anderson. 2019. A dynamic memory allocation library for high-level synthesis. In 2019 29th International Conference on Field Programmable Logic and Applications (FPL). IEEE, 314–320.
[12]
Yuko Hara, Hiroyuki Tomiyama, Shinya Honda, Hiroaki Takada, and Katsuya Ishii. 2008. CHStone: A benchmark program suite for practical C-based high-level synthesis. In 2008 IEEE International Symposium on Circuits and Systems. IEEE, 1192–1195.
[13]
Ben Hardekopf and Calvin Lin. 2007. The ant and the grasshopper: Fast and accurate pointer analysis for millions of lines of code. In 28th ACM SIGPLAN Conference on Programming Language Design and Implementation. 290–299.
[14]
Ben Hardekopf and Calvin Lin. 2009. Semi-sparse flow-sensitive pointer analysis. ACM SIGPLAN Notices 44, 1 (2009), 226–238.
[15]
Ben Hardekopf and Calvin Lin. 2011. Flow-sensitive pointer analysis for millions of lines of code. In International Symposium on Code Generation and Optimization (CGO 2011). IEEE, 289–298.
[16]
Nevin Heintze and Olivier Tardieu. 2001. Demand-driven pointer analysis. ACM SIGPLAN Notices 36, 5 (2001), 24–34.
[17]
Michael Hind and Anthony Pioli. 2000. Which pointer analysis should I use? In 2000 ACM SIGSOFT International Symposium on Software Testing and Analysis. 113–123.
[18]
Sakari Lahti, Panu Sjövall, Jarno Vanne, and Timo D. Hämäläinen. 2018. Are we there yet? A study on the state of high-level synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 38, 5 (2018), 898–911.
[19]
Chris Lattner and Vikram Adve. 2002. The LLVM instruction set and compilation strategy.CS Dept., Univ. of Illinois at Urbana-Champaign, Tech. Report UIUCDCS (2002).
[20]
Chris Lattner and Vikram Adve. 2003. Data Structure Analysis: An Efficient Context-sensitive Heap Analysis. Technical Report. Tech. Report UIUCDCSR-2003-2340, Computer Science Dept., Univ. of Illinois.
[21]
LegUp Computing Inc.2017. LegUp 5.1 Documentation. (2017). https://www.legupcomputing.com/docs/legup-5.1-docs/index.html.
[22]
LegUp Computing Inc.2017. LegUp 6.4 Documentation. (2017). https://bit.ly/legup-memory-controller.
[23]
Lian Li, Cristina Cifuentes, and Nathan Keynes. 2013. Precise and scalable context-sensitive pointer analysis via value flow graph. ACM SIGPLAN Notices 48, 11 (2013), 85–96.
[24]
Tingyuan Liang, Jieru Zhao, Liang Feng, Sharad Sinha, and Wei Zhang. 2018. HI-DMM: High-performance dynamic memory management in high-level synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 37, 11 (2018), 2555–2566.
[25]
Grant Martin and Gary Smith. 2009. High-level synthesis: Past, present, and future. IEEE Design & Test of Computers 26, 4 (2009), 18–25.
[26]
Erik M. Nystrom, Hong-Seok Kim, and W. Hwu Wen-mei. 2004. Bottom-up and top-down context-sensitive summary-based pointer analysis. In International Static Analysis Symposium. Springer, 165–180.
[27]
Christian Pilato and Fabrizio Ferrandi. 2013. Bambu: A modular framework for the high level synthesis of memory-intensive applications. In 2013 23rd International Conference on Field Programmable Logic and Applications. IEEE, 1–4.
[28]
Christian Pilato, Fabrizio Ferrandi, and Donatella Sciuto. 2011. A design methodology to implement memory accesses in high-level synthesis. In 7th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis. 49–58.
[29]
Ganesan Ramalingam. 1994. The undecidability of aliasing. ACM Transactions on Programming Languages and Systems (TOPLAS) 16, 5 (1994), 1467–1471.
[30]
Nadesh Ramanathan, George A. Constantinides, and John Wickerson. 2018. Concurrency-aware thread scheduling for high-level synthesis. In 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). IEEE, 101–108.
[31]
Nadesh Ramanathan, George A. Constantinides, and John Wickerson. 2020. Precise pointer analysis in high-level synthesis. In 2020 30th International Conference on Field-Programmable Logic and Applications (FPL). IEEE, 220–224.
[32]
Nadesh Ramanathan, John Wickerson, and George A. Constantinides. 2017. Scheduling weakly consistent C concurrency for reconfigurable hardware. IEEE Trans. Comput. 67, 7 (2017), 992–1006.
[33]
Luc Séméria and Giovanni De Micheli. 1998. SpC: Synthesis of pointers in C: Application of pointer analysis to the behavioral synthesis from C. In Proceedings of the 1998 IEEE/ACM International Conference on Computer-aided Design. 340–346.
[34]
Luc Séméria and Giovanni De Micheli. 2001. Resolution, optimization, and encoding of pointer variables for the behavioral synthesis from C. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 20, 2 (2001), 213–233.
[35]
Luc Séméria, Koichi Sato, and Giovanni De Micheli. 2001. Synthesis of hardware models in C with pointers and complex data structures. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 9, 6 (2001), 743–756.
[36]
Yannis Smaragdakis and George Balatsouras. 2015. Pointer analysis. Foundations and Trends® in Programming Languages 2, 1 (2015), 1–69.
[37]
Johannes Späth, Lisa Nguyen Quang Do, Karim Ali, and Eric Bodden. 2016. Boomerang: Demand-driven flow-and context-sensitive pointer analysis for java. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
[38]
Bjarne Steensgaard. 1996. Points-to analysis in almost linear time. In 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 32–41.
[39]
Yulei Sui and Jingling Xue. 2016. SVF: Interprocedural static value-flow analysis in LLVM. In 25th International Conference on Compiler Construction. ACM, 265–266.
[40]
Yulei Sui and Jingling Xue. 2018. Value-flow-based demand-driven pointer analysis for C and C++. IEEE Transactions on Software Engineering (2018).
[41]
John Whaley and Monica Lam. 2007. Context-Sensitive Pointer Analysis using Binary Decision Diagrams. Ph.D. Dissertation. Citeseer.
[42]
Robert P. Wilson, Robert S. French, Christopher S. Wilson, Saman P. Amarasinghe, Jennifer M. Anderson, Steve W. K. Tjiang, Shih-Wei Liao, Chau-Wen Tseng, Mary W. Hall, Monica S. Lam, and John L. Hennessy. 1994. SUIF: An infrastructure for research on parallelizing and optimizing compilers. ACM SIGPLAN Notices 29, 12 (1994), 31–37.
[43]
Robert P. Wilson and Monica S. Lam. 1995. Efficient context-sensitive pointer analysis for C programs. ACM SIGPLAN Notices 30, 6 (1995), 1–12.
[44]
Felix Winterstein. 2017. Separation Logic for High-Level Synthesis. Springer.
[45]
Felix Winterstein, Samuel Bayliss, and George A. Constantinides. 2013. High-level synthesis of dynamic data structures: A case study using Vivado HLS. In 2013 International Conference on Field-Programmable Technology (FPT). IEEE, 362–365.
[46]
Xilinx. 2018. Vivado Design Suite User Guide: High-Level Synthesis (v2018.2).
[47]
Xilinx. 2020. Vitis Unified Software Platform Documentation: Application Acceleration Development (v2020.1).
[48]
Zeping Xue and David B. Thomas. 2015. SysAlloc: A hardware manager for dynamic memory allocation in heterogeneous systems. In 2015 25th International Conference on Field Programmable Logic and Applications (FPL). IEEE, 1–7.
[49]
Zeping Xue and David B. Thomas. 2016. SynADT: Dynamic data structures in high level synthesis. In 2016 IEEE 24th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). IEEE, 64–71.
[50]
Y. Sui and J. Xue. 2020. PTABen Benchmark Suite. (2020). https://github.com/SVF-tools/PTABen.
[51]
Jianwen Zhu. 2005. Towards scalable flow and context sensitive pointer analysis. In 42nd Design Automation Conference, 2005. IEEE, 831–836.
[52]
Jianwen Zhu and Silvian Calman. 2004. Symbolic pointer analysis revisited. In PLDI. ACM, 145–157.
Index Terms
- A Case for Precise, Fine-Grained Pointer Synthesis in High-Level Synthesis
Recommendations
Hybrid Inlining: A Framework for Compositional and Context-Sensitive Static Analysis
ISSTA 2023: Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and AnalysisContext-sensitivity is essential for achieving good precision in inter-procedural static analysis. To be context-sensitive, top-down analysis needs to fully inline all the statements in a callee at all its callsites, leading to statement explosion. ...
Practical Integrated Analysis of Pointers, Dataflow and Control Flow
This article presents a family of static analyses to determine pointer targets, control flow, and dataflow in combination. The integrated solution to these mutually dependent problems approaches the result from the optimistic side. It is a general ...
Semi-sparse flow-sensitive pointer analysis
POPL '09Pointer analysis is a prerequisite for many program analyses, and the effectiveness of these analyses depends on the precision of the pointer information they receive. Two major axes of pointer analysis precision are flow-sensitivity and context-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
275 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Journal Family
Publication History
Published: 08 March 2022
Accepted: 01 October 2021
Revised: 01 September 2021
Received: 01 June 2021
Published in TODAES Volume 27, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
- Refereed
Funding Sources
- EPSRC
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 245Total Downloads
- Downloads (Last 12 months)49
- Downloads (Last 6 weeks)7
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format