15.1.1 Method of Means and Medians

The MMM algorithm iteratively divides the clock sinks within a routing grid (or plane) with the use of cuts (i.e., bipartitions) in the x and y directions, producing two new sets of clock sinks for each cut. Assuming a set of m clock sinks, each clock sink is notated as s_i with coordinates (x_i, y_i) in the routing plane. The clock sinks can be described by the finite set $S=\left\{s_1,s_2,s_3,\dots s_m\right\}\subset {\mathfrak{R}}^2$. The location of the center of mass for this set is

$x_c=\frac{\sum _{i=1}^m{x}_i}{m},$ (15.1)

(15.1)

$y_c=\frac{\sum _{i=1}^m{y}_i}{m},$ (15.2)

(15.2)

where these coordinates constitute the root of the clock tree. To proceed with the cuts along the physical directions, an ordering of the clock sinks is utilized. Two different orderings of the clock sinks are formed by separately considering the x and y coordinates of the clock sinks in increasing order, meaning that for each element of a subset S_x(S) of the set, s_i precedes s_j in S_x(S) if x_i≤x_j. A similar rule applies to the subset S_y(S) with respect to the y-coordinate. With these orderings, four different subsets are defined around the median of each ordering,

$S_L\left(S\right)\equiv \left\{s_i\in S_x\mathrm{|}i\le \lceil \frac{m}{2}\rceil \right\},$ (15.3)

(15.3)

$S_R\left(S\right)\equiv \left\{s_i\in S_x\mathrm{|}\lceil \frac{m}{2}\rceil <i\le m\right\},$ (15.4)

(15.4)

$S_B\left(S\right)\equiv \left\{s_i\in S_y\mathrm{|}i\le \lceil \frac{m}{2}\rceil \right\},$ (15.5)

(15.5)

$S_T\left(S\right)\equiv \left\{s_i\in S_y\mathrm{|}\lceil \frac{m}{2}\rceil <i\le m\right\}.$ (15.6)

(15.6)

These four subsets are produced by applying a cut at the median of each ordering along each direction. All of these subsets contain approximately the same number of clock sinks as | |S_L|–|S_R| |≤1. The same inequality applies to the subsets S_B and S_T. The center of mass is determined for each of these new subsets. The algorithm connects these newly determined points with the center of the mass of the initial set S, which is the root of the tree. This process is repeated, producing two sets, left (L) and right (R), for each x-cut and bottom (B) and top (T) sets for each y-cut. The process terminates when each new set includes only a single clock sink.

A simple example of this algorithm is shown in Fig. 15.2, where routes between the center of mass for different sets are noted. Although routes between a center of mass and a subsequent center of mass, determined by a cut in the next iteration, are of equal length, different route lengths can occur as the algorithm progresses, as depicted in Fig. 15.2A. To address this situation, two pairs of cuts are applied. The pair of cuts leads to lower skew. This look-ahead procedure yields superior routings. As shown in Fig. 15.2B, the tree resulting from the y- and x-cuts exhibits a lower skew as compared to the tree shown in Fig. 15.2A. The complexity of the algorithm, including the look-ahead function, is O(m log m).

The MMM method ensures that after each iteration where cuts are performed, the routing path to the center of mass of the newly formed subsets is of equal length, leading to low (or zero) skew. This routing, however, is typically longer than the length of the minimum rectilinear Steiner tree (RMST) with the same set of clock sinks [403]. As described in [578], the wirelength of the generated clock tree increases proportionally to 3/2$\sqrt{m}$, while for RMST, the length of the tree grows as $(\sqrt{m}+1)$ for m points (i.e., clock sinks) uniformly distributed across a routing grid. The ratio between the two routing algorithms increases by a constant factor of approximately 1.5×, demonstrating that the wirelength overhead of the MMM method is not excessive.

To limit this additional overhead, the MMM method is used in two phases. In the first phase, where the generated cut subsets include a large number of clock sinks, the routing proceeds with the MMM method. In the second phase, where the number of clock sinks within each subset produced at later iterations is small, standard routing algorithms are preferable to guarantee minimum wirelength with a low and acceptable increase in clock skew. The depth of the tree (or number of iterations) after which a routing technique other than MMM is applied depends upon the skew that can be tolerated.

15.1.2 Deferred-Merge Embedding Method

Another popular technique that has been extended to support the synthesis of 3-D clock networks is the DME method, which is a two phase CTS technique [581,582]. The input to the method is the connectivity of the sinks within some topology (typically a tree), where the location of the sinks is known and the internal nodes are placed to ensure that zero skew is achieved at minimum wirelength (assuming a linear delay model) [581]. Consequently, the DME technique produces optimal zero skew clock networks assuming a linear delay model, while suboptimal clock trees are produced if other more complex delay models, such as the Elmore delay model, are utilized. In this case, although the results are suboptimal, these results are in general of high quality, yielding zero skew clock trees with low wirelength. The advantage of the DME method is that as compared to MMM, the wirelength is minimized in addition to constructing a zero skew clock network.

The DME technique is not constrained by the topology of the clock network and, therefore, can be applied as a post-processing step once the internal nodes of a clock tree have, for example, been generated by the MMM method. Note, however, that the choice of topology or the choice of technique to generate the clock network affects the quality of the results produced by the DME method (i.e., the total wirelength since zero skew is guaranteed).

