KR101044295B1 - A method and apparatus to pack neighbor blocks and cells during the automatic chip level layout compaction - Google Patents

Abstract

PURPOSE: A block packing method and a standard cell packing method for automatic chip area optimization are provided to prevent wiring failure due to the congestion of hard blocks by securing an original area for wiring among the hard blocks and between the hard block and the standard cells. CONSTITUTION: An outline of all hard blocks is generated(S110). The outline is expanded with a merge factor(S120). The neighboring hard blocks which the outlines are overlapped each other are merged to one outline and make grouping(S130). The hard blocks within the group are merged to a small group in consideration of wiring between a standard cell and the hard blocks, and a bridge area is inserted between the small groups(S140). Hard block groups in which the bridge is inserted is packed to a group unit(S150).

Description

A Method and Apparatus to Pack Neighbor Blocks and Cells during the Automatic Chip Level Layout Compaction for Automated Chip Area Optimization

The present invention relates to a neighboring block and a standard cell packing method for automated chip area optimization. In particular, the present invention relates to a method of packing a neighbor block group packing by automatically recognizing a placement pattern of hard blocks. In addition, it provides a way to secure the exclusive area for the standard cells by extending the periphery of each group, as well as optimizing the placement of incremental batches using the alignment technique in standard cell packing while maintaining the original relative position as much as possible. A block packing method and a standard cell packing method for automated chip area optimization that enable performance.

Optimizing the chip area and reducing its size is an important factor to consider along with the functionality and performance of integrated circuits, but the design constraints caused by rapidly increasing circuit size and miniaturization of the manufacturing process make it difficult to predict chip area. Giving. Moreover, today's chip designs have a large number of relatively large blocks, which can be reused as part of existing layouts or the use of modular IP (Intellectual Property) and memory blocks is rapidly increasing. To meet all design constraints while optimizing the size of the chip requires considerable time and effort.

1. How to verify chip area optimization by hand

1 illustrates a general method of optimizing chip area through conventional manual work.

Once the design inputs of the designer's intents, such as the initial design area and the respective design objects and their connection information (Netlist) and power plan, are ready, Based on the connection information (Floor plan) (S1), the possibility of wiring (Trial route) is examined (S2). Then, to meet the chip's performance requirements, it performs route optimization (S3) through optimization of design (S3) and design closure (S4). When the process is completed, the initial chip layout (Initial layout) is operated, and then chip area optimization is performed to improve yield. First, it is determined whether it is an optimal area (Smallest Chip Size) (S6), otherwise it is performed again from the arrangement (S1) step and repeated.

The problem of manually optimizing chip area is firstly, iteratively repeating the whole design process, and secondly, the designers have to intervene through the continuous decision-making process based on their empirical expertise. As a result, the area optimization work by hand is difficult to evaluate the time required and to obtain the objective reliability of the result.

2. How to verify chip area optimization through automation software

2 illustrates a general method of optimizing chip area using conventional automation software. This method can automatically improve chip area optimization, significantly reducing the waste of design resources and time compared to the manual method.

When the design input is ready, perform the floor plan (S1), review the trial route (S2), optimize the layout (S3), and optimize the chip's function and performance (Optimize Design). Automatic chip area optimization operation (S11-S14) is started after the operation.

A new placement area of the reduced chip area is determined according to a shrink factor (Decrease Size) (S11), and each circuit element is packed (Place Design) on the x-axis and the y-axis, respectively (S12). The power wiring network and the global wiring possibility are examined (Power & Global Route) (S13) to determine re-execution and termination of the same process (S14).

When the automatic chip area optimization operations S11 to S14 are completed, a design closure verification S4 is performed, a route S5 is performed, and a termination S7 is performed.

Particularly, in the initial place design stage, the layout information is placed on a chip of a new area based on the input information of each input circuit element. In this case, the performance, function, and designer's intention of the chip are included in the layout information. It is important to maintain their relative location information.

3. Conventional block packing method

Conventional block packings move individual blocks in the lower left direction with respect to each axis. This method can only maintain the relative positions of the blocks, and it is impossible to secure the original space for the wiring of the blocks.

