Retiming DAGs

(eng) The increasing complexity of digital circuitry makes global design optimization no longer possible: a designer will only consider the critical parts of his circuit. This paper discusses timing optimization problems when these critical parts can be represented by Direct Acyclic Graphs (DAGs). We deal with different (though related) clock period problems, under various external constraints. The main algorithm concerns the determination of the optimal clock period of a given circuit. We propose an efficient solution, based on the retiming technique, which improves current results in the literature. We give three different formulations depending on which combinational gates delay model is used: same delay for every gate, different delays or non-uniform delays.(fre) La complexité grandissante des circuits numériques rend désormais impossible toute optimisation globale d'un circuit: les concepteurs ne considèrent plus que les parties critiques de leur circuit. Cet article traite des problèmes d'optimisation temporelle lorsque ces parties critiques peuvent être représentées par des graphes acycliques orientés. Nous considérons différents problèmes concernant les contraintes sur la période d'horloge, qui interviennent lors de la conception d'un circuit, et qui découlent de la détermination de la période optimale du circuit. Nous proposons un algorithme de faible complexité, basé sur la technique de resynchronisation, pour résoudre ce problème essentiel, et nous donnons trois formulations différentes, dépendant du modèle de délai utilisé pour les portes combinatoires : meme délai pour toutes les portes, délais différents ou délais non-uniformes