The DME method consists of a bottom-up and a top-down phase. In the bottom-up phase the feasible placement locations of each internal node are determined. Each internal node is a parent node for the root of (two) merged subtrees. In the top-down phase, the internal nodes are embedded into one of these feasible locations, ensuring that minimum wirelength is achieved (for the linear delay model) in addition to guaranteeing zero skew for all of the sinks within the clock network.

To explain this method, some related terminology is introduced. In the MMM method, a finite set S containing m clock sinks and the corresponding location of these sinks are considered as input. A clock tree notated as T(S) is embedded by the DME method in the Manhattan plane, where the location of each internal node of the tree is determined to ensure that the skew is zero and the wirelength of the clock tree is minimum. The placement of each node is denoted as pl(u). Assuming that u is the parent node of another node w, e_w denotes the directed edge from the parent to the child node. The cost of this edge is notated as |e_w|. As the Manhattan plane embeds the clock network, this cost is equal (or larger) to the Manhattan distance between these two nodes. Accordingly, the cost of the entire tree T(S) is the sum of the wirelength of all of these edges.

Similarly, the delay of any path from source node u to node w is notated as t_d(s_u,s_w). The clock skew between two paths from the same source node is described by |t_d(s_u,s_w)–t_d(s_u,s_v)|. Assuming the root of the clock network is s_r, the clock skew of T(S) is the maximum difference |t_d(s_r,s_i)–t_d(s_r,s_j)| among all pairs of sinks s_i, s_j belonging to S. If the linear delay model is used to estimate the delay of each source-sink path, this delay is the summation of the edges constituting the path from a source node u to a sink node w,

$t_{\mathit{ld}}\left(u,w\right)={\sum }_{e_v\in \mathrm{path}(u,w)}\mathrm{|}{e}_v\mathrm{|}.$ (15.7)

(15.7)

In addition to this notation, some other definitions are required to describe the DME method. The loci for each internal node determined during the bottom-up step are called merging segments. The merging segments are line segments with slope ±1 or, alternatively, with an angle of ±45° from the x–y routing directions. Similarly, a set of points on the Manhattan plane within a fixed distance from a Manhattan arc forms a tilted rectangular region (TRR), which is inscribed within Manhattan arcs. An example of a TRR is illustrated in Fig. 15.3, where the core arc and radius of the TRR are also shown. The core arc consists of all points located farthest from the boundary of the TRR (always assuming a Manhattan distance).

Considering a node u, the merging segment ms(u) for this node is determined as follows. If u belongs to S, the merging segment is the location of the clock sink; otherwise, u is an internal node and the length and position of the merging segment depend on the merging segments of the children nodes of u. Assuming that nodes a and b are the children nodes of u and since this step proceeds in a bottom-up manner, the merging segments of nodes a and b, notated, respectively, as ms(a) and ms(b) are known and are also Manhattan arcs [581]. This situation is illustrated in Fig. 15.4. The merging segment of node u is also a Manhattan arc and is obtained by intersecting two TRRs that have as core the segments ms(a) and ms(b). Consequently, ms(u) is formally described as ms(u)=TRR_a∩TRR_b. The radius of TRR_a and TRR_b is, respectively, |e_a| and |e_b|, as also shown in the figure. The merging cost for the subtrees rooted at nodes a and b is |e_a|+|e_b|. The objective is to determine these radii (i.e., |e_a| and |e_b|) such that the merging cost is minimized and the constraint of zero skew is satisfied.

Assuming a linear delay model, the lower bound for the merging cost is equal to the minimum Manhattan distance between ms(a) and ms(b), denoted as MD_min=d(ms(a), ms(b)). If the delay of nodes a and b is highly unbalanced, the merging cost deviates from this minimum to satisfy the zero skew requirement and may require additional wiring. The requirement of zero skew at node u can be satisfied from

$t_{\mathit{ld}}\left(a\right)+\left|e_a\right|=t_{\mathit{ld}}\left(b\right)+\left|e_b\right|,$ (15.8)

(15.8)

where t_ld(a) and t_ld(b) denote, respectively, the (linear model) delay to the sinks of the subtrees rooted at nodes a and b. Note that since the zero skew requirement is satisfied at each level of the tree, these delays are the same at each sink of the subtrees from these nodes. The radius of TRR_a and TRR_b is obtained by letting |e_a|+|e_b|=MD_min, and if |t_ld(a)−t_ld(b)|≤MD_min,

$\left|e_a\right|=\frac{{{\mathit{MD}}_{\min }+t}_{\mathit{ld}}\left(b\right)-t_{\mathit{ld}}(a)}{2},$ (15.9)

(15.9)

and

$\left|e_b\right|={\mathit{MD}}_{\min }-\left|e_a\right|.$ (15.10)

(15.10)

If the condition |t_ld(a)−t_ld(b)|≤MD_min is not satisfied, additional wirelength is required to balance the skew from node u to nodes a and b, increasing the merging cost.

The bottom-up phase recursively merges the nodes of T(S) until the root node s_r is reached. The clock driver is often placed at a specific location which is not intercepted by the merging segment of the root node. An additional segment connects to s_r without degrading the performance of the resulting tree. The bottom-up phase (i.e., deferred-merge) terminates when the merging segment for the root node is obtained.

