An Efficient FPGA-based Floating Random Walk Solver for Capacitance Extraction using SDAccel

Xin Wei, Changhao Yan*, Hai Zhou, Dian Zhou, Xuan Zeng

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 on-chip 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1040-1045
Number of pages6
ISBN (Electronic)9783981926323
DOIs
StatePublished - May 14 2019
Event22nd Design, Automation and Test in Europe Conference and Exhibition, DATE 2019 - Florence, Italy
Duration: Mar 25 2019Mar 29 2019

Publication series

NameProceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019

Conference

Conference22nd Design, Automation and Test in Europe Conference and Exhibition, DATE 2019
CountryItaly
CityFlorence
Period3/25/193/29/19

Fingerprint

Capacitance
Field Programmable Gate Array
Field programmable gate arrays (FPGA)
Random walk
Program processors
Energy Efficiency
Energy efficiency
Regular hexahedron
Networks (circuits)
VLSI circuits
Interconnect
Accelerate
Chip
Maximise
Integrate
kernel
Resources
Optimization
Computing

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering
  • Safety, Risk, Reliability and Quality
  • Control and Optimization

Cite this

Wei, X., Yan, C., Zhou, H., Zhou, D., & Zeng, X. (2019). An Efficient FPGA-based Floating Random Walk Solver for Capacitance Extraction using SDAccel. In Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019 (pp. 1040-1045). [8714992] (Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.23919/DATE.2019.8714992
Wei, Xin ; Yan, Changhao ; Zhou, Hai ; Zhou, Dian ; Zeng, Xuan. / An Efficient FPGA-based Floating Random Walk Solver for Capacitance Extraction using SDAccel. Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 1040-1045 (Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019).
@inproceedings{edcabcea95cf4a238c0a6fe2f54d7b82,
title = "An Efficient FPGA-based Floating Random Walk Solver for Capacitance Extraction using SDAccel",
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 on-chip 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.",
author = "Xin Wei and Changhao Yan and Hai Zhou and Dian Zhou and Xuan Zeng",
year = "2019",
month = "5",
day = "14",
doi = "10.23919/DATE.2019.8714992",
language = "English (US)",
series = "Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1040--1045",
booktitle = "Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019",
address = "United States",

}

Wei, X, Yan, C, Zhou, H, Zhou, D & Zeng, X 2019, An Efficient FPGA-based Floating Random Walk Solver for Capacitance Extraction using SDAccel. in Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019., 8714992, Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019, Institute of Electrical and Electronics Engineers Inc., pp. 1040-1045, 22nd Design, Automation and Test in Europe Conference and Exhibition, DATE 2019, Florence, Italy, 3/25/19. https://doi.org/10.23919/DATE.2019.8714992

An Efficient FPGA-based Floating Random Walk Solver for Capacitance Extraction using SDAccel. / Wei, Xin; Yan, Changhao; Zhou, Hai; Zhou, Dian; Zeng, Xuan.

Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 1040-1045 8714992 (Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - An Efficient FPGA-based Floating Random Walk Solver for Capacitance Extraction using SDAccel

AU - Wei, Xin

AU - Yan, Changhao

AU - Zhou, Hai

AU - Zhou, Dian

AU - Zeng, Xuan

PY - 2019/5/14

Y1 - 2019/5/14

N2 - 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 on-chip 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.

AB - 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 on-chip 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.

UR - http://www.scopus.com/inward/record.url?scp=85066620523&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85066620523&partnerID=8YFLogxK

U2 - 10.23919/DATE.2019.8714992

DO - 10.23919/DATE.2019.8714992

M3 - Conference contribution

AN - SCOPUS:85066620523

T3 - Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019

SP - 1040

EP - 1045

BT - Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Wei X, Yan C, Zhou H, Zhou D, Zeng X. An Efficient FPGA-based Floating Random Walk Solver for Capacitance Extraction using SDAccel. In Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 1040-1045. 8714992. (Proceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019). https://doi.org/10.23919/DATE.2019.8714992