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
 
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
Type
conference paper
Author(s)
Shrivastava, Shashwat  

EPFL

Nicolic, Stefan

University of Novi Sad

Tanaka, Sun
Ravishankar, Chirag
Gaitonde, Dinesh
Stojilovic, Mirjana  

EPFL

Date Issued

2025

Published in
Proceedings of the 33rd IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM 2025) [Forthcoming publication]
Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
SIN-ENS  
PARSA  
Event nameEvent acronymEvent placeEvent date
33rd IEEE International Symposium on Field-Programmable Custom Computing Machines

FCCM 2025

Fayetteville, Arkansas, USA

2025-05-04 - 2025-05-07

RelationRelated workURL/DOI

IsSupplementedBy

Guaranteed Yet Hard to Find: Uncovering FPGA Routing Convergence Paradox [software]

https://infoscience.epfl.ch/handle/20.500.14299/247869
Available on Infoscience
March 17, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/247877
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