The top-down phase (i.e., embedding) follows. The exact placement of each node pl(u) is successively determined starting from the root node. For s_r, any point along ms(s_r) can, in general, be chosen as pl(s_r). For any other internal node u, any point on ms(u) can be selected as pl(u), which is at a distance |e_u| or less from the placement pl(p) of the parent node of u. From the construction of the merging segments, this location must exist [582]. An example of this situation is illustrated in Fig. 15.5.

Operation of the DME technique can be better understood with a practical example. A simple clock topology with eight sinks (e.g., s₁ to s₈) is depicted in Fig. 15.6. The assumption of the same (or zero) delay for each sink permits the TRR for each sink to be determined. As the location of each sink is known and zero delay is assumed, t_ld(s_i)=0∀s_i (15.9) and (15.10) are equal to half the Manhattan distance between each pair of sinks s_i and s_j (see Fig. 15.6A). The radius of the TRRs for each pair of sinks is the same, and the merging segment for each parent node ms_i,j is illustrated by the thick lines. In Fig. 15.6B, the merging segments of the nodes at the next upper level of the tree are obtained. Note that in this specific example, ms_1,4 is a single point as the TRRs for nodes s_1,2 and s_3,4 only intersect at one point. In Fig. 15.6C, the merging segment ms_1,8 for the root node s_r is at the intersection of the TRRs for nodes s_1,4 and s_5,8.

Since the merging segments of all nodes have been determined, the top-down phase determines the placement of the internal nodes within the tree. As previously mentioned for the root of the tree, any point along ms_1,8 can be chosen. This point is indicated by a triangle in Fig. 15.6D. To determine pl(s_1,4) and pl(s_5,8), the TRRs are shown with, respectively, radius |e_ms1,4| and |e_ms5,8| from the placement of the root node pl(s_r). As ms_1,4 corresponds to only a single point, only the TRR for node s_1,4 is plotted in Fig. 15.6D. The thickest line segment depicts the valid placement points for node s_5,8, where any point on this segment can be selected as pl(s_5,8). Similarly, the TRRs are drawn in Fig. 15.6E to determine the valid placement location for nodes s_1,2, s_3,4, s_5,6, and s_7,8. Note that for nodes s_1,2 and s_3,4, valid placements are possible only at a single point. The resulting clock tree is shown in Fig. 15.6F, where the solid lines indicate merging segments and all other lines depict the branches of the tree. The dots depict the placement of the internal nodes within the tree.

15.3.1 Standard Synthesis Techniques

Classic synthesis techniques for 2-D clock trees are discussed in Section 15.1. These approaches can produce clock trees for 3-D circuits, assuming that each tier contains a tree connecting all of the clock sinks within that tier. The roots of all of these trees are connected through a single vertical connection (e.g., a few TSVs connected in parallel), providing a complete tree spanning the entire 3-D circuit. This single TSV topology, however, is a rather naïve approach as the advantages of the third dimension are not adequately exploited [593]. Consequently, a multi-TSV topology is a superior approach, offering a considerable reduction in wirelength, which typically translates to lower power.

The 3-D clock synthesis problem has been casted in several ways, where the primary objectives are to produce a zero-skew multi-TSV tree with minimum (or near-minimum) wirelength and/or power and the minimum [594] or a bounded number of TSVs [593] for a set of clock sinks $S=\left\{s_1,s_2,s_3,\dots s_m\right\}\subset {\mathfrak{R}}^3$. The clock sinks span several physical tiers. The location of these sinks is described by a triplet of coordinates (x_i, y_i, z_i) where z_i indicates the tier of s_i. In addition, the slew should satisfy a target constraint that is typically less than 5% of the clock period.

Techniques for multi-TSV clock tree synthesis proceed in two phases. A topology connecting the clock sinks in all of the tiers of a 3-D system is first generated, followed by an extension of the DME method to embed the topology throughout the tiers of the 3-D system. Topology generation extends the traditional MMM algorithm. As described in Section 15.1, the MMM algorithm operates recursively by bipartitioning a set of clock sinks using an x- or y-cut until only one sink belongs to each set. In 3-D circuits, the clock sinks within a subset produced by a cut are located in different tiers, where those sinks are connected by TSVs. Additionally, a z-cut divides S in several ways, resulting in different demands for TSVs.

The classic MMM algorithm is, therefore, indifferent to TSVs, which can lead to undesirable situations either due to insufficient usage of TSVs to reduce the total wirelength or excessive utilization of TSVs, resulting in lower savings (or even increasing) in power. To address these issues, the MMM algorithm has been extended to control the number of TSVs required by the synthesized tree topologies [593,594].

The MMM-TSV-Bound algorithm, called MMM-TB, generates topologies based on satisfying a user specified upper limit on the number of TSVs. The TSVs are distributed across the area of the tiers [593]. An example of the effect that different bounds of TSVs have on the resulting topologies is shown in Fig. 15.13. As observed in this figure, for larger TSV bounds, additional TSVs are used, where these TSVs appear closer to those sinks connecting a smaller number of internal nodes and/or sinks. This behavior decreases the total wirelength since the horizontal interconnections are shorter. The MMM-TB algorithm begins with a set of sinks S and a TSV bound for each tier within the 3-D system. If stack(S) denotes the number of tiers spanning the sinks of S, at each partitioning iteration, two sets S₁ and S₂ are produced based on two conditions.

