Method and apparatus for parallel Steiner tree routing

• US 6,247,167 B1
• Filed: 04/17/1998
• Issued: 06/12/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): Kik, Phallaka
• Application Number:
  US09/062,432
• Time in Patent Office: 1,152 Days
• Field of Search: 395/500-2-5, 716/1-21
• US Class Current: 716/122
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. The method according to claim 1 wherein the planar graph is formed by removing lines which intersect with other lines.

8. The method according to claim 7 wherein the planar graph is formed by iteratively removing the longest of two intersecting lines.

9. 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.

10. The method according to claim 1 wherein the connected cover is constructed as a function of the complexity of each basic element.

11. 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.

12. The method according to claim 1 wherein the basic elements forming the connected cover are processed for routing by multiple processors.

13. A semiconductor device having pins routed in accordance with the method of claim 12.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. The apparatus according to claim 14 wherein the planar graph is formed by removing lines which intersect with other lines.

21. The apparatus according to claim 20 wherein the planar graph is formed by iteratively removing the longest of two intersecting lines.

22. 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.

23. The apparatus according to claim 14 wherein the connected cover is constructed as a function of the complexity of each basic element.

24. 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.

25. The apparatus according to claim 14 wherein the basic elements forming the connected cover are processed for routing by multiple processors.

26. 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.

27. 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.

28. 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.

29. The apparatus of claim 28 further comprising:

E. means for identifying quasi-elementary pairs of pins at at least one expansion iteration.

30. The apparatus of claim 28 wherein said means for iteratively compressing the net alternates between compressing the net in the x- and y-directions.

31. 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.

32. The apparatus of claim 28 wherein said means for iteratively expanding the net alternates between expanding the net in the x- and y-directions.

33. 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.

34. 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.

35. The method of claim 34 further comprising the following step:

E. identifying quasi-elementary pairs of pins at at least one expansion iteration.

36. The method of claim 34 wherein said step of iteratively compressing the net alternates between compressing the net in the x- and y-directions.

37. 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.

38. The method of claim 34 wherein said step of iteratively expanding the net alternates between expanding the net in the x- and y-directions.

39. 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.

40. 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.

41. 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.

42. 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.

43. The method according to claim 42 wherein the planar graph is formed by removing lines which intersect with other lines.

44. The method according to claim 43 wherein the planar graph is formed by iteratively removing the longest of two intersecting lines.

45. 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.

46. 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.

47. 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.

48. The apparatus according to claim 47 wherein the planar graph is formed by iteratively removing the longest of two intersecting lines.

49. 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.

50. 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.

51. 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.

52. 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.

53. 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.

54. 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.

55. 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.

56. The method according to claim 50 wherein the planar graph is formed by removing lines which intersect with other lines.

57. The method according to claim 56 wherein the planar graph is formed by iteratively removing the longest of two intersecting lines.

58. 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.

59. A semiconductor device having pins routed in accordance with the method of claim 50.

60. 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.

61. 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.

62. 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.

63. 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.

64. 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.

65. 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).

66. 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.

67. The method according to claim 64 further comprising the step of processing the basic elements comprising the connected cover for routing with multiple processors.

68. A semiconductor device having pins routed in accordance with the method of claim 64.

69. 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.

70. 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.

71. 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.

72. 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.

73. 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.

74. 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.

75. The apparatus according to claim 72 wherein the basic elements forming the connected cover are processed for routing by multiple processors.

76. 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.

77. 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.

78. 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.

79. 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.

80. 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.

81. 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.

82. 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.