ON THE CIRCUIT IMPLEMENTATION PROBLEM

In this paper, we consider the problem of selecting an implementation of each circuit module from a cell library so as to satisfy overall de lay and area (or delay and power) requirements. Two versions of the ci rcuit implementation problem, basic circuit implementation problem and the general circuit implementation problem are shown to be NP-hard. A pseudo-polynomial time algorithm for the basic circuit implementation problem on series-parallel circuits is developed, and heuristics for the basic circuit implementation problem on general circuits are formu lated and experimented with.