A fast transistor-chaining algorithm for CMOS cell layout

Author

Hwang, Chi-Yi ; Hsieh, Yung-Ching ; Lin, Youn-Long ; Hsu, Yu-Chin

Author_Institution

Dept. of Comput. Sci., Tsing Hua Univ., Hsin-Chu, Taiwan

Volume

9

Issue

7

fYear

1990

fDate

7/1/1990 12:00:00 AM

Firstpage

781

Lastpage

786

Abstract

A fast algorithm is proposed for the transistor-chaining problem in CMOS functional cell layout based on the layout style of T. Uehara and W.M. van Cleemput (1981). The algorithm takes a transistor-level circuit schematic and outputs a minimum set of transistor chains. Possible diffusion abutments between the transistor pairs are modeled as a bipartite graph. A depth-first search algorithm is used to search for the optimal chaining. Theorems on the set of branches that needs to be explored at each node of the search tree are derived. A theoretical lower bound on the size of the chain set is also derived. This bound enables one to prune the search tree efficiently. The algorithm has been implemented and tested and is able to find optimal solutions almost instantly for all the cases from the literature that were examined

Keywords

CMOS integrated circuits; circuit layout; graph theory; network topology; CMOS cell layout; bipartite graph; depth-first search algorithm; diffusion abutments; optimal solutions; search tree; transistor-chaining algorithm; transistor-level circuit schematic; Bipartite graph; CMOS technology; Circuits; Proposals; Rails; Routing; Strips; Testing; Tree graphs; Very large scale integration;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.55207

Filename

55207