Method of designing a cell placement of an integrated circuit

• US 5,579,237 A
• Filed: 11/10/1994
• Issued: 11/26/1996
• Est. Priority Date: 11/15/1993
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Shibuya, Toshiyuki
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Walker, Tyrone V.
• Application Number:
  US08/339,211
• Time in Patent Office: 747 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

An integrated circuit placement method is executed according to a mini-cut method to design the cell placement of an integrated circuit by setting a cut line which divides the integrated circuit into a plurality of blocks and moving the cells such that the cut size, that is, the number of nets, connecting the cells and traversing the cut line can be minimum. It aims to determine the optimum placement by preventing cut size from keeping a local minimum state. A first process P1 detects stable nets which have caused a local minimum state if the cut size in a net has reached the local minimum state after executing the mini-cut method. A second process P2 selects all or a part of the detected stable nets and moves the cells connected to the selected stable nets and placed in different blocks to either of the blocks. A third process P3 detects stable nets if it is determined that the cut size of the net cannot satisfy a terminate condition after executing the mini-cut method immediately following the second process P2, and reactivates the second process P2.

Claims

1. An integrated circuit placement method for designing a cell placement of an integrated circuit by setting a cut line which divides the integrated circuit into a plurality of blocks and moving cells such that the cut size as a number of nets connecting the cells and traversing the cut line is minimized, said method comprising the steps of:

a) detecting stable nets, which have caused a local minimum state if the cut size has reached the local minimum state after executing a mini-cut method from the nets;

b) selecting all or a part of the detected stable nets and moving cells, connected to the selected stable nets and placed in different blocks, to either of the blocks; and

d) detecting stable nets if it is determined that cut size cannot satisfy a terminate condition after executing the mini-cut method immediately following said step b), and for reactivating said step b).

2. The integrated circuit placement method according to claim 1, comprising the steps of detecting nets cut at a start of the mini-cut method and also cut at an end of the mini-cut method as stable nets.

3. The integrated circuit placement method according to claim 2, further comprising the steps of:

d) detecting the stable nets when the stable nets have a long connection when a quadratic mini-cut method of a division level higher than a two-way mini-cut method is performed; and

e) selecting the stable nets having a long connection by priority in said step b).

4. The integrated circuit placement method according to claim 2, further comprising the steps of:

d) detecting the stable nets when the stable nets traverse a cut line of a higher congestion when a quadratic mini-cut method of a division level higher than a two-way mini-cut method is performed; and

e) selecting the stable nets traversing a cut line of a higher congestion by priority in said step b).

5. The integrated circuit placement method according to claim 2, further comprising the steps of:

d) detecting the stable nets when the stable nets have a long connection and traverse a cut line of a higher congestion when a quadratic mini-cut method of a division level higher than a two-way mini-cut method is performed; and

e) selecting the stable nets having a long connection and traversing a cut line of a higher congestion by priority in said step b).

6. The integrated circuit placement method according to claim 1, further comprising the steps of detecting the nets which are cut at an end of a process of the mini-cut method and have a number of connected cells as stable nets.

7. The integrated circuit placement method according to claim 6, further comprising the steps of:

d) detecting the stable nets when the stable nets have a long connection when a quadratic mini-cut method of a division level higher than a two-way mini-cut method is performed; and

e) selecting the stable nets having a long connection by priority in said step b).

8. The integrated circuit placement method according to claim 6, further comprising the steps of:

d) detecting the stable nets when the stable nets traverse a cut line of a higher congestion when a quadratic mini-cut method of a division level higher than a two-way mini-cut method is performed; and

e) selecting the stable nets traversing a cut line of a higher congestion by priority in said step b).

9. The integrated circuit placement method according to claim 6, further comprising the steps of:

d) detecting the stable nets when the stable nets have a long connection and traverse a cut line of a higher congestion when a quadratic mini-cut method of a division level higher than a two-way mini-cut method is performed; and

e) selecting the stable nets having a long connection and traversing a cut line of a higher congestion in said step b).

10. The integrated circuit placement method according to claim 1, further comprising the step of detecting the nets which are cut at an end of a process of the mini-cut method and connected cells having many terminals as a stable net.

11. The integrated circuit placement method according to claim 10, further comprising the steps of:

d) detecting the stable nets when the stable nets have a long connection when a quadratic mini-cut method of a division level higher than a two-way mini-cut method is performed; and

e) selecting the stable nets having a long connection as selected by said step b).

12. The integrated circuit placement method according to claim 10, further comprising the steps of:

d) detecting the stable nets when the stable nets traverse a cut line of a higher congestion when a quadratic mini-cut method of a division level higher than a two-way mini-cut method is performed; and

e) selecting the stable nets traversing a cut line having a higher congestion as selected by said step b).

13. The integrated circuit placement method according to claim 10, further comprising the steps of:

d) detecting the stable nets when the stable nets have a long connection and traverse a cut line of a higher congestion when a quadratic mini-cut method having a division level higher than a two-way mini-cut method is performed; and

e) selecting the stable nets having a long connection and traversing a cut line of a higher congestion as selected by said step b).

14. The integrated circuit placement method, according to claim 1, further comprising the step of moving the cells with a cell which has been prevented from being moved again in said step b).

15. The integrated circuit placement method, according to claim 1, further comprising the step of moving the cells such that an area of each block is balanced with a total of cell areas in said step b).

16. An integrated circuit placement method for designing a cell placement of an integrated circuit by setting a cut line which divides the integrated circuit into a plurality of blocks and moving cells such that the cut size as a number of nets connecting the cells and traversing the cut line is minimized, said method comprising the steps of:

a) performing a mini-cut method until the cut size reaches a stable state;

b) determining whether the stable states are a local minimum state or satisfy a terminate condition;

c) detecting, if a terminate condition is not satisfied, connections between the cells which have caused the local minimum state as stable nets;

d) repeating a process of performing the mini-cut method until the cut size reaches a stable state after deleting the stable nets by moving the cells, in all or a part of the detected stable nets, connected to the stable nets in one block and another block so that the stable nets may not traverse the cut line; and

e) determining a result of the mini-cut method as an optimum placement of the integrated circuit when the terminate condition is satisfied.

17. The integrated circuit placement method according to claim 16, further comprising the step of detecting nets cut at a start of the mini-cut method and also cut at an end of the mini-cut method as stable nets.

18. The integrated circuit placement method according to claim 16, further comprising the step of detecting nets which are cut at an end of a process of the mini-cut method and have a number of connected cells as stable nets.

19. The integrated circuit placement method according to claim 16, further comprising the step of detecting the nets which are cut at an end of a process of the mini-cut method and have connected cells having many terminals as stable nets.

20. The integrated circuit placement method, according to claim 16, further comprising the step of moving the cells with a cell which has been prevented from being moved again.

21. The integrated circuit placement method, according to claim 16, further comprising the step of moving the cells such that an area of each block is balanced with a total of cell areas in the block.