Keywords

3-D net timing optimization; multipin 3-D nets; Elmore delay; timing driven multi-TSV placement

11.1 Timing Driven Via Placement for Intertier Interconnect Trees

The problem of placing vias in intertier trees to decrease the delay of these trees is investigated in this section. A simple intertier interconnect tree (also called for simplicity an interconnect tree) is illustrated in Fig. 11.1A, while related terminology is listed in Table 11.1. The sinks of the tree are located on different physical tiers within a 3-D stack. Subtrees not directly connected to the intertier vias, which do not contain any intertier vias (i.e., intratier trees), are also shown. The interconnect segments from each physical tier are denoted by a solid line of varying thickness. Different objective functions can be applied to optimize the performance of an interconnect structure. In this chapter, the weighted summation of the distributed Elmore delay of the branches of an interconnect tree is considered as the objective function,

$T_w=\sum _{\forall s_{\mathit{pq}}}{w}_{s_{\mathit{pq}}}{T}_{s_{\mathit{pq}}},$ (11.1)

(11.1)

where $w_{s_{\mathit{pq}}}$ and $T_{s_{\mathit{pq}}}$ are, respectively, the weight and distributed Elmore delay of sink s_pq. The weights are assigned to the sinks according to the criticality of the sinks. For a via connecting multiple interconnect segments, or equivalently, for a via with degree greater than two, there are several candidate directions d_i along which the delay can be decreased. The placement of vias along these directions is constrained by the lengths $l_{d_i}$, as shown in Fig. 11.1B, where the $l_{d_i}$ terms are not generally equal. In addition, vias can span more than one physical tier. For example, consider the via connecting sinks s₂₃ and s₃₃. This via traverses two physical tiers, where the allowed interval for placing the via can be different for each tier.

Table 11.1

Notation for Two-Terminal Nets and Interconnect Trees

Notation	Definition
RS	Driver resistance
CL	Load capacitance
rj (cj)	Resistance (capacitance) per unit length of horizontal segment j
rvj (cvj)	Resistance (capacitance) per unit length of intertier via vj
Rj (Cj)	Total interconnect resistance (capacitance) of horizontal segment j
Rvj (Cvj)	Total interconnect resistance (capacitance) of intertier via vj
$R_{u_j}$	Upstream resistance of the allowed interval of via vj
$R_{u_{\mathit{ij}}}$	Common upstream resistance of the allowed interval of via vi and vj
di	Candidate direction for a type-2 move
$C_{d{v}_j}$	Total downstream capacitance of the allowed interval of via vj (in every direction di)
$P_{s_{\mathit{pq}}}$	Path from root of the tree to sink spq
$P_{s_{\mathit{pq}}{v}_j}$	Path to sink spq including vj in every candidate direction
Ukj	Set of vias located upstream of vj up to and including vk, and belonging to at least one path $P_{s_{\mathit{pq}}{v}_j}$
$\overline{P_{s_{\mathit{pq}}{v}_j}}$	Path to sink spq that does not include vj
$\overline{P_{s_{\mathit{pq}}{U}_{\mathit{kj}}}}$	Path to sink spq that does not include any of the vias in the set Ukj
$P_{s_{\mathit{pq}}{v}_j{d}_i}$	Path to sink spq that includes vj and belongs to direction di
$\overline{P_{s_{\mathit{pq}}{v}_j{d}_i}}$	Path to sink spq including vj in every candidate direction except for di
$C_{d{v}_j{d}_i}$	Downstream capacitance of the allowed interval of via vj for the paths $P_{s_{\mathit{pq}}{v}_j{d}_i}$
$C_{d{v}_j\overline{d_i}}$	Downstream capacitance of the allowed interval of via vj for the paths $\overline{P_{s_{\mathit{pq}}{v}_j{d}_i}}$

Three different types of moves for an intertier via are defined. A type-1 move is shown in Fig. 11.2A. This type of move requires the insertion of an intratier via (to preserve connectivity), as depicted by a dot in Fig. 11.2A. In the following analysis, the effect of these additional intratier vias on the delay of the tree is assumed to be insignificant. The impedance characteristics of the intratier vias are assumed to be considerably lower than the impedance characteristics of the intertier vias [436], particularly if bulk CMOS technology is used for the upper tiers. Alternatively, this effect can be included by appropriately shrinking the length of the allowed interval of the intertier via.

A type-2 move is shown in Fig. 11.2B. A type-2 move differs from a type-1 move in that an additional interconnect segment of length Δl is inserted. Although an additional interconnect segment is required for this type of move, a reduction in the delay of the tree can occur. The segments of length Δl illustrated in Fig. 11.2B are located on the same y-coordinate but on different physical tiers, yet are shown on different coordinates for added clarity.

Another type of move is illustrated in Fig. 11.2C, where additional intertier vias are inserted, and is denoted as a type-3 move. This type of move is not permitted for two reasons. The additional intertier vias outweigh the reduction in delay resulting from optimizing the length of the connected segments due to the high impedance characteristics of the intertier vias. Additional intertier vias also increase the vertical interconnect density, which is undesirable. The routing congestion also increases as these vias typically block the metal layers within a tier, adversely affecting the length of the allowed intervals for the remaining nets.

As with two-terminal nets, certain constraints on the total length of each source to sink path apply to interconnect trees

$L_{s_{\mathit{pq}}}=l_1+l_{v1}+\dots +l_j+l_{v_j}+\dots +l_{v_{n-1}}+l_n,$ (11.2)

(11.2)

where l_j and l_vj are, respectively, the length of the horizontal segment j and via v_j which describe the path from the root of the tree to the sink s_pq. The number of segments that constitute the path to this sink is denoted as n. The constraint in (11.2) is adapted to consider any increase in wirelength that can result from a type-2 move for some branches of the tree. In addition, the length of each segment of the tree and the via placement are also constrained by

$l_{j\min }\le l_j+l_{\mathit{di}, j-1}+l_{j\min }+l_{\mathit{di}, j},\forall i\in \left\{w,e,s,n\right\},\forall j\in [2,n-1]\mathrm{and}{l}_{\mathit{di},0}=l_{\mathit{di},n}=0,$ (11.3)

(11.3)

$0\le x_j\le l_{\mathit{di}, j},\forall i\in \left\{w,e,s,n\right\}.$ (11.4)

(11.4)

Consequently, the constrained optimization problem for placing a via within an intertier interconnect tree can be described as

With similar reasoning as for two-terminal nets, (P1) typically includes an indefinite quadratic form l^TAl, where A is the matrix described in Eq. (7.20) adapted for interconnect trees. Certain transformations can be applied to convert (P1) into a convex optimization problem [430]; the objective functions, however, are no longer quadratic. Alternatively, accurate heuristics are described in the following section to determine the location of the vias that minimizes the delay of the intertier interconnect trees.

11.2 Multiterminal Interconnect Via Placement Heuristics

Near-optimal heuristics for placing vias in interconnect trees in 3-D circuits are presented in this section. Initially, a heuristic for minimizing the weighted delay of the sinks of an intertier tree is described in Section 11.2.1. A second heuristic for optimizing the delay of a critical path in an intertier tree is discussed in Section 11.2.2.

11.2.1 Interconnect Trees

In this section, placing an intertier via within an interconnect tree in a 3-D circuit to minimize the summation of the weighted Elmore delay of the branches of the tree is described. Since several moves for intertier vias are possible, as discussed in Section 11.1, the expressions that determine the via location are different in multiterminal nets. To determine which type of move for those vias with a degree of connectivity greater than two will yield a decrease in the delay of the tree, the following conditions apply.

Condition 1

If r_j>r_j+1, only a type-1 move for v_j can reduce the delay of the tree.

Proof

The proposition is analytically proven in Appendix D. The condition can also be intuitively explained. A type-2 move increases by Δl the length of segment j. The reduction in l_j+1 is counterbalanced by the additional segment with length Δl on the j+1 tier (see Fig. 11.2B). Consequently, the total capacitance of the tree increases. If condition 1 is satisfied, a type-2 move also increases the total resistance of the tree and, therefore, the delay of the tree will only increase by this via move.

Condition 2

For a candidate direction d_i, if r_j<r_j+1 and

$\sum _{\forall s_{\mathit{pq}}\in \overline{P_{s_{\mathit{pq}}{v}_j{d}_i}}}{w}_{s_p}\left(r_j+r_{j+1}\right)C_{d_{\mathit{vj}}\overline{d_i}}\le \sum _{\forall s_{\mathit{pq}}\in P_{s_{\mathit{pq}}{v}_j{d}_i}}{w}_{s_p}\left(r_{j+1}-r_j\right)C_{d_{\mathit{vj}}{d}_i},$ (11.5)

(11.5)

is satisfied, a type-2 move can reduce the delay of the tree.

Proof

This condition is also intuitively demonstrated. All of the interconnect segments located upstream from v_j see an increase in the capacitance by c_j Δl, increasing the delay of each downstream sink v_j. Consequently, only a reduction in the resistance can decrease the delay of the tree. Alternatively, the sinks located downstream of via v_j on the candidate direction d_i see a reduction in the upstream resistance by (r_j−r_j+1)Δl<0, while the sinks downstream of via v_j on the other directions see an increase in the upstream resistance by (r_j+r_j+1)Δl. For a type-2 move, both the weighted sum of these two components as determined by the weight of the sinks and the downstream capacitances must be negative, resulting in a decrease in the delay of the tree.

Condition 2 is evaluated for each via of a tree with degree greater than two. If (11.5) is satisfied for more than one direction, the direction that produces the greatest value of the right hand side (RHS) of (11.5) is considered the optimum direction for that via. Finally, note that both conditions 1 and 2 are only necessary and not sufficient conditions. Following the notation listed in Table 11.1, the critical point for a via connecting two segments on tiers j and j+1 and satisfying condition 1 is

$x_{\mathit{type}-1}=\left[\begin{array}{c}\frac{\left(\sum _{v_i\in U_{1j}}\sum _{s_m\in \overline{P_{s_m{U}_{\mathit{ij}}}}}{w}_{s_m}{R}_{u_{\mathit{ij}}}+\sum _{s_p\in P_{s_p{v}_j}}{w}_{s_p}{R}_{u_j}\right)\left(c_{j+1}-c_j\right)-l_{v_j}\left(r_j{c}_{v_j}-r_{v_j}{c}_{j+1}\right)}{\sum _{s_p\in P_{s_p{v}_j}}{w}_{s_p}\left(r_j{c}_j+r_{j+1}{c}_{j+1}-2r_j{c}_{j+1}\right)}\\ +\frac{\left(r_j-r_{j+1}\right)\left(c_{j+1}{l}_{d_w}+C_{{\mathit{dv}}_j}\right)}{\sum _{s_p\in P_{s_p{v}_j}}{w}_{s_p}\left(r_j{c}_j+r_{j+1}{c}_{j+1}-2r_j{c}_{j+1}\right)}\end{array}\right].$ (11.6)

(11.6)

For a type-2 move along a candidate direction d_i, the critical point for a via connecting two segments on tiers j and j+1 is

$x_{\mathit{type}-2}=\left[\begin{array}{c}\frac{\sum _{s_p\in P_{s_p{v}_j{d}_i}}{w}_{s_p}{r}_{j+1}\left(C_{d{v}_j{d}_i}+c_{j+1}{l}_{d_i}\right)-\sum _{v_i\in U_{1j}}\sum _{s_m\in \overline{P_{s_m{U}_{\mathit{ij}}}}}{w}_{s_m}{R}_{u_{\mathit{ij}}}{c}_k}{\sum _{s_p\in P_{s_p{v}_j}}{w}_{s_p}\left(r_j{c}_j+r_{j+1}{c}_{j+1}\right)}\\ -\frac{\sum _{s_p\in P_{s_p{v}_j}}{w}_{s_p}\left(r_j{c}_{v_j}-c_{j+1}{l}_{d_i}+C_{d_j}+r_{j+1}{C}_{d{v}_j\overline{d_i}}+R_{u_j}{c}_k\right)}{\sum _{s_p\in P_{s_p{v}_j}}{w}_{s_p}\left(r_j{c}_j+r_{j+1}{c}_{j+1}\right)}\end{array}\right]$ (11.7)

(11.7)

11.2.2 Single Critical Sink Interconnect Trees

Cases exist where the delay of only one branch of a tree requires optimization. Although the heuristic presented in the previous section can be used for this type of tree, a computationally simpler, yet accurate, optimization procedure for single critical net trees is described here. Denoting the critical sink of the tree by s_c, the weight for this sink w_sc is one, while the assigned weight for the remaining sinks are zero. Consequently, the expression that minimizes the delay is significantly simplified. In addition, the approach is different as compared to the optimization problem discussed in the previous section. More specifically, those intertier vias that belong to the critical branch (the on path vias) are placed according to the heuristic for two-terminal nets. There is no need to test conditions 1 and 2 for these vias, as any type-2 move only occurs in the direction that includes the critical sink. Regarding those vias that are not part of the critical path (the off path vias), these vias are placed to minimize the capacitance of the tree. A simple interconnect tree depicting this terminology is illustrated in Fig. 11.3. This situation occurs since the noncritical sinks of the tree only contribute as capacitive loads to the delay of the critical sink.

The location of the off path vias is readily determined since the impedance characteristics of the interconnect segments are known. Note that in this case, the placement of the off path vias is always optimal. Any loss of optimality is due to the location of the on path vias. As the near-optimal two-terminal net heuristic is used to place the on path vias, the loss of optimality is negligible. In the following section, these heuristics are used to develop efficient algorithms for placing vias in multiterminal nets in 3-D ICs.

11.3 Via Placement Algorithms for Interconnect Trees

Efficient near-optimal algorithms for placing vias among intertier interconnects are presented in this section. Based on the aforementioned heuristic described in Section 11.2.1, an efficient algorithm for intertier interconnect trees is presented in Section 11.3.1. A second algorithm that places intertier vias to minimize the delay for the particular case of interconnect trees with a single critical branch is discussed in Section 11.3.2.

11.3.1 Interconnect Tree Via Placement Algorithm (ITVPA)

The via placement optimization algorithm for multiterminal nets is presented in this section. The input to the algorithm is an intertier interconnect tree where the minimum length of the segments, the weight of the sinks, and the length of the allowed intervals are provided. Pseudocode of the algorithm is shown in Fig. 11.4. Due to the different types of possible moves in intertier interconnect trees, the candidate direction for via placement is initially determined in steps one through five. The move_type routine operates from a leaf to the root, where the type and direction of the move of each via of the tree have a degree greater than two. Conditions 1 and 2 are tested for each via and direction. For those vias at the last level of the tree (close to the sinks), the downstream capacitance is determined. Alternatively, for those vias that belong to the next level closer to the root, the downstream capacitance cannot be accurately determined, and (11.5) is evaluated for the extreme values of C_dvj. If (11.5) is satisfied for only one of these extrema, a via can be placed along a nonoptimal direction, resulting in loss of optimality. Such instances, however, are not typically encountered, as discussed in the following section. In step six, the optimize_tree_delay routine places the vias within a tree to minimize (11.1). This routine is a slight modification of the algorithm used for two-terminal nets.

11.3.2 Single Critical Sink Interconnect Tree Via Placement Algorithm

