Method of automatic shape-based routing of interconnects in spines for integrated circuit design

• US 7,257,797 B1
• Filed: 05/31/2005
• Issued: 08/14/2007
• Est. Priority Date: 06/07/2004
• Status: Active Grant

• Current Assignee: Pulsic Limited
• Original Assignee: Pulsic Limited
• Inventors: Williams, Mark, Sato, Fumiaki, Waller, Mark, Birch, Jeremy, Parker, Tim, Balsdon, Graham
• Primary Examiner(s): Chiang; Jack
• Assistant Examiner(s): Parihar; Suchin
• Application Number:
  US10/908,895
• Time in Patent Office: 805 Days
• Field of Search: 716/14, 716/10, 716 12- 13
• US Class Current: 716/122
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A method and technique of routing interconnects of an integrated circuit providing improved routing quality. In an embodiment of the invention, the technique provides linear spine interconnect routing. In memory array blocks, such as in DRAM and SRAM memory designs, connected pins are generally separated by large distances in a first direction and small distances in a second direction, or a spine or channel region. A route area is defined within the spine region. In one embodiment, obstacles in the route area are identified and corresponding forbidden areas are demarcated. The linear spine interconnect is routed in the first direction within the route area while avoiding the forbidden areas. Pins are connected to the spine interconnect by stitching interconnects. Stitching interconnects are generally routed in the second direction.

Claims

1. A method of routing at least two interconnects of an integrated circuit comprising:

identifying a first set of at least two pins to couple;

calculating a route area, the route area extending a distance in a first direction to comprise positions in the first direction of the at least two pins;

routing a first spine interconnect extending in the first direction at least a length from a first pin to a second pin in the first direction;

determining a position in a second direction, orthogonal to the first direction, for the first spine interconnect to reduce an average length of the plurality of stitching interconnects;

routing a plurality of stitching interconnects in the second direction to couple the first pin and second pin to the first spine interconnect, wherein a position in the second direction of the first spine interconnect is based on a weighted average of positions in the second direction of the first set of at least two pins;

identifying a second set of at least two pins to couple, wherein the second set comprises at least a third pin and a fourth pin;

in the route area, routing a second spine interconnect extending in the first direction at least a length from the third pin to the fourth pin the first direction;

determining a position in a second direction, orthogonal to the first direction, for the second spine interconnect to reduce an average length of the plurality of stitching interconnects;

routing a plurality of stitching interconnects in the second direction to couple the third pin and fourth pin to the second spine interconnect, wherein a position in the second direction of the second spine interconnect is based on a weighted average of positions in the second direction of the second set of at least two pins;

placing a first shield on a first side of the first spine interconnect; and

placing a second shield interconnect adjacent to the first spine interconnect, between the first spine interconnect and the second spine interconnect.

2. The method of claim 1 further comprising:

determining if at least one forbidden area is located within the route area, wherein the at least one forbidden area extends in the first direction the entire length of the route area in the first direction and comprises at least one obstacle; and

routing the spine interconnect excludes the at least one forbidden area.

3. The method of claim 2 further comprising determining if a path of each of the plurality of stitching interconnects is unobstructed by the at least one obstacle.

4. The method of claim 1 wherein an edge of the route area comprises an edge of a chip and the edge of the chip comprises one of the at least two pins.

5. The method of claim 1 wherein the first shield or the second shield is coupled to a ground potential.

6. The method of claim 1 wherein the route area is a rectangle.

7. The method of claim 1 wherein the route area in the second direction extends between the most oppositely disposed in the second direction of the at least two pins.

8. A method of routing at least two interconnects of an integrated circuit comprising:

identifying a first set of at least two pins to couple;

calculating a route area, the route area extending a distance in a first direction to comprise positions in the first direction of the at least two pins;

routing a first spine interconnect extending in the first direction at least a length from a first pin to a second pin in the first direction;

determining a position in a second direction, orthogonal to the first direction, for the first spine interconnect to reduce an average length of the plurality of stitching interconnects;

routing a plurality of stitching interconnects in the second direction to couple the first pin and second pin to the first spine interconnect, wherein a position in the second direction of the first spine interconnect is based on a weighted average of positions in the second direction of the first set of at least two pins;

identifying a second set of at least two pins to couple wherein the second set comprises at least a third pin and a fourth pin;

in the route area, routing a second spine interconnect extending in the first direction at least a length from the third pin to the fourth pin the first direction;

determining a position in a second direction, orthogonal to the first direction, for the second spine interconnect to reduce an average length of the plurality of stitching interconnects;

routing a plurality of stitching interconnects in the second direction to couple the third pin and fourth pin to the second spine interconnect, wherein a position in the second direction of the second spine interconnect is based on a weighted average of positions in the second direction of the second set of at least two pins;

placing a first shield on a first side of the first spine interconnect; and

placing a second shield interconnect adjacent to the second spine interconnect, wherein the first and second spine interconnects are between the first and second shield interconnects.

9. The method of claim 8 further comprising:

determining if at least one forbidden area is located within the route area, wherein the at least one forbidden area extends in the first direction the entire length of the route area in the first direction and comprises at least one obstacle, and

routing the spine interconnect excludes the at least one forbidden area.

10. The method of claim 9 further comprising determining if a path of each of the plurality of stitching interconnects is unobstructed by the at least one obstacle.

11. The method of claim 8 wherein an edge of the route area comprises an edge of a chip and the edge of the chip comprises one of the at least two pins.

12. The method of claim 8 wherein the first shield or the second shield is coupled to a ground potential.

13. The method of claim 8 wherein the route area is a rectangle.

14. The method of claim 8 wherein the route area in the second direction extends between the most oppositely disposed in the second direction of the at least two pins.

15. A method of routing at least one interconnect of an integrated circuit comprising:

identifying at least two pins to couple, wherein each pin has a position in a first direction and a position in a second direction, orthogonal to the first direction;

calculating a route area, the route area extending a distance in the first direction to comprise positions in the first direction of the at least two pins;

determining if at least one forbidden area is located within the route area, wherein the at least one forbidden area extends in the first direction the entire length of the route area in the first direction and comprises at least one obstacle;

routing a spine interconnect extending in the first direction at least a length from a first pin to a second pin in the first direction, wherein the routing the spine interconnect excludes the at least one forbidden area; and

routing a plurality of stitching interconnects in the second direction to couple the first pin and second pin to the spine interconnect,

wherein a position in the second direction of the spine interconnect is at an available position, outside the at least one forbidden area, closest to a position based on a weighted average of positions in the second direction of the at least two pins.

16. The method of claim 15 wherein the route area is a rectangle.

17. The method of claim 15 wherein the route area in the second direction extends between the most oppositely disposed in the second direction of the at least two pins.

18. The method of claim 15 wherein an edge of the route area comprises an edge of a chip and the edge of the chip comprises one of the at least two pins.

19. The method of claim 15 further comprising automatically routing at least one shield parallel to the spine interconnect.

20. The method of claim 19 wherein the at least one shield comprises two shields positioned on opposite sides of the spine interconnect.

21. The method of claim 19 wherein the at least one shield is coupled to a ground potential.

22. A method of routing at least two interconnects of an integrated circuit comprising:

identifying N pins to couple;

calculating a rectangular route area comprising the positions in a first direction of the N pins;

determining if at least one forbidden area is located within the route area, wherein the at least one forbidden area is a rectangular area comprising at least one obstacle and extends an entire length of the route area in the first direction;

routing, outside of the forbidden area, a first spine interconnect extending in the first direction an entire length of the route area in the first direction;

determining a position in a second direction, orthogonal to the first direction, for the spine interconnect to reduce an average length of N stitching interconnects;

routing N stitching interconnects in the second direction to couple each of the N pins to the spine interconnect, wherein the position in the second direction of the spine interconnect is based on a quotient of a sum of the positions of the N pins in the second direction and N;

identifying M pins to couple;

routing, outside of the forbidden area, a second spine interconnect extending in the first direction an entire length of the route area in the first direction;

determining a position in the second direction for the second spine interconnect to reduce an average length of M stitching interconnects;

routing M stitching interconnects in the second direction to couple each of the M pins to the second spine interconnect, wherein the position in the second direction of the second spine interconnect is based on a quotient of a sum of the positions of the M pins in the second direction and M;

placing a first shield on a first side of the first spine interconnect; and

placing a second shield interconnect adjacent to the first spine interconnect, between the first spine interconnect and the second spine interconnect.

23. The method of claim 22 further comprising determining if a path of each of the plurality of stitching interconnects is unobstructed by the at least one obstacle.

24. The method of claim 22 wherein an edge of the route area comprises an edge of a chip and the edge of the chip comprises at least one of the N pins.

25. A method of routing at least one interconnect of an integrated circuit comprising:

identifying N pins to couple, wherein each pin has a position in a first direction and a position in a second direction, orthogonal to the first direction;

calculating a rectangular route area comprising the positions in the first direction of the N pins;

determining if at least one forbidden area is located within the route area, wherein the at least one forbidden area is a rectangular area comprising at least one obstacle and extends an entire length of the route area in the first direction;

routing, outside of the forbidden area, a spine interconnect extending in the first direction an entire length of the route area in the first direction;

determining a position in the second direction, orthogonal to the first direction, for the spine interconnect to reduce an average length of N stitching interconnects; and

routing N stitching interconnects in the second direction to couple each of the N pins to the spine interconnect, wherein the position in the second direction of the spine interconnect is at a position, outside the forbidden area, closest to a position based on a weighted average of positions in the second direction of the N pins.

26. The method of claim 25 further comprising determining if a path of each of the plurality of stitching interconnects is unobstructed by the at least one obstacle.

27. The method of claim 25 wherein an edge of the route area comprises an edge of a chip and the edge of the chip comprises at least one of the N pins.

28. A method of routing a plurality of nets of an integrated circuit comprising:

identifying pins to couple for each net;

calculating a route area for each net, wherein each route area comprises positions in a first direction of the pins for a net;

determining for each route area if at least one forbidden area is located within the route area, wherein a forbidden area includes at least one obstacle and extends in the first direction an entire length of the corresponding route area in the first direction;

routing, outside of the at least one forbidden area, a plurality of spine interconnects extending in a first direction the entire length of each corresponding route area in the first direction;

routing a plurality of stitching interconnects in a second direction to couple each of the pins to the corresponding spine interconnect;

automatically routing a first interconnect to match a timing delay of a second interconnect by lengthening the first interconnect;

placing a first shield on a first side of at least one spine interconnect; and

placing a second shield on a second side of the at least one spine interconnect.

29. The method of claim 28 further comprising automatically routing the plurality of spine interconnects using a spacing between interconnects that satisfies a design constraint.

30. The method of claim 29 wherein the design constraint comprises at least one of spacing constraint, crosstalk constraint, capacitance constraint, or timing constraint.

31. The method of claim 28 wherein between the first and second shields are a plurality of spine interconnects.

32. The method of claim 28 wherein between the first and second shields are every one of the plurality of spine interconnects.

33. A method of routing a plurality of nets of an integrated circuit comprising:

identifying pins to couple for each net;

calculating a route area for each net, wherein each route area comprises positions in a first direction of the pins for a net.

determining for each route area if at least one forbidden area is located within the route area, wherein a forbidden area includes at least one obstacle and extends in the first direction an entire length of the corresponding route area in the first direction;

routing, outside of the at least one forbidden area, a plurality of spine interconnects extending in a first direction the entire length of each corresponding route area in the first direction;

routing a plurality of stitching interconnects in a second direction to couple each of the pins to the corresponding spine interconnect;

automatically routing a first interconnect to match a timing delay of a second interconnect by increasing a spacing between the first interconnect and a third interconnect;

placing a first shield on a first side of at least one spine interconnect; and

placing a second shield on a second side of the at least one spine interconnect.

34. The method of claim 33 further comprising automatically routing the plurality of spine interconnects using a spacing between interconnects that satisfies a design constraint.

35. The method of claim 34 wherein the design constraint comprises at least one of spacing constraint, crosstalk constraint, capacitance constraint, or timing constraint.

36. A computer program product stored on a computer-readable storage medium for routing at least two interconnects of an integrated circuit comprising:

code for identifying a first and a second set of at least two pins to couple;

code for calculating a route area, the route area extending a distance in a first direction to include positions in the first direction of the first set of at least two pins;

code for routing a first spine interconnect extending in the first direction an entire length of the route area in the first direction;

code for determining a position in a second direction, orthogonal to the first direction, for the first spine interconnect to reduce an average length of the plurality of stitching interconnects;

code for routing a plurality of stitching interconnects in a second direction to couple each of the first set of at least two pins to the first spine interconnect, wherein the second direction is orthogonal to the first direction and a position in the second direction of the spine interconnect is based on a weighted average of positions in the second direction of the first set of at least two pins;

code for routing a second spine interconnect extending in the first direction an entire length of the route area in the first direction;

code for determining a position in the second direction for the second spine interconnect to reduce an average length of the plurality of stitching interconnects;

code for routing a plurality of stitching interconnects in the second direction to couple each of the second set of at least two pins to the second spine interconnect, wherein a position in the second direction of the spine interconnect is based on a weighted average of positions in the second direction of the second set of at least two pins;

code for placing a first shield interconnect adjacent to the first spine interconnect on a first side; and

code for placing a second shield interconnect adjacent to the first spine interconnect, between the first spine interconnect and the second spine interconnect.

37. A method comprising:

providing N pins to couple together using a net;

finding a rectangular route region comprising the N pins, having a length greater than a width, wherein the length is in a first direction and the width is a second direction, orthogonal to the first direction;

in the rectangular route region, placing a first spine interconnect extending in the first direction at a position in the second direction based on a weighted average of positions of the N pins;

routing N stitching interconnects in the second direction to couple each of the N pins to the first spine interconnect, wherein the first spine interconnect and N stitching interconnects forms a first interconnect track;

providing M pins to couple together using a net;

in the rectangular route region, placing a second spine interconnect extending in the first direction at a position in the second direction based on a weighted average of positions of the M pins;

routing M stitching interconnects in the second direction to couple each of the M pins to the second spine interconnect, wherein the second spine interconnect and M stitching interconnects forms a second interconnect track;

placing a first shield interconnect adjacent to the first spine interconnect, on a first side; and

placing a second shield interconnect adjacent to the first spine interconnect, between the first spine interconnect and the second spine interconnect.

38. The method of claim 37 further comprising:

lengthening the second interconnect track in order to match timing delays of the first and second interconnect tracks.

39. The method of claim 37 further comprising:

providing L pins to couple together using a net;

in the rectangular route region placing a third spine interconnect extending in the first direction adjacent to the second spine interconnect, wherein the second spine interconnect is between the third spine interconnect and the second shield interconnect; and

routing L stitching interconnects in the second direction to couple each of the L pins to the third spine interconnect, wherein the third spine interconnect and L stitching interconnects forms a third interconnect track.

40. The method of claim 39 further comprising:

increasing a space between the second and third interconnect track in order to match timing delays of the second and third interconnect track.

41. The method of claim 39 further comprising:

lengthening at least one of the second interconnect track and the third interconnect track in order to match timing delays of the second and third interconnect tracks.

42. The method of claim 37 further comprising:

placing a third shield interconnect adjacent to the second spine interconnect, wherein the second spine interconnect is between the second shield interconnect and the third shield interconnect.

43. A method comprising:

providing N pins to couple together using a net;

finding a rectangular route region comprising the N pins, having a length greater than a width, wherein the length is in a first direction and the width is a second direction, orthogonal to the first direction;

in the rectangular route region, placing a first spine interconnect extending in the first direction at a position in the second direction based on a weighted average of positions of the N pins;

routing N stitching interconnects in the second direction to couple each of the N pins to the first spine interconnect, wherein the first spine interconnect and N stitching interconnects forms a first interconnect track;

providing M pins to couple together using a net;

in the rectangular route region, placing a second spine interconnect extending in the first direction at a position in the second direction based on a weighted average of positions of the M pins;

routing M stitching interconnects in the second direction to couple each of the M pins to the second spine interconnect, wherein the second spine interconnect and M stitching interconnects forms a second interconnect track;

placing a first shield interconnect adjacent to the first spine interconnect on a first side; and

