Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-09-19
2003-09-30
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06629304
ABSTRACT:
FIELD OF THE INVENTION
This invention is directed to cell placement in integrated circuit (IC) chips, and particularly to removing cell overlaps and row overflows and to placement of dual height cells during design of IC chips.
BACKGROUND OF THE INVENTION
IC chips comprise plural cells each consisting of one or more circuit elements, such as transistors, capacitors and other basic circuit elements, grouped to perform a specific function. Each cell has one or more pins that are connected by wires to one or more pins of other cells of the chip. A net is the set of pins connected by the wire; a netlist is a list of nets of the chip. Each cell represents a single element, such as a gate; or several elements interconnected in a standardized manner to perform a specific function. Cells that consist of two or more interconnected gates or elements are also available as standard modules in circuit libraries. During chip layout, the cells may be treated as having a rectangular outline. Ordinal cells usually have the same height, although the width of the cells may be different.
All ordinal cells are arranged in rectangular regions along rows on the chip. The height of each row is equal to the common height of the ordinal cells; the length of a row is usually equal to the width of the chip. The rows define columns on the chip extending orthogonal to the rows; the column height is usually equal to the sum of the height of cells in the column.
A chip may contain several million transistors. Ordinarily, computer-aided design techniques cannot layout the entire circuit due to limitations on the memory space as well as the computation power available. Therefore, the layout is normally partitioned by grouping the components into blocks such as subcircuits and modules. The actual partitioning process considers many factors, such as the number and size of the blocks and number of interconnections between the blocks.
The output of partitioning is a set of blocks, along with the interconnections required between blocks. In large circuits, the partitioning process is often hierarchical and at the topmost level a circuit can have between 5 and 25 blocks. Each block is then partitioned recursively into smaller blocks. These blocks are called functions. Consequently, each function has a region of the chip where the cells of the function are placed. The regions of the different functions can be intersected.
Cells are -placed into the regions associated with the function. The different function regions can be intersected, and a characteristic vector (x
1
, . . . , x
n
) can be assigned to each point of the chip, where n is the number of the functions; xi is equal to 1 if this point belongs to the i-th function and xi is equal to 0 if the point does not belong to the i-th function. Each row of the chip can be partitioned into subrows such that different subrows contain points with different characteristic vectors, and all points of one subrow have the same characteristic vector (this vector is called the characteristic vector of the subrow).
In some cases, large cells (called dual height cells) may be appear as two or more ordinal cells (called half-cells) of neighboring rows, where the half-cells have common horizontal (x-direction) sides. Consequently, the heights of dual-height cells are usually some multiple of the height of ordinal cells.
Chips are designed using computer-aided design (CAD) techniques. Where a hierarchical placement is employed, timing resynthesis procedures are employed prior to final cell placement. In some cases, uniform density control procedures are applied during resynthesis to prevent the chip from having overflowed regions and cell congestion. However, these procedures do not prevent creation of cell overlaps in the chip.
A cell overflow condition occurs where the sum of the heights of cells assigned to a column exceeds the height of the column. Where there is no cell overflow in a given subrow, cell overlap can be removed using the cell placement technique described by Scepanovic et al. in U.S. Pat. No. 6,026,223 granted Feb. 15, 2000 for “Advanced Modular Cell Placement System with Overlap Remover with Minimal Noise” and assigned to the same assignee as the present invention. However, the overlap removal technique described by Scepanovic et al. is not altogether effective where subrows contain cell overflow. Moreover, after resynthesis and overlap removal, half-cells of a dual height cell may have different x coordinates. Consequently, it becomes necessary to assign new positions to the half-cells.
SUMMARY OF THE INVENTION
In one embodiment of the invention, cell overlap is removed from rows during a cell placement procedure for an integrated circuit chip. The rows are partitioned into subrows so that each subrow contains cells having a common characteristic vector. Cell overflow is removed from each of the subrows. Cell overlap is removed from each of the subrows, and the positions of half-cells of dual height cells are adjusted in adjacent rows for minimal offset of the half-cells.
In some embodiments, the half-cells of the dual height cells are moved to cell positions in a suitable pair of rows. A penalty is calculated based on a distance between the half-cells of a dual height cell before and after the move. A dual height cell is removed from the pair of rows if the calculated penalty is not acceptable. New row coordinates are calculated for the half-cells in the pair of rows if the penalty is acceptable, whereupon the pair of rows are aligned to minimize the penalty and the half-cells of the dual height cells are moved to cell positions in the pair of rows to minimize the penalty.
In other embodiments cell overflows are removed from a row. A movement is chosen, for example a movement of one cell or an exchange of two cells, each overflowed subrow. If the incremented size of the subrows does not exceed the maximum size and the overflows are removed, the movement is performed. Otherwise the size of the subrow containing overflows is incremented, and another movement is chosen.
In preferred embodiments, the invention is manifest in a computer readable program containing code that causes the computer to carry out the steps of the processes described.
REFERENCES:
patent: 5561607 (1996-10-01), Makofske
patent: 6026223 (2000-02-01), Scepanovic et al.
patent: 6128767 (2000-10-01), Chapman
patent: 6385761 (2002-05-01), Breid
patent: 6405356 (2002-06-01), Yang
patent: 6415425 (2002-07-01), Chaudhary et al.
patent: 6446239 (2002-09-01), Markosian et al.
Gasanov Elyar E.
Lu Aiguo
Pavisic Ivan
Zolotykh Andrej A.
LSI Logic Corporation
Siek Vuthe
Tat Binh C.
Westman Champlin & Kelly
LandOfFree
Cell placement in integrated circuit chips to remove cell... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cell placement in integrated circuit chips to remove cell..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cell placement in integrated circuit chips to remove cell... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3022708