Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Guaranteed Yet Hard to Find: Uncovering FPGA Routing Convergence Paradox
 
Loading...
Thumbnail Image
conference paper

Guaranteed Yet Hard to Find: Uncovering FPGA Routing Convergence Paradox

Shrivastava, Shashwat  
•
Nicolic, Stefan
•
Tanaka, Sun
Show more
2025
Proceedings of the 33rd IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM 2025) [Forthcoming publication]
33rd IEEE International Symposium on Field-Programmable Custom Computing Machines

Routing is one of the major challenges of FPGA compilation. PathFinder is a ubiquitous FPGA routing algorithm used in industry and academia due to its ability to adapt to arbitrary routing architectures and user circuits. However, to this day, we do not fully understand why PathFinder works so well and what its limitations are. When a circuit fails to route, it is difficult to pinpoint the problem: architecture or algorithm. Usually, in such cases, either Pathfinder is fine-tuned or routing resources are added to the architecture to improve routability, thereby ignoring the inherent inefficiencies that may exist in Pathfinder, which further prevents us from designing siliconefficient architectures. In this work, to pinpoint the problem, we construct constrained routing problems where nets have access to limited but specific routing resources that guarantee a legal routing solution. Yet, even with a state-of-the-art implementation, PathFinder fails to find the guaranteed routing solution or any other solution, highlighting issues specific to PathFinder. The reduced search space makes the underlying behavior more accessible for analysis and reasoning, allowing us to identify inefficiencies in the current PathFinder paradigm and propose a solution to address them. We uncovered that PathFinder's greedy approach of routing individual connections yields an inefficient route tree, in terms of the total number of nodes. We then transfer this insight-through a simple yet effective algorithm-from the constrained to the standard setting, where the search space is not reduced. By constructing more efficient route trees, the routed wirelength and the number of routed connections were reduced by 6.4% and 3.6%, respectively, on average.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

Shrivastava25 Guaranteed Yet Hard to Find (eprint).pdf

Type

Main Document

Access type

openaccess

License Condition

CC BY

Size

326.6 KB

Format

Adobe PDF

Checksum (MD5)

8b82af8e04e58f928eec4ac7ca4bcc57

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés