Title :
A graph-theoretical approach to transistor placement in CMOS cell layout
Author :
Lin, Youn-Long ; Hsu, Yu-Chin ; Hwang, Chi-Yi ; Hsieh, Yung-Ching
Author_Institution :
Dept. of Comput. Sci., Tsing Hua Univ., Taiwan
Abstract :
A graph-theoretical approach for solving the layout problem of a CMOS functional cell is presented. After the transistor pairing, the chaining problem is modeled as an abutability graph. The chaining problem is solved by finding a maximum independent set of vertices in the graph. A method based on Boolean arithmetic is applied to find all the maximal independent sets which correspond to all the optimal chainings. An exhaustive or an improved min-cut algorithm is applied to place the chains. Good layouts have been obtained on benchmark data
Keywords :
CMOS integrated circuits; circuit layout CAD; graph theory; integrated circuit technology; Boolean arithmetic; CMOS cell layout; abutability graph; chaining problem; graph-theoretical approach; maximal independent sets; min-cut algorithm; transistor pairing; transistor placement; Arithmetic; CMOS technology; Circuits; Computer science; Labeling; Proposals; Rails; Routing; Semiconductor device modeling; Strips;
Conference_Titel :
Circuits and Systems, 1989., Proceedings of the 32nd Midwest Symposium on
Conference_Location :
Champaign, IL
DOI :
10.1109/MWSCAS.1989.101913
