In standard cell design, many cell terminals and gates are permutable, and it is important for a channel router to take advantage of this to obtain better results. An efficient hierarchical algorithm is presented to determine the proper positions of permutable gates and cell terminals such that the results of the subsequent channel routing can be significantly improved. Experimental results show that our proposed algorithm considerably reduces the number of tracks and vias, and its time complexity is linear in the number of cell terminals.>

In standard cell design, some of the cell terminals and gates are permutable. Therefore, it is important for an over-the-cell channel router to take advantage of this so as to obtain better results. A greedy algorithm is presented to determine proper gate and terminal positions such that, when over-the-cell routers are used, the area above and below the channel can be utilized more effectively and the maximal channel density can be greatly reduced. Experimental results show that our proposed algorithm indeed considerably reduces the maximal channel density.>

It has been pointed out that, in many cases, results generated by non-Manhattan channel routers will be better than those generated by Manhattan routers. Non-optimal bubble sort based algorithms for non-Manhattan channel routing have been proposed in the literature by also allowing connections in the +45/spl deg/ and /spl minus/45/spl deg/ directions. In this paper, optimal algorithms are proposed for the two-layer and three-layer non-Manhattan channel routing problems based on an identical problem formulation. The time complexities of our algorithms and the existing algorithm (which produces the best results so far) are O(K/sup 2/ * N) and O(K * N/sup 2/), respectively, where N is the number of terminals (i.e., the length) of the channel and N is the number of routing tracks (i.e., the height) in the channel. K is always less than N, and in most cases is much smaller than N. Clearly, a significant improvement in time complexity over the existing algorithm (which produces the best results so far) is achieved, while ensuring optimality.>

A hierarchical pin permutation algorithm is presented which is used as a preprocessor of conventional channel routing algorithms. This algorithm determines the proper positions of permutable gates and cell terminals such that the results of the subsequent channel routing can be significantly improved. First, gates and terminals are interchanged to maximize the number of aligned terminal pairs and to reduce the channel density. Then, terminals that are not aligned are interchanged to remove cyclic constraints in the vertical constraint graph (VCG). Experimental results show that the proposed algorithm considerably reduces the number of tracks and vias.>

Efficient algorithms for CMOS gate matrix layouts which have fully utilized the duality between NMOS and PMOS are presented. Improper assumptions made by previous authors are pointed out. Problems which have prevented previous algorithms from reaching a real optimal result are discussed and solved. Significant improvements are achieved over previous algorithms.>

Efficient algorithms for the layout generation of CMOS complex gates are presented. Heuristics which use the concept of delayed binding are introduced. An optimized net list is decided during the layout generation phase, rather than before. Examples are given showing that this approach can achieve a considerable improvement over previous ones.>