3 shows the effect of the existing block packing on the wiring area for the chip 10 before packing and the chip 10 'after packing, respectively. Hard blocks A, B, and C (12-14) are located at the bottom of the chip, and standard cells (11) are present on the hard blocks (12-14), respectively, and the shaded portion is a routing area (16). )to be. The wiring space of the chip 10 before the block packing is already adjusted by the designer according to the layout pattern of each hard block 11-14 and the layout pattern of the surrounding standard cells 11, and the space is reduced. This increases the likelihood of wiring failure in this area after packing.

In fact, after packing the chip 10 'as a result of individual block packing, the relative positions of the hard blocks A, B, and C (12-14) were maintained along the direction of each axis, but the spacing 15 between them and the standard The spacing between the cells 11 is reduced so that the wiring area of the region is significantly reduced compared to the chip 10 before packing.

Individual hard block packing reduces the spacing 15 between each hard block 11-14, which in turn leads to a reduction in the wiring space 16 and with the standard cell 11 population, in addition to reducing the spacing between the hard blocks. It can be seen that the interval is also reduced.

Due to this problem, a wiring-based packing technique is required to correct the hard block packing.

In addition, despite the high probability of wiring failure after this block packing process, it is a waste of time if the final decision is made by checking the wiring failure only at the final stage of automation. If the wiring can be considered in the hard block packing step located earlier in the automation process, the automation process can be made faster.

4. Conventional standard cell packing method

4 is a conventional standard cell packing flow chart, and FIG. 5 is an existing standard cell packing explanatory diagram.

Incremental deployment technique performs legalization process (Sgal, S21, S22) and optimization process (Optimization) (S23). The site definition of the semiconductor manufacturing process strictly dictates the placement of standard cells on the placement grid for wiring. The width of the placement grid above the Placement Row is determined by the length declared in the site definition, and the width of the standard cell is determined by a multiple of this length.

Incremental placement ensures that all standard cells are correctly placed on the placement grid and then eliminates mutual overlap between circuit elements. Although the new placement area is determined according to the shrink factor and the hard blocks are packed by the existing block packing method, the standard cells 11 that are on the layout grid of the original layout are not shown in FIG. 5. There may also be standard cells 11 which deviate from) and which are completely out of the new placement area 21, especially on the upper and right sides.

In this case, in order to arrange all the circuit elements on a layout grid (S21), standard cells may be excessively dense in a specific area. In FIG. 5, the shaded area is the dense area 22. At this point two problems arise: one to eliminate the overlap between the standard cells 11 occurring in this dense area 22 and the other to distribute the high density to another area.

The process of legalizing the incremental placement technique used to solve these two problems does not take into account the relative placement relationship of the original standard cells, so that it cannot be maintained in the new placement area. Therefore, we need a way to legalize the process while maintaining the relative placement of the original.

The present invention is to provide a standard block packing method using a hard block packing method and an alignment method in consideration of power and global routing in order to solve the block packing problem.

The present invention was developed to improve the problems of the conventional method described above in the hard block and standard cell packing method. For hard block packing, the present invention automatically recognizes an initial chip block arrangement pattern and classifies the data into several groups based on adjacent blocks. In addition, the present invention provides a method of packing a group into a new chip arrangement area.

The present invention provides a block packing method in consideration of wiring to improve the accuracy of chip area optimization through automation and to enable high speed. To this end, the stacking pattern of adjacent hard blocks is automatically recognized, and the hard blocks are grouped and packed in units to preserve the wiring area of the original to improve wiring possibilities. Each group can maintain the spacing between hard blocks, as well as automatically expand the outline of the group to maintain spacing from standard cells.

In addition, the present invention provides a standard cell placement technique using alignment with respect to the standard cell packing method, which solves the problem of legalization of all standard cells using horizontal and vertical alignment, while maintaining the original relative position to optimize the incremental placement optimization process. This can be done to improve the accuracy of the automation results.

The present invention was developed to improve the problems of the conventional method described above in the hard block and standard cell packing method. For hard block packing, the present invention automatically recognizes an initial chip block arrangement pattern and classifies the data into several groups based on adjacent blocks. In addition, the present invention provides a method of packing a group into a new chip arrangement area.

According to another aspect of the present invention, there is provided a group-based packing method for hard blocks, the hard block outline generating process of generating an outline for all hard blocks;

