Placement and Routing Algorithms for One-Dimensional CMOS Layout Synthesis with Physical Constraints

Katsunori TANI

Placement and Routing Algorithms for One-Dimensional CMOS Layout Synthesis with Physical Constraints

Katsunori TANI

Full Text Views

0

Cite this

Summary :

This paper deals with the sub-problems of generating a mask pattern from the logical description of a large-scale CMOS circuit. The large-scale layout can be generated in divide-and-conquer style: divide a given circuit into a set of sub-circuits, generate the layout of each sub-circuit, and merge the resulting layouts to create the whole layout. This paper proposes a layout synthesis algorithm for a sub-circuit with physical constraints for the synthesis scheme above. The physical constraints considered here are the relative placement of logic cells (sets of logic gates) and the routing constraint based on the costs of wiring layers and vias. These constraints will be given by the global optimizer in a two-dimensional layout synthesis routine, and they should be kept at the subsequent one-dimensional layout synthesis for a sub-circuit. The latter is also given for enhancing the circuit performance by limiting the usage of wiring layers and vias for special net such as a clock net. The placement constraint is maintained using PQ-tree, a tree structure representing a set of restricted permutations of elements. One-dimensional layout synthesis determines the placement of transistors by the enhanced pairwise exchanging method under the PQ-tree representation. The routing constraints is considered in the newly developed line-search routing method using a cost-based searching. Experimental results for practical standard cells, including up to 200 transistors, prove that the algorithms can produce the layouts comparable to handcrafted cells. Also on a two-dimensional layout synthesis using the algorithms, the results for benchmark circuits of Physical Design Workshop 1989, i.e., MCNC benchmark circuits, are superior to the best results exhibited at Design Automation Conference 1990.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E75-A No.10 pp.1286-1293

Publication Date: 1992/10/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)

Category

Cite this

Copy

Katsunori TANI, "Placement and Routing Algorithms for One-Dimensional CMOS Layout Synthesis with Physical Constraints" in IEICE TRANSACTIONS on Fundamentals, vol. E75-A, no. 10, pp. 1286-1293, October 1992, doi: .
Abstract: This paper deals with the sub-problems of generating a mask pattern from the logical description of a large-scale CMOS circuit. The large-scale layout can be generated in divide-and-conquer style: divide a given circuit into a set of sub-circuits, generate the layout of each sub-circuit, and merge the resulting layouts to create the whole layout. This paper proposes a layout synthesis algorithm for a sub-circuit with physical constraints for the synthesis scheme above. The physical constraints considered here are the relative placement of logic cells (sets of logic gates) and the routing constraint based on the costs of wiring layers and vias. These constraints will be given by the global optimizer in a two-dimensional layout synthesis routine, and they should be kept at the subsequent one-dimensional layout synthesis for a sub-circuit. The latter is also given for enhancing the circuit performance by limiting the usage of wiring layers and vias for special net such as a clock net. The placement constraint is maintained using PQ-tree, a tree structure representing a set of restricted permutations of elements. One-dimensional layout synthesis determines the placement of transistors by the enhanced pairwise exchanging method under the PQ-tree representation. The routing constraints is considered in the newly developed line-search routing method using a cost-based searching. Experimental results for practical standard cells, including up to 200 transistors, prove that the algorithms can produce the layouts comparable to handcrafted cells. Also on a two-dimensional layout synthesis using the algorithms, the results for benchmark circuits of Physical Design Workshop 1989, i.e., MCNC benchmark circuits, are superior to the best results exhibited at Design Automation Conference 1990.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e75-a_10_1286/_p

Copy

@ARTICLE{e75-a_10_1286,
author={Katsunori TANI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Placement and Routing Algorithms for One-Dimensional CMOS Layout Synthesis with Physical Constraints},
year={1992},
volume={E75-A},
number={10},
pages={1286-1293},
abstract={This paper deals with the sub-problems of generating a mask pattern from the logical description of a large-scale CMOS circuit. The large-scale layout can be generated in divide-and-conquer style: divide a given circuit into a set of sub-circuits, generate the layout of each sub-circuit, and merge the resulting layouts to create the whole layout. This paper proposes a layout synthesis algorithm for a sub-circuit with physical constraints for the synthesis scheme above. The physical constraints considered here are the relative placement of logic cells (sets of logic gates) and the routing constraint based on the costs of wiring layers and vias. These constraints will be given by the global optimizer in a two-dimensional layout synthesis routine, and they should be kept at the subsequent one-dimensional layout synthesis for a sub-circuit. The latter is also given for enhancing the circuit performance by limiting the usage of wiring layers and vias for special net such as a clock net. The placement constraint is maintained using PQ-tree, a tree structure representing a set of restricted permutations of elements. One-dimensional layout synthesis determines the placement of transistors by the enhanced pairwise exchanging method under the PQ-tree representation. The routing constraints is considered in the newly developed line-search routing method using a cost-based searching. Experimental results for practical standard cells, including up to 200 transistors, prove that the algorithms can produce the layouts comparable to handcrafted cells. Also on a two-dimensional layout synthesis using the algorithms, the results for benchmark circuits of Physical Design Workshop 1989, i.e., MCNC benchmark circuits, are superior to the best results exhibited at Design Automation Conference 1990.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - Placement and Routing Algorithms for One-Dimensional CMOS Layout Synthesis with Physical Constraints
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1286
EP - 1293
AU - Katsunori TANI
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E75-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 1992
AB - This paper deals with the sub-problems of generating a mask pattern from the logical description of a large-scale CMOS circuit. The large-scale layout can be generated in divide-and-conquer style: divide a given circuit into a set of sub-circuits, generate the layout of each sub-circuit, and merge the resulting layouts to create the whole layout. This paper proposes a layout synthesis algorithm for a sub-circuit with physical constraints for the synthesis scheme above. The physical constraints considered here are the relative placement of logic cells (sets of logic gates) and the routing constraint based on the costs of wiring layers and vias. These constraints will be given by the global optimizer in a two-dimensional layout synthesis routine, and they should be kept at the subsequent one-dimensional layout synthesis for a sub-circuit. The latter is also given for enhancing the circuit performance by limiting the usage of wiring layers and vias for special net such as a clock net. The placement constraint is maintained using PQ-tree, a tree structure representing a set of restricted permutations of elements. One-dimensional layout synthesis determines the placement of transistors by the enhanced pairwise exchanging method under the PQ-tree representation. The routing constraints is considered in the newly developed line-search routing method using a cost-based searching. Experimental results for practical standard cells, including up to 200 transistors, prove that the algorithms can produce the layouts comparable to handcrafted cells. Also on a two-dimensional layout synthesis using the algorithms, the results for benchmark circuits of Physical Design Workshop 1989, i.e., MCNC benchmark circuits, are superior to the best results exhibited at Design Automation Conference 1990.
ER -