US5793643A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for handling variable width wires in a grid-based channel router
Assignee: Synopsys Inc
•
Filing: 1996-04-30
•
Granted: 1998-08-11
•
Expires: 2016-04-30
Abstract
Abstract In a grid-based channel router, a method for handling variable width wires. The user initially specifies the widths of the wires. In this manner, wider wires may be selected for special nets, such as those used for routing clock signals, whereas narrower wires are used for normal nets in order to minimize the die size. A refined grid map is generated. This refined grid map consists of extra rows and columns for marking the variable width wires. These extra rows and columns are spaced as a function of the wire width and are marked the same as with normal rows and columns. Before a wire is placed, the affected rows or columns are checked for any violations. If there are no violations, the wire is placed and the appropriate rows or columns are marked. Due to the extra rows and columns, the problems associated with overmarking and undermarking variable width wires are avoided.
Inventors
- 👤 Yang Cai
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 21:40
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
384 words
A computer-implemented method for preventing variable-width wire and pin placement violations caused by overmarking in a channel router, the method comprising the steps of: specifying the width of at least one of a wire and a pin to have a particular width relative to a default width; generating a channel grid map that includes a plurality of columns (C i ), wherein each column has at least one sub-column adjacent a first fraction of a default-wire width on the left (C i - ) and at least one sub-column adjacent a second fraction of said default-wire width on the right (C i + ); and placing said at least one of a wire and a pin in a particular column (C n ) that exists in said plurality of columns (C i ) by: checking if a first mark indicates said particular column (C n ) is already used, checking if a second mark indicates a left sub-column (C i - ) adjacent to said particular column (C n ) is already used, and checking if a third mark indicates a right sub-column (C i - ) adjacent to said particular column (C n ) is already used; placing said at least one of a wire and a pin in a particular column (C n ) if said first marking indicates said particular column (C n ) is not already used, and then marking said particular column (C n ) as being used, otherwise exiting the step of placing to avoid a violation; if said at least one of a wire and a pin is placed in said particular column (C n ) and has a wide width, checking if said second marking indicates said left sub-column (C n - ) is not already used, and then marking said left sub-column (C n - ) as being used, otherwise exiting the step of placing to avoid a violation; and if said at least one of a wire and a pin is placed in said particular column (C n ) and has a wide width, checking if said third marking indicates said right sub-column (C n + ) is not already used, and then marking said right sub-column (C n + ) as being used, otherwise exiting the step of placing to avoid a violation.
Claim 2
Dependent Claim
384 words
A computer-implemented method for preventing variable-width wire and pin placement violations caused by overmarking in a channel router, the method comprising the steps of: specifying the width of at least one of a wire and a pin to have a particular width relative to a default width; generating a channel grid map that includes a plurality of columns (C i ), wherein each column has at least one sub-column adjacent a first fraction of a default-wire width on the left (C i - ) and at least one sub-column adjacent a second fraction of said default-wire width on the right (C i + ); and placing said at least one of a wire and a pin in a particular column (C n ) that exists in said plurality of columns (C i ) by: checking if a first mark indicates said particular column (C n ) is already used, checking if a second mark indicates a left sub-column (C i - ) adjacent to said particular column (C n ) is already used, and checking if a third mark indicates a right sub-column (C i - ) adjacent to said particular column (C n ) is already used; placing said at least one of a wire and a pin in a particular column (C n ) if said first marking indicates said particular column (C n ) is not already used, and then marking said particular column (C n ) as being used, otherwise exiting the step of placing to avoid a violation; if said at least one of a wire and a pin is placed in said particular column (C n ) and has a wide width, checking if said second marking indicates said left sub-column (C n - ) is not already used, and then marking said left sub-column (C n - ) as being used, otherwise exiting the step of placing to avoid a violation; and if said at least one of a wire and a pin is placed in said particular column (C n ) and has a wide width, checking if said third marking indicates said right sub-column (C n + ) is not already used, and then marking said right sub-column (C n + ) as being used, otherwise exiting the step of placing to avoid a violation.
Claim 3
Dependent Claim
34 words
The method of claim 1, if the step of placing was exited to avoid a violation, then further comprising the subsequent step of: selecting a different column and then repeating the step of placing.
Claim 4
Dependent Claim
34 words
The method of claim 1, further comprising the subsequent step of: compacting after completing a detailed routing phase to remove all unnecessary gaps from a channel in order to minimize a silicon area needed.
Claim 5
Dependent Claim
69 words
The method of claim 1, further comprising the preceding step of: extracting a connections information from a netlist specification generated according to an integrated circuit design, wherein a global routing result specifies pin locations and their connections; and building said channel grid map and determining whether variable width wires are needed, if so, refining said channel grid map by adding extra columns in order to accommodate variable width wires.
Claim 6
Dependent Claim
384 words
A computer-implemented method for preventing variable-width wire and pin placement violations caused by overmarking in a channel router, the method comprising the steps of: specifying the width of at least one of a wire and a pin to have a particular width relative to a default width; generating a channel grid map that includes a plurality of rows (R i ), wherein each row has at least one sub-row adjacent a first fraction of a default-wire width on the lower (R i - ) and at least one sub-row adjacent a second fraction of said default-wire width on the upper (R i + ); and placing said at least one of a wire and a pin in a particular row (R n ) that exists in said plurality of rows (R i ) by: checking if a first mark indicates said particular row (R n ) is already used, checking if a second mark indicates a lower sub-row (R i - ) adjacent to said particular row (R n ) is already used, and checking if a third mark indicates a upper sub-row (R i - ) adjacent to said particular row (R n ) is already used; placing said at least one of a wire and a pin in a particular row (R n ) if said first marking indicates said particular row (R n ) is not already used, and then marking said particular row (R n ) as being used, otherwise exiting the step of placing to avoid a violation; if said at least one of a wire and a pin is placed in said particular row (R n ) and has a wide width, checking if said second marking indicates said lower sub-row (R n - ) is not already used, and then marking said lower sub-row (R n - ) as being used, otherwise exiting the step of placing to avoid a violation; and if said at least one of a wire and a pin is placed in said particular row (R n ) and has a wide width, checking if said third marking indicates said upper sub-row (R n + ) is not already used, and then marking said upper sub-row (R n + ) as being used, otherwise exiting the step of placing to avoid a violation.
Claim 7
Dependent Claim
384 words
A computer-implemented method for preventing variable-width wire and pin placement violations caused by overmarking in a channel router, the method comprising the steps of: specifying the width of at least one of a wire and a pin to have a particular width relative to a default width; generating a channel grid map that includes a plurality of rows (R i ), wherein each row has at least one sub-row adjacent a first fraction of a default-wire width on the lower (R i - ) and at least one sub-row adjacent a second fraction of said default-wire width on the upper (R i + ); and placing said at least one of a wire and a pin in a particular row (R n ) that exists in said plurality of rows (R i ) by: checking if a first mark indicates said particular row (R n ) is already used, checking if a second mark indicates a lower sub-row (R i - ) adjacent to said particular row (R n ) is already used, and checking if a third mark indicates a upper sub-row (R i - ) adjacent to said particular row (R n ) is already used; placing said at least one of a wire and a pin in a particular row (R n ) if said first marking indicates said particular row (R n ) is not already used, and then marking said particular row (R n ) as being used, otherwise exiting the step of placing to avoid a violation; if said at least one of a wire and a pin is placed in said particular row (R n ) and has a wide width, checking if said second marking indicates said lower sub-row (R n - ) is not already used, and then marking said lower sub-row (R n - ) as being used, otherwise exiting the step of placing to avoid a violation; and if said at least one of a wire and a pin is placed in said particular row (R n ) and has a wide width, checking if said third marking indicates said upper sub-row (R n + ) is not already used, and then marking said upper sub-row (R n + ) as being used, otherwise exiting the step of placing to avoid a violation.
Claim 8
Dependent Claim
34 words
The method of claim 5, if the step of placing was exited to avoid a violation, then further comprising the subsequent step of: selecting a different row and then repeating the step of placing.
Claim 9
Dependent Claim
34 words
The method of claim 5, further comprising the subsequent step of: compacting after completing a detailed routing phase to remove all unnecessary gaps from a channel in order to minimize a silicon area needed.
Claim 10
Dependent Claim
69 words
The method of claim 5, further comprising the preceding steps of: extracting a connections information from a netlist specification generated according to an integrated circuit design, wherein a global routing result specifies pin locations and their connections; and building said channel grid map and determining whether variable width wires are needed, if so, refining said channel grid map by adding extra rows in order to accommodate variable width wires.
Claim 11
Dependent Claim
270 words
A track assignment process, comprising the steps of: extracting connections information from a netlist specification generated according to an integrated circuit design in which a global routing result specifies pin locations and the pins to be connected; building a channel grid map; determining whether variable width wires are to be implemented, and if so, refining said grid map by additional rows and columns in order to accommodate variable width wires; representing pins as points to be connected, wherein a pin net is comprised of more than two interconnected pins and are decomposed into a set of mapped segments comprising simpler combinations of said two-pin subnets; marking existing objects on said channel grid map; building a vertical constraint graph (VCG) according to said set of mapped segments and to maintain the relative positions of said mapped segments inside a channel, wherein the vertical dimensions of any lines for each mapped segment are included to help prevent short circuits from occurring; computing a first track comprising a straight line of said channel grid map along a channel direction; and repeating a track assignment cycle until all requisite track assignments are made, wherein said VCG is processed, all feasible links are collected, said feasible links are weighted according to one or more weighting functions, an optimal set of feasible links is selected according to the results of a weighting function, said feasible links corresponding to unpreferred layers are collected, a set of chosen links is realized, and if all connections have been completed, a compaction routine is run, otherwise, said VCG is updated, and the process is repeated for a next routing track.
Claim 12
Dependent Claim
270 words
A track assignment process, comprising the steps of: extracting connections information from a netlist specification generated according to an integrated circuit design in which a global routing result specifies pin locations and the pins to be connected; building a channel grid map; determining whether variable width wires are to be implemented, and if so, refining said grid map by additional rows and columns in order to accommodate variable width wires; representing pins as points to be connected, wherein a pin net is comprised of more than two interconnected pins and are decomposed into a set of mapped segments comprising simpler combinations of said two-pin subnets; marking existing objects on said channel grid map; building a vertical constraint graph (VCG) according to said set of mapped segments and to maintain the relative positions of said mapped segments inside a channel, wherein the vertical dimensions of any lines for each mapped segment are included to help prevent short circuits from occurring; computing a first track comprising a straight line of said channel grid map along a channel direction; and repeating a track assignment cycle until all requisite track assignments are made, wherein said VCG is processed, all feasible links are collected, said feasible links are weighted according to one or more weighting functions, an optimal set of feasible links is selected according to the results of a weighting function, said feasible links corresponding to unpreferred layers are collected, a set of chosen links is realized, and if all connections have been completed, a compaction routine is run, otherwise, said VCG is updated, and the process is repeated for a next routing track.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-10 | 2002-02-09 | 2002-08-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-10 | 2006-02-09 | 2006-08-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-10 | 2010-02-09 | 2010-08-11 | $7700.00 | Window Closed / Lapsed |