An outline extension process of extending the hard block outline based on a merge factor (Δ) which is a constant set based on hard block density;

A grouping process of merging neighboring hard blocks in which the outlines of each of the hard blocks whose outlines have been expanded overlap with each other by merging them into a single outline;

For each group that has undergone the grouping process, in consideration of the wiring between the standard cell and the hard block, the hard blocks inside the group are expanded to merge overlapping hard blocks into small groups, and a bridge region is inserted between the separated small groups. Bridge insertion process;

And a packing process of packing each hard block group that has undergone the intra-bridge insertion process in group units.

The grouping process of automatically recognizing and grouping the adjacent hard block arrangement pattern (Neighbor Block Grouping),

An outline selection step of selecting one outline among them by inputting outlines of all blocks;

A merging step of merging the overlapping two when there is an outline of another hard block overlapping the selected outline in the outline selection step;

If there are no other overlapping lines in the merging step any more, select any other outline, perform the merging step with the outline selection step, repeat the above steps for all the ungrouped outlines, and then end the grouping. Characterized in that it is made to perform the steps.

The intra-group bridge insertion process for automatically expanding the exclusive area for the standard cell outside the group,

Creating a hard block outline in the group for generating group outlines for the internal hard blocks for each group when grouping is completed by overlapping hard block outlines;

An in-group outline expansion step of expanding a hard block outline in the group by a group expansion factor β set by the designer in consideration of the wiring between the standard cell and the hard block;

A small grouping step of merging hard blocks in which the in-group hard block outlines expanded by the in-group outline expanding step into small groups;

After the small grouping step, if there is only one small group in the group, the group area is determined as it is, and if there is more than one small group, a bridge area is inserted to insert a bridge area between neighboring small groups. Characterized in that made to perform.

Unlike the conventional block packing process of individually packing each hard block, this technique automatically recognizes a placement pattern of hard blocks and packs them to a neighbor block group packing. It also provides a way to automatically extend the outline.

In order to pack each block group, the present invention firstly recognizes a stacking pattern of adjacent hard blocks through a block arrangement pattern recognizer and groups them into multiple groups based on this. Second, standard cells for each group Is to automatically extend the exclusive scope to.

After that, pack the group to the lower left to complete the block packing process.

On the other hand, the packing method of the standard cell according to the present invention,

An original position setting step of searching for and setting an original position on a layout of standard cells;

Standard cell that proportionally moves each standard cell by the reduction factor (φ) by the reduction factor (φ) by setting the ratio of the area of the new layout to the original layout as the reduction factor (φ). A region reduction step;

A batch ratio determining step of determining a ratio r with respect to the number of standard cells to be allocated to the column in which the standard cells are to be arranged after the standard cell area is reduced;

A vertical axis sorting step of vertically arranging the standard cells in the vertical axis direction of the chip corresponding to the number assigned to each column in the vertical axis direction of the chip;

A horizontal axis sorting step of performing horizontal axis sorting on the number of standard cells allocated to each column when the vertical axis sorting is completed;

The standard cell optimization step of setting and packing the alignment positions of the standard cells aligned by the vertical axis and the horizontal axis alignment is performed.

In this way, a standard cell packing technique using a simple alignment is provided, which is capable of achieving a uniform distribution of density while packing while maintaining the relative position of the original standard cell as much as possible. This sorting technique replaces the legalization process in incremental batch order, which vertically sorts all standard cells to determine the vertical order between the cells that are assigned to each Placement Row, and then again for the standard cells assigned to each Placement Column. Aligning with the horizontal axis determines the left and right arrangement order between cells.

Standard cell-to-cell spacing within each batch column can be equalized. This technique ensures that for any standard cell, the cells that were located above this cell in the original are always at the top and also the relative positions of the left and right sides. By passing the standardized cell batches that have been legalized while maintaining the relative standard cell position of the originals to the optimization process, which is the final stage of the incremental placement technique, the optimization process can be performed with maximum consideration of the original design constraints.

Through the present invention, it is possible to proceed with the block packing considering the wiring around each block and the standard cell packing maintaining the relative position of the original arrangement, which can improve and speed up the accuracy of chip area optimization.