placing a second shield interconnect adjacent to the second spine interconnect, wherein the first and second spine interconnects are between the first and second shield interconnects.

44. The method of claim 43 further comprising:

lengthening the second interconnect track in order to match timing delays of the first and second interconnect tracks.

45. The method of claim 43 further comprising:

increasing a space between the first and second interconnect track in order to match timing delays of the first and second interconnect track.

46. The method of claim 43 further comprising:

providing L pins to couple together using a net;

in the rectangular route region, placing a third spine interconnect extending in the first direction adjacent to the second shield interconnect, wherein the second shield interconnect is between the second spine interconnect and the third spine interconnect; and

routing L stitching interconnects in the second direction to couple each of the L pins to the third spine interconnect, wherein the third spine interconnect and L stitching interconnects forms a third interconnect track.

47. The method of claim 46 further comprising:

lengthening the third interconnect track in order to match timing delays of the second and third interconnect tracks.

48. The method of claim 46 further comprising:

increasing a space between the second and third interconnect track in order to match timing delays of the second and third interconnect track.

49. A method comprising:

providing N pins to couple together using a net;

finding a rectangular route region, comprising the N pins, having a length greater than a width, wherein the length is in a first direction and the width is a second direction, orthogonal to the first direction;

in the rectangular route region, placing a first spine interconnect extending in the first direction at a position in the second direction based on a quotient of a sum of the positions of the N pins in the second direction and N;

routing N stitching interconnects in the second direction to couple each of the N pins to the first spine interconnect, wherein the first spine interconnect and N stitching interconnects forms a first interconnect track;

providing M pins to couple together using a net;

in the rectangular route region, placing a second spine interconnect extending in the first direction at a position in the second direction based on a weighted average of positions of the M pins;

routing M stitching interconnects in the second direction to couple each of the M pins to the second spine interconnect, wherein the second spine interconnect and M stitching interconnects forms a second interconnect track;

placing a first shield interconnect adjacent to the first spine interconnect on a first side; and

placing a second shield interconnect adjacent to the first spine interconnect, between the first spine interconnect and the second spine interconnect.

50. The method of claim 49 further comprising:

lengthening the second interconnect track in order to match timing delays of the first and second interconnect tracks.

51. The method of claim 49 further comprising:

increasing a space between the first and second interconnect track in order to match timing delays of the first and second interconnect track.

52. The method of claim 49 further comprising:

providing L pins to couple together using a net;

in the rectangular route region, placing a third spine interconnect extending in the first direction adjacent to the second spine interconnect, wherein the second spine interconnect is between the third spine interconnect and the second shield interconnect; and

routing L stitching interconnects in the second direction to couple each of the L pins to the third spine interconnect, wherein the third spine interconnect and L stitching interconnects forms a third interconnect track.

53. The method of claim 52 further comprising:

increasing a space between the second and third interconnect track in order to match timing delays of the second and third interconnect track.

54. The method of claim 52 further comprising:

lengthening at least one of the second interconnect track and the third interconnect track in order to match timing delays of the second and third interconnect tracks.

55. The method of claim 49 further comprising:

placing a third shield interconnect adjacent to the second spine interconnect, wherein the second spine interconnect is between the second shield interconnect and the third shield interconnect.

56. A method comprising:

providing N pins to couple together using a net;

finding a rectangular route region comprising the N pins, having a length greater than a width, wherein the length is in a first direction and the width is a second direction, orthogonal to the first direction;

in the rectangular route region, placing a first spine interconnect extending in the first direction at a position in the second direction based on a quotient of a sum of the positions of the N pins in the second direction and N;

routing N stitching interconnects in the second direction to couple each of the N pins to the first spine interconnect, wherein the first spine interconnect and N stitching interconnects forms a first interconnect track;

providing M pins to couple together using a net;

in the rectangular route region, placing a second spine interconnect extending in the first direction at a position in the second direction based on a weighted average of positions of the M pins;

routing M stitching interconnects in the second direction to couple each of the M pins to the second spine interconnect, wherein the second spine interconnect and M stitching interconnects forms a second interconnect track;

placing a first shield interconnect adjacent to the first spine interconnect on a first side; and

placing a second shield interconnect adjacent to the second spine interconnect, wherein the first and second spine interconnects are between the first and second shield interconnects.

57. The method of claim 56 further comprising:

lengthening the second interconnect track in order to match timing delays of the first and second interconnect tracks.

58. The method of claim 56 further comprising:

increasing a space between the first and second interconnect track in order to match timing delays of the first and second interconnect track.

59. The method of claim 56 further comprising:

providing L pins to couple together using a net;

in the rectangular route region, placing a third spine interconnect extending in the first direction adjacent to the second shield interconnect, wherein the second shield interconnect is between the second spine interconnect and the third spine interconnect; and

routing L stitching interconnects in the second direction to couple each of the L pins to the third spine interconnect, wherein the third spine interconnect and L stitching interconnects forms a third interconnect track.

60. The method of claim 59 further comprising:

lengthening the third interconnect track in order to match timing delays of the second and third interconnect tracks.

61. The method of claim 59 further comprising:

increasing a space between the second and third interconnect track in order to match timing delays of the second and third interconnect track.

62. A computer program product stored on a computer-readable storage medium for routing at least two interconnects of an integrated circuit comprising:

code for identifying a first and a second set of at least two pins to couple;

code for calculating a route area, the route area extending a distance in a first direction to include positions in the first direction of the first set of at least two pins;

code for routing a first spine interconnect extending in the first direction an entire length of the route area in the first direction;

code for determining a position in a second direction, orthogonal to the first direction, for the first spine interconnect to reduce an average length of the plurality of stitching interconnects;

code for routing a plurality of stitching interconnects in a second direction to couple each of the first set of at least two pins to the first spine interconnect, wherein the second direction is orthogonal to the first direction and a position in the second direction of the spine interconnect is based on a weighted average of positions in the second direction of the first set of at least two pins;

code for routing a second spine interconnect extending in the first direction an entire length of the route area in the first direction;

code for determining a position in the second direction for the second spine interconnect to reduce an average length of the plurality of stitching interconnects;

code for routing a plurality of stitching interconnects in the second direction to couple each of the second set of at least two pins to the second spine interconnect, wherein a position in the second direction of the spine interconnect is based on a weighted average of positions in the second direction of the second set of at least two pins;

code for placing a first shield interconnect adjacent to the first spine interconnect on a first side; and

code for placing a second shield adjacent to the second spine interconnect, wherein the first spine interconnect and the second spine interconnect are between the first shield and the second shield.

63. A method of routing at least two interconnects of an integrated circuit comprising:

identifying N pins to couple;

calculating a rectangular route area comprising the positions in a first direction of the N pins;

determining if at least one forbidden area is located within the route area, wherein the at least one forbidden area is a rectangular area comprising at least one obstacle and extends an entire length of the route area in the first direction;

routing, outside of the forbidden area, a first spine interconnect extending in the first direction an entire length of the route area in the first direction;

determining a position in a second direction, orthogonal to the first direction, for the spine interconnect to reduce an average length of N stitching interconnects;

routing N stitching interconnects in the second direction to couple each of the N pins to the spine interconnect, wherein the position in the second direction of the spine interconnect is based on a quotient of a sum of the positions of the N pins in the second direction and N;

identifying M pins to couple;

routing, outside of the forbidden area, a second spine interconnect extending in the first direction an entire length of the route area in the first direction;

determining a position in the second direction for the second spine interconnect to reduce an average length of M stitching interconnects;

routing M stitching interconnects in the second direction to couple each of the M pins to the second spine interconnect, wherein the position in the second direction of the second spine interconnect is based on a quotient of a sum of the positions of the M pins in the second direction and M;

placing a first shield on a first side of the first spine interconnect; and

placing a second shield interconnect adjacent to the second spine interconnect, wherein the first and second spine interconnects are between the first and second shield interconnects.

64. The method of claim 63 further comprising determining if a path of each of the plurality of stitching interconnects is unobstructed by the at least one obstacle.

65. The method of claim 63 wherein an edge of the route area comprises an edge of a chip and the edge of the chip comprises at least one of the N pins.