The main objective of this thesis is to design reliable clock-distribution networks and power-delivery networks for three-dimensional integrated circuits (3D ICs) using through-silicon vias (TSVs). This dissertation supports this goal by addressing six research topics. The first four works focus on 3D clock tree synthesis for low power, pre-bond testability, TSV-induced obstacle avoidance, and TSV utilization. The last two works develop modeling approaches for reliability analysis on 3D power-delivery networks. In the first work, a clock synthesis algorithm is developed for low-power and low-slew 3D clock network design. The impact of various design parameters on clock performance, including the wirelength, clock power, clock slew, and skew, is investigated. These parameters cover the TSV count, TSV parasitics, the maximum loading capacitance of the clock buffers, and the supply voltage. In the second work, a clock synthesis algorithm is developed to construct 3D clock networks for both pre-bond testability and post-bond operability. Pre-bond testing of 3D stacked ICs involves testing each individual die before bonding, which can improve the overall yield of 3D ICs by avoiding stacking defective dies with good ones. Two key techniques including TSV-buffer insertion and redundant tree generation are implemented to minimize clock skew and ensure pre-bond testing. The impact of TSV utilization and TSV parasitics on clock power is also investigated. In the third work, an obstacle-aware clock tree synthesis method is presented for through-silicon-via (TSV)-based 3D ICs. A unique aspect of this problem lies in the fact that various types of TSVs become obstacles during 3D clock routing including signal, power/ground, and clock TSVs. These TSVs may occupy silicon area or routing layers. The generated clock tree does not sacrifice wirelength or clock power too much and avoids TSV-induced obstacles. In the fourth work, a decision-tree-based clock synthesis (DTCS) method is developed for low-power 3D clock network design, where TSVs form a regular 2D array. This TSV array style is shown to be more manufacturable and practical than layouts with TSVs located at irregular spots. The DTCS method explores the entire solution space for the best TSV array utilization in terms of low power. Close-to-optimal solutions can be found for power efficiency with skew minimization in short runtime. In the fifth work, current crowding and its impact on 3D power grid integrity is investigated. Due to the geometry of TSVs and connections to the global power grid, significant current crowding can occur. The current density distribution within a TSV and its connections to the global power grid is explored. A simple TSV model is implemented to obtain current density distributions within a TSV and its local environment. This model is checked for accuracy by comparing with identical models simulated using finite element modeling methods. The simple TSV models are integrated with the global power wires for detailed chip-scale power analysis. In the sixth work, a comprehensive multi-physics modeling approach is developed to analyze electromigration (EM) in TSV-based 3D connections. Since a TSV has regions of high current density, grain boundaries play a significant role in EM dominating atomic transport. The transient analysis is performed on atomic transport including grain and grain boundary structures. The evolution of atomic depletion and accumulation is simulated due to current crowding. And the TSV resistance change is modeled.

<p>Minimum cycle mean (MCM) is an important concept in directed graphs. From clock period optimization, timing analysis to layout optimization, minimum cycle mean algorithms have found widespread use in VLSI system design optimization. With transistor size scaling to 10nm and below, complexities and size of the systems have grown rapidly over the last decade. Scalability of the algorithms both in terms of their runtime and memory usage is therefore important. </p> <p><br></p> <p>Among the few classical MCM algorithms, the algorithm by Young, Tarjan, and Orlin (YTO), has been particularly popular. When implemented with a binary heap, the YTO algorithm has the best runtime performance although it has higher asymptotic time complexity than Karp's algorithm. However, as an efficient implementation of YTO relies on data redundancy, its memory usage is higher and could be a prohibitive factor in large size problems. On the other hand, a typical implementation of Karp's algorithm can also be memory hungry. An early termination technique from Hartmann and Orlin (HO) can be directly applied to Karp's algorithm to improve its runtime performance and memory usage. Although not as efficient as YTO in runtime, HO algorithm has much less memory usage than YTO. We propose several improvements to HO algorithm. The proposed algorithm has comparable runtime performance to YTO for circuit graphs and dense random graphs while being better than HO algorithm in memory usage. </p> <p><br></p> <p>Minimum balancing of a directed graph is an application of the minimum cycle mean algorithm. Minimum balance algorithms have been used to optimally distribute slack for mitigating process variation induced timing violation issues in clock network. In a conventional minimum balance algorithm, the principal subroutine is that of finding MCM in a graph. In particular, the minimum balance algorithm iteratively finds the minimum cycle mean and the corresponding minimum-mean cycle, and uses the mean and cycle to update the graph by changing edge weights and reducing the graph size. The iterations terminate when the updated graph is a single node. Studies have shown that the bottleneck of the iterative process is the graph update operation as previous approaches involved updating the entire graph. We propose an improvement to the minimum balance algorithm by performing fewer changes to the edge weights in each iteration, resulting in better efficiency.</p> <p><br></p> <p>We also apply the minimum cycle mean algorithm in latency insensitive system design. Timing violations can occur in high performance communication links in system-on-chips (SoCs) in the late stages of the physical design process. To address the issues, latency insensitive systems (LISs) employ pipelining in the communication channels through insertion of the relay stations. Although the functionality of a LIS is robust with respect to the communication latencies, such insertion can degrade system throughput performance. Earlier studies have shown that the proper sizing of buffer queues after relay station insertion could eliminate such performance loss. However, solving the problem of maximum performance buffer queue sizing requires use of mixed integer linear programming (MILP) of which runtime is not scalable. We formulate the problem as a parameterized graph optimization problem where for every communication channel there is a parameterized edge with buffer counts as the edge weight. We then use minimum cycle mean algorithm to determine from which edges buffers can be removed safely without creating negative cycles. This is done iteratively in the similar style as the minimum balance algorithm. Experimental results suggest that the proposed approach is scalable. Moreover, quality of the solution is observed to be as good as that of the MILP based approach.</p><p><br></p>