Skip to Main content Skip to Navigation
Journal articles

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
Complete list of metadatas

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 : Thursday, November 19, 2020 - 1:00:25 PM
Long-term archiving on: : 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

470

Files downloads

681