Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Appendix C

Proof of the Two-Terminal Via Placement Heuristic

A formal proof of the two terminal heuristic for placing intertier vias (e.g., TSVs) is described in this appendix. Consider the following expression that describes the critical point (i.e., the derivative of the delay is set equal to zero) for placing a via v_j, as illustrated in Fig. C.1,

$x_{j}^{*} = - [\frac{l_{v j} (r_{j} c_{v j} - r_{v j} c_{j + 1} + r_{j + 1} c_{j + 1} - r_{j} c_{j + 1}) + R_{u j} (c_{j} - c_{j + 1}) + Δ x_{j} (r_{j} - r_{j + 1}) c_{j + 1} + C_{d j} (r_{j} - r_{j + 1})}{r_{j} c_{j} - 2 r_{j} c_{j + 1} + r_{j + 1} c_{j + 1}}] .$ $x_{j}^{*} = - [\frac{l_{v j} (r_{j} c_{v j} - r_{v j} c_{j + 1} + r_{j + 1} c_{j + 1} - r_{j} c_{j + 1}) + R_{u j} (c_{j} - c_{j + 1}) + Δ x_{j} (r_{j} - r_{j + 1}) c_{j + 1} + C_{d j} (r_{j} - r_{j + 1})}{r_{j} c_{j} - 2 r_{j} c_{j + 1} + r_{j + 1} c_{j + 1}}] .$ (C.1)

(C.1)

Figure C.1 Intertier interconnect consisting of m segments connecting two circuits located n tiers apart.

From this expression, the critical point x_j is a monotonic function of the upstream resistance and downstream capacitance of the allowed interval for via v_j, denoted respectively, as R_uj and C_dj,

$x_{j}^{*} = f (R_{u j}^{*}, C_{d j}^{*}) .$ $x_{j}^{*} = f (R_{u j}^{*}, C_{d j}^{*}) .$ (C.2)

(C.2)

These quantities ( $R_{u j}^{*}$ $R_{u j}^{*}$ and $C_{d j}^{*}$ $C_{d j}^{*}$ ) depend upon the location of the other vias along the net and are unknown. However, as the allowed intervals for the vias and the impedance characteristics of the line are known, the minimum and maximum value of these impedances, $R_{u j \min}$ $R_{u j \min}$ , $R_{u j \max},$ $R_{u j \max},$ $C_{d j \min},$ $C_{d j \min},$ and $C_{d j \max}$ $C_{d j \max}$ , can be determined. Without loss of generality, assume that r_j > r_j+1 and c_j > c_j+1 (the other cases are similarly treated). For this case, the critical point (i.e., $\partial T / \partial x_{j} = 0$ $\partial T / \partial x_{j} = 0$ ) is a strictly increasing function of R_uj and C_dj. Consequently, the minimum and maximum value for the critical point $x_{j \min}^{*}$ $x_{j \min}^{*}$ and $x_{j \max}^{*}$ $x_{j \max}^{*}$ are determined from, respectively,

$x_{j \min}^{*} = f (R_{u j \min}, C_{d j \min}),$ $x_{j \min}^{*} = f (R_{u j \min}, C_{d j \min}),$ (C.3)

(C.3)

$x_{j \max}^{*} = f (R_{u j \max}, C_{d j \max}) .$ $x_{j \max}^{*} = f (R_{u j \max}, C_{d j \max}) .$ (C.4)

(C.4)

The final value of the upstream (downstream) capacitance for via v_j, which is determined after placing all of the remaining vias of the net denoted as $R_{u j}^{*} (C_{d j}^{*})$ $R_{u j}^{*} (C_{d j}^{*})$ within the range, is

$R_{u j \min} < R_{u j}^{*} < R_{u j \max}, (C_{d j \min} < C_{d j}^{*} < C_{d j \max}) .$ $R_{u j \min} < R_{u j}^{*} < R_{u j \max}, (C_{d j \min} < C_{d j}^{*} < C_{d j \max}) .$ (C.5)

(C.5)

Due to the monotonic relationship of the critical point x_j on R_uj and C_dj,

$x_{j \min}^{*} = f (R_{u j \min}, C_{d j \min}) < x_{j}^{*} = f (R_{u j}^{*}, C_{d j}^{*}) < x_{j \max}^{*} = f (R_{u j \max}, C_{d j \max}) .$ $x_{j \min}^{*} = f (R_{u j \min}, C_{d j \min}) < x_{j}^{*} = f (R_{u j}^{*}, C_{d j}^{*}) < x_{j \max}^{*} = f (R_{u j \max}, C_{d j \max}) .$ (C.6)

(C.6)

Consequently, by iteratively decreasing the range of the x_j^* according to (C.6), the location for v_j can be determined.

To better explain this iterative procedure, an example is offered in Chapter 10, Timing Optimization for Two-Terminal Interconnects, where the vias, v_i, v_j, and v_k, shown in Fig. C.1, have not yet been placed. In this example, vias v_i and v_k are assumed to belong to case (iii) of the heuristic. Since the allowed intervals for vias v_i, v_j, and v_k and the impedance characteristics of the respective horizontal segments are known, the minimum $x_{\min}^{* 0}$ $x_{\min}^{* 0}$ and maximum $x_{\max}^{* 0}$ $x_{\max}^{* 0}$ critical point for all of the segments i, j, and k are obtained. The minimum and maximum values of $R_{u i}^{0}$ $R_{u i}^{0}$ , $R_{u j}^{0}$ $R_{u j}^{0}$ , $R_{u k}^{0}$ $R_{u k}^{0}$ , $C_{d i}^{0}$ $C_{d i}^{0}$ , $C_{d j}^{0}$ $C_{d j}^{0}$ , and $C_{d k}^{0}$ $C_{d k}^{0}$ are determined, where the superscript represents the number of iterations.

