OVER-THE-CELL CHANNEL ROUTING

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. In this paper, we show that the first step can be reduced to the problem of finding a maximum independent set of a circle graph, and thus can be solved optimally in quadratic time. Also, we show that to determine an optimal choice of net segments in the second step is NP-hard in general, and we present an efficient heuristic algorithm for this step. The third step can be carried out using a conventional channel router. Based on these theoretical results, we design an over-the-cell channel router that produces solutions which are better than the optimal two-layer channel routing solutions for all test examples. Our over-the-cell channel router also outperforms the over-the-cell channel router in [19]. In particular, for the famous Deutsch’s difficult example, our solution yields a saving of 10.5 percent in channel routing area when compared with the optimal two-layer channel routing solution, and a saving of 15 percent in channel routing area when compared with the routing solution produced by the over-the-cell channel router in [19]. © 1990 IEEE