By using the block packing method considering the wiring according to the present invention, since the original area for wiring between the hard blocks and between the hard blocks and the standard cells is secured, it is possible to prevent the failure of the wiring due to the density of the existing hard blocks.

In addition, the legalization process through the alignment technique enables the optimization process of the incremental placement technique while maintaining the original position of each standard cell as much as possible.

These techniques enable block packing with complete wiring considerations and standard cell packing to maintain the original design constraints, which improves and speeds up chip area optimization accuracy.

1 is a conventional chip area optimization flow chart.
2 is a flow chart of a conventional automatic progress chip area optimization.
3 is a diagram illustrating a conventional hard block packing result.
4 is a flow diagram of an existing standard cell packing.
5 is an explanatory diagram of an existing standard cell packing.
6 is a hard block packing flow chart according to the present invention.
7 is a flow chart of adjacent hard block groupings in accordance with the present invention.
8 is an explanatory diagram of adjacent hard block groupings according to the present invention;
9 is an intragroup hard block outline extension flowchart according to the present invention;
Fig. 10 is an explanatory diagram of inserting bridges between small groups in a group according to the present invention.
11 is a standard cell packing flow chart according to the present invention.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

6 is a flowchart of adjacent hard block blocking and outline expansion according to the present invention.

The present invention provides a hard block packing method and a standard cell packing method, respectively.

A hard block outline generation process (S110) for generating an outline for all hard blocks;

An outline expansion step (S120) of extending the hard block outline based on a merge factor (Δ) which is a constant set based on a hard block density;

A grouping process (S130) of merging neighboring hard blocks in which the outlines of the hard blocks having the extended outlines overlap each other are merged into one outline in the outline extension process (S120);

For each group that has undergone the grouping process (S130), in consideration of the wiring between the standard cell and the hard blocks, the outlines of the hard blocks in the group are expanded to merge the overlapping hard blocks into small groups, and a bridge region is formed between the separated small groups. Intra-bridge insertion process (S140) for insertion;

A packing process S150 for packing each hard block group that has undergone the intra-group bridge insertion process S140 on a group basis is performed.

Such a hard block packing method of the present invention,

First, for hard block packing, a hard block outline generation process (S110) is performed. Subsequently, an extension process S120 of expanding each hard block outline by a merge factor is performed. Here, the merge factor is a constant related to the density of hard blocks. If the value is large, the merge factor is searched for and merged adjacent hard blocks in a wide range.

When the outline of each hard block is expanded according to the merging factor, the outlines of neighboring hard blocks may overlap, and the grouping process (S130) of merging the overlapping hard blocks so as to belong to one outline is performed. . That is, each hard block having an outline extended by the merging factor is searched for another hard blocks having overlapping outlines and attempted to merge and grouped.

After that, the exclusive area is expanded for each group, and the overlapping outlines are merged into small groups, and after the intra-group bridge insertion process (S140) for inserting bridge areas between the small groups separated from each other in the group, packing in groups The packing process (S150) is performed.

7 is a flowchart for automatically recognizing and grouping adjacent hard block arrangement patterns according to the present invention. This represents a grouping process (S130) for automatically recognizing and grouping neighbor block grouping patterns.

An outline selection step (S131) of selecting one outline among them by inputting outlines of all blocks;

Merging step (S132) of merging the overlapping two when there is an outline of another hard block overlapping the selected outline in the outline selection step (S131);

If there are no other overlapping lines in the merging step (S132) any more, select any other outline to perform the merging step with the outline selection step, repeat the above steps for all the ungrouped outlines, and then end the grouping. The grouping end step (S133) is performed.

8 is an explanatory diagram of a grouping process according to recognition of an adjacent hard block arrangement pattern according to the present invention.

When there are hard blocks A, B, and C (Block A, B, C), an outline 101 is generated for each hard block, and the outline 101 of each hard block is expanded by a merge factor Δ.

As shown in (a) of FIG. 8, when the outlines of each hard block are expanded, overlapping portions may be formed. First, since there is a portion where the outline A of hard block A and the outline B of hard block B overlap each other, merging the two outlines makes the boundary AB. Subsequently, overlapping with the outline AB in FIG. 8 (b) merges it with the outline C, and as a result, as shown in FIG. 8 (c), the outline ABC is determined, thereby determining the hard blocks A, B, and C as one group. do.

