Resource-constrained link insertion for delay reduction

Abstract: Under the design experience of a single open on any wiring segment in a signal net, it is known that the non-tree topology for a signal net does not need any adjacent loop. In this paper, based on two time-equivalent splitting operations in a cyclic connection, an accurate transformation-based analysis approach is firstly proposed to compute the timing delays of all the sinks in a non-tree topology without any adjacent loop. Furthermore, given a resource constraint, a 0–1 integer linear programming (ILP) formulation for resource-constrained link insertion is proposed to insert timing-driven geometrical links to reduce the delay of the critical path in a given rectilinear Steiner tree according to the definition of timing-driven redundant links and the design experience of a single open on any wiring segment. For tested Steiner trees, the experimental results show that the 0–1 ILP formulation based on our proposed transformation-based timing analysis has 21.0% and 23.5% of the delay reduction of the critical path under the resource constraints for 10% and 20% of the total wirelength of the original tree in reasonable CPU time on the average, respectively. [Copyright &y& Elsevier]