US6247167B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for parallel Steiner tree routing
Assignee: Bell Semiconductor LLC
•
Filing: 1998-04-17
•
Granted: 2001-06-12
•
Expires: 2018-04-17
Abstract
Abstract The present invention provides for a method and apparatus to partition high fanout nets into smaller subnets. Said method includes the steps of identifying elementary pairs of pins in the net, each such elementary pair defining a line; eliminating lines such that a planar graph is formed; eliminating further lines such that a spanning tree is formed, said spanning tree connecting each pin in the net; identifying basic elements, each basic element forming a portion of said spanning tree; and constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements.
Inventors
- 👤 Pedja Raspopovic
- 👤 Ranko Scepanovic
- 👤 Alexander E. Andreev
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 20:33
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 95
Claim 1
Independent Claim
145 words
A method for routing connections between pins in a net, said method comprising the steps of: A. identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and specifying a line between each said elementary pair so as to form a graph; B. eliminating lines from said graph such that a planar graph is formed; C. eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; D. identifying basic elements, each basic element forming a portion of said spanning tree; E. constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements; and F. routing connections between pins in the net based on said connected cover.
Claim 2
Independent Claim
145 words
A method for routing connections between pins in a net, said method comprising the steps of: A. identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and specifying a line between each said elementary pair so as to form a graph; B. eliminating lines from said graph such that a planar graph is formed; C. eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; D. identifying basic elements, each basic element forming a portion of said spanning tree; E. constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements; and F. routing connections between pins in the net based on said connected cover.
Claim 3
Dependent Claim
70 words
The method according to claim 1 wherein step (A) comprises iteratively compressing the net to one elementary pair of pins and then iteratively expanding the net, wherein said compression is performed by reducing (x,y) coordinates for each pin during said iterations and combining pins when their (x,y) coordinates match to form combined pins, and wherein said expansion is performed by retrieving pins that were combined to form said combined pins.
Claim 4
Dependent Claim
25 words
The method according to claim 2 wherein the compression iterations alternate from compressing the net in the x-direction to compressing the net in the y-direction.
Claim 5
Dependent Claim
25 words
The method accordingly to claim 2 wherein the expansion iterations alternate from expanding the net in the x-direction to expanding the net in the y-direction.
Claim 6
Dependent Claim
29 words
The method according to claim 4 wherein at each expansion iteration each elementary and quasi-elementary pair of pins from the previous iteration is checked for elementary pairs of pins.
Claim 7
Dependent Claim
33 words
The method according to claim 5 wherein at least one expansion iteration each elementary and quasi-elementary pair of pins from the previous iteration is checked for both elementary and quasi-elementary pairs of pins.
Claim 8
Dependent Claim
20 words
The method according to claim 1 wherein the planar graph is formed by removing lines which intersect with other lines.
Claim 9
Dependent Claim
21 words
The method according to claim 7 wherein the planar graph is formed by iteratively removing the longest of two intersecting lines.
Claim 10
Dependent Claim
29 words
The method according to claim 1 wherein the lines of said planar graph form regions and said spanning tree is formed by iteratively removing the longest line between regions.
Claim 11
Dependent Claim
22 words
The method according to claim 1 wherein the connected cover is constructed as a function of the complexity of each basic element.
Claim 12
Dependent Claim
26 words
The method according to claim 10 wherein the complexity of a basic element is defined as the half-perimeter of the bounding box of the basic element.
Claim 13
Dependent Claim
21 words
The method according to claim 1 wherein the basic elements forming the connected cover are processed for routing by multiple processors.
Claim 14
Dependent Claim
15 words
A semiconductor device having pins routed in accordance with the method of claim 12 .
Claim 15
Independent Claim
155 words
An apparatus for routing connections between pins in a net, said apparatus comprising: A. means for identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and for specifying a line between each said elementary pair so as to form a graph; B. means for eliminating lines from said graph such that a planar graph is formed; C. means for eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; D. means for identifying basic elements, each basic element forming a portion of said spanning tree; E. means for constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements; and F. means for routing connections between pins in the net based on said connected cover.
Claim 16
Independent Claim
155 words
An apparatus for routing connections between pins in a net, said apparatus comprising: A. means for identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and for specifying a line between each said elementary pair so as to form a graph; B. means for eliminating lines from said graph such that a planar graph is formed; C. means for eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; D. means for identifying basic elements, each basic element forming a portion of said spanning tree; E. means for constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements; and F. means for routing connections between pins in the net based on said connected cover.
Claim 17
Dependent Claim
78 words
The apparatus according to claim 14 wherein the means for identifying elementary pairs of pins in the net iteratively compresses the net into one elementary pair of pins and then iteratively expands the net wherein said compression is performed by reducing (x,y) coordinates for each pin during said iterations and combining pins when their (x,y) coordinates match to form combined pins, and wherein said expansion is performed by retrieving pins that were combined to form said combined pins.
Claim 18
Dependent Claim
25 words
The apparatus according to claim 15 wherein the compression iterations alternate from compressing the net in the x-direction to compressing the net in the y-direction.
Claim 19
Dependent Claim
25 words
The apparatus accordingly to claim 15 wherein the expansion iterations alternate from expanding the net in the x-direction to expanding the net in the x-direction.
Claim 20
Dependent Claim
29 words
The apparatus according to claim 17 wherein at each expansion iteration each elementary and quasi-elementary pair of pins from the previous iteration is checked for elementary pairs of pins.
Claim 21
Dependent Claim
33 words
The apparatus according to claim 18 wherein at least one expansion iteration each elementary and quasi-elementary pair of pins from the previous iteration is checked for both elementary and quasi-elementary pairs of pins.
Claim 22
Dependent Claim
20 words
The apparatus according to claim 14 wherein the planar graph is formed by removing lines which intersect with other lines.
Claim 23
Dependent Claim
21 words
The apparatus according to claim 20 wherein the planar graph is formed by iteratively removing the longest of two intersecting lines.
Claim 24
Dependent Claim
29 words
The apparatus according to claim 14 wherein the lines of said planar tree form regions and said spanning tree is formed by iteratively removing the longest line between regions.
Claim 25
Dependent Claim
22 words
The apparatus according to claim 14 wherein the connected cover is constructed as a function of the complexity of each basic element.
Claim 26
Dependent Claim
27 words
The apparatus according to claim 23 wherein the complexity of a basic element is a function of the half-perimeter of the bounding box of the basic element.
Claim 27
Dependent Claim
21 words
The apparatus according to claim 14 wherein the basic elements forming the connected cover are processed for routing by multiple processors.
Claim 28
Dependent Claim
172 words
A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, comprising: A. encoded computer means for identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and for specifying a line between each said elementary pair so as to form a graph; B. encoded computer means for eliminating lines from said graph such that a planar graph is formed; C. encoded computer means for eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; D. encoded computer means for identifying basic elements, each basic element forming a portion of said spanning tree; E. encoded computer means for constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements; and F. encoded computer means for routing connections between pins in the net based on said connected cover.
Claim 29
Dependent Claim
172 words
A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, comprising: A. encoded computer means for identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and for specifying a line between each said elementary pair so as to form a graph; B. encoded computer means for eliminating lines from said graph such that a planar graph is formed; C. encoded computer means for eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; D. encoded computer means for identifying basic elements, each basic element forming a portion of said spanning tree; E. encoded computer means for constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements; and F. encoded computer means for routing connections between pins in the net based on said connected cover.
Claim 30
Dependent Claim
39 words
A storage medium according to claim 26 wherein said storage medium is selected from a group consisting of semiconductor memory device, magnetic device, optical device, magneto-optical device, floppy diskette, hard drive, CD-ROM, magnetic tape, computer memory, and memory card.
Claim 31
Independent Claim
107 words
An apparatus for routing connections between pins in a net, said apparatus comprising: A. means for iteratively compressing the net by reducing (x,y) coordinates for each pin during said iterations and combining pins when their (x,y) coordinates match to form combined pins; B. means for iteratively expanding the net by retrieving pins that were combined to form said combined pins; C. means for identifying elementary pairs at expansion iterations, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair; and D. means for routing connections between pins in the net based on said elementary pairs.
Claim 32
Independent Claim
107 words
An apparatus for routing connections between pins in a net, said apparatus comprising: A. means for iteratively compressing the net by reducing (x,y) coordinates for each pin during said iterations and combining pins when their (x,y) coordinates match to form combined pins; B. means for iteratively expanding the net by retrieving pins that were combined to form said combined pins; C. means for identifying elementary pairs at expansion iterations, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair; and D. means for routing connections between pins in the net based on said elementary pairs.
Claim 33
Dependent Claim
21 words
The apparatus of claim 28 further comprising: E. means for identifying quasi-elementary pairs of pins at at least one expansion iteration.
Claim 34
Dependent Claim
23 words
The apparatus of claim 28 wherein said means for iteratively compressing the net alternates between compressing the net in the x- and y-directions.
Claim 35
Dependent Claim
69 words
The apparatus of claim 30 wherein the pins of the net are located on a grid based upon relative x- and y- coordinates and after each x-direction compression iteration the relative x-coordinate of each pin is the absolute value of half the pin's previous relative x-coordinate and after each y-direction compression iteration the relative y-coordinate of each pin is the absolute value of half the pin's previous relative y-coordinate.
Claim 36
Dependent Claim
23 words
The apparatus of claim 28 wherein said means for iteratively expanding the net alternates between expanding the net in the x- and y-directions.
Claim 37
Dependent Claim
35 words
The apparatus of claim 28 wherein said means for iteratively expanding the net executes the same number of expansion iterations as the number of compression iterations executed by the means for iteratively compressing the net.
Claim 38
Independent Claim
102 words
A method for routing connections between pins in a net, said method comprising the following steps: A. iteratively compressing the net by reducing (x,y) coordinates for each pin during said iterations and combining pins when their (x,y) coordinates match to form combined pins; B. iteratively expanding the net by retrieving pins that were combined to form said combined pins; C. identifying elementary pairs at expansion iterations, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair; and D. routing connections between pins in the net based on said elementary pairs.
Claim 39
Independent Claim
102 words
A method for routing connections between pins in a net, said method comprising the following steps: A. iteratively compressing the net by reducing (x,y) coordinates for each pin during said iterations and combining pins when their (x,y) coordinates match to form combined pins; B. iteratively expanding the net by retrieving pins that were combined to form said combined pins; C. identifying elementary pairs at expansion iterations, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair; and D. routing connections between pins in the net based on said elementary pairs.
Claim 40
Dependent Claim
22 words
The method of claim 34 further comprising the following step: E. identifying quasi-elementary pairs of pins at at least one expansion iteration.
Claim 41
Dependent Claim
23 words
The method of claim 34 wherein said step of iteratively compressing the net alternates between compressing the net in the x- and y-directions.
Claim 42
Dependent Claim
69 words
The method of claim 36 wherein the pins of the net are located on a grid based upon relative x- and y- coordinates and after each x-direction compression iteration the relative x-coordinate of each pin is the absolute value of half the pin's previous relative x-coordinate and after each y-direction compression iteration the relative y-coordinate of each pin is the absolute value of half the pin's previous relative y-coordinate.
Claim 43
Dependent Claim
23 words
The method of claim 34 wherein said step of iteratively expanding the net alternates between expanding the net in the x- and y-directions.
Claim 44
Dependent Claim
33 words
The method of claim 34 wherein said step of iteratively expanding the net comprises executing the same number of expansion iterations as the number of compression iterations executed in the iteratively compressing step.
Claim 45
Dependent Claim
29 words
The method according to claim 34 wherein at each expansion iteration each elementary and quasi-elementary pair of pins from the previous iteration is checked for elementary pairs of pins.
Claim 46
Dependent Claim
33 words
The method according to claim 40 wherein at least one expansion iteration each elementary and quasi-elementary pair of pins from the previous iteration is checked for both elementary and quasi-elementary pairs of pins.
Claim 47
Independent Claim
113 words
A method for routing connections between pins in a net, said method comprising the steps of: A. identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and specifying a line between each said elementary pair so as to form a graph; B. eliminating lines from said graph such that a planar graph is formed; C. eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; and D. routing connections between pins in the net based on said spanning tree.
Claim 48
Independent Claim
113 words
A method for routing connections between pins in a net, said method comprising the steps of: A. identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and specifying a line between each said elementary pair so as to form a graph; B. eliminating lines from said graph such that a planar graph is formed; C. eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; and D. routing connections between pins in the net based on said spanning tree.
Claim 49
Dependent Claim
20 words
The method according to claim 42 wherein the planar graph is formed by removing lines which intersect with other lines.
Claim 50
Dependent Claim
21 words
The method according to claim 43 wherein the planar graph is formed by iteratively removing the longest of two intersecting lines.
Claim 51
Dependent Claim
29 words
The method according to claim 42 wherein the lines of said planar tree form regions and said spanning tree is formed by iteratively removing the longest line between regions.
Claim 52
Independent Claim
119 words
An apparatus for routing connections between pins in a net, said apparatus comprising: A. means for identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and for specifying a line between each said elementary pair so as to form a graph; B. means for eliminating lines from said graph such that a planar graph is formed; C. means for eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; and D. means for routing connections between pins in the net based on said spanning tree.
Claim 53
Independent Claim
119 words
An apparatus for routing connections between pins in a net, said apparatus comprising: A. means for identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and for specifying a line between each said elementary pair so as to form a graph; B. means for eliminating lines from said graph such that a planar graph is formed; C. means for eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; and D. means for routing connections between pins in the net based on said spanning tree.
Claim 54
Dependent Claim
31 words
The apparatus according to claim 46 wherein said means for eliminating lines such that a planar graph is formed forms the planar graph by removing lines which intersect with other lines.
Claim 55
Dependent Claim
21 words
The apparatus according to claim 47 wherein the planar graph is formed by iteratively removing the longest of two intersecting lines.
Claim 56
Dependent Claim
29 words
The apparatus according to claim 48 wherein the lines of said planar tree form regions and said spanning tree is formed by iteratively removing the longest line between regions.
Claim 57
Independent Claim
128 words
A method for routing connections between pins in a net, said method comprising the steps of: A. identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and specifying a line between each said elementary pair so as to form a graph; B. eliminating lines from said graph such that a planar graph is formed; C. eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; D. dividing said spanning tree into subtrees collectively forming a connected cover for the net; and E. routing connections between pins in the net based on said connected cover.
Claim 58
Independent Claim
128 words
A method for routing connections between pins in a net, said method comprising the steps of: A. identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and specifying a line between each said elementary pair so as to form a graph; B. eliminating lines from said graph such that a planar graph is formed; C. eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; D. dividing said spanning tree into subtrees collectively forming a connected cover for the net; and E. routing connections between pins in the net based on said connected cover.
Claim 59
Dependent Claim
70 words
The method according to claim 50 wherein step (A) comprises iteratively compressing the net to one elementary pair of pins and then iteratively expanding the net, wherein said compression is performed by reducing (x,y) coordinates for each pin during said iterations and combining pins when their (x,y) coordinates match to form combined pins, and wherein said expansion is performed by retrieving pins that were combined to form said combined pins.
Claim 60
Dependent Claim
25 words
The method according to claim 51 wherein the compression iterations alternate from compressing the net in the x-direction to compressing the net in the y-direction.
Claim 61
Dependent Claim
25 words
The method accordingly to claim 51 wherein the expansion iterations alternate from expanding the net in the x-direction to expanding the net in the y-direction.
Claim 62
Dependent Claim
29 words
The method according to claim 53 wherein at each expansion iteration each elementary and quasi-elementary pair of pins from the previous iteration is checked for elementary pairs of pins.
Claim 63
Dependent Claim
33 words
The method according to claim 54 wherein at least one expansion iteration each elementary and quasi-elementary pair of pins from the previous iteration is checked for both elementary and quasi-elementary pairs of pins.
Claim 64
Dependent Claim
20 words
The method according to claim 50 wherein the planar graph is formed by removing lines which intersect with other lines.
Claim 65
Dependent Claim
21 words
The method according to claim 56 wherein the planar graph is formed by iteratively removing the longest of two intersecting lines.
Claim 66
Dependent Claim
29 words
The method according to claim 57 wherein the lines of said planar tree form regions and said spanning tree is formed by iteratively removing the longest line between regions.
Claim 67
Dependent Claim
15 words
A semiconductor device having pins routed in accordance with the method of claim 50 .
Claim 68
Independent Claim
137 words
An apparatus for routing connections between pins in a net, said apparatus comprising: A. means for identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and for specifying a line between each said elementary pair so as to form a graph; B. means for eliminating lines from said graph such that a planar graph is formed; C. means for eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; D. means for dividing said spanning tree into subtrees which collectively form a connected cover for said net; and E. means for routing connections between pins in the net based on said connected cover.
Claim 69
Independent Claim
137 words
An apparatus for routing connections between pins in a net, said apparatus comprising: A. means for identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and for specifying a line between each said elementary pair so as to form a graph; B. means for eliminating lines from said graph such that a planar graph is formed; C. means for eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; D. means for dividing said spanning tree into subtrees which collectively form a connected cover for said net; and E. means for routing connections between pins in the net based on said connected cover.
Claim 70
Dependent Claim
78 words
The apparatus according to claim 60 wherein the means for identifying elementary pairs of pins in the net iteratively compresses the net into one elementary pair of pins and then iteratively expands the net, wherein said compression is performed by reducing (x,y) coordinates for each pin during said iterations and combining pins when their (x,y) coordinates match to form combined pins, and wherein said expansion is performed by retrieving pins that were combined to form said combined pins.
Claim 71
Dependent Claim
132 words
A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, comprising: A. encoded computer means for identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and for specifying a line between each said elementary pair so as to form a graph; B. encoded computer means for eliminating lines from said graph such that a planar graph is formed; C. encoded computer means for eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; and D. encoded computer means for routing connections between pins in the net based on said spanning tree.
Claim 72
Dependent Claim
132 words
A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, comprising: A. encoded computer means for identifying elementary pairs of pins in the net, an elementary pair being a pair for which no other pin is within or on a bounding box defined by said pair, and for specifying a line between each said elementary pair so as to form a graph; B. encoded computer means for eliminating lines from said graph such that a planar graph is formed; C. encoded computer means for eliminating further lines from said planar graph such that a spanning tree is formed, said spanning tree connecting each pin in the net; and D. encoded computer means for routing connections between pins in the net based on said spanning tree.
Claim 73
Dependent Claim
39 words
A storage medium according to claim 62 wherein said storage medium is selected from a group consisting of semiconductor memory device, magnetic device, optical device, magneto-optical device, floppy diskette, hard drive, CD-ROM, magnetic tape, computer memory, and memory card.
Claim 74
Independent Claim
112 words
A method for routing connections between pins in a net, said method comprising the steps of: A. supplying a spanning tree, said spanning tree connecting each pin in the net; B. identifying basic elements in said spanning tree, with each basic element comprising a subtree that forms a portion of said spanning tree, with at least one basic element formed for each pin in the net, and with plural basic elements formed for at least some pins in the net; C. constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements; and D. routing connections between pins in the net based on said connected cover.
Claim 75
Independent Claim
112 words
A method for routing connections between pins in a net, said method comprising the steps of: A. supplying a spanning tree, said spanning tree connecting each pin in the net; B. identifying basic elements in said spanning tree, with each basic element comprising a subtree that forms a portion of said spanning tree, with at least one basic element formed for each pin in the net, and with plural basic elements formed for at least some pins in the net; C. constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements; and D. routing connections between pins in the net based on said connected cover.
Claim 76
Dependent Claim
26 words
The method according to claim 64 wherein the connected cover is constructed as a function of the complexity of each basic element identified in step (B).
Claim 77
Dependent Claim
27 words
The method according to claim 65 wherein the complexity of a basic element is a function of the half-perimeter of the bounding box of the basic element.
Claim 78
Dependent Claim
24 words
The method according to claim 64 further comprising the step of processing the basic elements comprising the connected cover for routing with multiple processors.
Claim 79
Dependent Claim
15 words
A semiconductor device having pins routed in accordance with the method of claim 64 .
Claim 80
Dependent Claim
36 words
A method according to claim 64 , wherein groups of basic elements are formed for each pin in the net, with one group of basic elements being formed for each edge connecting to said each pin.
Claim 81
Dependent Claim
40 words
A method according to claim 69 , wherein each basic element in any group includes the edge for which said group was formed and does not include any other edge connecting to the pin for which said group was formed.
Claim 82
Dependent Claim
78 words
A method according to claim 70 , wherein the basic elements in each group are formed using the pin for which said each group was formed as a root, wherein a maximum radius has been specified, and wherein the basic elements in said each group include subtrees of said spanning tree in which a number of edges from the pin for which said each group was formed to each other vertex is no more than the maximum radius.
Claim 83
Independent Claim
117 words
An apparatus for routing connections between pins in a net, said apparatus comprising: A. means for providing a spanning tree, said spanning tree connecting each pin in the net; B. means for identifying basic elements in said spanning tree, with each basic element comprising a subtree that forms a portion of said spanning tree, with at least one basic element formed for each pin in the net, and with plural basic elements formed for at least some pins in the net; C. means for constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements; and D. means for routing connections between pins in the net based on said connected cover.
Claim 84
Independent Claim
117 words
An apparatus for routing connections between pins in a net, said apparatus comprising: A. means for providing a spanning tree, said spanning tree connecting each pin in the net; B. means for identifying basic elements in said spanning tree, with each basic element comprising a subtree that forms a portion of said spanning tree, with at least one basic element formed for each pin in the net, and with plural basic elements formed for at least some pins in the net; C. means for constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements; and D. means for routing connections between pins in the net based on said connected cover.
Claim 85
Dependent Claim
39 words
The apparatus according to claim 72 wherein the means for constructing the connected cover for such net constructs the connected cover as a function of the complexity of each basic element identified by the means for identifying basic elements.
Claim 86
Dependent Claim
27 words
The apparatus according to claim 73 wherein the complexity of a basic element is a function of the half-perimeter of the bounding box of the basic element.
Claim 87
Dependent Claim
21 words
The apparatus according to claim 72 wherein the basic elements forming the connected cover are processed for routing by multiple processors.
Claim 88
Dependent Claim
36 words
An apparatus according to claim 72 , wherein groups of basic elements are formed for each pin in the net, with one group of basic elements being formed for each edge connecting to said each pin.
Claim 89
Dependent Claim
40 words
An apparatus according to claim 76 , wherein each basic element in any group includes the edge for which said group was formed and does not include any other edge connecting to the pin for which said group was formed.
Claim 90
Dependent Claim
78 words
An apparatus according to claim 77 , wherein the basic elements in each group are formed using the pin for which said each group was formed as a root, wherein a maximum radius has been specified, and wherein the basic elements in said each group include subtrees of said spanning tree in which a number of edges from the pin for which said each group was formed to each other vertex is no more than the maximum radius.
Claim 91
Dependent Claim
129 words
A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, comprising: A. encoded computer means providing a spanning tree, said spanning tree connecting each pin in a net; B. encoded computer means for identifying basic elements in said spanning tree, with each basic element comprising a subtree that forms a portion of said spanning tree, with at least one basic element formed for each pin in the net, and with plural basic elements formed for at least some pins in the net; C. encoded computer means for constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements; and D. encoded computer means for routing connections between pins in the net based on said connected cover.
Claim 92
Dependent Claim
129 words
A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, comprising: A. encoded computer means providing a spanning tree, said spanning tree connecting each pin in a net; B. encoded computer means for identifying basic elements in said spanning tree, with each basic element comprising a subtree that forms a portion of said spanning tree, with at least one basic element formed for each pin in the net, and with plural basic elements formed for at least some pins in the net; C. encoded computer means for constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements; and D. encoded computer means for routing connections between pins in the net based on said connected cover.
Claim 93
Dependent Claim
38 words
A machine-readable storage medium according to claim 79 , wherein groups of basic elements are formed for each pin in the net, with one group of basic elements being formed for each edge connecting to said each pin.
Claim 94
Dependent Claim
42 words
A machine-readable storage medium according to claim 80 , wherein each basic element in any group includes the edge for which said group was formed and does not include any other edge connecting to the pin for which said group was formed.
Claim 95
Dependent Claim
80 words
A machine-readable storage medium according to claim 81 , wherein the basic elements in each group are formed using the pin for which said each group was formed as a root, wherein a maximum radius has been specified, and wherein the basic elements in said each group include subtrees of said spanning tree in which a number of edges from the pin for which said each group was formed to each other vertex is no more than the maximum radius.
References Cited (Backward Citations)
US5568322A
Cited
US5491641A
Cited
US5615128A
Cited
US5742510A
Cited
US5495419A
Cited
US5636125A
Cited
US5745363A
Cited
US5682322A
Cited
US5568636A
Cited
US5638293A
Cited
US5682321A
Cited
US5578840A
Cited
US5661663A
Cited
US5712793A
Cited
US5818729A
Cited
US5808899A
Cited
US5930500A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-06-11 | 2004-12-11 | 2005-06-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-06-11 | 2008-12-11 | 2009-06-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-06-11 | 2012-12-11 | 2013-06-12 | $7700.00 | Window Closed / Lapsed |