US5980093A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Integrated circuit layout routing using multiprocessing
Assignee: Bell Semiconductor LLC
•
Filing: 1996-12-04
•
Granted: 1999-11-09
•
Expires: 2016-12-04
Abstract
Abstract A multithreaded wavefront routing system for simultaneously planning routes for wiring a semiconductor chip surface. The surface has a plurality of grids located thereon, and routes are planned according to a predetermined netlist. The system steps across the surface from a first location to a second location in a wave-type pattern. The system sequentially steps through the grid arrangement on the chip surface and plans routing one grid at a time using a plurality of threaded processors. The system recognizes pins as it steps through grids and determines a plan for the current grid by evaluating current wire position, target pin location, and any currently planned routes, designating reserved locations wherein the route may be planned subsequent to the current grid, and establishing a wire direction for each wire traversing the current grid. The system plans wiring through grids using multiple threaded processors employing shared memory and a semi-hard coded rule based expert system applying heuristics by planning various routes based on current and potential wire locations. The system propagates wiring and performs memory bookkeeping functions. The system also has the capability to plan an additional route from one target pin toward a first pin. Meetings between routes are designated and resolved. Reservations may be established when a processor plans a route. Mutex locks may be utilized to avoid multiprocessor conflicts.
Inventors
- 👤 Edwin Jones
- 👤 James S. Koford
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 16:14
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 55
Claim 1
Independent Claim
127 words
A multithreaded wavefront routing system for creating a plan of a route for wiring for a semiconductor chip surface having a grid arrangement located thereon based on a netlist, comprising: a sequencing processor for sequentially stepping through the grid arrangement from one chip surface location to another chip surface location in a wavefront, thereby establishing a current grid on the chip surface; and a plurality of processors, wherein each processor comprises: a pin identifier for recognizing pins located on the surface of the chip; a planner for establishing a proposed route proceeding from a first pin on the chip surface to a subsequent pin on the chip surface; and a current grid wire direction planner for individually planning a direction for a wire traversing the current grid.
Claim 2
Dependent Claim
127 words
A multithreaded wavefront routing system for creating a plan of a route for wiring for a semiconductor chip surface having a grid arrangement located thereon based on a netlist, comprising: a sequencing processor for sequentially stepping through the grid arrangement from one chip surface location to another chip surface location in a wavefront, thereby establishing a current grid on the chip surface; and a plurality of processors, wherein each processor comprises: a pin identifier for recognizing pins located on the surface of the chip; a planner for establishing a proposed route proceeding from a first pin on the chip surface to a subsequent pin on the chip surface; and a current grid wire direction planner for individually planning a direction for a wire traversing the current grid.
Claim 3
Dependent Claim
21 words
The multithreaded wavefront routing system of claim 1, further comprising a marker for marking connections between routes planned between recognized pins.
Claim 4
Dependent Claim
22 words
The multithreaded wavefront routing system of claim 1, further comprising a propagator for propagating from the current grid to a subsequent grid.
Claim 5
Dependent Claim
17 words
The multithreaded wavefront routing system of claim 1, further comprising a bookkeeper for performing memory bookkeeping functions.
Claim 6
Dependent Claim
40 words
The multithreaded wavefront routing system of claim 1, wherein said planner comprises a semi-hard coded rule based expert system which applies a group of heuristics and plans various routes according to current location of each wire and potential wire locations.
Claim 7
Dependent Claim
30 words
The multithreaded wavefront routing system of claim 1, wherein said planner further comprises a reverse direction planner for planning an additional route from one target pin toward the first pin.
Claim 8
Dependent Claim
27 words
The multithreaded wavefront routing system of claim 6, wherein the route is planned by a first processor and the additional route is planned by a second processor.
Claim 9
Dependent Claim
41 words
The multithreaded wavefront routing system of claim 7, wherein completion of said planned route and said additional planned route result in said first processor and said second processor separately designating meetings, and said meetings are resolved by a meeting resolution processor.
Claim 10
Dependent Claim
20 words
The multithreaded wavefront routing system of claim 8, wherein the meeting resolution processor is either the first or second processor.
Claim 11
Dependent Claim
26 words
The multithreaded wavefront routing system of claim 1, further comprising a locking mechanism for establishing a lock to avoid concurrent processing by the plurality of processors.
Claim 12
Dependent Claim
15 words
The multithreaded wavefront routing system of claim 10, wherein said locking mechanism employs mutex locks.
Claim 13
Dependent Claim
56 words
The multithreaded wavefront routing system of claim 1, wherein said planner comprises: an evaluator for evaluating current wire position; a target pin locator for assessing a target pin location; a route appraiser for appraising currently planned routes; and a location designator for designating reserved locations wherein the route may be planned subsequent to said current grid.
Claim 14
Dependent Claim
21 words
The multithreaded wavefront routing system of claim 12, wherein said location designator reserves a line of grids on the chip surface.
Claim 15
Dependent Claim
18 words
The multithreaded wavefront routing system of claim 12, wherein said location designator lifts reservations on any unreserved locations.
Claim 16
Independent Claim
101 words
A method for creating a routing plan for wiring a semiconductor chip surface based on a given netlist, comprising the steps of: establishing a first location, a second location, and a grid system on said chip; and sequentially traversing from said first location to said second location by sequentially stepping through grids on the surface to establish a current grid using a plurality of processors, comprising the substeps of: recognizing pin positions on said surface; and simultaneously planning routes from a plurality of first pins through the current grid toward at least one subsequent target pin using said plurality of processors.
Claim 17
Independent Claim
101 words
A method for creating a routing plan for wiring a semiconductor chip surface based on a given netlist, comprising the steps of: establishing a first location, a second location, and a grid system on said chip; and sequentially traversing from said first location to said second location by sequentially stepping through grids on the surface to establish a current grid using a plurality of processors, comprising the substeps of: recognizing pin positions on said surface; and simultaneously planning routes from a plurality of first pins through the current grid toward at least one subsequent target pin using said plurality of processors.
Claim 18
Dependent Claim
21 words
The method of claim 15, further comprising the substep of propagating to a subsequent grid after said simultaneous route planning substep.
Claim 19
Dependent Claim
25 words
The method of claim 16, wherein establishing the grid system comprises establishing a plurality of grids on the chip surface and designating a current grid.
Claim 20
Dependent Claim
22 words
The method of claim 16, further comprising the step of establishing a lock to avoid concurrent processing by the plurality of processors.
Claim 21
Dependent Claim
14 words
The method of claim 18, wherein said lock establishing step comprises using mutex locks.
Claim 22
Dependent Claim
47 words
The method of claim 16, further comprising an additional route planning substep of planning a route from one target pin toward the first pin, wherein said additional route planning substep occurs simultaneously with planning the route from the first pin toward at least one subsequent target pin.
Claim 23
Dependent Claim
24 words
The method of claim 20, wherein said route is planned by a first processor and said additional route is planned by a second processor.
Claim 24
Dependent Claim
39 words
The method of claim 21, wherein completion of said planned route and said additional planned route result in said first processor and said second processor separately designating meetings, and said meetings are resolved subsequent to designation by said processors.
Claim 25
Dependent Claim
63 words
The method of claim 16, wherein said route planning step comprises: determining a plan for the current grid using each processor according to the substeps of: evaluating current wire position; assessing target location; appraising currently planned routes; designating reserved locations wherein the route may be planned subsequent to said current grid; and establishing a wire direction for each wire traversing the current grid.
Claim 26
Dependent Claim
18 words
The method of claim 23, wherein said designating substep further comprises removing reservations on any determined unreserved locations.
Claim 27
Dependent Claim
41 words
The method of claim 23, wherein said appraising, designating, and establishing substeps utilize a semi-hard coded rule based expert system which applies a group of heuristics and plans various routes according to where each wire is located and potential wire locations.
Claim 28
Dependent Claim
12 words
The method of claim 23, wherein said designating substep comprises reserving locations.
Claim 29
Dependent Claim
14 words
The method of claim 26, wherein location reservation comprises reserving a line of grids.
Claim 30
Dependent Claim
18 words
The method of claim 16, further comprising the step of performing memory bookkeeping functions after said propagating step.
Claim 31
Independent Claim
102 words
A method of simultaneously planning routes for wiring a semiconductor chip surface having a plurality of grids located thereon based on a given netlist from a plurality of first pins through a current grid toward at least one subsequent target pin using a plurality of processors, comprising the steps of: determining a plan for the current grid using each processor according to the substeps of: evaluating current wire position; assessing target location; appraising currently planned routes; designating reserved locations wherein the route may be planned subsequent to said current grid; and establishing a wire direction for each wire traversing the current grid.
Claim 32
Independent Claim
102 words
A method of simultaneously planning routes for wiring a semiconductor chip surface having a plurality of grids located thereon based on a given netlist from a plurality of first pins through a current grid toward at least one subsequent target pin using a plurality of processors, comprising the steps of: determining a plan for the current grid using each processor according to the substeps of: evaluating current wire position; assessing target location; appraising currently planned routes; designating reserved locations wherein the route may be planned subsequent to said current grid; and establishing a wire direction for each wire traversing the current grid.
Claim 33
Dependent Claim
44 words
The method of claim 29, further comprising the substep of planning an additional route from one target pin toward the first pin, wherein said additional route planning occurs simultaneously with planning the route from the first pin toward at least one subsequent target pin.
Claim 34
Dependent Claim
24 words
The method of claim 30, wherein said route is planned by a first processor and said additional route is planned by a second processor.
Claim 35
Dependent Claim
39 words
The method of claim 31, wherein completion of said planned route and said additional planned route result in said first processor and said second processor separately designating meetings, and said meetings are resolved subsequent to designation by said processors.
Claim 36
Dependent Claim
12 words
The method of claim 29, wherein said designating substep comprises reserving locations.
Claim 37
Dependent Claim
17 words
The method of claim 33, wherein said designating substep further comprises removing reservations on determined unreserved locations.
Claim 38
Dependent Claim
14 words
The method of claim 33, wherein location reservation comprises reserving a line of grids.
Claim 39
Dependent Claim
22 words
The method of claim 29, further comprising the step of establishing a lock to avoid concurrent processing by the plurality of processors.
Claim 40
Dependent Claim
14 words
The method of claim 36, wherein said lock establishing step comprises using mutex locks.
Claim 41
Dependent Claim
41 words
The method of claim 29, wherein said appraising, designating, and establishing substeps utilize a semi-hard coded rule based expert system which applies a group of heuristics and plans various routes according to where each wire is located and potential wire locations.
Claim 42
Independent Claim
92 words
A method of planning multiple routes along a surface of a semiconductor chip surface divided into a plurality of grids using multiple processing threads according to a predetermined netlist, comprising the following steps: sequentially stepping through the grid arrangement from one chip surface location to another chip surface location in a wavefront, thereby establishing a current grid on the chip surface; recognizing pins along the wavefront; using each processing thread to separately plan routes between pins according to the netlist; and individually planning a direction for each wire traversing the current grid.
Claim 43
Independent Claim
92 words
A method of planning multiple routes along a surface of a semiconductor chip surface divided into a plurality of grids using multiple processing threads according to a predetermined netlist, comprising the following steps: sequentially stepping through the grid arrangement from one chip surface location to another chip surface location in a wavefront, thereby establishing a current grid on the chip surface; recognizing pins along the wavefront; using each processing thread to separately plan routes between pins according to the netlist; and individually planning a direction for each wire traversing the current grid.
Claim 44
Dependent Claim
21 words
The method of claim 39, further comprising propagating from the current grid to a subsequent grid after said individual planning step.
Claim 45
Dependent Claim
18 words
The method of claim 40, further comprising the step of performing memory bookkeeping functions after said propagating step.
Claim 46
Dependent Claim
38 words
The method of claim 40, wherein said using step comprises: evaluating current wire position; assessing a target pin location; appraising currently planned routes; and designating reserved locations wherein the route may be planned subsequent to said current grid.
Claim 47
Dependent Claim
12 words
The method of claim 42, wherein said designating substep comprises reserving locations.
Claim 48
Dependent Claim
17 words
The method of claim 43, wherein said designating substep further comprises lifting reservations on any unreserved locations.
Claim 49
Dependent Claim
41 words
The method of claim 42, wherein said appraising, designating, and establishing substeps utilize a semi-hard coded rule based expert system which applies a group of heuristics and plans various routes according to where each wire is located and potential wire locations.
Claim 50
Dependent Claim
22 words
The method of claim 39, further comprising the step of establishing a lock to avoid concurrent processing by the multiple processing threads.
Claim 51
Dependent Claim
12 words
The method of claim 46, wherein locations are locked using mutex locks.
Claim 52
Dependent Claim
44 words
The method of claim 39, further comprising the substep of planning an additional route from one target pin toward the first pin, wherein said additional route planning occurs simultaneously with planning the route from the first pin toward at least one subsequent target pin.
Claim 53
Dependent Claim
24 words
The method of claim 48, wherein said route is planned by a first processor and said additional route is planned by a second processor.
Claim 54
Dependent Claim
14 words
The method of claim 49, wherein location reservation comprises reserving a line of grids.
Claim 55
Dependent Claim
39 words
The method of claim 49, wherein completion of said planned route and said additional planned route result in said first processor and said second processor separately designating meetings, and said meetings are resolved subsequent to designation by said processors.
References Cited (Backward Citations)
US4306286A
Cited
US4484292A
Cited
US4495559A
Cited
US4656580A
Cited
US4612618A
Cited
US4621339A
Cited
US4615011A
Cited
US4613941A
Cited
US4850027A
Cited
US4777606A
Cited
US5157778A
Cited
US5222029A
Cited
US4908772A
Cited
US4918614A
Cited
US4815003A
Cited
US4872125A
Cited
US5051895A
Cited
US5255345A
Cited
US5159682A
Cited
US5267176A
Cited
US5140526A
Cited
US5144563A
Cited
US5140530A
Cited
US5200908A
Cited
US5251147A
Cited
US5297283A
Cited
US5198987A
Cited
US5249259A
Cited
US5222031A
Cited
US5136686A
Cited
US5361214A
Cited
US5208759A
Cited
US5202840A
Cited
US5245550A
Cited
US5224056A
Cited
US5742510A
Cited
US5636129A
Cited
US5587923A
Cited
US5631842A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-08 | 2003-05-10 | 2003-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-08 | 2007-05-10 | 2007-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-08 | 2011-05-10 | 2011-11-09 | $7700.00 | Window Closed / Lapsed |