Search

We present a technology mapping procedure in which an area-delay trade-off curve is constructed at each node using matches found for different decompositions of the node. This information is used effectively to find implementations that meet delay constraints while reducing area. The procedure combines state-of-the-art mapping procedures, in which a graph covering is applied to a special graph structure which succinctly encodes many representations. Major challenges were avoiding memory explosion and finding good cost estimations. The combined procedure outperforms the best result among any of the procedures used separately.

Often, and certainly in the early stages of a design, the knowledge about delays is imprecise. Stochastic programming is not an adequate means to account for this imprecision. Not only is a probability distribution seldom a correct translation of the designer's delay knowledge, it also leads to inefficient algorithms. In this paper possibilistic programming is proposed for handling the retiming problem where delays are modelled as (triangular) possibilistic numbers. Beside the capability of optimizing the most possible clock cycle time and generating its possibility distribution, it allows for trade-offs between reducing clock cycle time and chances for obtaining worse solutions. It is shown that the computational complexity is the same as for retiming with exact circuit delays.