Although the heuristic presented in Section 11.2.2 can be used to improve the delay of trees with a single critical path, a simpler optimization procedure for single critical net trees is described in this section. The input to the single critical sink via placement algorithm (SCSVPA) is a description of the intertier interconnect tree where the minimum length of the segments, the weight of the sinks, and the length of the allowed intervals are provided. Pseudocode of the algorithm is shown in Fig. 11.5. In steps one to three, each of the off path vias is placed at the location that minimizes the capacitance within the corresponding allowed interval. The direction that includes the critical sink of the tree is set by the direction_move routine as the direction along which the on path vias can be placed. In step five, the optimize_tree_delay routine is utilized to determine the location of the on path vias. As previously mentioned, any loss of optimality for this type of tree results from the heuristic that places the via in two-terminal nets. As described in Chapter 10, Timing Optimization for Two-Terminal Interconnects, this heuristic produces results similar to optimization solvers. SCSVPA naturally exhibits significantly lower computational time as compared to general purpose solvers.

11.4 Discussion of Via Placement Results

These algorithms are applied to several example intertier interconnect trees to evaluate efficiency and accuracy. Trees for a different number of tiers and sinks are analyzed. A discussion of the limitations of these algorithms is provided in this section. The impedance characteristics of the horizontal segments and vias are extracted for several interconnect structures using a commercial impedance extraction tool [423]. Copper interconnect is assumed with an effective resistivity of 2.2 μΩ-cm. Based on the extracted impedances, the resistance and capacitance of the horizontal segments range, respectively, from 25 to 125 Ω/mm and 100 to 300 fF/mm, respectively, for a 90 nm CMOS technology node [252,432]. The cross-section of the vias is 1 μm×1 μm, with 1 μm spacing from the surrounding horizontal metal layers, assuming a silicon on insulator (SOI) process, as described in [307]. The total and minimum length of each horizontal segment is randomly generated for each of the interconnect structures. For simplicity, all of the vias connect the segments of two adjacent physical tiers. The savings in delay that can be achieved by optimally placing the vias is listed in Table 11.2 for different via placement scenarios.

In Table 11.2, the optimization results for interconnect trees with different number of sinks and tiers are reported. The accuracy and efficiency of ITVPA are similar to that of TTVPA (discussed in Chapter 10, Timing Optimization for Two-Terminal Interconnects) as the optimization routine for ITVPA is the same as in TTVPA, after a move type and direction have correctly been determined. As mentioned in Section 11.3.1, a nonoptimal direction can be selected to place a via. A nonoptimal direction for via placement, however, can only be chosen if the connected branches are slightly asymmetric (i.e., have similar impedance characteristics and criticality). In these cases, the value of the downstream capacitance and weight of these branches are close, making the weighted delay of these sinks similar. For these slightly asymmetric branches, (11.7) yields x^*_type-2=0 for type-2 moves, meaning that if a nonoptimal direction is chosen, the delay of the tree is not affected. Alternatively, a type-2 move usually occurs for highly asymmetric trees where the delay of a branch dominates the delay of the tree. As described in (11.5), the type of move for an intertier via depends upon the weight of the branches and the impedance characteristics of the interconnect segments. Consider the symmetric tree shown in Fig. 11.6. The difference in the criticality and impedance of the branches is captured from the value of the assigned weights.

In Table 11.3, the optimum location for via v₂ is listed for different weights. From these values, note that a type-2 move for via v₂ only occurs when branch s₂ dominates the delay of the tree. When the assigned weight of the branches of the tree is of similar value, a type-2 move does not occur as this move would only increase the interconnect delay of the tree, as determined by the ITVPA (i.e., x_j*=Δx_j). Consequently, for a type-2 move, if the weight of the sinks, which originate from a via, are similar, the algorithm does not allow the via to be relocated.

The improvement in delay of the interconnect trees is listed in columns 6 through 9 of Table 11.2. The results are compared to the case where the vias are initially placed at the center of the allowed interval (i.e., x_i=l_di/2), and to the case where the vias are placed at the lower edge of the allowed interval (i.e., x_i=0). The improvement in delay depends upon the length of the allowed interval. This dependence, however, is weak as compared to two-terminal nets. In addition, the improvement in delay is lower than point-to-point nets for the same allowed length intervals. This reduction in delay improvement occurs for two reasons.

