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 vj, as illustrated in Fig. C.1,
(C.1)
From this expression, the critical point xj is a monotonic function of the upstream resistance and downstream capacitance of the allowed interval for via vj, denoted respectively, as Ruj and Cdj,
(C.2)
These quantities ( and ) 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, , and , can be determined. Without loss of generality, assume that rj > rj+1 and cj > cj+1 (the other cases are similarly treated). For this case, the critical point (i.e., ) is a strictly increasing function of Ruj and Cdj. Consequently, the minimum and maximum value for the critical point and are determined from, respectively,
(C.3)
(C.4)
The final value of the upstream (downstream) capacitance for via vj, which is determined after placing all of the remaining vias of the net denoted as within the range, is
(C.5)
Due to the monotonic relationship of the critical point xj on Ruj and Cdj,
(C.6)
Consequently, by iteratively decreasing the range of the xj* according to (C.6), the location for vj 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, vi, vj, and vk, shown in Fig. C.1, have not yet been placed. In this example, vias vi and vk are assumed to belong to case (iii) of the heuristic. Since the allowed intervals for vias vi, vj, and vk and the impedance characteristics of the respective horizontal segments are known, the minimum and maximum critical point for all of the segments i, j, and k are obtained. The minimum and maximum values of , , , , , and 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 vi and vk decreases, the minimum (maximum) value of the upstream resistance and downstream capacitance of segment j increases (decreases), that is, and Due to the monotonicity of xj* [see (C.2)–(C.4) and (C.6)] on Ruj and Cdj, and , the range of values for xj* 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 Ruj and Cdj are precisely determined or, equivalently, and Consequently, the placement of both vias vi and vk is known and The placement of vj is also determined within the first iteration.
b. i belongs to case (i) or (ii) and k belongs to case (iii). Ruj is precisely determined or, equivalently, and the placement of via vi is known. Since vi is placed and k belongs to case (iii), and . The placement of via vj 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). Cdj is precisely determined or, equivalently, and the placement of via vk is known. Since vk is placed and i belongs to case (iii), and . The placement of via vj 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). Ruj is readily determined [cases (i) and (ii)] or converges, as described in the previous example, and As k belongs to case (iv), however, Cdj does not change as in the cases above. If the decrease in the upstream resistance is sufficient to determine according to (C.1), vj is marked as processed, otherwise vj 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). Cdj is readily determined [cases (i) and (ii)] or converges, as described in the previous example, implying and . As i belongs to case (iv), however, Ruj does not change as in the aforementioned cases. Overall, if the decrease in the downstream capacitance is sufficient to determine according to (C.1), vj is marked as processed, otherwise vj 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 Ruj and Cdj cannot be bounded. Consequently, vj 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.