An Efficient FPGA-based Floating Random Walk Solver for Capacitance Extraction using SDAccel
Xin Wei1, Changhao Yan1,a, Hai Zhou1,2, Dian Zhou1,3 and Xuan Zeng1,b
1State Key Lab of ASIC and System, Microelectronics Department, Fudan University, China
ayanch@fudan.edu.cn
bxzeng@fudan.edu.cn
2Department of Electrical Engineering and Computer Science, Northwestern University, USA
3Department of Electrical Engineering, University of Texas at Dallas, USA
ABSTRACT
The floating random walk (FRW) algorithm is an important method widely used in the capacitance extraction of very large-scale integration (VLSI) interconnects. FRW could be both time-consuming and power-consuming as the circuit scale grows. However, its highly parallel nature prompts us to accelerate it with FPGAs, which have shown great performance and energy efficiency potential to other computing architectures. In this paper, we propose a scalable FPGA/CPU heterogeneous framework of FRW using SDAccel. Large-scale circuits are partitioned first by the CPU into several segments, and these segments are then sent to the FPGA random walking one by one. The framework solves the challenge of limited FPGA onchip resource and integrates both merits of FPGAs and CPUs by targeting separate parts of the algorithm to suitable architecture, and the FPGA bitstream is built once for all. Several kernel optimization strategies are used to maximize performance of FPGAs. Besides, the FRW algorithm we use is the naive version with walking on spheres (WOS), which is much simpler and easier to implement than the complicatedly optimized version with walking on cubes (WOC). The implementation on AWS EC2 F1 (Xilinx VU9P FPGA) shows up to 6.1x performance and 42.6x energy efficiency over a quad-core CPU, and 5.2x energy efficiency over the state-of-the-art WOC implementation on an 8-core CPU.
