Redundant-Wires-Aware ECO Timing and Mask Cost Optimization

Due to the increasing IC design complexity, engineering change order (ECO) has become a necessary technique to resolve late-found functional and/or timing deficiencies. To fix timing violations using spare cells in post-mask ECO, the reduction of the mask respin cost has become very critical. The mask respin cost is proportional to the number of changed masks of vias and metal layers for rewiring. In this thesis, we introduce a new problem of ECO timing optimization considering redundant wires reuse toeduce the number of layers used for rewiring and present the first work for this problem. First, we present a multi-commodity flow model of the spare-cell selection with used routing resources minimization by considering redundant wires and apply integer linear programming (ILP) to solve the selection problem with ILP reduction without loss of the solution optimality. Then, we present a tile-based gridless router considering redundant wires reuse to complete the routing. Our algorithm iteratively performspare-cell selection and routing considering redundant wires on each layer to find the minimum number of changed metal layer masks and via masks. Experimental results based on five industry benchmarks show that our algorithm not only effectively resolves timing violations but also reduces the mask respin cost under reasonable run times.