Patent US6182271B1 successfully refreshed from Google Patents.
US6182271B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cell placement method and apparatus for integrated circuit and storage medium having cell placement program for integrated circuit stored thereon
Assignee: Socionext Inc
•
Filing: 1997-10-17
•
Granted: 2001-01-30
•
Expires: 2017-10-17
Abstract
Abstract The invention provides a cell placement method and apparatus wherein an area for cell's placement is assured to place cells as many as possible to be placed efficiently on a single chip and a storage medium on which a cell placement program which allows such placement is stored. In the cell placement method and apparatus, in order to design an integrated circuit having a plurality of routing layers, when to place cells in a situation wherein a wire is already routed prior to the placement of the cells is present, placement of each of the cells at a position at which the cell overlaps with the already routed wire is permitted unless a wiring pattern in the cell and the already routed wire overlap with each other in a same routing layer. The invention is applied, in designing an integrated circuit (LSI, VLSI, ASIC or the like) having a plurality of routing layers, for example, a gate array to placement of cells on a chip in a state wherein an already routed wire such as a bulk power supply wire or a clock signal wire routed prior to the placement of the cells is present.
Inventors
- 👤 Noriko Yahagi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 14:14
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 46
Claim 1
Independent Claim
152 words
A method for placing a plurality of cells, each containing a particular pattern of first wiring, in a plurality of routing layers of a substrate, in which second wiring is previously routed, in designing an integrated circuit, said method comprising: (a) selecting at least one cell among the plural cells and a local substrate area corresponding to the selected one cell for the prospective placement of the selected one cell; (b) judging whether the second wiring of the plural routing layers overlaps the first wiring of the selected one cell in at least one of the plural routing layers inside the selected local substrate area; and (c) placing the selected one cell in the selected local substrate area if the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area.
Claim 2
Independent Claim
152 words
A method for placing a plurality of cells, each containing a particular pattern of first wiring, in a plurality of routing layers of a substrate, in which second wiring is previously routed, in designing an integrated circuit, said method comprising: (a) selecting at least one cell among the plural cells and a local substrate area corresponding to the selected one cell for the prospective placement of the selected one cell; (b) judging whether the second wiring of the plural routing layers overlaps the first wiring of the selected one cell in at least one of the plural routing layers inside the selected local substrate area; and (c) placing the selected one cell in the selected local substrate area if the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area.
Claim 3
Dependent Claim
43 words
A method as claimed in claim 1 , wherein each of the plural routing layers is divided into a plurality of site units each corresponding to a basic cell, and said judging in said (b) is carried out for each said site unit.
Claim 4
Dependent Claim
163 words
A method as claimed in claim 2 , wherein said judging in said (b) includes: if the lowest routing layer that is crossed by the second wiring of the plural routing layers is not lowest among the plural routing layers, (b1) determining, for each said site unit, the highest layer that is crossed by the first wiring of the selected one cell as a representative routing layer; (b2) determining the lowest routing layer crossed by the second wiring of the plural routing layers as a reference routing layer; (b3) comparing, for each said site unit, the representative routing layer with the reference routing layer; and (b4) judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if the representative routing layer is lower than the reference routing layer at every site unit in the selected local substrate area.
Claim 5
Dependent Claim
162 words
A method as claimed in claim 2 , wherein said judging in said (b) includes: if the highest routing layer that is crossed by the second wiring of the plural routing layers is not highest among the plural routing layers, (b1) determining, for each said site unit, the lowest layer that is crossed by the first wiring of the selected one cell as a representative routing layer; (b2) determining the highest layer crossed by the second wiring of the plural routing layers as a reference routing layer; (b3) comparing, for each said site unit, the representative routing layer with the reference routing layer; and (b4) judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if the representative routing layer is higher than the reference routing layer at every site unit in the selected local substrate area.
Claim 6
Dependent Claim
182 words
A method as claimed in claim 2 , wherein said judging in said (b) includes: if the number of the plural routing layers is n and the second wiring is routed only in the n-th layer which is highest among the plural routing layers, where n is a natural number, (b1) determining, for each said site unit, the highest layer that is crossed by the first wiring of the selected one cell as the x-th layer from the bottom; (b2) allocating to each sated site unit n if the second wiring crosses the last-named site unit and n+1 if the second wiring does not cross the same site unit; (b3) comparing x with y for each said site unit, where y represents n or n+1 allocated in said step (b2); and (b4) judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if x is smaller than y at every site unit in the selected local substrate.
Claim 7
Dependent Claim
182 words
A method as claimed in claim 2 , wherein said judging in said (b) includes: if the number of the plural, routing layers is n and the second wiring is routed only in the n-th layer which is lowest among the plural routing layers, where n is a natural number, (b1) determining, for each said site unit, the lowest layer that is crossed by the first wiring of the selected one cell as the x-th layer from the top; (b2) allocating to each said site unit n if the second wiring crosses the last-named site unit and n+1 if the second wiring does not cross the same site unit; (b3) comparing x with y for each said site unit, where y represents n or n+1 allocated in said step (b2); and (b4) judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if x is smaller than y at every site unit in the selected local substrate.
Claim 8
Dependent Claim
139 words
A method as claimed in claim 1 , further comprising: (d) selecting another local substrate area in which the selected cell is to be placed; (e) computing, for each of the first local substrate area selected in said (a) and the second local substrate area selected in said (d), a cost representing a probable congestion of routing based on both the second wiring in the last-named local substrate area and a wiring which connects the selected one cell with another cell among the plural cells; (f) moving the selected one cell to the second local substrate area according to a predetermined probability function on the basis of both the cost for the second local substrate area and the cost of the first local substrate area; and (g) repeating said (d) through (f) to thereby reduce the congestion of routing.
Claim 9
Independent Claim
206 words
An apparatus for placing a plurality of cells, each containing a particular pattern of first wiring, in a plurality of routing layers of a substrate, in which second wiring is previously routed, in designing an integrated circuit, said apparatus comprising: (a) a first-wiring storage section for storing the pattern of wiring contained in each of the plural cells; (b) a second-wiring storage section for storing the pattern of wiring routed in the plural routing layers; (c) a search section for selecting at least one cell among the plural cell, and for selecting at least one local substrate area corresponding to the selected one cell for the prospective placement of the selected one cell; and (d) a placement section for judging, for the selected local substrate area, whether the second wiring of the plural routing layers overlaps the first wiring of the selected one cell in at least one of the plural routing layers inside the selected local substrate area, and for placing the selected one cell in the selected local substrate area if the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area.
Claim 10
Independent Claim
206 words
An apparatus for placing a plurality of cells, each containing a particular pattern of first wiring, in a plurality of routing layers of a substrate, in which second wiring is previously routed, in designing an integrated circuit, said apparatus comprising: (a) a first-wiring storage section for storing the pattern of wiring contained in each of the plural cells; (b) a second-wiring storage section for storing the pattern of wiring routed in the plural routing layers; (c) a search section for selecting at least one cell among the plural cell, and for selecting at least one local substrate area corresponding to the selected one cell for the prospective placement of the selected one cell; and (d) a placement section for judging, for the selected local substrate area, whether the second wiring of the plural routing layers overlaps the first wiring of the selected one cell in at least one of the plural routing layers inside the selected local substrate area, and for placing the selected one cell in the selected local substrate area if the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area.
Claim 11
Dependent Claim
91 words
An apparatus as claimed in claim 8 , further comprising (e) an individual site information section for, when each of the plural routing layers is divided into plurality of site units each corresponding to a basic cell, discriminating routing layers that the first wiring of the selected one cell crosses and routing layers that the second wiring crosses among the plural routing layers for each site unit; said placement section being operable to carry out the judgement for each said site unit based on the discrimination of said site information section.
Claim 12
Dependent Claim
174 words
An apparatus as claimed in claim 9 , wherein said placement section includes, for carrying out the judgement if the lowest routing layer that is crossed by the second wiring of the plural routing layers is not lowest among the plural routing layers: (d1) means for determining, for each said site unit, the highest layer that is crossed by the first wiring of the selected one cell as a representative routing layer; (d2) means for determining the lowest routing layer crossed by the second wiring of the plural routing layers as a reference routing layer; (d3) means for comparing, for each said site unit, the representative routing layer with the reference routing layer; and (d4) means for judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if the representative routing layer is lower than the reference routing layer at every site unit in the selected local substrate area.
Claim 13
Dependent Claim
173 words
An apparatus as claimed in claim 9 , wherein said placement section includes, for carrying out the judgement if the highest routing layer that is crossed by the second wiring of the plural routing layers is not highest among the plural routing layers: (d1) means for determining, for each said site unit, the lowest layer that is crossed by the first wiring of the selected one cell as a representative routing layer; (d2) means for determining the highest layer crossed by the second wiring of the plural routing layers as a reference routing layer; (d3) means for comparing, for each said site unit, the representative routing layer with the reference routing layer; and (d4) means for judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if the representative routing layer is higher than the reference routing layer at every site unit in the selected local substrate area.
Claim 14
Dependent Claim
194 words
An apparatus as claimed in claim 9 , wherein said placement section includes, for carrying out the judgement if the number of the plural routing layers is n and the second wiring is routed only in the n-th layer which is highest among the plural routing layers, where n is a natural number: (d1) means for determining, for each said site unit, the highest layer that is crossed by the first, wiring of the selected one cell as the x-th layer from the bottom; (d2) means for allocating to each said site unit n if the second wiring crosses the last-named site unit and n+1 if the second wiring does not crosses the same site unit; (d3) means for comparing x with y for each said site unit, where y represents n or n+1 allocated to the last-named site unit; and (d4) means for judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if x is smaller than y at every site unit in the selected local substrate.
Claim 15
Dependent Claim
194 words
An apparatus as claimed in claim 9 , wherein said placement section includes, for carrying out the judgement if the number of the plural routing layers is n and the second wiring is routed only in the n-th layer which is lowest among the plural routing layers, where n is a natural number: (d1) means for determining, for each said site unit, the lowest layer that is crossed by the first wiring of the selected one cell as the x-th layer from the top; (d2) means for allocating to each said site unit n if the second wiring crosses the last-named site unit and n+1 if the second wiring does not cross the same site unit; (d3) means for comparing x with y for each said site unit, where y represents n or n+1 allocated to the last-named site unit; and (d4) means for judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if x is smaller than y at every site unit in the selected local substrate.
Claim 16
Dependent Claim
133 words
An apparatus as claimed in claim 8 , further comprising: (f) a cost calculation section for calculating, for each of the first local substrate area in which the selected one cell is placed by said placement section and a second local substrate area which is also selected by said search section, a cost representing a probable congestion of routing based on both the second wiring in the last-named local substrate area and a wiring which connects the selected one cell with another cell among the plural cells; and (g) a cell movement section for moving the selected one cell from the first local substrate area according to a predetermined probability function on the basis of both the cost for the first local substrate area and the cost for the second local substrate area.
Claim 17
Dependent Claim
191 words
A storage medium storing a computer program for placing a plurality of cells, each containing a particular pattern of first wiring, in a plurality of routing layers of a substrate, in which second wiring is previously routed, in designing an integrated circuit, said program causing a computer to perform: (a) storing the pattern of wiring contained in each of the plural cells; (b) storing the pattern of wiring routed in the plural routing layers; (c) selecting at least one cell among the plural cells, and for selecting at least one local substrate area corresponding to the selected one cell for the prospective placement of the selected one cell; and (d) judging whether the second wiring of the plural routing layers overlaps the first wiring of the selected one cell in at least one of the plural routing layers inside the selected local substrate area, and for placing the selected one cell in the selected local substrate area if the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area.
Claim 18
Dependent Claim
191 words
A storage medium storing a computer program for placing a plurality of cells, each containing a particular pattern of first wiring, in a plurality of routing layers of a substrate, in which second wiring is previously routed, in designing an integrated circuit, said program causing a computer to perform: (a) storing the pattern of wiring contained in each of the plural cells; (b) storing the pattern of wiring routed in the plural routing layers; (c) selecting at least one cell among the plural cells, and for selecting at least one local substrate area corresponding to the selected one cell for the prospective placement of the selected one cell; and (d) judging whether the second wiring of the plural routing layers overlaps the first wiring of the selected one cell in at least one of the plural routing layers inside the selected local substrate area, and for placing the selected one cell in the selected local substrate area if the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area.
Claim 19
Dependent Claim
93 words
A storage medium as claimed in claim 15 , wherein said computer program further causes the computer to perform: (e) discriminating, when each of the plural routing layers is divided into a plurality of site units each corresponding to a basic cell, routing layers that the first wiring of the selected one cell crosses and routing layers that the second wiring crosses among the plural routing layers for each site unit; said judging and placing operable to carry out the judgement for each said site unit based on the discrimination of said discriminating.
Claim 20
Dependent Claim
169 words
A storage medium as claimed in claim 16 , wherein said placing and judging includes, for carrying out the judgement if the lowest routing layer that is crossed by the second wiring of the plural routing layers is not lowest among the plural routing layers: (d1) determining, for each said site unit, the highest layer that is crossed by the first wiring of the selected one cell as a representative routing layer; (d2) determining the lowest routing layer crossed a by the second wiring of the plural routing layers as a reference routing layer; (d3) comparing, for each said site unit, the representative routing layer with the reference routing layer; and (d4) judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if the representative routing layer is lower than the reference routing layer at every site unit in the selected local substrate area.
Claim 21
Dependent Claim
167 words
A storage medium as claimed in claim 16 , wherein said placing and judging includes, for carrying out the judgement if the highest routing layer that is crossed by the second wiring of the plural routing layers is not highest among the plural routing layers: (d1) determining, for each said site unit, the lowest layer that is crossed by the first wiring of the selected one cell as a representative routing layer; (d2) determining the highest layer crossed by the second wiring of the plural routing layers as a reference routing layer; (d3) comparing, for each said site unit, the representative routing layer with the reference routing layer; and (d4) judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if the representative routing layer is higher than the reference routing layer at every site unit in the selected local substrate area.
Claim 22
Dependent Claim
188 words
A storage medium as claimed in claim 16 , wherein said judging and placing includes, for carrying out the judgement if the number of the plural routing layers is n and the second wiring is routed only in the n-th layer which is highest among the plural routing layer, where n is a natural number: (d1) determining, for each said site unit, the highest layer that is crossed by the first wiring of the selected one cell as the x-th layer from the bottom; (d2) allocating to each said site unit n if the second wiring crosses the last-named site unit and n+1 if the second wiring does not cross the same site unit; (d3) comparing x with y for each said site unit, where y represents n or n+1 allocated to the last-named site unit; and (d4) judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if x is smaller than y at every site unit in the selected local substrate.
Claim 23
Dependent Claim
188 words
A storage medium as claimed in claim 16 , wherein said judging and placing includes, for carrying out the judgement if the number of the plural routing layers is n and the second wiring is routed only in the n-th layer which is lowest among the plural routing layers, where n is a natural number: (d1) determining, for each said site unit, the lowest layer that is crossed by the first wiring of the selected one cell as the x-th layer from the top; (d2) allocating to each said site unit n if the second wiring crosses the last-named site unit and n+1 if the second wiring does not cross the same site unit; (d3) comparing x with y for each said site unit, where y represents n or n+1 allocated to the last-named site unit; and (d4) judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if x is smaller than y at every site unit in the selected local substrate.
Claim 24
Dependent Claim
132 words
A storage medium as claimed in claim 15 , wherein said program further causes the computer to perform: (f) calculating, for each of the first local substrate area in which the selected one cell is placed by said judging and placing and a second local substrate area which is also selected by said searching, a cost representing a probable congestion of routing based on both the second wiring in the last-named local substrate area and a wiring which connects the selected one cell with another cell among the plural cells; and (g) moving the selected one cell from the first local substrate area the according to a predetermined probability function on the basis of both the cost for the first local substrate area and the cost for the second local substrate area.
Claim 25
Independent Claim
77 words
A method comprising: selecting a cell and a substrate area containing a plurality of routing layers, each routing layer divided into a plurality of site units corresponding to a basic cell; and judging, for each site unit, whether a second wiring of plural routing layers overlaps a first wiring of the selected cell in the selected substrate area, wherein, if there is no overlap in the judging, then placing the selected cell in the selected substrate area.
Claim 26
Independent Claim
77 words
A method comprising: selecting a cell and a substrate area containing a plurality of routing layers, each routing layer divided into a plurality of site units corresponding to a basic cell; and judging, for each site unit, whether a second wiring of plural routing layers overlaps a first wiring of the selected cell in the selected substrate area, wherein, if there is no overlap in the judging, then placing the selected cell in the selected substrate area.
Claim 27
Dependent Claim
87 words
A computer readable storage medium storing a program directing a computer to perform: selecting a cell and a substrate area containing a plurality of routing layers, each routing layer divided into a plurality of site units corresponding to a basic cell; and judging, for each site unit, whether a second wiring of plural routing layers overlaps a first wiring of the selected cell in the selected substrate area, wherein, if there is no overlap in the judging, then placing the selected cell in the selected substrate area.
Claim 28
Dependent Claim
87 words
A computer readable storage medium storing a program directing a computer to perform: selecting a cell and a substrate area containing a plurality of routing layers, each routing layer divided into a plurality of site units corresponding to a basic cell; and judging, for each site unit, whether a second wiring of plural routing layers overlaps a first wiring of the selected cell in the selected substrate area, wherein, if there is no overlap in the judging, then placing the selected cell in the selected substrate area.
Claim 29
Independent Claim
176 words
A method for placing a plurality of cells, each containing a particular pattern of first wiring, in a plurality of routing layers of a substrate, in which second wiring is previously routed, in designing an integrated circuit, said method comprising: selecting at least one cell among the plural cells and a local substrate area in which the selected one cell is to be placed; judging whether the second wiring of the plural routing layers overlaps the first wiring of the selected one cell in at least one of the plural routing layers at the selected local substrate area; and placing the selected one cell in the selected local substrate area if the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area, wherein each of the plural routing layers is divided into a plurality of site units each corresponding to a basic cell, and said judging is carried out for each said site unit.
Claim 30
Independent Claim
176 words
A method for placing a plurality of cells, each containing a particular pattern of first wiring, in a plurality of routing layers of a substrate, in which second wiring is previously routed, in designing an integrated circuit, said method comprising: selecting at least one cell among the plural cells and a local substrate area in which the selected one cell is to be placed; judging whether the second wiring of the plural routing layers overlaps the first wiring of the selected one cell in at least one of the plural routing layers at the selected local substrate area; and placing the selected one cell in the selected local substrate area if the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area, wherein each of the plural routing layers is divided into a plurality of site units each corresponding to a basic cell, and said judging is carried out for each said site unit.
Claim 31
Dependent Claim
156 words
A method as claimed in claim 24 , wherein said judging includes: if the lowest routing layer that is crossed by the second wiring of the plural routing layers is not lowest among the plural routing layers, determining, for each said site unit, the highest layer that is crossed by the first wiring of the selected one cell as a representative routing layer; determining the lowest routing layer crossed by the second wiring of the plural routing layers as a reference routing layer; comparing, for each said site unit, the representative routing layer with the reference routing layer; and judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if the representative routing layer is lower than the reference routing layer at every site unit in the selected local substrate area.
Claim 32
Dependent Claim
155 words
A method as claimed in claim 24 , wherein said judging includes: if the highest routing layer that is crossed by the second wiring of the plural routing layers is not highest among the plural routing layers, determining, for each said site unit, the lowest layer that is crossed by the first wiring of the selected one cell as a representative routing layer; determining the highest layer crossed by the second wiring of the plural routing layers as a reference routing layer; comparing, for each said site unit, the representative routing layer with the reference routing layer; and judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if the representative routing layer is higher than the reference routing layer at every site unit in the selected local substrate area.
Claim 33
Dependent Claim
175 words
A method as claimed in claim 24 , wherein said judging includes: if the number of the plural routing layers is n and the second wiring is routed only in the n-th layer which is highest among the plural routing layers, where n is a natural number, determining, for each said site unit, the highest layer that is crossed by the first wiring of the selected one cell as the x-th layer from the bottom; allocating to each sated site unit n if the second wiring crosses the last-named site unit and n+1 if the second wiring does not cross the same site unit; comparing x with y for each said site unit, where y represents n or n+1 allocated in said step (b2); and judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if x is smaller than y at every site unit in the selected local substrate.
Claim 34
Dependent Claim
175 words
A method as claimed in claim 24 , wherein said judging includes: if the number of the plural, routing layers is n and the second wiring is routed only in the n-th layer which is lowest among the plural routing layers, where n is a natural number, determining, for each said site unit, the lowest layer that is crossed by the first wiring of the selected one cell as the x-th layer from the top; allocating to each said site unit n if the second wiring crosses the last-named site unit and n+1 if the second wiring does not cross the same site unit; comparing x with y for each said site unit, where y represents n or n+1 allocated in said step (b2); and judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if x is smaller than y at every site unit in the selected local substrate.
Claim 35
Independent Claim
271 words
An apparatus for placing a plurality of cells, each containing a particular pattern of first wiring, in a plurality of routing layers of a substrate, in which second wiring is previously routed, in designing an integrated circuit, said apparatus comprising: a first-wiring storage section for storing the pattern of wiring contained in each of the plural cells; a second-wiring storage section for storing the pattern of wiring routed in the plural routing layers; a search section for selecting at least one cell among the plural cell, and for selecting at least one local substrate area in which the selected one cell is to be placed; a placement section for judging whether the second wiring of the plural routing layers overlaps the first wiring of the selected one cell in at least one of the plural routing layers at the selected local substrate area, and for placing the selected one cell in the selected local substrate area if the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area; and an individual site information section for, when each of the plural routing layers is divided into plurality of site units each corresponding to a basic cell, discriminating routing layers that the first wiring of the selected one cell crosses and routing layers that the second wiring crosses among the plural routing layers for each site unit; said placement section being operable to carry out the judgement for each said site unit based on the discrimination of said site information section.
Claim 36
Independent Claim
271 words
An apparatus for placing a plurality of cells, each containing a particular pattern of first wiring, in a plurality of routing layers of a substrate, in which second wiring is previously routed, in designing an integrated circuit, said apparatus comprising: a first-wiring storage section for storing the pattern of wiring contained in each of the plural cells; a second-wiring storage section for storing the pattern of wiring routed in the plural routing layers; a search section for selecting at least one cell among the plural cell, and for selecting at least one local substrate area in which the selected one cell is to be placed; a placement section for judging whether the second wiring of the plural routing layers overlaps the first wiring of the selected one cell in at least one of the plural routing layers at the selected local substrate area, and for placing the selected one cell in the selected local substrate area if the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area; and an individual site information section for, when each of the plural routing layers is divided into plurality of site units each corresponding to a basic cell, discriminating routing layers that the first wiring of the selected one cell crosses and routing layers that the second wiring crosses among the plural routing layers for each site unit; said placement section being operable to carry out the judgement for each said site unit based on the discrimination of said site information section.
Claim 37
Dependent Claim
170 words
An apparatus as claimed in claim 29 , wherein said placement section includes, for carrying out the judgement if the lowest routing layer that is crossed by the second wiring of the plural routing layers is not lowest among the plural routing layers: means for determining, for each said site unit, the highest layer that is crossed by the first wiring of the selected one cell as a representative routing layer; means for determining the lowest routing layer crossed by the second wiring of the plural routing layers as a reference routing layer; means for comparing, for each said site unit, the representative routing layer with the reference routing layer; and means for judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if the representative routing layer is lower than the reference routing layer at every site unit in the selected local substrate area.
Claim 38
Dependent Claim
169 words
An apparatus as claimed in claim 29 , wherein said placement section includes, for carrying out the judgement if the highest routing layer that is crossed by the second wiring of the plural routing layers is not highest among the plural routing layers: means for determining, for each said site unit, the lowest layer that is crossed by the first wiring of the selected one cell as a representative routing layer; means for determining the highest layer crossed by the second wiring of the plural routing layers as a reference routing layer; means for comparing, for each said site unit, the representative routing layer with the reference routing layer; and means for judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if the representative routing layer is higher than the reference routing layer at every site unit in the selected local substrate area.
Claim 39
Dependent Claim
190 words
An apparatus as claimed in claim 29 , wherein said placement section includes, for carrying out the judgement if the number of the plural routing layers is n and the second wiring is routed only in the n-th layer which is highest among the plural routing layers, where n is a natural number: means for determining, for each said site unit, the highest layer that is crossed by the first, wiring of the selected one cell as the x-th layer from the bottom; means for allocating to each said site unit n if the second wiring crosses the last-named site unit and n+1 if the second wiring does not crosses the same site unit; means for comparing x with y for each said site unit, where y represents n or n+1 allocated to the last-named site unit; and means for judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if x is smaller than y at every site unit in the selected local substrate.
Claim 40
Dependent Claim
190 words
An apparatus as claimed in claim 29 , wherein said placement section includes, for carrying out the judgement if the number of the plural routing layers is n and the second wiring is routed only in the n-th layer which is lowest among the plural routing layers, where n is a natural number: means for determining, for each said site unit, the lowest layer that is crossed by the first wiring of the selected one cell as the x-th layer from the top; means for allocating to each said site unit n if the second wiring crosses the last-named site unit and n+1 if the second wiring does not cross the same site unit; means for comparing x with y for each said site unit, where y represents n or n+1 allocated to the last-named site unit; and means for judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if x is smaller than y at every site unit in the selected local substrate.
Claim 41
Dependent Claim
256 words
A storage medium storing a computer program for placing a plurality of cells, each containing a particular pattern of first wiring, in a plurality of routing layers of a substrate, in which second wiring is previously routed, in designing an integrated circuit, said program causing a computer to perform: storing the pattern of wiring contained in each of the plural cells; storing the pattern of wiring routed in the plural routing layers; selecting at least one cell among the plural cells, and for selecting at least one local substrate area in which the selected one cell is to be placed; and judging whether the second wiring of the plural routing layers overlaps the first wiring of the selected one cell in at least one of the plural routing layers at the selected local substrate area, and for placing the selected one cell in the selected local substrate area if the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area; and discriminating, when each of the plural routing layers is divided into a plurality of site units each corresponding to a basic cell, routing layers that the first wiring of the selected one cell crosses and routing layers that the second wiring crosses among the plural routing layers for each site unit; said judging and placing operable to carry out the judgement for each said site unit based on th discrimination of said discriminating.
Claim 42
Dependent Claim
256 words
A storage medium storing a computer program for placing a plurality of cells, each containing a particular pattern of first wiring, in a plurality of routing layers of a substrate, in which second wiring is previously routed, in designing an integrated circuit, said program causing a computer to perform: storing the pattern of wiring contained in each of the plural cells; storing the pattern of wiring routed in the plural routing layers; selecting at least one cell among the plural cells, and for selecting at least one local substrate area in which the selected one cell is to be placed; and judging whether the second wiring of the plural routing layers overlaps the first wiring of the selected one cell in at least one of the plural routing layers at the selected local substrate area, and for placing the selected one cell in the selected local substrate area if the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area; and discriminating, when each of the plural routing layers is divided into a plurality of site units each corresponding to a basic cell, routing layers that the first wiring of the selected one cell crosses and routing layers that the second wiring crosses among the plural routing layers for each site unit; said judging and placing operable to carry out the judgement for each said site unit based on th discrimination of said discriminating.
Claim 43
Dependent Claim
165 words
A storage medium as claimed in claim 34 , wherein said placing and judging includes, for carrying out the judgement if the lowest routing layer that is crossed by the second wiring of the plural routing layers is not lowest among the plural routing layers: determining, for each said site unit, the highest layer that is crossed by the first wiring of the selected one cell as a representative routing layer; determining the lowest routing layer crossed a by the second wiring of the plural routing layers as a reference routing layer; comparing, for each said site unit, the representative routing layer with the reference routing layer; and judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if the representative routing layer is lower than the reference routing layer at every site unit in the selected local substrate area.
Claim 44
Dependent Claim
163 words
A storage medium as claimed in claim 34 , wherein said placing and judging includes, for carrying out the judgement if the highest routing layer that is crossed by the second wiring of the plural routing layers is not highest among the plural routing layers: determining, for each said site unit, the lowest layer that is crossed by the first wiring of the selected one cell as a representative routing layer; determining the highest layer crossed by the second wiring of the plural routing layers as a reference routing layer; comparing, for each said site unit, the representative routing layer with the reference routing layer; and judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if the representative routing layer is higher than the reference routing layer at every site unit in the selected local substrate area.
Claim 45
Dependent Claim
184 words
A storage medium as claimed in claim 34 , wherein said judging and placing includes, for carrying out the judgement if the number of the plural routing layers is n and the second wiring is routed only in the n-th layer which is highest among the plural routing layer, where n is a natural number: determining, for each said site unit, the highest layer that is crossed by the first wiring of the selected one cell as the x-th layer from the bottom; allocating to each said site unit n if the second wiring crosses the last-named site unit and n+1 if the second wiring does not cross the same site unit; comparing x with y for each said site unit, where y represents n or n+1 allocated to the last-named site unit; and judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if x is smaller than y at every site unit in the selected local substrate.
Claim 46
Dependent Claim
184 words
A storage medium as claimed in claim 34 , wherein said judging and placing includes, for carrying out the judgement if the number of the plural routing layers is n and the second wiring is routed only in the n-th layer which is lowest among the plural routing layers, where n is a natural number: determining, for each said site unit, the lowest layer that is crossed by the first wiring of the selected one cell as the x-th layer from the top; allocating to each said site unit n if the second wiring crosses the last-named site unit and n+1 if the second wiring does not cross the same site unit; comparing x with y for each said site unit, where y represents n or n+1 allocated to the last-named site unit; and judging that the second wiring of the plural routing layers does not overlap the first wiring of the selected one cell in any one of the plural routing layers at the selected local substrate area if x is smaller than y at every site unit in the selected local substrate.
References Cited (Backward Citations)
US5264390A
Cited
US5303161A
Cited
JPH0513577A
Cited
JPH0582642A
Cited
US5917729A
Cited
US5801960A
Cited
US5946476A
Cited
US5729467A
Cited
US5926397A
Cited
US6011912A
Cited
US5831870A
Cited
US6006024A
Cited
US6002857A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-01-30 | 2004-07-31 | 2005-01-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-30 | 2008-07-31 | 2009-01-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-30 | 2012-07-31 | 2013-01-30 | $7700.00 | Window Closed / Lapsed |