Minimization of circuit registers: retiming revisited

Abstract : In this paper, we address the following problem: given a synchronous digital circuit, is it possible to construct a new circuit computing the same function as the original one but using a minimal number of registers? The construction of such a circuit can be done in polynomial time and is based on a result of Orlin for one periodic bi-infinite graphs showing that the cardinality maximum flow is equal to the size of a minimum cut. The idea is to view such a graph as the unfolding of the dependences in a digital circuit.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072480
Contributor : Jean Mairesse <>
Submitted on : Tuesday, July 24, 2007 - 6:40:48 PM
Last modification on : Friday, January 4, 2019 - 5:32:57 PM
Document(s) archivé(s) le : Tuesday, September 21, 2010 - 1:41:29 PM

Files

circuit.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00072480, version 2

Collections

Citation

Bruno Gaujal, Jean Mairesse. Minimization of circuit registers: retiming revisited. Discrete Applied Mathematics, Elsevier, 2007. ⟨inria-00072480v2⟩

Share

Metrics

Record views

383

Files downloads

304