The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
PathFinder: a negotiation-based performance-driven router for FPGAs
Abstract
Routing FPGAs is a challenging problem because of the relative scarcity of routing resources, both wires and connection points. This can lead either to slow implementations caused by long wiring paths that avoid congestion or a failure to route all signals. This paper presents PathFinder, a router that balances the goals of performance and routability. PathFinder uses an iterative algorithm that converges to a solution in which all signals are routed while achieving close to the optimal performance allowed by the placement. Routability is achieved by forcing signals to negotiate for a resource and thereby determine which signal needs the resource most. Delay is minimized by allowing the more critical signals a greater say in this negotiation. Because PathFinder requires only a directed graph to describe the architecture of routing resources, it adapts readily to a wide variety of FPGA architectures such as Triptych, Xilinx 3000 and mesh-connected arrays of FPGAs. The results of routing ISCAS benchmarks on the Triptych FPGA architecture show an average increase of only 4.5% in critical path delay over the optimum delay for a placement. Routes of ISCAS benchmarks on the Xilinx 3000 architecture show a greater completion rate than commercial tools, as well as 11% faster implementations.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 29,065
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738
An Algorithm for Path Connections and Its Applications
Lee, C. Y. (1961) · IEEE Transactions on Electronic Computers · doi:10.1109/tec.1961.5219222 · Cited by 1,619
The shortest path through a maze
Moore, E. (1959) · Medical Entomology and Zoology · Cited by 1,236
An approximate solution for the Steiner problem in graphs
Takahashi, H., & Matsuyama, A. (1980) · Mathematica japonica · Cited by 878
Placement and routing tools for the Triptych FPGA
Ebeling, C. W., McMurchie, L., Hauck, S., et al. (1995) · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · doi:10.1109/92.475966 · Cited by 170
Self-citation(1979) · Journal of Mechanical Design · doi:10.1115/1.3454096 · Cited by 112
Iterative and adaptive slack allocation for performance-driven layout and FPGA routing
Frankle, J. (1992) · doi:10.5555/113938.149626 · Cited by 94
Plane parallel a maze router and its application to FPGAs
Palczewski, M. (1992) · doi:10.5555/113938.149679 · Cited by 36
Cited by
Reconfigurable computing: a survey of systems and software
Compton, K., & Hauck, S. (2002) · ACM Computing Surveys · doi:10.1145/508352.508353 · Cited by 1,240
VTR 8: High-performance CAD and Customizable FPGA Architecture Modelling
Murray, K. E., Petelin, O., Zhong, S., Wang, J. M., Eldafrawy, M., Legault, J.-P., Sha, E., Graham, A. G., Wu, J., Walker, M. J. P., et al. (2020) · ACM Transactions on Reconfigurable Technology and Systems · doi:10.1145/3388617 · Cited by 300
The VTR project: architecture and CAD for FPGAs from verilog to routing
Rose, J., Luu, J., Yu, C. W., Densmore, O., Goeders, J., Somerville, A., Kent, K. B., Jamieson, P., & Anderson, J. (2012) · Proceedings of the ACM/SIGDA international symposium on Field Programmable Gate Arrays · doi:10.1145/2145694.2145708 · Cited by 265
Nanowire-based programmable architectures
Dehon, A. (2005) · ACM Journal on Emerging Technologies in Computing Systems · doi:10.1145/1084748.1084750 · Cited by 257
Trimberger, S. M. S. (2018) · IEEE Solid-State Circuits Magazine · doi:10.1109/mssc.2018.2822862 · Cited by 77
Metadata
- Authors
- McMurchie, L., & Ebeling, C.
- Venue
- Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays
- Publisher
- ACM
- Published
- 1995-02-15
- Pages
- 111-117
- OpenAlex
- W2275304190
- Cited by
- 683
- References
- 9
- FWCI
- 14.33
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.