Skip to Main content Skip to Navigation
Journal articles

Minimization of circuit registers: retiming revisited

Bruno Gaujal 1 Jean Mairesse 2
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble [2007-2015]
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
Contributor : Jean Mairesse <>
Submitted on : Tuesday, July 24, 2007 - 6:40:48 PM
Last modification on : Thursday, July 9, 2020 - 9:44:35 AM
Document(s) archivé(s) le : Tuesday, September 21, 2010 - 1:41:29 PM


Files produced by the author(s)


  • HAL Id : inria-00072480, version 2



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



Record views


Files downloads