Minimum padding to satisfy short path constraints

Combinational circuits are often embedded in synchronous designs with memory elements at the input and output ports. A performance metric for a circuit is the cycle time of the clock signal. Correct circuit operation requires that all paths have a delay that lies between an upper bound and a lower bound. Traditional approaches in delay optimization for combinational circuits have dealt with methods to decrease the delay of the longest path. We address the issue of satisfying the lower bound constraints. Such a problem also arises in wave pipelining of circuits. We propose to handle short path constraints as a post processing step after traditional delay optimization techniques. There are two issues presented in this paper. We first discuss necessary and sufficient conditions for successful delay insertion without increasing delays of any long paths. In the second part, we present a naive approach to padding delays (greedy heuristic) and an algorithm based on linear programming. We describe an application of the theory to wave pipelining of circuits. Results are presented on a set of benchmark circuits, using two delay models.