Improvements on efficiency and efficacy of SPFD-based rewiring for LUT-based circuits

Pongstorn Maidee, Kia Bazargan

Research output: Contribution to journalArticlepeer-review


This paper proposes two set-of-pairs-of-functions-to-be-distinguished (SPFD)-based rewiring algorithms to be used in a multi-tier rewiring framework, which employs multiple rewiring techniques. The first algorithm has two unique features: 1) a satisfiability problem (SAT) instance was devised so that an unsuccessful rewiring can be identified very quickly, and 2) unlike binary decision diagram-based methods that require all pairs of SPFD, our algorithm uses a few SAT instances to perform rewiring for a given wire without explicitly enumerating all SPFDs. Experimental results show that the runtime of our algorithm is about three times faster than that of a conventional one under a simulated setting of such a framework and it scales well with the number of candidate wires considered. The efficacy of the framework can be further improved by the second proposed algorithm. The algorithm relies on a theory presented herein to allow adding a new wire outside of the restricted set of dominator nodes, a feature common in automatic-test-pattern-generation-based rewiring, but absent in existing SPFD-based ones. Although this algorithm may suffer from long runtimes in the same way conventional SPFD-based techniques do, experiments show that the number of wires which can be rewired increases 13% on average and the number of alternative wires also increases.

Original languageEnglish (US)
Article number5621036
Pages (from-to)1870-1883
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number12
StatePublished - Dec 1 2010


  • Rewiring
  • SAT application
  • set-of-pairs-of-functions-to-be-distinguished (SPFD)

Fingerprint Dive into the research topics of 'Improvements on efficiency and efficacy of SPFD-based rewiring for LUT-based circuits'. Together they form a unique fingerprint.

Cite this