9 is a flowchart of an exclusive area automatic expansion process for a standard cell outside each group according to the present invention.

When the grouping is completed by whether each of the hard block outlines overlap, in-group hard block outline generation step (S141) for generating an outline for each of the internal hard blocks for each group;

 An in-group outline expansion step (S142) of extending the hard block outline in the group by the group expansion factor β set by the designer in consideration of the wiring between the standard cell and the hard block;

 A small grouping step (S143) of merging hard blocks in which the in-group hard block outlines expanded by the in-group outline expanding step (S142) overlap into small groups;

 After the small grouping step (S143), if there is only one small group in the group, the group region is determined as it is, and if there is more than one small group, the bridge region 101 is inserted between neighboring small groups. It is made to perform the bridge insertion step (S145) to determine the.

In this way, for each group determined by the process of FIG. 8, an outline of hard blocks in the group is generated (S141), and the hard block outline in the group is extended by an expansion factor β (S142). In this case, the expansion factor β is a constant representing the interval in which the designer's intention is implied to secure the wiring between the hard blocks and the standard cell, and means the distance to the standard cell closest to its outer boundary.

 After the expansion of the hard block outline in the group, overlapping adjacent blocks are small-grouped in the same manner as in FIG. 10, which is performed only for the hard blocks in the same group, which is different from the grouping process in FIG.

 However, a difference may occur between the merging factor Δ in the grouping process of FIG. 8 and the expansion factor β for the small grouping in the group of FIG. 9, but the difference may be divided into several small groups. have. In this case, an exclusive space for the standard cell can be secured by inserting a bridge into the space between the separated small groups and the small groups to maintain the spacing between the small groups. That is, as illustrated in FIG. 10, blocks A, B, and C (blocks A, B, and C) of the same group are subjected to the small group A (Block A) of the neighbor block in FIG. And Block B merged) and small group B (Block C). This is because the expansion factor beta value used for small group determination is smaller than the merging factor (Δ) value used in the decision step of this group, and if the bridge region 101 is inserted between small group A and small group B, Exclusive space is secured. In this case, the bridge region 101 is not an actual region, but means an area for maintaining a gap.

After performing the neighbor block grouping process (S130) and the intra-group bridge insertion process (S140) as described above, the hard block packing process (S150) is performed in groups. The packing process is to move each group closer to the coordinate (0,0) position of the chip. Conventionally, hard blocks are packed. However, in the present invention, the grouping is performed while grouping while maintaining the distance between the hard blocks and the standard cell. Packed in groups.

11 is a standard cell packing flow chart according to the present invention.

As shown therein,

An original position setting step (S201) of searching and setting an original position on a layout of standard cells;

Standard cell that proportionally moves each standard cell by the reduction factor (φ) by the reduction factor (φ) by setting the ratio of the area of the new layout to the original layout as the reduction factor (φ). An area reduction step (S202);

A batch ratio determining step (S203) of determining a ratio r with respect to the number of standard cells to be allocated to a column for arranging the standard cells after the standard cell area is reduced;

A vertical axis aligning step (S204) for vertically aligning the standard cells in the vertical axis direction of the chip corresponding to the number assigned to each column in the vertical axis direction of the chip;

A horizontal axis sorting step (S205) for performing horizontal axis sorting (x-sort) for the number of standard cells allocated to each column when the vertical axis sorting is completed;

The standard cell optimization step S206 of setting and packing the alignment positions of the standard cells aligned by the vertical axis alignment S204 and the horizontal axis alignment S205 is performed.

In this way, the standard cell packing method moves each standard cell proportionally in the lower left direction of the placement area according to the reduction factor φ at the original position as in the block packing.

 Here, the reduction factor φ is the ratio of the area of the new layout to the original layout. If the reduction factor φ is 0.95, the area of the new layout is 95% of the original layout area. Because of the proportional shift, the standard cells placed farther from the lower left of the new placement area travel longer distances than those close to them, eventually moving all standard cells into the new placement area.