If the TSV bound is one, the existing set S is partitioned to ensure that sinks with the same z_i (i.e., from the same tier) are assigned to the same subset. This partition is straightforward as long as stack(S)=2. If, however, the sinks span more than two tiers and since cuts bipartition set S, there are (stack(S)–1) iterations that partition the sinks into the z-direction to ensure that sinks with the same z_i are on the same tier. The procedure, illustrated in Fig. 15.14, demonstrates the process in which the partitions in the z-direction occur. In this figure, z_min (z_max) is the lowest (highest) index of the tier that contains the sinks of set S at a specific iteration of the MMM-TB algorithm. In addition, the root of the clock tree is assumed to be located at z_r. Indexing the tiers is achieved in ascending order from the bottom tier to the uppermost tier.

As shown in Fig. 15.14, if z_r≤z_min, which means the root is located at a lower tier than any of the sinks in S, all sinks with z_i=z_min form the (bottom) subset S_B and the remaining sinks (e.g., z_i∈[z_min+1, z_max]) constitute the (top) subset S_T. Alternatively, if z_r≥z_max, which means the root is located at a higher tier than any of the sinks in S, all sinks with z_i=z_max form the (top) subset S_T and the remaining sinks (e.g., z_i∈[z_min, z_max−1]) constitute the (bottom) subset S_B. In any other case, the (top) subset S_T includes those sinks in the same tier as the root of the tree, while the (bottom) subset S_B contains the remaining sinks in the other tiers. An example of this procedure for a small set S={a, b, c} is depicted in Fig. 15.15, where the number of TSVs resulting from different z-cuts are illustrated by the thick line segments.

In the second condition, where the TSV bound is greater than one, a cut along the horizontal direction is applied to the median of the x- or y-coordinate of the sinks as in MMM and the z-dimension is not considered. The resulting subsets require several TSVs if sinks with a different z-coordinate are contained in these subsets. At the end of each partitioning step, a new TSV bound is assigned to each subset to ensure that the TSV bound is maintained. This new TSV bound is determined by estimating the number of TSVs required by the newly formed subsets and dividing the bound by the estimated number of TSVs. The TSV estimates are determined from the minimum number of sinks within each tier resulting from the horizontal cuts. The complexity of the MMM-TB algorithm remains the same as that of MMM, which is O(m log m).

The MMM-TB algorithm guarantees that the number of TSVs does not exceed the TSV bound. Any number of TSVs can, however, be employed as long as this bound is satisfied. The number of TSVs greatly affects the total wirelength and, therefore, the power consumed by the clock network. An exhaustive sweep is used to determine the optimum number of TSVs. This approach, however, is computationally expensive, particularly for large TSV bounds. The MMM-TB can be further enhanced to determine the optimal number of TSVs in terms of power. Note that simply using as many TSVs as possible may not yield the least power if the capacitance of the TSVs is high as this trait can adversely affect the savings in power by the decrease in the horizontal wirelength. To determine the number of TSVs, look ahead operations similar to those operations used in [578] are employed [593]. These operations proceed by (a) a z-cut followed by xy-cuts, and (b) xy-cuts followed by a z-cut. The distance of the newly formed centers of mass is compared for cases (a) and (b). A cost function is applied in both cases that relates the resulting number of TSVs and wirelength to estimate the power. The sequence of steps that yields the lower estimate of power is selected during the following iteration.

The second phase of the synthesis process is a variant of the DME method, adapted to consider TSVs and a slew constraint. To satisfy slew constraints, a general practice is to not allow the capacitance seen by any node of the tree to exceed a specific limit, C_max [602]. This constraint is met by adding clock buffers to ensure that the load seen by these buffers remains below C_max. The merging segments produced from the bottom-up pass of the DME method (see Section 15.1), computed in [593] based on the Elmore delay, are also determined for the buffers whenever the downstream capacitance of the internal nodes exceed C_max. During the top-down phase, DME is extended to evaluate the type of merging (e.g., merging of an internal node and a buffer from the root of the subtrees or a standard merging of an internal node with the children nodes) and determines the placement of the internal node and buffer. An example of the two different merging types encountered when buffer insertion is integrated with the DME method is illustrated in Fig. 15.16.

Application of the MMM-TB algorithm and the integrated buffer insertion with the DME technique to several benchmarks [603] has demonstrated that multi-TSV clock trees can greatly reduce power, ranging from 16.1% to 18.8%, 10.3% to 13.7%, and 6.6% to 8.3%, as compared to a single TSV clock network where the TSV capacitance is, respectively, 15, 50, and 100 fF, for a two tier circuit. The corresponding decrease in total wirelength is, respectively, 24.0% to 26.5%, 23.9% to 26.6%, and 16.6% to 18.9%. Another advantage of multi-TSV clock trees is that the average slew and distribution of slews are better managed due to the reduced wirelength. Although the combination of the MMM-TB algorithm and the DME method produces efficient multi-TSV clock trees, a greater reduction in wirelength for unbuffered trees is demonstrated by other variants of the MMM and DME methods, which are presented below to offer greater insight.

15.3.1.1 Further reduction of through silicon vias in synthesized clock trees

