More Web Proxy on the site http://driver.im/

Article

Free access

FPGA routing and routability estimation via Boolean satisfiability

Authors:

Rob A. RutenbarAuthors Info & Claims

FPGA '97: Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays

Pages 119 - 125

https://doi.org/10.1145/258305.258322

Published: 09 February 1997 Publication History

Abstract

Guaranteeing or even estimating the routability of a portion of a placed FPGA remains difficult or impossible in most practical applications. In this paper we develop a novel formulation of both routing and routability estimation that relies on a rendering of the routing constraints as a single large Boolean equation. Any satisfying assignment to this equation specifies a complete detailed routing. By representing the equation as a Binary Decision Diagram (BDD), we represent all possible routes for allnets simultaneously. Routability estimation is transformed to Boolean satisfiability, which is trivial for BDDs. We use the technique in the context of a perfect routability estimator for a global router. Experimental results from a standard FPGA benchmark suite suggest the technique is feasible for realistic circuits, but refinements are needed for very large designs.

References

[1]

M.J. Alexander, J.P. Cohoon, J.L. GaMey, and G. Robins, "An Architecture-Independent Approach to FPGA Routing Based on Multi-Weighted Graphs," Prec. European Design Auto. Conf., pp. 259-264, Sept. 1994.

Digital Library

[2]

C.L. Berman, "Ordered Binary Decision Diagrams and Circuit Structure," Prec. IEEE ICCD, pp. 392-395, Oct. 1989.

[3]

J. Bern, C. Meinel, and A. Slobodova, "Efficient OBDD-Based Boolean Manipulation in CAD Beyond Current Limits," Proc ACM/ IEEEDAC, pp. 408-413, June 1995.

Digital Library

[4]

K.S. Brace, R.L. Rudell, and R.E. Bryant, "Efficient Implementation of a BDD package," Prec. ACM/IEEE DAC, pp. 40-45, June 1990.

Digital Library

[5]

S. Brown, J. Rose, and Z.G. Vranesie, "A Detailed Router for Field Programmable Gate Arrays," IEEE Trans. CAD, pp. 620-628, vol. 11, no. 5, May 1992.

[6]

S.D. Brown, R.J. Francis, J. Rose, and Z.G.Vranesie, Field Programmable Gate Arrays, Boston, Kluwer Acad. Publishers, 1992.

Digital Library

[7]

R.E. Bryant, "Graph-Based Algorithms for Boolean Function Manipulation," IEEE Trans. Computers, pp. 677-691, 1986.

Digital Library

[8]

R.E. Bryant, "Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams," ACM Computing Surveys, vol. 24, no. 3, pp. 293-318, Sept. 1992.

Digital Library

[9]

P.K. than et. al., "On Routability Prediction for Field Programmable gate Arrays," Prec. IEEE DAC, June 1993.

Digital Library

[10]

Y-W. Chang, S. Thahu', K. 23u, and D.F. Wong, "A New Global Routing Algorithm for FPGAs," Proa ACM/IEEE ICCAD, pp. 356--361,1994.

Digital Library

[11]

S. Devadas, "Optimal Layout Via Boolean Safisfiability," Prec. ACM/IEEE iCCAD, pp. 294-297, 1989.

[12]

J. Greene, V. Roychowdhury, S. Kaptanoglu, and A. El Gamal, "Segmented Channel Routing," Prec. ACM/1EEEDAC, pp. 567-572,1990.

Digital Library

[13]

K.M. Hall, "An R-Dimensional Quadratic Placement Algorithm,'' Management Set, vol. 17, pp. 219-229, Nov. 1970.

[14]

G. Lemieux and S. Brown, "A Detailed Router for Allocating Wire Segments in FPGAs," Prec. ACM Physical Design Workshop, California, Apr. 1993.

[15]

J.P. Marques Silva and ICA. Sakallab, "GRASP-A New Search Algorithm for Satisfiability;' Prec. ACM/IEEE ICCAD, Nov. 1997.

Digital Library

[16]

S-i. Minato, "Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems," Prec. ACM/IEEEDAC, pp. 272-277, June 1993.

Digital Library

[17]

L.E. McMurchie and C. Ebeling, "PathFinder:. A Negotiation- Based Path-Driven Router for FPGAs," Prec. A CM/IEEE International Syrup. Field Programmable Gate Arrays, Feb. 1995.

Digital Library

[18]

S.K. Nag and R.A. Rutenbar, "Performance-Driven Simultaneous Place and Route for Island-Style FPGAs," Prec. ACM/IEEE ICCAD, Nov. 1995.

Digital Library

[19]

S.K. Nag and R.A. Rutenbar, "Performance-Driven Simultaneous Place and Route for Row-Based FPGAs," Prec. A CM/IEEE DAC, June 1994.

Digital Library

[20]

R. RudeU, "Dynamic Variable Ordering for Ordered Binary Decision Diagrams," Prec. ACM/IEEE ICCAD, pp. 42-47, Nov. 1993.

Digital Library

[21]

R. Glenn Wood, Routing for FPGAs via Boolean Sati~ability, M.S. Thesis, Dept. of ECE, Carnegie Mellon University, May 1996.

[22]

Y-L, Wu and M. Marek-Sadowska, "Graph Based Analysis of FPGA Routing," Prec. European Design Auto. Conf., pp. 104-109, 1993.

[23]

