US6408427B1ExpiredUtility
Wire width planning and performance optimization for VLSI interconnects
Est. expiryFeb 22, 2020(expired)· nominal 20-yr term from priority
G06F 30/394
91
PatentIndex Score
98
Cited by
13
References
68
Claims
Abstract
The present invention discloses a method, apparatus, and article of manufacture for wire width planning and performance optimization for very large scale integration (VLSI) interconnects. Two simplified wire sizing schemes are described for the VLSI interconnect, namely a single-width sizing (1-WS) or a two-width sizing (2-WS). These simplified wire sizing schemes have near optimal performance as compared to more complex wire sizing schemes with many or even an infinite number of wire widths. A wire width planning method is then described to determine a small set of globally optimal wire widths for the VLSI interconnects in a range of lengths. It is concluded that near optimal interconnect performance can be achieved by using such pre-designed, limited number of wire widths (usually two-width design is adequate). The layout for the VLSI interconnects is then generated and optimized using the limited number of wire widths.
Claims
exact text as granted — not AI-modifiedWhat is claimed is:
1. A method for wire width planning and performance optimization for a very large scale integration (VLSI) interconnect, comprising:
(a) determining a small number of globally optimal wire widths for the VLSI interconnect in a range of interconnect lengths; and
(b) generating an optimized layout for the VLSI interconnect using the small number of globally optimal wire widths.
2. The method of claim 1 , wherein the determining and generating steps are guided by a metric including both area and delay for the VLSI interconnect.
3. The method of claim 1 , wherein the determining and generating steps further comprise two wire sizing optimization schemes for the VLSI interconnect, including single-width sizing (1-WS) and two-width sizing (2-WS).
4. The method of claim 3 , wherein the single-width sizing (1-WS) computes an optimal wire sizing (OWS) with a uniform wire width for the VLSI interconnect.
5. The method of claim 3 , wherein the two-width sizing (2-WS) computes an optimal wire sizing (OWS) with two optimal wire widths together with a length for each of the two optimal wire widths for the VLSI interconnect.
6. The method of claim 3 , wherein the single-width sizing (1-WS) and the two-width sizing (2-WS) approximate an optimal wire sizing (OWS) with a plurality of wire widths in both delay and area, and achieve close to optimal performance under a fixed effective-fringing capacitance coefficient for the VLSI interconnect.
7. The method of claim 3 , wherein the two-width sizing (2-WS) approximates an optimal global interconnect sizing and spacing (GISS) with a plurality of wire widths in both delay and area, and achieves close to optimal performance under a fixed pitch-spacing for the VLSI interconnect.
8. The method of claim 1 , wherein the determining step further comprises planning the small number of globally optimal wire widths for the range of interconnect lengths.
9. The method of claim 8 , wherein planning step further comprises finding at least one-width vector {right arrow over (W)} with the small number of globally optimal wire widths for the range of interconnect lengths l min to l max such that an objective function: Φ ( W → , l m i n , l m a x ) = ∫ l m i n l m a x λ ( l ) · f ( W → , l ) l
is minimized, wherein λ(l) is a weighting function for l, and f({right arrow over (W)}, l) is the objective function for an interconnect length l using {right arrow over (W)}.
10. The method of claim 9 , wherein f({right arrow over (W)}, l)=A j ({right arrow over (W)}, l) T k ({right arrow over (W)}, l) with A ({right arrow over (W)}, l) being an area using {right arrow over (W)} and T({right arrow over (W)}, l) being a delay using {right arrow over (W)} that provides an area-delay tradeoff in the objective function.
11. The method of claim 10 , wherein j=1 and k=4 for an area-efficient performance optimization.
12. The method of claim 9 , wherein {right arrow over (W)} has one component W for one-width planning for the range of interconnect lengths.
13. The method of claim 9 , wherein {right arrow over (W)} has two components W 1 and W 2 for two-width planning for the range of interconnect lengths.
14. The method of claim 9 , further comprising finding a best one-width planning, two-width planning, or wire-width planning with a small number of wire widths to minimize the objective function.
15. The method of claim 14 , wherein the two-width planning achieves close to optimal performance in both delay and area for the range of interconnect lengths.
16. The method of claim 9 , further comprising determining a maximum error δ max using a weighting function λ(l), wherein if f ( W → , l ) - f ( W → * , l ) f ( W → * , l ) ≤ δ m a x for any l ∈ ( l m i n , l m a x )
then for the weighting function λ(l): Φ ( W → , l m i n , l m ax ) - Φ ( W → * , l m i n , l m a x ) Φ ( W * , l m i n , l m a x ) ≤ δ m a x
and Φ({right arrow over (W)}, l min ,l max ) is an optimization metric for the interconnect lengths l min to l max .
17. The method of claim 8 , further comprising planning the small number of globally optimal wire widths for the range of interconnect lengths per metal layer of the VLSI interconnect to achieve near-optimal performance.
18. An apparatus for wire width planning and performance optimization for a very large scale integrated (VLSI) interconnect, comprising:
(a) a computer;
(b) means, performed by the computer, for:
(1) determining a small number of globally optimal wire widths for the VLSI interconnect in a range of interconnect lengths; and
(2) generating an optimized layout for the VLSI interconnect using the small number of globally optimal wire widths.
19. The apparatus of claim 18 , wherein the means for determining and generating are guided by a metric including both area and delay for the VISI interconnect.
20. The apparatus of claim 18 , wherein the means for determining and generating further comprise two wire sizing optimization schemes for the VLSI interconnect, including single-width sizing (1-WS) and two-width sizing (2-WS).
21. The apparatus of claim 20 , wherein the single-width sizing (1-WS) computes an optimal wire sizing (OWS) with a uniform wire width for the VLSI interconnect.
22. The apparatus of claim 20 , wherein the two-width sizing (2-WS) computes an optimal wire sizing (OWS) with two optimal wire widths together with a length for each of the two optimal wire widths for the VLSI interconnect.
23. The apparatus of claim 20 , wherein the single-width sizing (1-WS) and the two-width sizing (2-WS) approximate an optimal wire sizing (OWS) with a plurality of wire widths in both delay and area, and achieve close to optimal performance under a fixed effective-fringing capacitance coefficient for the VLSI interconnect.
24. The apparatus of claim 20 , wherein the two-width sizing (2-WS) approximates an optimal global interconnect sizing and spacing (GISS) with a plurality of wire widths in both delay and area, and achieves close to optimal performance under a fixed pitch-spacing for the VLSI interconnect.
25. The apparatus of claim 18 , wherein the means for determining further comprises means for planning the small number of globally optimal wire widths for the range of interconnect lengths.
26. The apparatus of claim 25 , wherein the means for planning further comprises means for finding at least one-width vector {right arrow over (W)} with the small number of globally optimal wire widths for the range of interconnect lengths l min to l max such that an objective function: Φ ( W → , l m i n , l m a x ) = ∫ l m i n l m a x λ ( l ) · f ( W → , l ) l
is minimized, wherein λ(l) is a weighting function for l, and f({right arrow over (W)}, l) is the objective function for an interconnect length l using {right arrow over (W)}.
27. The apparatus of claim 26 , wherein f({right arrow over (W)}, l)=A j ({right arrow over (W)}, l) T k ({right arrow over (W)}, l) with A({right arrow over (W)}, l) being an area using {right arrow over (W)} and T({right arrow over (W)}, l) being a delay using {right arrow over (W)} that provides an area-delay tradeoff in the objective function.
28. The apparatus of claim 27 , wherein j=1 and k=4 for an area-efficient performance optimization.
29. The apparatus of claim 26 , wherein {right arrow over (W)} has one component W for one-width planning for the range of interconnect lengths.
30. The apparatus of claim 26 , wherein {right arrow over (W)} has two components W 1 and W 2 for two-width planning for the range of interconnect lengths.
31. The apparatus of claim 26 , further comprising means for finding a best one-width planning, two-width planning, or wire-width planning with a small number of wire widths to minimize the objective function.
32. The apparatus of claim 31 , wherein the two-width planning achieves close to optimal performance in both delay and area for the range of interconnect lengths.
33. The apparatus of claim 26 , further comprising means for determining a maximum error δ max using a weighting function λ(l), wherein if f ( W → , l ) - f ( W → * , l ) f ( W → * , l ) ≤ δ m a x for any l ∈ ( l m i n , l m a x )
then for the weighting function λ(l): Φ ( W → , l m i n , l m a x ) - Φ ( W → * , l m i n , l m a x ) Φ ( W * , l m i n , l m a x ) ≤ δ m a x
and Φ({right arrow over (W)}, l min , l max ) is an optimization metric for the interconnect lengths l min to l max .
34. The apparatus of claim 25 , further comprising means for planning the small number of globally optimal wire widths for the range of interconnect lengths per metal layer of the VLSI interconnect to achieve near-optimal performance.
35. An article of manufacture embodying logic for performing a method for wire width planning and performance optimization for a very large scale integrated (VLSI) interconnect, the method comprising:
(a) determining a small number of globally optimal wire widths for the VLSI interconnect in a range of interconnect lengths; and
(b) generating an optimized layout for the VLSI interconnect using the small number of globally optimal wire widths.
36. The method of claim 35 , wherein the determining and generating steps are guided by a metric including both area and delay for the VLSI interconnect.
37. The method of claim 35 , wherein the determining and generating steps further comprise two wire sizing optimization schemes for the VLSI interconnect, including single-width sizing (1-WS) and two-width sizing (2-WS).
38. The method of claim 37 , wherein the single-width sizing (1-WS) computes an optimal wire sizing (OWS) with a uniform wire width for the VLSI interconnect.
39. The method of claim 37 , wherein the two-width sizing (2-WS) computes an optimal wire sizing (OWS) with two optimal wire widths together with a length for each of the two optimal wire widths for the VLSI interconnect.
40. The method of claim 37 , wherein the single-width sizing (1-WS) and the two-width sizing (2-WS) approximate an optimal wire sizing (OWS) with a plurality of wire widths in both delay and area, and achieve close to optimal performance under a fixed effective-fringing capacitance coefficient for the VLSI interconnect.
41. The method of claim 37 , wherein the two-width sizing (2-WS) approximates an optimal global interconnect sizing and spacing (GISS) with a plurality of wire widths in both delay and area, and achieves close to optimal performance under a fixed pitch-spacing for the VLSI interconnect.
42. The method of claim 35 , wherein the determining step further comprises planning the small number of globally optimal wire widths for the range of interconnect lengths.
43. The method of claim 42 , wherein planning step further comprises finding at least one-width vector {right arrow over (W)} with the small number of globally optimal wire widths for the range of interconnect lengths l min to l max such that an objective function: Φ ( W → , l m i n , l m a x ) = ∫ l m i n l m a x λ ( l ) · f ( W → , l ) l
is minimized, wherein λ(l) is a weighting function for l, and f({right arrow over (W)}, l) is the objective function for an interconnect length l using {right arrow over (W)}.
44. The method of claim 43 , wherein f({right arrow over (W)}, l)=A j ({right arrow over (W)}, l) T k ({right arrow over (W)}, l) with A ({right arrow over (W)}, l) being an area using {right arrow over (W)} and T({right arrow over (W)}, l) being a delay using {right arrow over (W)} that provides an area-delay tradeoff in the objective function.
45. The method of claim 44 , wherein j=1 and k=4 for an area-efficient performance optimization.
46. The method of claim 43 , wherein {right arrow over (W)} has one component W for one-width planning for the range of interconnect lengths.
47. The method of claim 43 , wherein {right arrow over (W)} has two components W 1 and W 2 for two-width planning for the range of interconnect lengths.
48. The method of claim 43 , further comprising finding a best one-width planning, two-width planning, or wire-width planning with a small number of wire widths to minimize the objective function.
49. The method of claim 48 , wherein the two-width planning achieves close to optimal performance in both delay and area for the range of interconnect lengths.
50. The method of claim 43 , further comprising determining a maximum error δ max using a weighting function λ(l), wherein if f ( W → , l ) - f ( W → * , l ) f ( W → * , l ) ≤ δ m a x for any l ∈ ( l m i n , l m a x )
then for the weighting function λ(l): Φ ( W → , l m i n , l m a x ) - Φ ( W → * , l m i n , l m a x ) Φ ( W * , l m i n , l m a x ) ≤ δ m a x
and Φ({right arrow over (W)}, l min , l max ) is an optimization metric for the interconnect lengths l min to l max .
51. The method of claim 42 , further comprising planning the small number of globally optimal wire widths for the range of interconnect lengths per metal layer of the VLSI interconnect to achieve near-optimal performance.
52. A very large scale integration (VLSI) interconnect generated using a method for wire width planning and performance optimization, wherein the method comprises:
(a) determining a small number of globally optimal wire widths for the VLSI interconnect in a range of interconnect lengths; and
(b) generating an optimized layout for the VLSI interconnect using the small number of globally optimal wire widths.
53. The method of claim 52 , wherein the determining and generating steps are guided by a metric including both area and delay for the VLSI interconnect.
54. The method of claim 52 , wherein the determining and generating steps further comprise two wire sizing optimization schemes for the VLSI interconnect, including single-width sizing (1-WS) and two-width sizing (2-WS).
55. The method of claim 54 , wherein the single-width sizing (1-WS) computes an optimal wire sizing (OWS) with a uniform wire width for the VLSI interconnect.
56. The method of claim 54 , wherein the two-width sizing (2-WS) computes an optimal wire sizing (OWS) with two optimal wire widths together with a length for each of the two optimal wire widths for the VLSI interconnect.
57. The method of claim 54 , wherein the single-width sizing (1-WS) and the two-width sizing (2-WS) approximate an optimal wire sizing (OWS) with a plurality of wire widths in both delay and area, and achieve close to optimal performance under a fixed effective-fringing capacitance coefficient for the VLSI interconnect.
58. The method of claim 54 , wherein the two-,width sizing (2-WS) approximates an optimal global interconnect sizing and spacing (GISS) with a plurality of wire widths in both delay and area, and achieves close to optimal performance under a fixed pitch-spacing for the VLSI interconnect.
59. The method of claim 52 , wherein the determining step further comprises planning the small number of globally optimal wire widths for the range of interconnect lengths.
60. The method of claim 59 , wherein planning step further comprises finding at least one-width vector {right arrow over (W)} with the small number of globally optimal wire widths for the range of interconnect lengths l min to l max such that an objective function: Φ ( W → , l m i n , l m a x ) = ∫ l m i n l m a x λ ( l ) · f ( W → , l ) l
is minimized, wherein λ(l) is a weighting function for l, and f({right arrow over (W)}, l) is the objective function for an interconnect length l using {right arrow over (W)}.
61. The method of claim 60 , wherein f({right arrow over (W)}, l)=A j ({right arrow over (W)}, l) T k ({right arrow over (W)}, l) with A({right arrow over (W)}, l) being an area using {right arrow over (W)} and T({right arrow over (W)}, l) being a delay using {right arrow over (W)} that provides an area-delay tradeoff in the objective function.
62. The method of claim 61 , wherein j=1 and k=4 for an area-efficient performance optimization.
63. The method of claim 60 , wherein {right arrow over (W)} has one component W for the one-width planning for the range of interconnect lengths.
64. The method of claim 60 , wherein {right arrow over (W)} has two components W 1 and W 2 for two-width planning for the range of interconnect lengths.
65. The method of claim 60 , further comprising finding a best one-width planning, two-width planning, or wire-width planning with a small number of wire widths to minimize the objective function.
66. The method of claim 65 , wherein the two-width planning achieves close to optimal performance in both delay and area for the range of interconnect lengths.
67. The method of claim 60 , further comprising determining a maximum error δ max using a weighting function λ(l), wherein if f ( W → , l ) - f ( W → * , l ) f ( W → * , l ) ≤ δ m a x for any l ∈ ( l m i n , l m a x )
then for the weighting function λ(l): Φ ( W → , l m i n , l m a x ) - Φ ( W → * , l m i n , l m a x ) Φ ( W * , l m i n , l m a x ) ≤ δ m a x
and Φ({right arrow over (W)}, l min , l max ) is an optimization metric for the interconnect lengths l min to l max .
68. The method of claim 59 , further comprising planning the small number of globally optimal wire widths for the range of interconnect lengths per metal layer of the VLSI interconnect to achieve near-optimal performance.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.