A simple extension of MMM in three physical dimensions, called MMM-half perimeter wirelength (HPWL), is introduced in [594], where a user defined parameter, ρ (0≤ρ≤1) determines the direction of a cut. If ρ=0, the standard MMM is employed, and the z-dimension is ignored. Alternatively, if ρ=1, the sinks are partitioned among the tiers comprising the 3-D circuit, and the resulting per tier subsets are bipartitioned using xy-cuts as in MMM. For any other ρ, a horizontal cut is performed along the geometric median in a 2-D Manhattan plane. The HPWL for these subsets of sinks is determined. If the HPWL of a subset of sinks is smaller than ρ· HPWL of all of the sinks, the sinks are partitioned among the tiers (i.e., a z-cut) rather than along the xy-directions. This condition shares some concepts with the MMM-TB algorithm, where the TSV bound is used to determine the direction of the sink partition. Furthermore, in the MMM-TB algorithm, constraining the number of TSVs does not guarantee that the total vertical wirelength is minimized.

The MMM-TB algorithm provides the number of TSVs required to connect the sinks during the recursive top-down partition. However, TSV usage also depends upon the tier in which the internal nodes of the connection topology of T(S) are placed. This information, however, is not determined by the MMM-TB algorithm. In addition, the standard DME technique is applied to a 2-D plane where the sinks are projected and does not minimize the number of TSVs.

To demonstrate the different number of TSVs that can originate from diverse placements of the internal nodes of a tree topology, consider the example shown in Fig. 15.17. Depending upon the placement of nodes x₁, x₂, and the root node s_r, the number of TSVs can differ significantly for a two tier tree, as depicted in Fig. 15.17. As illustrated in this example, embedding the nodes for cases (A) and (H) yields the fewest number of TSVs. An algorithm that embeds the tiers to ensure a minimum vertical length is presented in [594]. The vertical length for a 3-D clock tree is

$L_{v\_\mathrm{total}}=\sum _{\forall i,j\in G\left(S\right)}{L}_{\mathrm{TSV}}(z_i-z_j),$ (15.11)

(15.11)

where L_TSV is the length of one TSV connecting adjacent tiers, and the summation applies to every pair of nodes within the connection topology of tree T(S). Any pair of nodes placed within the same tier does not contribute to the vertical wirelength since z_i=z_j. To determine the number of TSVs for a node i of T(S) and, subsequently, the vertical wirelength, the following expressions are used

$n_{\mathrm{TSV}}\left(i\right)=\{\begin{array}{c}0,\mathrm{if}i\mathrm{is}\mathrm{a}\mathrm{sink}\mathrm{node},\\ n_{\mathrm{TSV}}\left(T_{\mathrm{left}}\left(i\right)\right)+n_{\mathrm{TSV}}\left(T_{\mathrm{right}}\left(i\right)\right)\\ +n_{\mathrm{TSV}}\left(i,T_{left}\left(i\right)\right)+n_{\mathrm{TSV}}\left(i,T_{right}\left(i\right)\right),\\ \mathrm{if}i\mathrm{is}\mathrm{an}\mathrm{internal}\mathrm{node},\end{array}$ (15.12a–b)

(15.12a–b)

where n_TSV(T_left(i)) and n_TSV(T_right(i)) are, respectively, the number of TSVs contained in the subtrees rooted at the children of node i and n_TSV(i, T_left(i)) and n_TSV(i, T_right(i)) are, respectively, the number of TSVs connecting node i to subtrees T_left(i) and T_right(i).

If the children of node i are sinks and the location of the sinks is known, the tier(s) where node i can be embedded is notated as ET(i) to ensure that the minimum number of TSVs is determined by the tier of the children nodes. If, however, the children nodes are internal nodes, the embedding tiers for these nodes are sets of embedding tiers. In this case, from these sets of embedding tiers, the set of tiers ET(i) that lead to the minimum number of TSVs n_TSV(i) for this node can be determined. An example of embedding an internal node x based on the embedding tiers of the children nodes x₁ and x₂ is shown in Fig. 15.18. If the children nodes are sinks, which means that x₁=s₁ and x₂=s₂, the length of the vertical connection for merging these nodes at node x is |t₂−t₁|, where t₂=z₂ and t₁=z₁ are the tier of the sinks, as depicted in Fig. 15.18A.

If the children nodes are also internal nodes, two cases can be distinguished. If the embedding tiers ET(x₁) and ET(x₂) have some common tier(s), the minimum vertical length to merge these nodes with node x is n_TSV(T_left(x))+n_TSV(T_right(x)), and the tier where the node is embedded is between tier t₂ and t₃, as shown in Fig. 15.18C. Choosing any other tier for embedding x results in an increase in n_TSV(x), as depicted in Fig. 15.18D. In the second case, where the set of embedding tier(s) for the children nodes x₁ and x₂ do not share any common embedding tier, as shown in Fig. 15.18E, node x is embedded between tier t₂ and t₃. The difference between these two cases, as shown in Figs. 15.18C and 15.18E, a common embedding tier for the children nodes exists in Fig. 15.18C and, consequently, merging with node x does not require a TSV. As shown in Fig. 15.18E, however, |t₃−t₂|>1 and at least one TSV is required to embed node x.

The set of embedding tiers for the internal nodes (required by (15.12a)) is iteratively determined in a bottom-up process [594],

$\mathit{ET}\left(x\right)=<\min \left(t_1,t_2\right),\max \left(t_1,t_2\right)>,$ (15.13)

(15.13)

where

$t_1=\max (\min \left(\mathit{ET}\right(T_{\mathrm{left}}\left(x\right)\left)\right),\min (\mathit{ET}(T_{\mathrm{right}}\left(x\right)))),$ (15.14)

(15.14)

and

$t_2=\min (\max \left(\mathit{ET}\right(T_{\mathrm{left}}\left(x\right)\left)\right),\max \left(\mathit{ET}\right(T_{\mathrm{right}}\left(x\right)\left)\right)).$ (15.15)

(15.15)

The optimality of these expressions has been proven through a series of lemmas [594]. The process of embedding the nodes of a tree to ensure that the minimum vertical length is employed exhibits a complexity of O(m) where m is the number of nodes of tree T(S).

Once the embedding tiers for the nodes within a tree are determined, the placement of the nodes of the tree follows based on the DME technique, where the Elmore or a linear delay model is employed. In a linear delay model, the TSVs are modeled differently due to a disimilar capacitance as compared to the horizontal wires. As with the application of DME to 2-D clock trees with a linear delay model, zero skew with minimum wirelength is also produced for 3-D clock trees. The situation is more subtle since the Elmore delay is used for e_a and e_b for merging nodes a and b (see Section 15.1). This approach can lead to a suboptimal wirelength due to the lack of a specific position along a merging segment to balance the delay from the merging node x to the root of subtrees T_a and T_b. This behavior requires wire snaking, which results in detouring from the minimum wirelength.

15.3.2 Synthesis Techniques for Pre-bond Testable Three-Dimensional Clock Trees

The previously discussed synthesis techniques produce 3-D clock trees for any number of tiers, yet suffer from a drawback that limits usability. As pre-bond test can guarantee high yield of 3-D systems [604], the correct functionality and expected performance of each tier should be verified prior to assembly of the stack. This demand places considerable constraints on the design of 3-D systems. For pre-bond test methodologies of 3-D circuits, see [605]. For the design of clock trees, specific changes must be made to provide pre-bond test. The fundamental difference of pre-bond test related to CTS techniques is the additional circuitry. The salient features of these techniques are presented in this section.

A method for providing a 3-D clock distribution network that can be tested during pre-bond is to utilize single TSV topologies as shown, for example, in Fig. 15.19, where these topologies include fully connected trees in each tier of the 3-D system. One clock input for each tier provides the clock signal to all of the clock pins within that tier. This approach, however, yields minor improvements over 2-D circuits, reducing the advantages of 3-D integration. Instead, adapting multi-TSV clock networks to support pre-bond test is more advantageous. The main challenge is in multi-TSV topologies. There is typically only one tier that contains a fully connected tree (typically the tier where the primary clock driver resides), while the other tiers comprise several (or a forest) of trees connected to the full tree through TSVs. These several trees within each tier are however disconnected from each other during pre-bond test operation. A non-negligible number of clock inputs is required to clock these disconnected trees prior to bonding, complicating the test process and increasing cost.

Additionally, even for the tier that includes the fully connected clock network, test is not a simple process as this network drives the entire clock load. During pre-bond test, only part of this load exists, which means that clock skew and slew can deviate significantly from the target skew and slew during normal operation. This network can, therefore, cause several timing violations that can incorrectly be interpreted as faults. To mitigate this situation, two measures are applied: (1) insert a buffer at each node of the complete network that connects to a TSV, and (2) add an appropriate number of redundant networks that connect the local trees of a tier with each other during pre-bond test. During normal operation, that is post-bond, these redundant trees are disconnected from the rest of the clock network [606]. Buffer insertion from (1) decouples the fully connected tree from the rest of the network. Consequently, the capacitance at each node of this clock tree remains the same during both pre- and post-bond operation.

An example of a pre-bond testable clock tree in two tiers is shown in Fig. 15.20. Drawn with dashed lines, the buffers before the TSVs, the redundant tree, and the transmission gates (TGs) that disconnect this tree during normal operation, are noted in this figure. Also note that an additional control signal is required for this structure to switch the TGs in tier 2.

Having described the characteristics of pre-bond testable clock networks, the synthesis problem is formulated as follows: for a set of sinks $S=\left\{s_1,s_2,s_3,\dots s_m\right\}\subset {\mathfrak{R}}^3$ distributed across n tiers, a root node s_r, and a TSV bound, synthesize a 3-D clock network with a minimum or zero clock skew both in post-bond (for the entire stack) and pre-bond (for each tier) operation. The wirelength and power of the 3-D clock network are minimized while simultaneously satisfying the clock slew constraints.

Employing the MMM-TB method, as described in the previous section, a connection topology for the sinks of S, denoted as T(S), is generated. The MMM-TB method produces a topology where the sinks are located on the same tier as the source, called herein the source tier. These sinks are connected by a tree. Connections to other tiers are implemented with TSVs. To decouple the subtrees in these tiers from the network in the source tier, the following steps are followed [596]: (1) if a TSV connects the source tier with another tier, a TSV buffer is inserted in the source tier, (2) if two nodes of the 3-D clock tree are connected by a TSV traversing the source tier, a TSV buffer is added to the source tier, and (3) if one TSV interconnects two nodes without traversing the source tier, no TSV buffer is inserted. In this case, the absence of this TSV during pre-bond test has no effect on the capacitance of the source tier and, therefore, a TSV buffer is not needed.

The next phase of the synthesis process includes a modified DME, which is a two stage technique. In this pre-bond aware CTS (PBA-CTS) technique, a zero skew tree is produced that considers merging segments both for the TSV buffers and the nodes of the connection topology originating from the MMM-TB algorithm. The TSV buffers, however, often require additional wirelength to maintain the zero (or low) skew requirement [596]. This situation can result in the minimum wirelength objective to not be satisfied. The insertion of common clock buffers avoids this situation. Consider the example shown in Fig. 15.21 where two subtrees, ST₁ and ST₂, are, respectively, in tiers one and two. A TSV buffer is used to merge these subtrees as the trees are located on separate tiers. This TSV buffer adds to the delay from node E to ST₂. If this delay is much greater than the delay from E to ST₁, before the insertion of the TSV buffer, this delay increases. Wire “snaking” is added to maintain the zero skew objective, which departs from the minimum wirelength objective. A clock buffer can be inserted to avoid wire snaking. Case studies show that these imbalances occur infrequently; the use of a clock buffer for this purpose is, therefore, not a significant issue.

Another reason exists for adding clock buffers during the bottom-up process where the merging of subtrees takes place. Clock buffers are widely used to satisfy slew constraints. Inserting these clock buffers ensures that the load that each clock buffer drives does not exceed a downstream capacitance threshold C_max [602]. This practice has been shown to control slew. In the case of pre-bond testable 3-D clock trees, examples where the clock and TSV buffers are inserted are illustrated in Fig. 15.22. The simple case is shown in Fig. 15.22A, which is common in both 2-D and 3-D (either pre-bond testable or not) synthesized clock trees if the delay of the merged branches is highly imbalanced (e.g., t_dA<t_dB). In Fig. 15.22B, multiple clock buffers are utilized due to the excessive length of the wires and/or if the downstream capacitance exceeds C_max. Another case is shown in Fig. 15.22C, which requires the addition of a clock buffer to counteract the delay imbalance caused by inserting a TSV buffer. The insertion of the TSV buffer also decouples the subtrees, thereby facilitating pre-bond test.

The output of the PBA-CTS method is a 3-D clock tree used for post-bond operation and a tree that spans all of the clock sinks lying in the source tier. Similar trees are generated for the remaining tiers, which is achieved by redundant trees connecting the unconnected trees in these tiers. This process is similar to a conventional CTS technique for planar circuits [596] comprising: (1) construction of a binary connection topology T(S) generated in a top-down manner, (2) insertion of a TG at each sink node, and (3) embedding and buffering of T(S) in a tier under skew and minimum wirelength constraints. Note that the sinks are the roots of the subtrees connected by the redundant tree in this tier. Insertion of the TGs, which connect (pre-bond operation) or disconnect (post-bond operation) the redundant tree, requires a control signal spanning a large portion of the tier. To limit the wirelength of this signal, the rectilinear minimum spanning tree (RMST) algorithm can be used [403,607].

IBM [603] and ISPD [608] benchmark circuits are utilized to ascertain the efficiency of this pre-bond CTS technique, where the clock sinks are randomly assigned within the tiers of the 3-D circuits. A 45 nm process node based on the Predictive Technology Model (PTM) model is assumed [252]. The clock frequency is 1 GHz and the power supply is 1.2 volts. A via-last TSV technology is used where the area, length, and liner thickness of a TSV are, respectively, 10 μm×10 μm, 20 μm, and 0.1 μm. The clock skew and slew constraints are, respectively, 10% and 3% of the clock period. Other electrical and physical characteristics assumed for these circuits are listed in [596]. A comparison of a single TSV, which is inherently pre-bond testable, and multi-TSV clock trees, which require redundant trees and TSV buffers, has demonstrated that multi-TSV clock trees decrease wirelength from 14.8% to 24.4% and 39.2% to 42.0%, for circuits with, respectively, two and four tiers. The savings in power vary from 10.1% to 15.9% and from 18.2% to 29.7%, respectively, for circuits comprising two and four tiers.

The departure between the wirelength and power savings, as wirelength and power depend linearly on wire capacitance, is attributed to the additional circuits, such as the TSV buffers and TGs, and the TSV capacitance, which can be greater than the capacitance of the horizontal wires on a per unit length basis. Furthermore, the control signal for the TGs adds to the overall wirelength congestion of the clock trees. The breakdown of the wirelength components for several benchmark circuits implemented in two tiers is reported in Table 15.3. The wirelength breakdown is reported for the post-bond 3-D clock trees, the pre-bond trees in the source tier (tier 1), and the pre-bond trees in tier 2. Notably, the length of the control signal of the TGs constitutes a significant portion of the total wirelength (on average, 29%).

Another potential source of overhead is the TSV buffers. The change in wirelength and power from the case where no TSV buffers are used in the source tier to decouple that tree from the downstream capacitance in the other tiers is listed in Table 15.4. The change in wirelength is small; for specific benchmark circuits, a decrease in the interconnect length is observed. Alternatively, an increase in power is always observed, verifying that inserting TSV buffers narrows the power gains for multi-TSV clock trees that are pre-bond testable.

Lastly, the effect of the TSV capacitance on the performance of a 3-D clock trees is assessed by the results reported in Table 15.5 for the IBM benchmark circuit r₅. These results include disparate TSV bounds, which constrain the number of TSVs in the clock tree. Two interesting observations are noted from these results. First, the power worsens with increasing TSV capacitance irrespective of the TSV bound. Second, increasing the TSV bound lowers power as more TSVs drive a shorter interconnect length. This trend is reversed if the TSV capacitance is much larger, increasing the power by 17.7% for 2,469 TSVs and a TSV capacitance of 100 fF.

Although the results listed in Tables 15.3 to 15.5 demonstrate considerable improvements, two limitations of the CTS technique in [596] are noted. One of these limitations relates to the effect of the added TSV buffers, which can produce delay imbalances that are controlled by additional clock buffers. The outcome is increased power. Another limitation stems from the use of TGs in all but the source tier to (dis)connect the redundant trees according to the operational mode (pre- or postbond). Indeed, as listed in column 13 of Table 15.3, the interconnect overhead due to the control signal of the TGs (although the routing of this signal is embedded with RMST) reaches, on average, 29% of the total wirelength of the post-bond clock tree. This overhead adds to the wirelength required by the clock distribution network or, alternatively, severely curtails the benefits of pre-bond testable multi-TSV trees.

These limitations can be circumvented through more elaborate CTS methods and a suitable self-configured circuit that can substitute for the TGs [595]. This approach commences with an advanced methodology for topology generation, called herein MMM-HPWLmax, which is based on the MMM-HPWL algorithm followed by the embedding of the topology in the tiers of the stack to minimize the vertical wirelength [594]. These steps provide a post-bond 3-D clock tree. To generate the redundant clock trees for pre-bond test, the same methods are applied again to all but the source tier, where the TGs are replaced by a self-configured circuit that adapts to the operating mode.

There are two primary differences between this method, called herein low overhead pre-bond aware CTS (LO-PBA-CTS) [595], and PBA-CTS [596]. These differences are (1) relaxation of the constraint that a buffer should be placed before a TSV to decouple the tree in the source tier from the downstream subtrees, and (2) elimination of the control signal for the TGs along with the associated interconnect overhead.

Consequently, in LO-PBA-CTS, a buffer can be placed anywhere along the branch of the tree that connects to a TSV. Greater flexibility is, therefore, offered for placing the buffers, lowering the likelihood of inserting a TSV buffer that produces a delay imbalance during the node merging process. This flexibility may, however, be insufficient to prevent delay imbalances, in particular when a TSV buffer is inserted at a branch with a small capacitive load. To cope with this situation, the TSV buffers are characterized as stable or unstable [595]. A TSV buffer is stable if inserting this buffer isolates the tree of the source tier and does not require insertion of another clock buffer at another edge to satisfy delay imbalances. Otherwise, a TSV buffer is unstable.

The LO-PBA-CTS technique manages the unstable TSV buffers through the MMM-HPWLmax algorithm [594], which builds on the MMM-HPWL. Whereas the latter algorithm handles the density of TSVs by the parameter ρ during the recursive bipartition, the MMM-HPWLmax checks whether the HPWL of the sinks included in a candidate subset is less than or equal to HPWLmax,cap,

${\mathrm{HPWL}}_{\max ,\mathrm{cap}}=\frac{C_{\max }-2C_{\max ,\mathrm{sink}}}{c_w},$ (15.16)

(15.16)

where C_max is the maximum capacitance constraint, c_w is the unit length capacitance of the horizontal interconnects, and C_max,sink is the maximum capacitive load of all of the sinks. MMM-HPWLmax employs the threshold max(HPWL_max,_cap, ρ·HPWL) to decide whether partitioning the sinks occurs in the z-direction or along the xy-directions. This threshold is rather conservative as the TSV capacitance is not included; however, simulation results demonstrate that the number of unstable TSV buffers is reduced, particularly in those circuits with a high number of clock sinks [595]. Note that this treatment resembles the practice of [596] to satisfy slew constraints but targets a different design objective.

The other key difference of LO-PBA-CTS [595] as compared to PBA-CTS [596] is the use of a self-configured circuit to switch the TGs connecting the redundant clock tree in all but the source tier. This circuit is depicted in Fig. 15.23, where, in addition to the TG, only a handful of transistors are required. The circuit operates as follows. During pre-bond test, the clock signal is supplied to the root of the redundant tree and reaches the root of every subtree preceded by a TG. A rising edge of the clock signal T_clk is inverted by INV1 and the device P₂ turns on, charging node PBTEST to V_dd. This high voltage drives the output of INV3 low, turning off N₂. The output signal of inverters INV3 and INV4 produces the control signals for the TG.

Alternatively, if the T_clk signal is low (no pre-bond test), P₂ turns off. The capacitance of node PBTEST slowly discharges through the different leakage current paths. At some time, the output of INV3 is driven high, turning on N₂, completely discharging node PBTEST. The TG is also turned off, disconnecting the redundant tree. The turn-off time of the circuit can be regulated by sizing P₂ and N₂, which are along, respectively, the charge and discharge paths of node PBTEST. The circuit in [595] is based on a 45 nm predictive technology [252], resulting in a turn-off time of about 100 ns.

Application of LO-PBA-CTS to the same benchmark circuits as in PBA-CTS and the same technology parameters demonstrates comparable results in terms of wirelength, clock skew, slew rate, and power. However, for specific benchmark circuits, such as ispd09fnb1 and ispd09fnb2, reductions of 56% to 88% in the number of TSVs, 53% to 67% in the number of buffers, 22% to 65% in total wirelength, and 26% to 43% in the power of the post-bond clock distribution network are observed. Additionally, the wirelength overhead of the control signal for the TGs no longer exists. Further developments in CTS techniques for 3-D clock trees emphasize other important issues, such as limitations on the TSV placement. These techniques are reviewed in the following section.