EXPIDER: an object-based expert system for VLSI channel routing

Author

Shen, Ding-Lan ; Wu, Chih-Hung ; Lee, Shie-Jue

Author_Institution

Dept. of Electr. Eng., Nat. Sun Yat-Sen Univ., Kaohsiung, Taiwan

Volume

1

fYear

1996

fDate

14-17 Oct 1996

Firstpage

226

Abstract

Channel routing is the most important problem in VLSI routing. Because it is NP-hard, the algorithmic approach cannot have a good solution. We propose an object-based expert system to solve this problem. By using the object-based approach, objects are allowed to apply rules iteratively and the number of rules is reduced. With routing tuning techniques, our system can adjust the routing direction of a blocked net or relax a net blocking others, 20 increase the applicability of the system. The concept of minimal rectilinear Steiner tree (MRST) is used to assist the progress of routing. The program has been implemented in CLIPS. Some test cases have been run successfully, and the results are presented and compared with other routing systems

Keywords

VLSI; circuit layout CAD; circuit optimisation; expert systems; integrated circuit layout; network routing; object-oriented methods; tree searching; CLIPS; EXPIDER; NP-hard; VLSI channel routing; blocked net; minimal rectilinear Steiner tree; object-based expert system; routing direction; Circuits; Ear; Expert systems; Iterative algorithms; Pins; Routing; System testing; Very large scale integration; Waste materials; Wires;

fLanguage

English

Publisher

ieee

Conference_Titel

Systems, Man, and Cybernetics, 1996., IEEE International Conference on

Conference_Location

Beijing

ISSN

1062-922X

Print_ISBN

0-7803-3280-6

Type

conf

DOI

10.1109/ICSMC.1996.569771

Filename

569771