US6289495B1 — Method and apparatus for local optimization of th…

Claim 1

Independent Claim 94 words

A method for routing nets in an integrated circuit design, said method comprising the following steps: a. Forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction; b. globally routing said integrated circuit design in accordance with said routing graph; c. dividing the routing graph into strips; d. for each strip in the routing graph, generating a general task for optimizing the routing in the strip; e. solving general tasks in parallel by assigning different processors different strips to process.

Claim 2

Independent Claim 94 words

A method for routing nets in an integrated circuit design, said method comprising the following steps: a. Forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction; b. globally routing said integrated circuit design in accordance with said routing graph; c. dividing the routing graph into strips; d. for each strip in the routing graph, generating a general task for optimizing the routing in the strip; e. solving general tasks in parallel by assigning different processors different strips to process.

Claim 3

Dependent Claim 21 words

The method of claim 1 wherein general tasks are generated with respect to each net fragment which passes in a strip.

Claim 4

Dependent Claim 25 words

The method of claim 2 wherein the solving of general tasks is repeated for a predetermined number of times with respect to a particular strip.

Claim 5

Dependent Claim 29 words

The method of claim 1 wherein an edge in the routing graph has an associated penalty and the solution of a general task is a function of the penalty.

Claim 6

Dependent Claim 23 words

The method of claim 4 wherein the penalty is a function of an occupancy value and a capacity value associated with the edge.

Claim 7

Dependent Claim 19 words

The method of claim 4 wherein the solving of a general task involves determining a vector of minimal penalty.

Claim 8

Dependent Claim 37 words

The method of claim 1 wherein a second routing graph is formed, nets are rerouted in accordance with the second routing graph, and steps c, d and e are repeated with respect to said second routing graph.

Claim 9

Dependent Claim 29 words

The method of claim 1 wherein a strip comprises a small number of lines comprising edges in the first direction and edges in the second direction connecting said lines.

Claim 10

Dependent Claim 21 words

The method of claim 1 , wherein at least one of said strips includes more than one pin from a net.

Claim 11

Independent Claim 101 words

A apparatus for routing nets in an integrated circuit design, said apparatus comprising: a. means for forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction; b. means for globally routing said integrated circuit design in accordance with said routing graph; c. means for dividing the routing graph into strips; d. means for, for each strip in the routing graph, generating a general task for optimizing the routing in the strip; e. means for solving general tasks in parallel by assigning different processors different strips to process.

Claim 12

Independent Claim 101 words

A apparatus for routing nets in an integrated circuit design, said apparatus comprising: a. means for forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction; b. means for globally routing said integrated circuit design in accordance with said routing graph; c. means for dividing the routing graph into strips; d. means for, for each strip in the routing graph, generating a general task for optimizing the routing in the strip; e. means for solving general tasks in parallel by assigning different processors different strips to process.

Claim 13

Dependent Claim 21 words

The apparatus of claim 10 wherein general tasks are generated with respect to each net fragment which passes in a strip.

Claim 14

Dependent Claim 25 words

The apparatus of claim 11 wherein the solving of general tasks is repeated for a predetermined number of times with respect to a particular strip.

Claim 15

Dependent Claim 29 words

The apparatus of claim 10 wherein an edge in the routing graph has an associated penalty and the solution of a general task is a function of the penalty.

Claim 16

Dependent Claim 23 words

The apparatus of claim 13 wherein the penalty is a function of an occupancy value and a capacity value associated with the edge.

Claim 17

Dependent Claim 19 words

The apparatus of claim 13 wherein the solving of a general task involves determining a vector of minimal penalty.

Claim 18

Dependent Claim 41 words

The apparatus of claim 10 further comprising means for forming a second routing graph, means for rerouting nets in accordance with the second routing graph, and means for reutilizing elements c, d and e with respect to said second routing graph.

Claim 19

Dependent Claim 29 words

The apparatus of claim 10 wherein a strip comprises a small number of lines comprising edges in the first direction and edges in the second direction connecting said lines.

Claim 20

Dependent Claim 21 words

The apparatus of claim 10 , wherein at least one of said strips includes more than one pin from a net.

Claim 21

Dependent Claim 123 words

A computer encoded storage medium with instructions thereon for routing nets in an integrated circuit design, said storage medium comprising: a. a computer encoded instruction for forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction; b. a computer encoded instruction for globally routing said integrated circuit design in accordance with said routing graph; c. a computer encoded instruction for dividing the routing graph into strips; d. a computer encoded instruction for for each strip in the routing graph, generating a general task for optimizing the routing in the strip; e. a computer encoded instruction for solving general tasks in parallel by assigning different processors different strips to process.

Claim 22

Dependent Claim 123 words

A computer encoded storage medium with instructions thereon for routing nets in an integrated circuit design, said storage medium comprising: a. a computer encoded instruction for forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction; b. a computer encoded instruction for globally routing said integrated circuit design in accordance with said routing graph; c. a computer encoded instruction for dividing the routing graph into strips; d. a computer encoded instruction for for each strip in the routing graph, generating a general task for optimizing the routing in the strip; e. a computer encoded instruction for solving general tasks in parallel by assigning different processors different strips to process.

Claim 23

Dependent Claim 22 words

The storage medium of claim 19 , wherein at least one of said strips includes more than one pin from a net.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2004-09-10	2005-03-12	2005-09-11	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2008-09-10	2009-03-12	2009-09-11	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2012-09-10	2013-03-12	2013-09-11	$7700.00	Window Closed / Lapsed

Method and apparatus for local optimization of the global routing

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag