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.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2007
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00072480
Contributeur : Jean Mairesse <>
Soumis le : mardi 24 juillet 2007 - 18:40:48
Dernière modification le : jeudi 11 janvier 2018 - 06:21:39
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:41:29

Fichiers

circuit.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

292

Téléchargements de fichiers

172