ARBSA: Adaptive Range-Based Simulated Annealing for FPGA Placement
- 25 October 2018
- 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. 38 (12) , 2330-2342
Abstract
Placement has always been the most time-consuming part of the FPGA compilation flow. Conventional simulated annealing has been unable to keep pace with ever increasing sizes of designs and FPGA chip resources. Without utilizing information of the circuit topology, it relies on large amounts of random swap operations, which are time-costly. This paper proposes an adaptive range-based algorithm to improve the behavior of swap operations and limit the swap distances by introducing the concept of range-limiting strategy for nets. It avoids unnecessary design space exploration, and thus can converge to near-optimal solutions much more quickly. The experimental results are based on the Titan benchmarks, which contain 4K to 30K blocks, including LABs, IOs, DSPs and RAMs. This approach achieves 2.82X speed up, 4.8% reduction on wire length, 4.1% improvement on critical path compared with the SA from VTR with wire length-driven optimization, and 1.78X speed up, 10% reduction on wire length, 2% reduction on critical path with path timing-driven optimization. It also manifests better scalability on larger benchmarks.Keywords
This publication has 24 references indexed in Scilit:
- VTR 7.0ACM Transactions on Reconfigurable Technology and Systems, 2014
- StarPlace: A new analytic method for FPGA placementIntegration, 2011
- Efficient and Deterministic Parallel Placement for FPGAsACM Transactions on Design Automation of Electronic Systems, 2011
- Recursive bisection based mixed block placement2004
- Can recursive bisection alone produce routable placements?2000
- VPR: a new packing, placement and routing tool for FPGA research1997
- A note on the effect of neighborhood structure in simulated annealingComputers & Operations Research, 1991
- Simulated annealing: A tool for operational researchEuropean Journal of Operational Research, 1990
- The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problemComputers & Operations Research, 1990
- Optimization by Simulated AnnealingScience, 1983