Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
versions View all 2 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Guaranteed Yet Hard to Find: Uncovering FPGA Routing Convergence Paradox

Authors: Shrivastava, Shashwat; Nikolić, Stefan; Tanaka, Sun; Ravishankar, Chirag; Gaitonde, Dinesh; Stojilović, Mirjana;

Guaranteed Yet Hard to Find: Uncovering FPGA Routing Convergence Paradox

Abstract

This repository contains the data and software needed to reproduce the results from the paper "Guaranteed Yet Hard to Find: Uncovering FPGA Routing Convergence Paradox" by Shashwat Shrivastava (EPFL), Stefan Nikolić (University of Novi Sad), Sun Tanaka (University of Tokyo), Chirag Ravishankar (AMD), Dinesh Gaitonde (AMD), and Mirjana Stojilović (EPFL). The paper has been accepted for publication in the Proceedings of the 33rd IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM 2025). The README file details the repository's structure, contents, and instructions for using the provided software and data. Abstract: Routing is one of the major challenges of FPGA compilation. PathFinder is a ubiquitous FPGA routing algorithm used in industry and academia thanks to its ability to adapt to arbitrary routing architectures and user circuits. However, to this day, we do not completely 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 in the architecture to improve routability, ignoring the exploration of inherent inefficiencies that may exist in PathFinder and further preventing 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 existing routing solution or any other solution for that matter, highlighting issues in PathFinder solely. The reduced search space makes the underlying behavior more accessible for analysis and reasoning, allowing us to uncover the inefficiency in the current paradigm of PathFinder and propose a solution to fix it. We then transfer the learnings from the constrained to the standard setting, where the search space is not reduced, to show the potential benefits that could be achieved.

Keywords

Computer-aided design, FPGA, Routing, PathFinder

  • BIP!
    Impact byBIP!
    citations
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
citations
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average