Title :
An extended 1-D assignment problem: net assignment in gate matrix layout
Author :
Xu, Dong-Min ; Kuh, Ernest ; Chen, Yun-Kang
Author_Institution :
Dept. of Electr. Eng., Tsinghua Univ., Beijing, China
Abstract :
A formulation for the net assignment problem in gate matrix layout is presented. A problem called the extended one-dimensional assignment problem is defined. A heuristic algorithm for solving this extended one-dimensional assignment problem is proposed. Since the net assignment problem in gate matrix is the extended one-dimensional assignment problem exactly, this algorithm is applied to the net assignment. The time complexity of the algorithm is bounded by O(m×n2), where n is the number of nets and m is the sum of the number of vertical diffusion runs and the number of gates
Keywords :
CMOS integrated circuits; circuit layout CAD; heuristic programming; logic gates; 1D assignment; C language; CMOS circuits; DEC 3100; extended one-dimensional assignment problem; gate matrix layout; heuristic algorithm; net assignment; time complexity; vertical diffusion runs; Algorithm design and analysis; Circuit testing; Heuristic algorithms; Integrated circuit interconnections; Logic design; Logic gates;
Conference_Titel :
Circuits and Systems, 1990., IEEE International Symposium on
Conference_Location :
New Orleans, LA
DOI :
10.1109/ISCAS.1990.111937
