EXPIDER: A channel routing expert for VLSI design

摘要

Channel routing plays an important role in VLSI (Very Large Scale Integration) design. Because of the ill-structured nature of the problem, algorithmic approaches fail to provide satisfactory solutions. Techniques using expert knowledge have been solicited and developed successfully. In this paper, we present an expert system, EXPIDER, for channel routing. Wires are placed on the tracks from the boundaries toward the middle of a channel on a track-by-track basis, with the help of weighted vertical constraint graphs. Heuristics are applied to escape from blocked states and to do directed routing without search. Tuning knowledge is provided to reduce the wire length and the number of vias. The routing area can be determined automatically without human intervention. The system was implemented in CLIPS (C Language Integrated Production System) and has been tested successfully on many cases. Some results, together with a comparison with other methods, are shown at the end of the paper.