24 December 2022 in ACM Transactions on Design Automation of Electronic Systems
Chip floorplanning has long been a critical task with high computation complexity in the physical implementation of VLSI chips. Its key objective is to determine the initial locations of large chip modules with minimized wirelength while adhering to the density constraint, which in essence is a process of constructing an optimized mapping from circuit connectivity to physical locations. Proven to be an NP-hard problem, chip floorplanning is difficult to be solved efficiently using algorithmic approaches. This article presents GraphPlanner, a variational graph-convolutional-network-based deep learning technique for chip floorplanning. GraphPlanner is able to learn an optimized and generalized mapping between circuit connectivity and physical wirelength and produce a chip floorplan using efficient model inference. GraphPlanner is further equipped with an efficient clustering method, a unification of hyperedge coarsening with graph spectral clustering, to partition a large-scale netlist into high-quality clusters with minimized inter-cluster weighted connectivity. GraphPlanner has been integrated with two state-of-the-art mixed-size placers. Experimental studies using both academic benchmarks and industrial designs demonstrate that compared to state-of-the-art mixed-size placers alone, GraphPlanner improves placement runtime by 25% with 4% wirelength reduction on average.
19 May 2011 in IEEE Transactions on Circuits and Systems I: Regular Papers
For anti-fuse or flash-memory-based field-programmable gate arrays (FPGAs), single-event transient (SET)-induced faults are significantly more pronounced than single-event upsets (SEUs). While most existing work studies SEU, this paper proposes a retiming algorithm for mitigating variational SETs (i.e., SETs with different durations and strengths). Considering the reshaping effect of an SET pulse caused by broadening and attenuation during its propagation, SET-aware retiming (SaR) redistributes combinational paths via post layout retiming and minimizes the possibility that an SET pulse is latched. The SaR problem is formulated as an integer linear programming (ILP) problem and solved efficiently by a progressive ILP approach. In contrast to existing SET-mitigation techniques, the proposed SaR does not change the FPGA architecture or the layout of an FPGA application. Instead, it reconfigures the connection between a flip-flop and an LUT within a programmable logic block. Experimental results show that SaR increases mean-time-to-failure (MTTF) by 78% for variational SETs with a 10-min runtime limit while preserving the clock frequency on ISCAS89 benchmark circuits. To the best of our knowledge, this paper is the first in-depth study on FPGA retiming for SET mitigation.
8 March 2024 in IEEE Transactions on Very Large Scale Integration (VLSI) Systems
Floorplanning is a complex physical design problem that produces initial locations of movable objects, the quality of which has a great impact on downstream tasks such as placement and routing. To improve the efficacy of floorplanning, machine learning techniques have recently been recruited for help. However, the application-specific location constraints (IOs and cells with fixed locations) pose a huge challenge for machine learning. This article presents a novel uniformization approach by Dirichlet boundary conditions, which decomposes floorplanning into two easier-to-solve subproblems, namely a convex quadratic wirelength optimization problem with location constraints and an NP-hard combinatorial problem with homogeneous Dirichlet boundary conditions. The former problem is efficiently solved using quadratic optimization, and the latter is addressed by efficient graph inference using the proposed hierarchical GNN-based model. The proposed floorplanner called DPlanner has been integrated with state-of-the-art mixed-size placers to generate high-quality placement solutions with up to 56% and 41% improvement in placement iterations and runtime. In addition, compared to the state-of-the-art integrated floorplanning-placement flow, DPlanner achieves over a 20% improvement in placement iteration and more than a 21% reduction in total runtime, along with a 2% average reduction in wirelength.