A Boolean satisfiability-based incremental rerouting approach with application to FPGAs

Gi Joon Nam, Karem Sakallah, Rob Rutenbar

Research output: Contribution to journalConference articlepeer-review


Incremental redesign is an increasingly essential step in any complex design. Late changes or corrections in functional specifications (so-called "engineering change orders" or ECOs) force us to search for a minimal perturbation that achieves the desired repair. In reconfigurable design scenarios, these incremental repairs may be in response to physical faults: the goal is to "design around" the fault. For FPGAs, incremental rerouting is an essential component of this repair problem. We have developed a new incremental rerouting algorithm for FPGAs using techniques from Boolean Satisfiability (SAT). In this application, these techniques have the twin virtues that they (1) represent all possible routing (and rerouting) constraints simultaneously and exactly, and (2) search for rerouting solutions by perturbing all nets concurrently. Preliminary results are promising. For several FPGA benchmarks, we were able to reroute fault reconfigurations that perturb up to 5.74% of all nets for a small number of fault sets (one to four faults) with only 1.55 track overhead per channel on average, with CPU time 0.76 to 4.91 seconds/fault.

Original languageEnglish (US)
Article number915079
Pages (from-to)560-564
Number of pages5
JournalProceedings -Design, Automation and Test in Europe, DATE
StatePublished - 2001
EventDesign, Automation and Test in Europe Conference and Exhibition 2001, DATE 2001 - Munich, Germany
Duration: Mar 13 2001Mar 16 2001

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'A Boolean satisfiability-based incremental rerouting approach with application to FPGAs'. Together they form a unique fingerprint.

Cite this