Y-L. Wu and D. Chang, "On the NP-Completeness of Regular 2- D FPGA Routing Architectures and a Novel Solution," Prec. ACM/ IEEE ICCAD, pp. 362-367, 1994.

Digital Library

Cited By

Nie TWang YLiu PZhao KWang Z(2025)Predicting routability of FPGA design by learning complex network imagesExpert Systems with Applications10.1016/j.eswa.2024.125486261(125486)Online publication date: Feb-2025
https://doi.org/10.1016/j.eswa.2024.125486
Fiege NKumm MZipf P(2024)Bit-Level Optimized Constant Multiplication Using Boolean SatisfiabilityIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2023.332781471:1(249-261)Online publication date: Jan-2024
https://doi.org/10.1109/TCSI.2023.3327814
Gunter AWilton S(2023)A Machine Learning Approach for Predicting the Difficulty of FPGA Routing Problems2023 IEEE 31st Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)10.1109/FCCM57271.2023.00016(63-74)Online publication date: May-2023
https://doi.org/10.1109/FCCM57271.2023.00016
Show More Cited By

Index Terms

FPGA routing and routability estimation via Boolean satisfiability
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
  2. Very large scale integration design
    1. Application-specific VLSI designs
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

FPGA routing and routability estimation via Boolean satisfiability

Guaranteeing or even estimating the routability of a portion of a placed field programmable gate array (FPGA) remains difficult or impossible in most practical applications. In this paper, we develop a novel formulation of both routing and routability ...
Fast and accurate routing demand estimation for efficient routability-driven placement
DATE '07: Proceedings of the conference on Design, automation and test in Europe

This paper presents a fast and accurate routing demand estimation called RUDY and its efficient integration in a force-directed quadratic placer to optimize placements for routability.

RUDY is based on a Rectangular Uniform wire DensitY per net and ...
UTPlaceF: A routability-driven FPGA placer with physical and congestion aware packing
2016 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)
FPGA packing and placement without routability consideration could lead to unroutable results for high-utilization designs. Conventional FPGA packing and placement approaches are shown to have severe difficulties to yield good routability. In this paper, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FPGA '97: Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays

February 1997

174 pages

ISBN:0897918010

DOI:10.1145/258305

Chairman:
Carl Ebeling
Univ. of Washington

Copyright © 1997 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 February 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

FPGA97

Sponsor:

SIGDA

FPGA97: 1997 ACM/SIGDA International Symposium on Field Programmable Gate Arrays

February 9 - 11, 1997

California, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
512
Total Downloads

Downloads (Last 12 months)65
Downloads (Last 6 weeks)8

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nie TWang YLiu PZhao KWang Z(2025)Predicting routability of FPGA design by learning complex network imagesExpert Systems with Applications10.1016/j.eswa.2024.125486261(125486)Online publication date: Feb-2025
https://doi.org/10.1016/j.eswa.2024.125486
Fiege NKumm MZipf P(2024)Bit-Level Optimized Constant Multiplication Using Boolean SatisfiabilityIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2023.332781471:1(249-261)Online publication date: Jan-2024
https://doi.org/10.1109/TCSI.2023.3327814
Gunter AWilton S(2023)A Machine Learning Approach for Predicting the Difficulty of FPGA Routing Problems2023 IEEE 31st Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)10.1109/FCCM57271.2023.00016(63-74)Online publication date: May-2023
https://doi.org/10.1109/FCCM57271.2023.00016
Al-Hyari ASzentimrey HShamli AMartin TGréwal GAreibi S(2021)A Deep Learning Framework to Predict Routability for FPGA Circuit PlacementACM Transactions on Reconfigurable Technology and Systems10.1145/346537314:3(1-28)Online publication date: 12-Aug-2021
https://dl.acm.org/doi/10.1145/3465373
Guo PZhang Y(2021)ISSATA: An algorithm for solving the 3-satisfiability problem based on improved strategyApplied Intelligence10.1007/s10489-021-02493-1Online publication date: 27-May-2021
https://doi.org/10.1007/s10489-021-02493-1
Peng CXu ZMei M(2020)Applying aspiration in local search for satisfiabilityPLOS ONE10.1371/journal.pone.023170215:4(e0231702)Online publication date: 23-Apr-2020
https://doi.org/10.1371/journal.pone.0231702
Khasawneh MMadden PHomayoun HTaskin BMohsenin TZhao W(2019)HydraRouteProceedings of the 2019 Great Lakes Symposium on VLSI10.1145/3299874.3317997(177-182)Online publication date: 13-May-2019
https://dl.acm.org/doi/10.1145/3299874.3317997
Zha AKoshimura MFujita H(2019)N-level Modulo-Based CNF encodings of Pseudo-Boolean constraints for MaxSATConstraints10.1007/s10601-018-9299-024:2(133-161)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s10601-018-9299-0
Das JWilton S(2013)Towards development of an analytical model relating FPGA architecture parameters to routabilityACM Transactions on Reconfigurable Technology and Systems10.1145/2499625.24996276:2(1-24)Online publication date: 2-Aug-2013
https://dl.acm.org/doi/10.1145/2499625.2499627
Dutta ATuttle NAnandh K(2013)Canonical ordering of instances to immunize the FPGA place and route flow from ECO-induced varianceInternational Symposium on Quality Electronic Design (ISQED)10.1109/ISQED.2013.6523635(359-363)Online publication date: Mar-2013
https://doi.org/10.1109/ISQED.2013.6523635
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents