Automatic Layout Algorithms for Function Blocks of CMOS Gate Arrays

Automatic layout algorithms, placement and routing, for function blocks of CMOS gate arrays are presented. The placement algorithm assigns transistors to basic cells so as to minimize the number of cells used and to minimize the number of interconnections crossing cut-lines. The former objective is achieved by finding a maximum matching and the latter is achieved by iterative interchanges of transistor pairs. A new routing technique based on channel routing methods is introduced to handle the internal cell area. It intends to route with the primary use of the first layer and with the least use of tracks. A program based on the algorithms has been developed and applied to many block designs for up to 200 transistors. The results show that the presented algorithms could realize as good a layout as manual.