For those vias with degree greater than two, which constitute the majority of intertier vias in interconnect trees, after the type of move for each via is determined, the actual interval length that these vias are allowed to move is l_di/2 and not l_di (see Fig. 11.2). Furthermore, in ITVPA, any modification to the routing tree is strictly confined within the allowed interval which least affects the routing tree. This constraint requires an additional interconnect segment for type-2 moves. If this constraint is relaxed, an additional interconnect segment is not necessary and the length of the interconnect segments can be further reduced, resulting in a considerably greater improvement in speed. Maintaining fixed paths limits the efficiency of the algorithms; however, these algorithms are applicable to placement and routing tools for 3-D ICs as long as these tools provide an allowed interval for via placement. In addition, interconnect routing can consider other important design objectives such as thermal effects or routing congestion. These algorithms for placing vias in multiterminal nets can be applied as a subsequent post-processing step without significantly affecting the initial layout produced by existing tools.

In Table 11.4, placement results for single critical branch interconnect trees are reported. The improvement in the delay of these trees is listed in columns 6 through 9 of Table 11.4, as compared to the situation where the vias are initially placed at the center of the allowed interval (i.e., x_i=l_di/2) and where the vias are placed at the lower edge of the allowed interval (i.e., x_i=0). This improvement is lower than for those interconnect trees listed in Table 11.2 as only type-1 moves can occur for the off path vias. Indeed, any type-2 move for the off path via only increases the off path capacitance and, in turn, the delay of the critical leaf. A smaller number of vias can, therefore, be relocated to reduce the delay of the single critical sink trees. Alternatively, for off path vias, placing the via at the center of the allowed intervals usually produces an optimum placement, resulting in a smaller overall improvement in the delay of this type of tree, as is demonstrated by the test structures. This situation occurs since type-2 moves for the off path vias are not allowed as a type-2 move increases the off path capacitance.

Typically, the larger the allowed interval, the greater the improvement in delay. Consequently, efficient placement tools for 3-D circuits that generate sufficiently large allowed intervals are desired. These intervals can be available space reserved for intertier interconnect routing (i.e., white space). For interconnect trees, the improvement in delay is smaller than for two-terminal nets. This decreased improvement in delay is due to the constraint of placing the vias within the allowed intervals to minimally affect local routing congestion. If the placement of the vias is permitted within an entire region (e.g., the bounding box of the net), a greater decrease in delay can occur. Assigning a region for placing vias, however, increases the congestion within a 3-D circuit as the same number of vias compete for sparser routing resources.

Despite the considerably lower computational time of these algorithms, further speed improvements can be achieved if more than one net are simultaneously processed. Although these algorithms support multiple net optimization without significant modification, a single net at a time approach likely yields improved results as the most critical nets are routed first. Net ordering algorithms [26] can be used to prioritize the routing of these interconnects, permitting a considerable reduction in the delay of these nets. Additionally, since the number of intertier interconnects is small as compared to the number of intratier interconnects [291], processing these interconnects one net at a time will not significantly increase the total computational time.

Thermal issues are important in 3-D ICs, as discussed in Chapter 13, Thermal Management Strategies for Three-Dimensional ICs, where additional dummy vias are utilized to control the average and peak temperature of the upper tiers within a 3-D system. Additionally, thermally aware cell placement improves the heat distribution and removal characteristics. These two techniques are decoupled from the via placement problem, which is a later step in the design process. Consequently, thermal issues are not strongly connected with the via placement approach.

In the techniques discussed in Chapter 13, Thermal Management Strategies for Three-Dimensional ICs, the thermal vias are placed in the available space among the blocks with either uniform or nonuniform densities. Alternatively, some of the thermal vias within this available space can be replaced with signal vias connecting circuits on different tiers. Placing the signal vias prior to placing the thermal vias within these regions results in large allowed intervals, thereby improving the effectiveness of this via placement technique. In this case, where the via placement can significantly enhance the thermal profile of a physical tier, the allowed interval for some vias can be decreased or removed. This practice, however, trades off performance for thermal management.

11.5 Summary

Algorithms for timing driven placement of intertier interconnect trees are presented in this chapter. The primary characteristics of these algorithms are: