METHODS FOR REDUCING CONGESTION REGION IN LAYOUT AREA OF IC

• US 20160203254A1
• Filed: 06/18/2015
• Published: 07/14/2016
• Est. Priority Date: 01/08/2015
• Status: Active Grant

• Current Assignee: MediaTek, Inc.
• Original Assignee: MediaTek, Inc.
• Inventors: HSU, Chin-Hsiung, YANG, Chun-Chih
• Granted Patent: US 9,940,422 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06F 2119/06 Power analysis or power optimisation
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: G06F 30/398 Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] optical proximity correction [OPC] design processes G03F1/36
• CPC Class Codes: H03K 19/17728 Reconfigurable logic blocks, e.g. lookup tables
• CPC Class Codes: H03K 19/17736 Structural details of routing resources
• CPC Class Codes: H03K 19/17756 for partial configuration or partial reconfiguration
• CPC Class Codes: H03K 19/17796 for physical disposition of blocks

Abstract

A method for reducing congestion regions of an integrated circuit is provided. A placement of the IC is obtained, wherein the placement includes a signal path between a first macro module and a second macro module. The signal path passes through a routing area of the placement for transmitting a specific signal. A congestion region of the routing area is identified. The signal path includes at least one cell or routing path in the congestion region. A cost evaluation is obtained for each candidate position of the routing area by moving the cell or the routing path out of the congestion region. The cell is moved to the candidate position having a minimum cost evaluation among the cost evaluations. The placement and the routing paths are simultaneously updated according to the cell moved to the candidate position having the minimum cost evaluation.

Claims

1. A method for reducing congestion regions in a layout of an integrated circuit, comprising:

obtaining a placement of the integrated circuit, wherein the placement comprises a first signal path between a first macro module and a second macro module, and the first signal path passes through a routing area of the placement for transmitting a specific signal;

identifying a congestion region of the routing area, wherein the first signal path comprises at least one cell or at least one routing path in the congestion region;

obtaining a cost evaluation for each candidate position of the routing area by moving the cell or the routing path out of the congestion region; and

moving the cell or the macro module corresponding to the routing path to the candidate position having a minimum cost evaluation among the cost evaluations, and simultaneously updating the placement and the routing paths according to the cell or the macro module moved to the candidate position having the minimum cost evaluation.

2. The method as claimed in claim 1, wherein the updated placement comprises a second signal path between the first macro module and the second macro module for transmitting the specific signal, and the second signal path comprises the moved cell and the updated routing paths corresponding to the moved cell.

3. The method as claimed in claim 2, wherein the second signal path does not pass through the congestion region, and the first and second macro modules are arranged around the routing area.

4. The method as claimed in claim 1, further comprising:

dividing the routing area into a plurality of exploration regions; and

obtaining a cell density and a routing density of each of the exploration regions.

5. The method as claimed in claim 4, wherein the congestion region comprises the exploration regions having the cell density or the routing density greater than a specific density.

6. The method as claimed in claim 5, wherein the step of obtaining the cost evaluation for each of the candidate positions of the routing area by moving the cell or the routing path out of the congestion region further comprises:

obtaining a sparse region of the routing area, wherein the sparse region is adjacent to the congestion region, and the sparse region comprises the exploration regions having the cell density or the routing density smaller than the specific density;

obtaining the candidate positions within the sparse region, wherein each of the candidate positions is an unoccupied area capable of placing the cell; and

calculating the cost evaluation for each of the candidate positions within the sparse region by moving the cell from the congestion region to the candidate position.

7. The method as claimed in claim 6, the step of calculating the cost evaluation of each of the candidate positions within the sparse region by moving the cell or the routing path from the congestion region to the candidate position further comprises:

obtaining a placement cost when the cell is moved from the congestion region to the candidate position;

obtaining a routing cost when the routing paths of the moved cell are rerouted; and

obtaining the cost evaluation of the candidate position according to the placement cost and the routing cost.

8. The method as claimed in claim 1, the step of obtaining the cost evaluation for each of the candidate positions of the routing area by moving the cell or the routing path out of the congestion region further comprises:

selecting one candidate position from the candidate positions;

obtaining a placement cost by moving the cell from the congestion region to the selected candidate position;

obtaining a routing cost by rerouting the routing paths corresponding to the cell moved to the selected candidate position; and

obtaining the cost evaluation for the selected candidate position according to the placement cost and the routing cost.

9. The method as claimed in claim 8, wherein the routing area is divided into a plurality of exploration regions, and the placement cost comprises a cell density of the exploration region that the selected candidate position is located, and the routing cost comprises a routing density of the exploration region where the selected candidate position is located.

10. The method as claimed in claim 1, wherein positions of the first macro module and the second macro module in the placement are different from the positions of the first macro module and the second macro module in the updated placement.

11. The method as claimed in claim 10, wherein the positions of the first macro module and the second macro module in the updated placement are arranged in a straight line.

12. A method for reducing congestion regions in a layout of an integrated circuit, comprising:

obtaining a placement of the integrated circuit, wherein the placement comprises a first signal path between a first macro module and a second macro module;

obtaining a congestion region of a routing area of the placement and a sparse region of the routing area adjacent to the congestion region, wherein the first signal path comprises at least one cell in the congestion region and a plurality of routing paths corresponding to the cell;

