Hybrid routing for FPGAs by integrating boolean satisfiability with geometric search

Gi Joon Nam, Karem Sakallah, Rob Rutenbar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Boolean Satisfiability (SAT)-based routing has unique advantages over conventional one-net-at-a-time approaches such as simultaneous net embedding or routability decision. Yet SAT-based routing has been criticized for scalability issues. On the other hand, geometric search routing algorithms, even with extensive rip-up-reroute capabilities, have difficulty achieving routing solution convergence when a problem has tight routing constraints. In this paper, we revisit the SAT-based routing idea for FPGA routing, and propose a new hybrid algorithm that integrates SAT-based FPGA routing with a conventional geometric search FPGA router. The advantages of such a combination are twofold: 1) the scalability handicap of SAT-based routing is overcome due to the path pruning techniques of the geometric search algorithm, and 2) more concrete routability decisions can be made thus achieving the convergence, because the SAT-based technique considers simultaneously any paths in the history of iterative routings. The proposed algorithm named search-SAT is implemented and applied to real-world industry circuits. Preliminary experimental results show "search-SAT" is a more viable routing technique than any earlier SAT-based routing approach.

Original languageEnglish (US)
Title of host publicationField-Programmable Logic and Applications
Subtitle of host publicationReconfigurable Computing is Going Mainstream - 12th International Conference, FPL 2002, Proceedings
Pages360-369
Number of pages10
StatePublished - Dec 1 2002
Event12th International Conference on Field-Programmable Logic and Applications, FPL 2002 - Montpellier, France
Duration: Sep 2 2002Sep 4 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2438 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Conference on Field-Programmable Logic and Applications, FPL 2002
CountryFrance
CityMontpellier
Period9/2/029/4/02

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Hybrid routing for FPGAs by integrating boolean satisfiability with geometric search'. Together they form a unique fingerprint.

Cite this