有關層VLSI佈局層指定的混合式演算法

作者:張國恩(國立臺灣師範大學資訊教育研究所)

摘要：

佈局層指定（又稱可限性穿孔減少）是決定佈局中各線段的佈局層位置使得佈局所產生的穿孔數能盡量少。由於穿孔數的增加會降低電路之執行效益和增加電路製造成本，因此減少佈局中的穿孔是重要的。本文提出一個有效的演算法以減少三層佈局中的穿孔數。文中採用一種混合式的方式，並考慮實際設計上的限制問題，如端點限制與鄰接限制。這些問題皆有助於VLSI電路之製造。經過實驗證明，本混合式演算法是快速而有效的，並得到很好的結果。

《詳全文》

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.