Abstract:

The constrained via minimization (CVM) is a problem of determining which layers can be used for routing wire segments in interconnections of nets such that the number of vias is minimized. Based on a segment-crossing graph, a constrained via minimization algorithm for multi-layer routing is proposed. The algorithm uses tournament selection, selects individuals according to their penalty until feasible solutions are found, and searches for the best solution among feasible solutions. In addition, steady state reproduction and elitist model further improve efficiency of the algorithm. Experimental results show that the proposed algorithm is efficient and provides satisfactory solutions.

Key words: constrained via minimization, multi-layer routing, genetic algorithm