A "Hybrid Sense" Algorithm for Layer Assignment in Three-Layer VLSI Routing

Author: Kuo-En Chang(Department of Information and Computer Education, National Taiwan Normal University )

Abstract：

The layer assignment, also called constrained via minimization, is to determine which layers can be used for routing the wire segments such that the number of vias can be minimized. Vias should be eliminated as many as possible in the layout design because vias will reduce the performance of the circuits and increase the manufacturing cost. In this paper, we present a heuristic algorithm to eliminate the vias in the three-layer routing instances using the hybrid sense method. Some asso-ciated constraints under practical considerations, such as restricted terminals and ad-jacent limitation, will be addressed and solved extensively. By our experiments, the algorithm is fast and efficient to generate very good solutions.
Index terms-Via minimization, layer assignment, channel routing, NP-complete.

《Full Text》