OpenPARF: An Open-source Placement and Routing Framework for Large-scale Heterogeneous FPGAs with Deep Learning Toolkit

MAI Jing; WANG Jiarui; DI Zhixiong; LIN Yibo

doi:10.11999/JEIT230387

Volume 45 Issue 9

Sep. 2023

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2023 > 45(9): 3118-3131

MAI Jing, WANG Jiarui, DI Zhixiong, LIN Yibo. OpenPARF: An Open-source Placement and Routing Framework for Large-scale Heterogeneous FPGAs with Deep Learning Toolkit[J]. Journal of Electronics & Information Technology, 2023, 45(9): 3118-3131. doi: 10.11999/JEIT230387

Citation:

MAI Jing, WANG Jiarui, DI Zhixiong, LIN Yibo. OpenPARF: An Open-source Placement and Routing Framework for Large-scale Heterogeneous FPGAs with Deep Learning Toolkit[J]. Journal of Electronics & Information Technology, 2023, 45(9): 3118-3131. doi: 10.11999/JEIT230387

Citation:

PDF( 2843 KB)

OpenPARF: An Open-source Placement and Routing Framework for Large-scale Heterogeneous FPGAs with Deep Learning Toolkit

doi: 10.11999/JEIT230387

MAI Jing^{1, 2},
WANG Jiarui^{1, 2},
DI Zhixiong³,
LIN Yibo^{2
,
,}

1.
School of Computer Science, Peking University, Beijing 100871, China
2.
School of Integrated Circuits, Peking University, Beijing 100871, China
3.
School of Information and Science and Technology, Southwest Jiaotong University, Chengdu 611756, China

Funds: Key Research and Development Program Projects of the Ministry of Science and Technology (2021ZD0114702)

Received Date: 2023-05-08
Rev Recd Date: 2023-08-21

Available Online: 2023-08-23

Publish Date: 2023-09-27

Abstract

Abstract

An Open-source Placement And Routing Framework (OpenPARF) for large-scale FPGA physical design is proposed in this paper. OpenPARF is implemented with of deep learning toolkit PyTorch and supports GPU massive parallel acceleration. For placement, the framework incorporates a novel asymmetric multi-electrostatic filed system to model the FPGA placement problem. For routing, OpenPARF integrates finer-grained internal routing of FPGA Configurable Logic Blocks (CLBs) in the routing model and supports routing on large-scale irregular routing resource graph. This study can significantly improve the FPGA routing algorithm's efficiency and effectiveness. Experimental results on ISPD 2016 and ISPD 2017 FPGA conest benchmarks and industrial-level FPGA benchmarks demonstrate that OpenPARF can achieve 0.4%～12.7% improvement in routed wirelength and more than two times speedup in placement.
- Integrated circuit design and design automation,
- Physical design,
- FPGA,
- Placement and douting,
- Machine learning

FullText(HTML)

References(41)

References

[1]	MARKOV I L, HU Jin, and KIM M C. Progress and challenges in VLSI placement research[J]. Proceedings of the IEEE, 2015, 103(11): 1985–2003. doi: 10.1109/JPROC.2015.2478963
[2]	CHEN Deming, CONG J, and PAN Peichan. FPGA design automation: A survey[M]. BOX P O. Foundations and Trends in Electronic Design Automation. Hanover: Now Publishers Inc. , 2006.
[3]	MURRAY K E, WHITTY S, LIU Suya, et al. Timing-driven Titan: Enabling large benchmarks and exploring the gap between academic and commercial CAD[J]. ACM Transactions on Reconfigurable Technology and Systems, 2015, 8(2): 1–18. doi: 10.1145/2629579
[4]	MURRAY K E, PETELIN O, ZHONG Suya, et al. VTR 8: High-performance CAD and customizable FPGA architecture modelling[J]. ACM Transactions on Reconfigurable Technology and Systems, 2020, 13(2): 1–55. doi: 10.1145/3388617
[5]	UltraScale architecture configurable logic block user guide (UG574)[EB/OL].https://china.xilinx.com/content/dam/xilinx/support/documents/user_guides/ug574-ultrascale-clb.pdf, 2017.
[6]	YANG S, GAYASEN A, MULPURI C, et al. Routability-driven FPGA placement contest[C]. The 2016 on International Symposium on Physical Design, Santa Rosa, USA, 2016: 139–143.
[7]	ZHANG Niansong, CHEN Xiang, and KAPRE N. RapidLayout: Fast hard block placement of FPGA-optimized systolic arrays using evolutionary algorithm[J]. ACM Transactions on Reconfigurable Technology and Systems, 2022, 15(4): 38. doi: 10.1145/3501803
[8]	ZHOU Yun, MAIDEE P, LAVIN C, et al. RWRoute: An open-source timing-driven router for commercial FPGAs[J]. ACM Transactions on Reconfigurable Technology and Systems, 2022, 15(1): 8. doi: 10.1145/3491236
[9]	YANG S, MULPURI C, REDDY S, et al. Clock-aware FPGA placement contest[C]. The 2017 ACM on International Symposium on Physical Design, Portland, USA, 2017: 159–164.
[10]	MARTIN T, BARNES C, AREIBI S, et al. An adaptive sequential decision making flow for FPGAs using machine learning[C]. 2022 International Conference on Microelectronics (ICM), Casablanca, Morocco, 2022: 34–37.
[11]	LIANG Tingyuan, CHEN Gengjie, ZHAO Jieru, et al. AMF-placer: High-performance analytical mixed-size placer for FPGA[C]. 2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD), Munich, Germany, 2021: 1–9.
[12]	CHEN T C, JIANG Zhewei, HSU T C, et al. NTUplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(7): 1228–1240. doi: 10.1109/TCAD.2008.923063
[13]	LU Jingwei, CHEN Pengwen, CHANG C C, et al. ePlace: Electrostatics based placement using Nesterov’s method[C]. The the 51st Annual Design Automation Conference, San Francisco, USA, 2014: 1–6.
[14]	CHENG C K, KAHNG A B, KANG I, et al. RePlAce: Advancing solution quality and routability validation in global placement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 38(9): 1717–1730. doi: 10.1109/TCAD.2018.2859220
[15]	LIU Lixin, FU Bangqi, WONG M D F, et al. Xplace: An extremely fast and extensible global placement framework[C]. The 59th ACM/IEEE Design Automation Conference, San Francisco, USA, 2022: 1309–1314.
[16]	AGNESINA A, RAJVANSHI P, YANG Tian, et al. AutoDMP: Automated DREAMPlace-based macro placement[C]. The 2023 International Symposium on Physical Design, Virtual Event, USA, 2023: 149–157.
[17]	MAI Jing, MENG Yibai, DI Zhixiong, et al. Multi-electrostatic FPGA placement considering SLICEL-SLICEM heterogeneity and clock feasibility[C]. The 59th ACM/IEEE Design Automation Conference, San Francisco, USA, 2022: 649–654.
[18]	RAJARATHNAM R S, ALAWIEH M B, JIANG Zixuan, et al. DREAMPlaceFPGA: An open-source analytical placer for large scale heterogeneous FPGAs using deep-learning toolkit[C]. 2022 27th Asia and South Pacific Design Automation Conference (ASP-DAC), Taipei, China, 2022: 300–306.
[19]	RAJARATHNAM R S, JIANG Zixuan, IYER M A, et al. DREAMPlaceFPGA-PL: An open-source GPU-accelerated packer-legalizer for heterogeneous FPGAs[C]. The 2023 International Symposium on Physical Design, Virtual Event, USA, 2023: 175–184.
[20]	MENG Yibai, LI Wuxi, LIN Yibo, et al. elfPlace: Electrostatics-based placement for large-scale heterogeneous FPGAs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(1): 155–168. doi: 10.1109/TCAD.2021.3053191
[21]	KIM M C, HU Jin, LEE D J, et al. A SimPLR method for routability-driven placement[C]. 2011 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Jose, USA, 2011: 67–73.
[22]	LI Wuxi, DHAR S, and PAN D Z. UTPlaceF: A routability-driven FPGA placer with physical and congestion aware packing[C]. The 2016 IEEE/ACM International Conference on Computer-Aided Design, Austin, USA, 2016: 1–7.
[23]	CHEN Gengjie, PUI C W, CHOW W K, et al. RippleFPGA: Routability-driven simultaneous packing and placement for modern FPGAs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(10): 2022–2035. doi: 10.1109/TCAD.2017.2778058
[24]	HSU M K, CHOU S, LIN T H, et al. Routability-driven analytical placement for mixed-size circuit designs[C]. 2011 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Jose, USA, 2011: 80–84.
[25]	CHEN Jianli, LIN Zhifeng, KUO Y C, et al. Clock-aware placement for large-scale heterogeneous FPGAs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(12): 5042–5055. doi: 10.1109/TCAD.2020.2968892
[26]	PUI C W, CHEN Gengjie, MA Yuzhe, et al. Clock-aware ultrascale FPGA placement with machine learning routability prediction: (Invited paper)[C]. 2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Irvine, USA, 2017: 929–936.
[27]	LI Wuxi, LIN Yibo, LI Meng, et al. UTPlaceF 2.0: A high-performance clock-aware FPGA placement engine[J]. ACM Transactions on Design Automation of Electronic Systems, 2018, 23(4): 42. doi: 10.1145/3174849
[28]	LI Wuxi, DEHKORDI M E, YANG S, et al. Simultaneous placement and clock tree construction for modern FPGAs[C]. The 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Seaside, USA, 2019: 132–141.
[29]	ZHU Ziran, MEI Yangjie, LI Zijun, et al. High-performance placement for large-scale heterogeneous FPGAs with clock constraints[C]. The 59th ACM/IEEE Design Automation Conference, San Francisco, USA, 2022: 643–648.
[30]	FENG Wenyi. K-way partitioning based packing for FPGA logic blocks without input bandwidth constraint[C]. 2012 International Conference on Field-Programmable Technology, Seoul, Korea (South), 2012: 8–15.
[31]	BETZ V and ROSE J. VPR: A new packing, placement and routing tool for FPGA research[M]. LUK W, CHEUNG P Y K and GLESNER M. Field-Programmable Logic and Applications. Berlin, Heidelberg: Springer, 1997: 213–222.
[32]	LI Wuxi and PAN D Z. A new paradigm for FPGA placement without explicit packing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 38(11): 2113–2126. doi: 10.1109/TCAD.2018.2877017
[33]	DI Zhixiong, TAO Runzhe, CHEN Lin, et al. Imbalanced large graph learning framework for FPGA logic elements packing prediction[EB/OL]. Available: http: //arxiv. org/abs/2308. 03231, 2023.
[34]	MCMURCHIE L and EBELING C. PathFinder: A negotiation-based performance-driven router for FPGAs[C]. Third International ACM Symposium on Field-Programmable Gate Arrays, Napa Valley, USA, 1995: 111–117.
[35]	MURRAY K E, ZHONG Sheng, and BETZ V. AIR: A fast but lazy timing-driven FPGA router[C]. 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC), Beijing, China, 2020: 338–344.
[36]	ZHOU Yun, VERCRUYCE D, and STROOBANDT D. Accelerating FPGA routing through algorithmic enhancements and connection-aware parallelization[J]. ACM Transactions on Reconfigurable Technology and Systems, 2020, 13(4): 1–26. doi: 10.1145/3406959
[37]	ZHA Yue and LI Jing. Revisiting pathfinder routing algorithm[C]. Proceedings of the 2022 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Virtual Event, USA, 2022: 24–34.
[38]	SHEN Minghua and LUO Guojie. Corolla: GPU-accelerated FPGA routing based on subgraph dynamic expansion[C]. The 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Monterey, USA, 2017: 105–114.
[39]	WANG Jiarui, MAI Jing, DI Zhixiong, et al. A Robust FPGA router with concurrent intra-CLB rerouting[C]. The 28th Asia and South Pacific Design Automation Conference, Tokyo, Japan, 2023: 529–534.
[40]	RAY B N B, TRIPATHY A R, SAMAL P, et al. Half-perimeter wirelength model for VLSI analytical placement[C]. 2014 International Conference on Information Technology, Bhubaneswar, India, 2014: 287–292.
[41]	SPINDLER P and JOHANNES F M. Fast and accurate routing demand estimation for efficient routability-driven placement[C]. 2007 Design Automation & Test in Europe Conference & Exhibition, Nice, France, 2007: 1–6.