High-Performance Placement Engine for Modern Large-Scale FPGAs With Heterogeneity and Clock Constraints
- 6 November 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 43 (3) , 956-969
Abstract
As field-programmable gate array (FPGA) architectures continue to evolve and become more complex, the heterogeneity and clock constraints imposed by modern FPGAs have posed significant challenges to FPGA placement. This paper proposes a high-performance placement engine for modern large-scale FPGAs with heterogeneity and clock constraints. To improve efficiency and scalability, we develop a clustering method considering both internal/external connectivity and the balance of block types to build the hierarchy. In each hierarchy level, we propose a hybrid penalty and augmented Lagrangian method (HPALM) to convert the FPGA global placement with heterogeneity and clock constraints into a series of unconstrained optimization subproblems, then use the Adam method to solve each subproblem. In particular, we prove that the HPALM is globally convergent for global placement. Besides, a matching-based IP block legalization is developed to legalize the DSPs and RAMs, and a multi-stage packing is presented to cluster LUTs and FFs into HCLBs. Finally, we propose a history-based legalization to legalize CLBs in an FPGA, and a simulated-annealing-based detailed placement is presented to reduce the wirelength while maintaining legality. Compared with the state-of-the-art works, experimental results based on the ISPD 2017 contest benchmarks show that the proposed algorithm can achieve the shortest routed wirelength in a reasonable runtime.Keywords
Funding Information
- Natural Science Foundation of Jiangsu Province, China (BK20210219)
- National Natural Science Foundation of China (62104037)
- National Key Research and Development Program of China (2022YFB4400500)
- MOST of Taiwan (MOST 110-2221-E-002-177-MY3)
This publication has 29 references indexed in Scilit:
- DREAMPlaceFPGA: An Open-Source Analytical Placer for Large Scale Heterogeneous FPGAs using Deep-Learning Toolkit2022
- Generalized Augmented Lagrangian and Its Applications to VLSI Global Placement2018
- Clock-aware ultrascale FPGA placement with machine learning routability prediction: (Invited paper)2017
- K-way partitioning based packing for FPGA logic blocks without input bandwidth constraint2012
- An efficient and effective detailed placement algorithm2005
- Cluster-based logic blocks for FPGAs: area-efficiency vs. input sharing and size2002
- RPack: routability-driven packing for cluster-based FPGAs2002
- Numerical Optimization1999
- VPR: a new packing, placement and routing tool for FPGA research1997
- Multiplier and gradient methodsJournal of Optimization Theory and Applications, 1969