Mixed Planar and H-V Over-the-Cell Routing for Standard Cells with Nonuniform Over-the-Cell Routing Capacities

Tetsushi KOIDE  Shin'ichi WAKABAYASHI  Noriyoshi YOSHIDA  

IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.10   pp.1419-1430
Publication Date: 1996/10/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Synthesis and Verification of Hardware Design)
Category: Lauout Synthesis
over-the-cell routing,  non-uniform over-the-cell routing capacity,  planar routing,  H-V routing,  dynamic programming,  

Full Text: PDF>>
Buy this Article

This paper presents a three layer over-the-cell (OTC) routing algorithm for standard cells with nonuniform OTC routing capacities in standard cell design. Since the number of available routing tracks on the second metal layer of OTC varies column by column, the proposed OTC routing method can effectively utilize the OTC regions. The proposed router performs two types of OTC routing. For the OTC regions near the channel, it performs planar routing. For the OTC regions far from the channel, it performs H-V routing on the second and third layers. Combining planar and H-V routings, the router can utilize the OTC effectively, that could hardly be achieved by existing algorithms. We also formulate the problem of selecting planar routable nets on the third layer as the maximum weighted planar routable net selection problem with nonuniform routing capacity, and propose an optimal algorithm. Experimental results show that the proposed router produces small height layouts as compared to those produced by the routers based on the existing cell model with uniform OTC routing capacity.