Title :
Via minimization with associated constraints in three-layer routing problem
Author :
Fang, Sung-Chuan ; Chang, Kuo-En ; Feng, Wu-Shiung
Author_Institution :
Dept. of Electr. Eng., Nat. Taiwan Univ., Taipei, Taiwan
Abstract :
Via minimization is the same as the layer assignment problem in VLSI or PCB routing. It consists of determining which layers can be used for routing the wire segments such that the number of vias can be minimized. A heuristic algorithm is presented to globally eliminate the vias in the three-layer channel routing. Some associated constraints, such as restricted terminals and adjacent limitation, are addressed extensively. According to the results, the algorithm is fast and efficient, thus generating very good results
Keywords :
VLSI; circuit layout CAD; graph theory; integrated circuit technology; minimisation; network topology; printed circuit design; CAD; PCB; VLSI; adjacent limitation; channel routeing; circuit layout; heuristic algorithm; layer assignment problem; restricted terminals; three-layer channel routing; via minimisation; Computer science education; Heuristic algorithms; Large scale integration; NP-complete problem; Polynomials; Routing; Topology; Very large scale integration; Wire;
Conference_Titel :
Circuits and Systems, 1990., IEEE International Symposium on
Conference_Location :
New Orleans, LA
DOI :
10.1109/ISCAS.1990.112450
