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

Gi Joon Nam, Karem Sakallah, Rob Rutenbar

Research output: Contribution to journalConference article

Abstract

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
DOIs
StatePublished - Dec 1 2001
EventDesign, Automation and Test in Europe Conference and Exhibition 2001, DATE 2001 - Munich, Germany
Duration: Mar 13 2001Mar 16 2001

Fingerprint

Field programmable gate arrays (FPGA)
Repair
Program processors
Specifications

ASJC Scopus subject areas

  • Engineering(all)

Cite this

A Boolean satisfiability-based incremental rerouting approach with application to FPGAs. / Nam, Gi Joon; Sakallah, Karem; Rutenbar, Rob.

In: Proceedings -Design, Automation and Test in Europe, DATE, 01.12.2001, p. 560-564.

Research output: Contribution to journalConference article

@article{84dd7603ff074fb1912ce75ba075df49,
title = "A Boolean satisfiability-based incremental rerouting approach with application to FPGAs",
abstract = "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.",
author = "Nam, {Gi Joon} and Karem Sakallah and Rob Rutenbar",
year = "2001",
month = "12",
day = "1",
doi = "10.1109/DATE.2001.915079",
language = "English (US)",
pages = "560--564",
journal = "Proceedings -Design, Automation and Test in Europe, DATE",
issn = "1530-1591",

}

TY - JOUR

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

AU - Nam, Gi Joon

AU - Sakallah, Karem

AU - Rutenbar, Rob

PY - 2001/12/1

Y1 - 2001/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84893678051&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893678051&partnerID=8YFLogxK

U2 - 10.1109/DATE.2001.915079

DO - 10.1109/DATE.2001.915079

M3 - Conference article

AN - SCOPUS:84893678051

SP - 560

EP - 564

JO - Proceedings -Design, Automation and Test in Europe, DATE

JF - Proceedings -Design, Automation and Test in Europe, DATE

SN - 1530-1591

M1 - 915079

ER -