Title :
Over-the-cell channel routing
Author :
Cong, Jingsheng ; Liu, C.L.
Author_Institution :
Dept. of Comput. Sci., Illinois Univ., Urbana, IL, USA
fDate :
4/1/1990 12:00:00 AM
Abstract :
A common approach to the over-the-cell channel routing problem is to divide the problem into three steps: (1) routing over the cells; (2) choosing net segments; and (3) routing within the channel. It is shown that the first step can be reduced to the problem and finding a maximum independent set of a circle graph, and thus can be solved optimally in quadratic time. Also, it is shown that to determine an optimal choice of net segments in the second step is NP-hard in general, and an efficient heuristic algorithm for this step is presented. The third step can be carried out using a conventional channel router. On the basis of these theoretical results, an over-the-cell channel router that produces solutions which are better than the optimal two-layer channel routing solutions for all test examples is designed. The over-the-cell channel router also outperforms the over-the-cell channel router described by Y. Shiraishi and Y. Sakemi (ibid., vol.CAD-6, no.3, p.462-71, 1987). In particular, for Deutsch´s difficult example, the solution yields a saving of 10.5% in channel routing area when compared with the optimal two-layer channel routing solution, and a saving of 15% in channel routing area when compared with the routing solution produced by the over-the-cell channel router
Keywords :
circuit layout CAD; computational complexity; graph theory; network topology; CAD; NP-hard; channel routing area; circle graph; computational complexity; heuristic algorithm; maximum independent set; net segments; optimal choice; over-the-cell channel routing; quadratic time; Computer science; Heuristic algorithms; Integrated circuit interconnections; Routing; Testing; Very large scale integration;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on