Critical Path Selection for Performance Optimization

In this paper we study the problem of selecting a set of paths to optimize the performance of a combinational circuit. We assume that gate resizing and buffer insertion are the two possible optimizing techniques used to reduce the delay of a circuit; that is, during the optimization process the topology of a circuit remains the same and the lead/gate delays are reduced. The objective of the path selection problem is to select as small as possible a set of paths to ease the optimization process. However, we also want to guarantee the delay of the circuit is no longer than a given threshold τ if the delays of all the selected paths are shortened to no longer than τ. In this paper we have shown that the path selection is different from path sensitization. We first proposed an input vector-oriented path selection algorithm. Due to the fact that the input vector-oriented algorithm may be infeasible for complex circuits with many primary inputs, we also designed and developed a path-oriented algorithm. We have implemented the path-oriented algorithm. The experimental results on ISCAS85 benchmark circuits show a potentially big improvement for optimization process. For some circuits, less than 10% of the long paths need to be shortened.