An optimal resource binding algorithm with inter-transition switching activities for low power

Deming Chen, Scott Cromar

Research output: Contribution to journalArticlepeer-review

Abstract

Resource binding, a key step encountered in behavioral synthesis, has been studied intensively in the past. Among the published results, resource binding to reduce switching activity (SA) of the design for minimizing dynamic power has been one of the actively-pursued topics. Two types of SAs can be minimized: the intra-transition SA (occurring during the propagation of a single input vector) and the inter-transition SA (occurring between different input vectors). Previous work either ignored the inter-transition SA or provided heuristic to deal with it. When the inter-transition SA was considered, it was not clear previously whether the problem could still be solved optimally. In this paper, for the first time, we demonstrate that resource binding considering inter-transition SAs can be solved in polynomial time for designs that can be represented by data-flow graphs (DFG). This is realized by transforming the problem into finding the shortest path problem in a k-dimensional graph. We also propose an efficient heuristic that uses a network-flow algorithm followed by a legalization step using a bipartite matching algorithm. Experimental results show that a considerable amount of SA reduction can be obtained compared to the previous state-of-the-art results.

Original languageEnglish (US)
Pages (from-to)454-463
Number of pages10
JournalJournal of Low Power Electronics
Volume5
Issue number4
DOIs
StatePublished - Dec 2009

Keywords

  • Behavioral synthesis
  • Low power design
  • Resource binding
  • Switching activity estimation

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'An optimal resource binding algorithm with inter-transition switching activities for low power'. Together they form a unique fingerprint.

Cite this