obtaining a plurality of candidate positions within the sparse region, wherein each of the candidate positions is an unoccupied area capable of placing the cell;

calculating a cost evaluation for each of the candidate positions by moving the cell from the congestion region to the candidate position; and

simultaneously updating the placement and the routing paths according to a second signal path between the first macro module and the second macro module, wherein the second signal path comprises the cell moved to the candidate position having a minimum cost evaluation among the cost evaluations.

13. The method as claimed in claim 12, wherein the second signal path further comprises the updated routing paths corresponding to the cell moved to the candidate position having the minimum cost evaluation.

14. The method as claimed in claim 12, wherein the second signal path does not pass through the congestion region, and the first and second macro modules are arranged around the routing area.

15. The method as claimed in claim 12, wherein the step of obtaining the congestion region of the routing area of the placement and the sparse region of the routing area adjacent to the congestion region further comprises:

dividing the routing area into a plurality of exploration regions; and

obtaining a cell density and a routing density of each of the exploration regions.

16. The method as claimed in claim 15, wherein the congestion region comprises the exploration regions having the cell density or the routing density greater than a specific density, and the sparse region comprises the exploration regions having the cell density or the routing density smaller than the specific density.

17. The method as claimed in claim 12, the step of calculating the cost evaluation for each of the candidate positions by moving the cell from the congestion region to the candidate position further comprises:

selecting one candidate position from the candidate positions;

obtaining a placement cost by moving the cell from the congestion region to the selected candidate position;

obtaining a routing cost by rerouting the routing paths corresponding to the cell moved to the selected candidate position; and

obtaining the cost evaluation for the selected candidate position according to the placement cost and the routing cost.

18. The method as claimed in claim 17, wherein the routing area is divided into a plurality of exploration regions, and the placement cost comprises a cell density of the exploration region that the selected candidate position is located, and the routing cost comprises a routing density of the exploration region where the selected candidate position is located.

19. The method as claimed in claim 12, wherein positions of the first macro module and the second macro module in the placement are different from the positions of the first macro module and the second macro module in the updated placement.

20. The method as claimed in claim 19, wherein the positions of the first macro module and the second macro module in the updated placement are arranged in a straight line.

21. A non-transitory computer-readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method for reducing congestion regions in a layout of an integrated circuit, the method comprising:

obtaining a placement of the integrated circuit, wherein the placement comprises a first signal path between a first macro module and a second macro module, and the first signal path passes through a routing area of the placement for transmitting a specific signal;

identifying a congestion region of the routing area, wherein the first signal path comprises at least one cell or at least one routing path in the congestion region;

obtaining a cost evaluation for each candidate position of the routing area by moving the cell or the routing path of the congestion region; and

moving the cell or the macro module corresponding to the routing path to the candidate position having a minimum cost evaluation among the cost evaluations, and simultaneously updating the placement and the routing paths according to the cell or the macro module moved to the candidate position having the minimum cost evaluation.

22. The non-transitory computer-readable storage medium as claimed in claim 21, wherein the updated placement comprises a second signal path between the first macro module and the second macro module for transmitting the specific signal, and the second signal path comprises the moved cell and the updated routing paths corresponding to the moved cell.

23. The non-transitory computer-readable storage medium as claimed in claim 21, the method further comprising:

dividing the routing area into a plurality of exploration regions; and

obtaining a cell density and a routing density of each of the exploration regions.

24. The non-transitory computer-readable storage medium as claimed in claim 23, wherein the step of obtaining the cost evaluation for each candidate position of the routing area by moving the cell or the routing path out of the congestion region further comprises:

obtaining a sparse region of the routing area, wherein the sparse region is adjacent to the congestion region;

obtaining the candidate positions within the sparse region, wherein each of the candidate positions is an unoccupied area capable of placing the cell; and

calculating the cost evaluation for each of the candidate positions within the sparse region by moving the cell from the congestion region to the candidate position,

wherein the congestion region comprises the exploration regions having the cell density or the routing density greater than a specific density, and the sparse region comprises the exploration regions having the cell density or the routing density smaller than the specific density.

25. The non-transitory computer-readable storage medium as claimed in claim 21, the step of obtaining the cost evaluation for each candidate position of the routing area by moving the cell or the routing path out of the congestion region further comprises:

selecting one candidate position from the candidate positions;

obtaining a placement cost by moving the cell from the congestion region to the selected candidate position;

obtaining a routing cost by rerouting the routing paths corresponding to the cell moved to the selected candidate position; and

obtaining the cost evaluation for the selected candidate position according to the placement cost and the routing cost.

26. The non-transitory computer-readable storage medium as claimed in claim 25, wherein the routing area is divided into a plurality of exploration regions, and the placement cost comprises a cell density of the exploration region that the selected candidate position is located, and the routing cost comprises a routing density of the exploration region where the selected candidate position is located.

27. The non-transitory computer-readable storage medium as claimed in claim 21, wherein positions of the first macro module and the second macro module in the placement are different from the positions of the first macro module and the second macro module in the updated placement.

28. The method as claimed in claim 27, wherein the positions of the first macro module and the second macro module in the updated placement are arranged in a straight line.