US5579237A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of designing a cell placement of an integrated circuit
Assignee: Fujitsu Ltd
•
Filing: 1994-11-10
•
Granted: 1996-11-26
•
Expires: 2014-11-10
Abstract
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.
Inventors
- 👤 Toshiyuki Shibuya
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 23:37
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
150 words
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).
Claim 2
Dependent Claim
150 words
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).
Claim 3
Dependent Claim
36 words
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.
Claim 4
Dependent Claim
60 words
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).
Claim 5
Dependent Claim
68 words
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).
Claim 6
Dependent Claim
78 words
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).
Claim 7
Dependent Claim
40 words
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.
Claim 8
Dependent Claim
60 words
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).
Claim 9
Dependent Claim
68 words
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).
Claim 10
Dependent Claim
76 words
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).
Claim 11
Dependent Claim
40 words
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.
Claim 12
Dependent Claim
60 words
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).
Claim 13
Dependent Claim
68 words
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).
Claim 14
Dependent Claim
78 words
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).
Claim 15
Dependent Claim
32 words
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).
Claim 16
Dependent Claim
36 words
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).
Claim 17
Dependent Claim
191 words
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.
Claim 18
Dependent Claim
191 words
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.
Claim 19
Dependent Claim
37 words
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.
Claim 20
Dependent Claim
39 words
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.
Claim 21
Dependent Claim
40 words
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.
Claim 22
Dependent Claim
28 words
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.
Claim 23
Dependent Claim
35 words
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.
References Cited (Backward Citations)
US4593363A
Cited
US4577276A
Cited
US5257201A
Cited
US5159682A
Cited
US5267176A
Cited
US5224057A
Cited
US5144563A
Cited
US5113352A
Cited
US5189784A
Cited
US5349536A
Cited
US5359538A
Cited
US5224056A
Cited
US5308798A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-11-26 | 2000-05-27 | 2000-11-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-11-26 | 2004-05-27 | 2004-11-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-11-26 | 2008-05-27 | 2008-11-26 | $7700.00 | Window Closed / Lapsed |