Method and apparatus for coarse global routing

• US 6,260,183 B1
• Filed: 04/17/1998
• Issued: 07/10/2001
• Est. Priority Date: 04/17/1998
• Status: Expired due to Term

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Scepanovic, Ranko, Andreev, Alexander E., Raspopovic, Pedja
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Siek, Vuthe
• Application Number:
  US09/062,246
• Time in Patent Office: 1,180 Days
• Field of Search: 395/500.12, 395/500.13, 395/500.14, 716/11, 716/12, 716/13, 716/14
• US Class Current: 716/131
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Nets are routed on an integrated circuit device by dividing a portion of the integrated circuit device into a first group of tiles. A first routing graph is then formed as a function of the first group of tiles and nets are routed as a function of the first routing graph. A new group of tiles is formed by dividing the tiles of the first group of tiles, a new routing graph is formed as a function of the new group of tiles, and nets are rerouted as a function of the new routing graph. The steps of the preceding sentence are then repeated and each time a new group of tiles is formed, the tiles are divided in a same first dimension, resulting in tiles have progressively smaller lengths in that first dimension, while the size of the tiles in a second dimension does not change.

Claims

1. A method for routing nets on an integrated circuit device, said method comprising the following steps:

a. dividing a portion of the integrated circuit device into a first plurality of tiles using cut lines in a first direction and cut lines in a second direction;

b. forming a first routing graph as a function of said first plurality of tiles;

c. routing nets as a function of said first routing graph;

d. forming a new plurality of tiles by dividing the tiles of said first plurality of tiles;

e. forming a new routing graph as a function of said new plurality of tiles;

f. rerouting nets as a function of said new routing graph; and

g. repeating steps d, e and f,

wherein, at each iteration of step d, the tiles are further divided by adding more cut lines in the first direction, while a number of cut lines in the second direction does not change.

2. The method of claim 1 wherein the tiles of said first plurality of tiles are rectangular.

3. The method of claim 2 wherein the tiles of said new plurality of tiles are rectangular.

4. The method of claim 3 wherein the tiles of the first plurality of tiles are substantially equal in size.

5. The method of claim 4 wherein the tiles of the new plurality of the tiles are substantially half the size of the tiles in the first plurality of tiles.

6. The method of claim 4 wherein the tiles of the first plurality of tiles are formed by parallel lines in a first direction and parallel lines in a second direction, said second direction being substantially perpendicular to said first direction.

7. The method of claim 6 wherein the tiles of the new plurality of tiles are formed by adding additional parallel lines in the second direction.

8. The method of claim 6 wherein some of the parallel lines in the first direction are located in the middle of a column of cells.

9. The method of claim 8 wherein some of the parallel lines in the first direction are located in the middle of wiring channels.

10. The method of claim 7 wherein the parallel lines in the second direction that form the tiles of the first plurality of tiles are spaced substantially equally apart.

11. The method of claim 10 wherein the parallel lines in the second direction that form the tiles of the first plurality of tiles are spaced a distance of 2^k grids, wherein k is a predetermined integer.

12. The method of claim 11 wherein steps d, e and f are each performed k times.

13. The method of claim 11 wherein steps d, e and f are iterated until the distance between parallel lines in the second direction are substantially 1 grid apart.

14. The method of claim 1 further comprising the step of partitioning nets into smaller nets.

15. The method of claim 14 wherein nets having a number of pins between a predetermined lower limit and a predetermined upper limit are partitioned into smaller nets.

16. The method of claim 14 wherein said predetermined lower limit is approximately 7.

17. An apparatus for routing nets on an integrated circuit device, said apparatus comprising

a. means for dividing a portion of the integrated circuit device into a first plurality of tiles using cut lines in a first direction and cut lines in a second direction;

b. means for forming a first routing graph as a function of said first plurality of tiles;

c. means for routing nets as a function of said first routing graph;

d. means for forming a new plurality of tiles by dividing the tiles of said first plurality of tiles;

e. means for forming a new muting graph as a function of said new plurality of tiles;

f. means for rerouting nets as a function of said new routing graph; and

g. means for repeating the functions performed by means d, e and f,

wherein, at each iteration of the function performed by means d, the tiles are further divided by adding more cut lines in the first direction, while a number of cut lines in the second direction does not change.

18. The apparatus of claim 17 wherein the tiles of said first plurality of tiles are rectangular.

19. The apparatus of claim 18 wherein the tiles of said new plurality of tiles are rectangular.

20. The apparatus of claim 19 wherein the tiles of the first plurality of tiles are substantially equal in size.

21. The apparatus of claim 20 wherein the tiles of the new plurality of the tiles are substantially half the size of the tiles in the first plurality of tiles.

22. The apparatus of claim 20 wherein the tiles of the first plurality of tiles are formed by parallel lines in a first direction and parallel lines in a second direction, said second direction being substantially perpendicular to said first direction.

23. The apparatus of claim 20 wherein the tiles of the new plurality of tiles are formed by adding additional parallel lines in the second direction.

24. The apparatus of claim 22 wherein some of the parallel lines in the first direction are located in the middle of a column of cells.

25. The apparatus of claim 24 wherein some of the parallel lines in the first direction are located in the middle of wiring channels.

26. The apparatus of claim 25 wherein the parallel lines in the second direction that form the tiles of the first plurality of tiles are spaced substantially equally apart.

27. The apparatus of claim 26 wherein the parallel lines in the second direction that form the tiles of the first plurality of tiles are spaced a distance of 2^k grids, wherein k is a predetermined integer.

28. The apparatus of claim 27 wherein elements d, e and f are each utilized k times.

29. The apparatus of claim 27 wherein utilization of elements d, e and f are iterated until the distance between parallel lines in the second direction are substantially 1 grid apart.

30. The apparatus of claim 17 further comprising means for partitioning nets into smaller nets.

31. The apparatus of claim 30 wherein nets having a number of pins between a predetermined lower limit and a predetermined upper limit are partitioned into smaller nets.

32. The apparatus of claim 31 wherein said predetermined lower limit is approximately 7.

33. A computer-readable storage medium storing a computer-executable program for use in routing nets on an integrated circuit device, comprising:

a computer-readable storage medium; and

means recorded on said storage medium for directing a computer processor to;

a. divide a portion of the integrated circuit device into a first plurality of tiles using cut lines in a first direction and cut lines in a second direction;

b. form a first routing graph as a function of said first plurality of tiles;

c. route nets as a function of said first routing graph;

d. form a new plurality of tiles by dividing the tiles of said first plurality of tiles;

e. form a new routing graph as a function of said new plurality of tiles;

f. reroute nets as a function of said new routing graph; and

g. repeat steps d, e and f,

wherein, at each iteration of step d, the tiles are further divided by adding more cut lines in the first direction, while a number of cut lines in the second direction does not change.