From (C.6), the via location of segments i and k is contained within the limits determined by (C.1). As the interval for placing the vias v_i and v_k decreases, the minimum (maximum) value of the upstream resistance and downstream capacitance of segment j increases (decreases), that is, $R_{u j \min}^{0} < R_{u j \min}^{1},$ $R_{u j \min}^{0} < R_{u j \min}^{1},$ $C_{d j \min}^{0} < C_{d j \min}^{1},$ $C_{d j \min}^{0} < C_{d j \min}^{1},$ $R_{u j \max}^{1} < R_{u j \max}^{0},$ $R_{u j \max}^{1} < R_{u j \max}^{0},$ and $C_{d j \max}^{1} < C_{d j \max}^{0} .$ $C_{d j \max}^{1} < C_{d j \max}^{0} .$ Due to the monotonicity of x_j^* [see (C.2)–(C.4) and (C.6)] on R_uj and C_dj, $x_{j \min}^{* 0} < x_{j \min}^{* 1}$ $x_{j \min}^{* 0} < x_{j \min}^{* 1}$ and $x_{j \max}^{* 1} < x_{j \max}^{* 0}$ $x_{j \max}^{* 1} < x_{j \max}^{* 0}$ , the range of values for x_j^* therefore also decreases and, typically, after two or three iterations, the optimum location for the corresponding via is determined.

The above example is extended to each of the other possible cases that can occur for segments i and k. Specifically,

a. i and k belong to either case (i) or (ii). Both R_uj and C_dj are precisely determined or, equivalently, $R_{u j \min} = R_{u j \max}$ $R_{u j \min} = R_{u j \max}$ and $C_{d j \min} = C_{d j \max} .$ $C_{d j \min} = C_{d j \max} .$ Consequently, the placement of both vias v_i and v_k is known and $x_{j \min}^{* 0} = x_{j \max}^{* 0} = x_{j}^{*} .$ $x_{j \min}^{* 0} = x_{j \max}^{* 0} = x_{j}^{*} .$ The placement of v_j is also determined within the first iteration.

b. i belongs to case (i) or (ii) and k belongs to case (iii). R_uj is precisely determined or, equivalently, $R_{u j \min} = R_{u j \max}$ $R_{u j \min} = R_{u j \max}$ and the placement of via v_i is known. Since v_i is placed and k belongs to case (iii), $C_{d j \min}^{0} < C_{d j \min}^{1}$ $C_{d j \min}^{0} < C_{d j \min}^{1}$ and $C_{d j \max}^{1} < C_{d j \max}^{0}$ $C_{d j \max}^{1} < C_{d j \max}^{0}$ . The placement of via v_j converges faster, as only the placement of segment k remains unknown after the first iteration.

c. k belongs to case (i) or (ii) and i belongs to case (iii). C_dj is precisely determined or, equivalently, $C_{d j \min} = C_{d j \max}$ $C_{d j \min} = C_{d j \max}$ and the placement of via v_k is known. Since v_k is placed and i belongs to case (iii), $R_{u j \min}^{0} < R_{u j \min}^{1}$ $R_{u j \min}^{0} < R_{u j \min}^{1}$ and $R_{u j \max}^{1} < R_{u j \max}^{0}$ $R_{u j \max}^{1} < R_{u j \max}^{0}$ . The placement of via v_j converges faster as only the placement of segment i remains unknown after the first iteration.

d. i belongs to any of the cases (i) to (iii) and k belongs to case (iv). R_uj is readily determined [cases (i) and (ii)] or converges, as described in the previous example, $R_{u j \min}^{0} < R_{u j \min}^{1}$ $R_{u j \min}^{0} < R_{u j \min}^{1}$ and $R_{u j \max}^{1} < R_{u j \max}^{0} .$ $R_{u j \max}^{1} < R_{u j \max}^{0} .$ As k belongs to case (iv), however, C_dj does not change as in the cases above. If the decrease in the upstream resistance is sufficient to determine $x_{j}^{*}$ $x_{j}^{*}$ according to (C.1), v_j is marked as processed, otherwise v_j is marked as unprocessed and the algorithm continues to the next via. In the latter case, the placement approach is described by case (iv) of the heuristic.

e. k belongs to any of the cases (i) to (iii) and i belongs to case (iv). C_dj is readily determined [cases (i) and (ii)] or converges, as described in the previous example, implying $C_{d j \min}^{0} < C_{d j \min}^{1}$ $C_{d j \min}^{0} < C_{d j \min}^{1}$ and $C_{d j \max}^{1} < C_{d j \max}^{0}$ $C_{d j \max}^{1} < C_{d j \max}^{0}$ . As i belongs to case (iv), however, R_uj does not change as in the aforementioned cases. Overall, if the decrease in the downstream capacitance is sufficient to determine $x_{j}^{*}$ $x_{j}^{*}$ according to (C.1), v_j is marked as processed, otherwise v_j is marked as unprocessed and the algorithm continues to the next via. In the latter case, the placement approach is described by case (iv) of the heuristic.

f. Both i and k belong to case (iv). Therefore, both R_uj and C_dj cannot be bounded. Consequently, v_j is marked as unprocessed and the next via is processed. Alternatively, this sub-case degenerates to case (iv) of the heuristic presented in Chapter 10, Timing Optimization for Two-Terminal Interconnects.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for Appendix C. Proof of the Two-Terminal Via Placement Heuristic

Create new playlist

Sign In

Sign Up

Proof of the Two-Terminal Via Placement Heuristic

Table of Contents for
Appendix C. Proof of the Two-Terminal Via Placement Heuristic