Resource-Constrained Timing-Driven Link Insertion for Critical Delay Reduction

摘要

For timing-driven or yield-driven designs, non-tree routing has become more and more popular and additional loops provide the redundant paths to protect against the effect of the open defects. Based on the assumption of a single wiring open in a signal net, it is known that the non-tree interconnection of a signal net has no adjacent loop. In this paper, based on the concept of splitting a time-equivalent node or edge in a cyclic connection for timing analysis, a 0-1 integer linear programming(ILP) formulation for resource-constrained timing-driven link insertion is proposed to insert timing-driven links to maximize the reduced delay of the critical path in a rectilinear Steiner tree under a given resource constraint. The experimental results show that our proposed algorithm has the 21.0% and 23.5% reduction of the critical delay on the average for the tested trees in reasonable CPU time under the 10% and 20% resource constraint of the total wirelength, respectively.