Advanced search
1 file | 2.41 MB Add to list

Accelerating FPGA routing through algorithmic enhancements and connection-aware parallelization

Yun Zhou (UGent) , Dries Vercruyce (UGent) and Dirk Stroobandt (UGent)
Author
Organization
Abstract
Routing is a crucial step in Field Programmable Gate Array (FPGA) physical design, as it determines the routes of signals in the circuit, which impacts the design implementation quality significantly. It can be very time-consuming to successfully route all the signals of large circuits that utilize many FPGA resources. Attempts have been made to shorten the routing runtime for efficient design exploration while expecting high-quality implementations. In this work, we elaborate on the connection-based routing strategy and algorithmic enhancements to improve the serial FPGA routing. We also explore a recursive partitioning-based parallelization technique to further accelerate the routing process. To exploit more parallelism by a finer granularity in both spatial partitioning and routing, a connection-aware routing bounding box model is proposed for the source-sink connections of the nets. It is built upon the location information of each connection’s source, sink, and the geometric center of the net that the connection belongs to, different from the existing net-based routing bounding box that covers all the pins of the entire net. We present that the proposed connection-aware routing bounding box is more beneficial for parallel routing than the existing net-based routing bounding box. The quality and runtime of the serial and multi-threaded routers are compared to the router in VPR 7.0.7. The large heterogeneous Titan23 designs that are targeted to a detailed representation of the Stratix IV FPGA are used for benchmarking. With eight threads, the parallel router using the connection-aware routing bounding box model reaches a speedup of 6.1× over the serial router in VPR 7.0.7, which is 1.24× faster than the one using the existing net-based routing bounding box model, while reducing the total wire-length by 10% and the critical path delay by 7%.
Keywords
FPGA routing, timing-driven, connection-based routing, algorithmic enhancements, connection-aware parallelization, routing bounding box model, partitioning-based, DESIGN

Downloads

  • (...).pdf
    • full text (Published version)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 2.41 MB

Citation

Please use this url to cite or link to this publication:

MLA
Zhou, Yun, et al. “Accelerating FPGA Routing through Algorithmic Enhancements and Connection-Aware Parallelization.” ACM TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS, vol. 13, no. 4, 2020, doi:10.1145/3406959.
APA
Zhou, Y., Vercruyce, D., & Stroobandt, D. (2020). Accelerating FPGA routing through algorithmic enhancements and connection-aware parallelization. ACM TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS, 13(4). https://doi.org/10.1145/3406959
Chicago author-date
Zhou, Yun, Dries Vercruyce, and Dirk Stroobandt. 2020. “Accelerating FPGA Routing through Algorithmic Enhancements and Connection-Aware Parallelization.” ACM TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS 13 (4). https://doi.org/10.1145/3406959.
Chicago author-date (all authors)
Zhou, Yun, Dries Vercruyce, and Dirk Stroobandt. 2020. “Accelerating FPGA Routing through Algorithmic Enhancements and Connection-Aware Parallelization.” ACM TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS 13 (4). doi:10.1145/3406959.
Vancouver
1.
Zhou Y, Vercruyce D, Stroobandt D. Accelerating FPGA routing through algorithmic enhancements and connection-aware parallelization. ACM TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS. 2020;13(4).
IEEE
[1]
Y. Zhou, D. Vercruyce, and D. Stroobandt, “Accelerating FPGA routing through algorithmic enhancements and connection-aware parallelization,” ACM TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS, vol. 13, no. 4, 2020.
@article{8672568,
  abstract     = {Routing is a crucial step in Field Programmable Gate Array (FPGA) physical design, as it determines the routes of signals in the circuit, which impacts the design implementation quality significantly. It can be very time-consuming to successfully route all the signals of large circuits that utilize many FPGA resources. Attempts have been made to shorten the routing runtime for efficient design exploration while expecting high-quality implementations. In this work, we elaborate on the connection-based routing strategy and algorithmic enhancements to improve the serial FPGA routing. We also explore a recursive partitioning-based parallelization technique to further accelerate the routing process. To exploit more parallelism by a finer granularity in both spatial partitioning and routing, a connection-aware routing bounding box model is proposed for the source-sink connections of the nets. It is built upon the location information of each connection’s source, sink, and the geometric center of the net that the connection belongs to, different from the existing net-based routing bounding box that covers all the pins of the entire net. We present that the proposed connection-aware routing bounding box is more beneficial for parallel routing than the existing net-based routing bounding box. The quality and runtime of the serial and multi-threaded routers are compared to the router in VPR 7.0.7. The large heterogeneous Titan23 designs that are targeted to a detailed representation of the Stratix IV FPGA are used for benchmarking. With eight threads, the parallel router using the connection-aware routing bounding box model reaches a speedup of 6.1× over the serial router in VPR 7.0.7, which is 1.24× faster than the one using the existing net-based routing bounding box model, while reducing the total wire-length by 10% and the critical path delay by 7%.},
  articleno    = {18},
  author       = {Zhou, Yun and Vercruyce, Dries and Stroobandt, Dirk},
  issn         = {1936-7406},
  journal      = {ACM TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS},
  keywords     = {FPGA routing,timing-driven,connection-based routing,algorithmic enhancements,connection-aware parallelization,routing bounding box model,partitioning-based,DESIGN},
  language     = {eng},
  number       = {4},
  pages        = {26},
  title        = {Accelerating FPGA routing through algorithmic enhancements and connection-aware parallelization},
  url          = {http://dx.doi.org/10.1145/3406959},
  volume       = {13},
  year         = {2020},
}

Altmetric
View in Altmetric
Web of Science
Times cited: