A general heuristic for detailed VLSI routing /
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | Thesis Book |
| Language: | English |
| Published: |
1990.
|
| Subjects: | |
| Online Access: | Link to OAKTrust copy |
| Abstract: | The complexity of VLSI chips is increasing at a very fast pace. The early manual approach to designing VLSI chips is no longer practical, or economically feasible. Computer aids are necessary to deal with the complexity of today's chips. The present dissertation proposes a tool to help reduce the complexity of one phase of VLSI design: VLSI routing. A multilayer router to do the detailed phase of VLSI routing is presented. The router can route both switchboxes and channels. It uses two layers for switchboxes, and any number of layers for channels. Each layer can be used in both the horizontal and vertical directions. The heuristic has a partitioning, and a group routing section. The partitioning section divides the available routing layers into two and/or three layer groups, divides the nets of the problem among the groups, then assigns the nets with a group to one of the layers in the group. The group routing section does the interconnection of the individual groups. The features of this section include the use of domain dependent information in the form of rules and heuristic functions to guide the selection of the routing tracks, the use of both directions of each layer, and the calculation of the length of the longest path in cyclic vertical constraint graphs. Experimental results using benchmarks from the literature confirm the generality (wider scope of use) of the heuristic as well as the good quality of the solutions it generates. The heuristic was able to complete the routing of the most difficult problems in three categories: switchboxes, channels, and multilayer problems. The completion rate, the total interconnection length, the number of vias, and the cpu time quality measures show that the solutions obtained by the heuristic compare well with those obtained by some of the best routers reported in the literature for switchbox and multilayer channel problems. For two layer channel problems the heuristic gives solutions with slightly longer total interconnection lengths and wider widths. The overall quality of the two layer channel solutions are still good compared with those of many routers, however. Finally, an inherently parallel heuristic for a special case of the detailed routing problem called River Routing is presented in the appendix. The results obtained from running the heuristic on test problems from the literature are encouraging. |
|---|---|
| Item Description: | Typescript (photocopy). Vita. "Major subject: Electrical engineering." |
| Physical Description: | xiv, 153 leaves : illustrations ; 29 cm |
| Bibliography: | Includes bibliographical references. |