INTEGRATED CIRCUIT DETAILED ROUTING

Abstract

Detailed routing is an important, time consuming, and difficult problem in layout design phase of integrated circuits. It involves the interconnection of a large number of electrical signals on a chip, under a set of constraints related to the technology used. The problem becomes more complex when the interconnection needs to achieve a number of confliction desirable objectives such as minimizing area, wire length, and number of vias. In general, the problem is NP-hard. Tools capable of automating the routing process have been built to reduce the design turn-around-time and cost for the past twenty years. Studies into these tools have shown that they do not provide satisfactory results. Although some tools can provide good solutions, they are still too slow for interactive use. On the other hand, though others require relatively short execution time, they do not consider sufficiently the objectives for routing. In this thesis, we use the simple figure of merit approach for routing to achieve both good solutions and fast execution time. To illustrate how the approach works, four heuristic algorithms for different types of detailed routing problems are presented. They are: score function channel router (SFCR): horizontal-vertical-horizontal three-layer channel router (SFHVH); score function selection algorithm (SFS) for discretionary channel routing problem; and score function switchbox router (SFSR). Experiments with benchmark examples show that our algorithms are efficient and perform as well as, if not better than, other exiting tools.