Uniform area timing-driven circuit implementation

摘要

We consider the problem of selecting the proper implementation of each circuit module from a cell library to minimize the propagation delay along every path from any primary input to any primary output. An earlier problem definition, known as the general circuit implementation problem, assumes that each implementation has different delays on the input-output paths in the circuit, and that different implementations may have different areas. We primarily focus on the version of the problem, where no restrictions for the overall area of the circuit exist and therefore we ignore the module areas. We show that this problem is NP-hard even for directed acyclic graphs with two implementations per module, and we present a polynomial time algorithm for trees. We have developed heuristics for combinational and sequential circuits.