IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1985 · 89 citations · 5 references
EngineeringComputer EngineeringElectrical EngineeringAlgorithmsCircuit TheoryMicroelectronicsCmos Circuit DesignGraph AlgorithmsGraph Layout AlgorithmsIntegrated Circuit DesignLayout OptimizationVery-large-scale Integration LayoutCircuit Graph TheoryCircuit Matrix AnalysisGate Layout DesignGraph-theoretic Circuit FormulationLayout TechniquesMatrix Layout DesignMatrix Permutation OptimizationVertical Diffusion
A graph-theoretic description of the problem of layout of CMOS circuits in the style of gate matrix in minimum area is presented. The problem is formulated as one of finding two assignment functions f and h such that the layout L(f, h) requires the minimum number of rows of the gate matrix. The function f maps the distinct gates of the transistors to the columns of the gate matrix and the function h maps the nets of the circuit to the rows such that all of the vertical diffusion runs which connect nets on different rows are realizable. A two-stage approach to the problem is described which first obtains a layout without regard to the vertical constraints and then rows are permuted to satisfy the constraints. Detailed algorithms and examples are given. The gate matrix layout of a 118-transistor circuit was obtained in 9 s on a mainframe computer.
5
Incidence matrices and interval graphs
D. R. Fulkerson, Oliver Gross · Pacific Journal of Mathematics · 1965 · 1.3K citations · Full text
One-dimensional logic gate assignment and interval graphs
Tomi Ohtsuki, H. Mori, E.S. Kuh et al. · IEEE Transactions on Circuits and Systems · 1979 · 107 citations
Engineering, Computer Engineering, Electrical Engineering +15