The present invention uses an alignment technique to place them on the placement grid without overlap. In a layout in which standard cells are arranged, there are a plurality of placement rows. First, a ratio r of the number of standard cells to be allocated to each placement column must be determined. r is determined as the ratio of the total number of layout grids occupied by all standard cells to the total number of layout grids held by all layout columns. In other words, if you assign a standard cell by the ratio of r to each batch column, the same number of batch grids are used for all cell batches.

 Once the value of r is determined, the vertical cells are aligned based on the placement positions of the standard cells, and the standard cells are allocated by the ratio of r to the lowest placement column. This way, standard cells with their original positions above them will always be placed in the same column or above it. After that, the horizontal alignment of the assigned standard cells is determined by the horizontal alignment for each batch column. This technique solves the legalization problem while always ensuring the original position of each standard cell in the left and bottom directions relative to the other cells, and passes the results to the optimization process to maintain the placement of the original standard cell while maintaining the placement of the original standard cell. Optimization can be performed.

11: Standard Cell 21: New Layout Outline
22: dense area 101: bridge area

Claims (4)

In the hard block packing method for finding and packing the optimal arrangement of hard blocks in the chip in order to optimize the chip area in the design process of a semiconductor chip,
A hard block outline generation process (S110) for generating an outline for all hard blocks;
An outline expansion step (S120) of extending the hard block outline based on a merge factor (Δ) which is a constant set based on a hard block density;
A grouping process (S130) of merging neighboring hard blocks in which the outlines of the hard blocks having the extended outlines overlap each other are merged into one outline in the outline extension process (S120);
For each group that has undergone the grouping process (S130), in consideration of the wiring between the standard cell and the hard blocks, the outlines of the hard blocks in the group are expanded to merge the overlapping hard blocks into small groups, and a bridge region is formed between the separated small groups. Intra-bridge insertion process (S140) for insertion;
Hard block packing method for the automated chip area optimization, characterized in that for performing a packing step (S150) for packing each hard block group through the intra-group bridge insertion step (S140) in groups.
The method of claim 1, wherein the grouping process (S130),
An outline selection step (S131) of selecting an outline of one hard block among outlines of all hard blocks;
Merging step (S132) of merging the overlapping two when there is an outline of another hard block overlapping the selected outline in the outline selection step (S131);
If there are no other overlapping lines in the merging step (S132) any more, select any other outline to perform the merging step with the outline selection step, repeat the above steps for all the ungrouped outlines, and then end the grouping. Hard block packing method for the automated chip area optimization, characterized in that for performing the grouping end step (S133).
The method of claim 1, wherein the intra-group bridge insertion process (S140),
When the grouping is completed by whether each of the hard block outlines overlap, in-group hard block outline generation step (S141) for generating an outline for each of the internal hard blocks for each group;
An in-group outline expansion step (S142) of extending the hard block outline in the group by the group expansion factor β set by the designer in consideration of the wiring between the standard cell and the hard block;
A small grouping step (S143) of merging hard blocks in which the in-group hard block outlines expanded by the in-group outline expanding step (S142) overlap into small groups;
After the small grouping step (S143), if there is only one small group in the group, the group region is determined as it is, and if there is more than one small group, the bridge region 101 is inserted between neighboring small groups. Hard block packing method for the automated chip area optimization, characterized in that for performing the bridge insertion step (S145) to determine the.
In a standard cell packing method for automated chip area optimization,
An original position setting step (S201) of searching and setting an original position on a layout of standard cells;
Standard cell that proportionally moves each standard cell by the reduction factor (φ) by the reduction factor (φ) by setting the ratio of the area of the new layout to the original layout as the reduction factor (φ). An area reduction step (S202);
A batch ratio determining step (S203) of determining a ratio r with respect to the number of standard cells to be allocated to a column for arranging the standard cells after the standard cell area is reduced;
A vertical axis aligning step (S204) for vertically aligning the standard cells in the vertical axis direction of the chip corresponding to the number assigned to each column in the vertical axis direction of the chip;
A horizontal axis sorting step (S205) for performing horizontal axis sorting (x-sort) for the number of standard cells allocated to each column when the vertical axis sorting is completed;
Hard block for automated chip area optimization, characterized in that for performing the standard cell optimization step (S206) of setting and packing the alignment position of the standard cells aligned by the longitudinal axis alignment (S204) and the horizontal axis alignment (S205) Packing way.

Images