Physical Design Methodologies for Low Power and Reliable 3D ICs

As the semiconductor industry struggles to maintain its momentum down the path following the Moore's Law, three dimensional integrated circuit (3D IC) technology has emerged as a promising solution to achieve higher integration density, better performance, and lower power consumption. However, despite its significant improvement in electrical performance, 3D IC presents several serious physical design challenges. In this dissertation, we investigate physical design methodologies for 3D ICs with primary focus on two areas: low power 3D clock tree design, and reliability degradation modeling and management. Clock trees are essential parts for digital system which dissipate a large amount of power due to high capacitive loads. The majority of existing 3D clock tree designs focus on minimizing the total wire length, which produces sub-optimal results for power optimization. In this dissertation, we formulate a 3D clock tree design flow which directly optimizes for clock power. Besides, we also investigate the design methodology for clock gating a 3D clock tree, which uses shutdown gates to selectively turn off unnecessary clock activities. Different from the common assumption in 2D ICs that shutdown gates are cheap thus can be applied at every clock node, shutdown gates in 3D ICs introduce additional control TSVs, which compete with clock TSVs for placement resources. We explore the design methodologies to produce the optimal allocation and placement for clock and control TSVs so that the clock power is minimized. We show that the proposed synthesis flow saves significant clock power while accounting for available TSV placement area. Vertical integration also brings new reliability challenges including TSV's electromigration (EM) and several other reliability loss mechanisms caused by TSV-induced stress. These reliability loss models involve complex inter-dependencies between electrical and thermal conditions, which have not been investigated in the past. In this dissertation we set up an electrical/thermal/reliability co-simulation framework to capture the transient of reliability loss in 3D ICs. We further derive and validate an analytical reliability objective function that can be integrated into the 3D placement design flow. The reliability aware placement scheme enables co-design and co-optimization of both the electrical and reliability property, thus improves both the circuit's performance and its lifetime. Our electrical/reliability co-design scheme avoids unnecessary design cycles or application of ad-hoc fixes that lead to sub-optimal performance. Vertical integration also enables stacking DRAM on top of CPU, providing high bandwidth and short latency. However, non-uniform voltage fluctuation and local thermal hotspot in CPU layers are coupled into DRAM layers, causing a non-uniform bit-cell leakage (thereby bit flip) distribution. We propose a performance-power-resilience simulation framework to capture DRAM soft error in 3D multi-core CPU systems. In addition, a dynamic resilience management (DRM) scheme is investigated, which adaptively tunes CPU's operating points to adjust DRAM's voltage noise and thermal condition during runtime. The DRM uses dynamic frequency scaling to achieve a resilience borrow-in strategy, which effectively enhances DRAM's resilience without sacrificing performance. The proposed physical design methodologies should act as important building blocks for 3D ICs and push 3D ICs toward mainstream acceptance in the near future.

POSITIVE FILTERED P_N METHOD FOR LINEAR TRANSPORT EQUATIONS AND THE ASSOCIATED OPTIMIZATION ALGORITHM

We propose a positive, accurate moment closure for linear kinetic transport equations based on a filtered spherical harmonic (FP_N) expansion in the angular variable. The FP_N moment equations are accurate approximations to linear kinetic equations, but they are known to suffer from the occurrence of unphysical, negative particle concentrations. The new positive filtered P_N (FP_N+) closure is developed to address this issue. The FP_N+ closure approximates the kinetic distribution by a spherical harmonic expansion that is non-negative on a finite, predetermined set of quadrature points. With an appropriate numerical PDE solver, the FP_N+ closure generates particle concentrations that are guaranteed to be non-negative. Under an additional, mild regularity assumption, we prove that as the moment order tends to infinity, the FP_N+ approximation converges, in the L2 sense, at the same rate as the FP_N approximation; numerical tests suggest that this assumption may not be necessary. By numerical experiments on the challenging line source benchmark problem, we confirm that the FP_N+ method indeed produces accurate and non-negative solutions. To apply the FP_N+ closure on problems at large temporal-spatial scales, we develop a positive asymptotic preserving (AP) numerical PDE solver. We prove that the propose AP scheme maintains stability and accuracy with standard mesh sizes at large temporal-spatial scales, while, for generic numerical schemes, excessive refinements on temporal-spatial meshes are required. We also show that the proposed scheme preserves positivity of the particle concentration, under some time step restriction. Numerical results confirm that the proposed AP scheme is capable for solving linear transport equations at large temporal-spatial scales, for which a generic scheme could fail. Constrained optimization problems are involved in the formulation of the FP_N+ closure to enforce non-negativity of the FP_N+ approximation on the set of quadrature points. These optimization problems can be written as strictly convex quadratic programs (CQPs) with a large number of inequality constraints. To efficiently solve the CQPs, we propose a constraint-reduced variant of a Mehrotra-predictor-corrector algorithm, with a novel constraint selection rule. We prove that, under appropriate assumptions, the proposed optimization algorithm converges globally to the solution at a locally q-quadratic rate. We test the algorithm on randomly generated problems, and the numerical results indicate that the combination of the proposed algorithm and the constraint selection rule outperforms other compared constraint-reduced algorithms, especially for problems with many more inequality constraints than variables.

Tensor Completion for Multidimensional Inverse Problems with Applications to Magnetic Resonance Relaxometry

This thesis deals with tensor completion for the solution of multidimensional inverse problems. We study the problem of reconstructing an approximately low rank tensor from a small number of noisy linear measurements. New recovery guarantees, numerical algorithms, non-uniform sampling strategies, and parameter selection algorithms are developed. We derive a fixed point continuation algorithm for tensor completion and prove its convergence. A restricted isometry property (RIP) based tensor recovery guarantee is proved. Probabilistic recovery guarantees are obtained for sub-Gaussian measurement operators and for measurements obtained by non-uniform sampling from a Parseval tight frame. We show how tensor completion can be used to solve multidimensional inverse problems arising in NMR relaxometry. Algorithms are developed for regularization parameter selection, including accelerated k-fold cross-validation and generalized cross-validation. These methods are validated on experimental and simulated data. We also derive condition number estimates for nonnegative least squares problems. Tensor recovery promises to significantly accelerate N-dimensional NMR relaxometry and related experiments, enabling previously impractical experiments. Our methods could also be applied to other inverse problems arising in machine learning, image processing, signal processing, computer vision, and other fields.

Spectral Frame Analysis and Learning through Graph Structure

This dissertation investigates the connection between spectral analysis and frame theory. When considering the spectral properties of a frame, we present a few novel results relating to the spectral decomposition. We first show that scalable frames have the property that the inner product of the scaling coefficients and the eigenvectors must equal the inverse eigenvalues. From this, we prove a similar result when an approximate scaling is obtained. We then focus on the optimization problems inherent to the scalable frames by first showing that there is an equivalence between scaling a frame and optimization problems with a non-restrictive objective function. Various objective functions are considered, and an analysis of the solution type is presented. For linear objectives, we can encourage sparse scalings, and with barrier objective functions, we force dense solutions. We further consider frames in high dimensions, and derive various solution techniques. From here, we restrict ourselves to various frame classes, to add more specificity to the results. Using frames generated from distributions allows for the placement of probabilistic bounds on scalability. For discrete distributions (Bernoulli and Rademacher), we bound the probability of encountering an ONB, and for continuous symmetric distributions (Uniform and Gaussian), we show that symmetry is retained in the transformed domain. We also prove several hyperplane-separation results. With the theory developed, we discuss graph applications of the scalability framework. We make a connection with graph conditioning, and show the in-feasibility of the problem in the general case. After a modification, we show that any complete graph can be conditioned. We then present a modification of standard PCA (robust PCA) developed by Cand\`es, and give some background into Electron Energy-Loss Spectroscopy (EELS). We design a novel scheme for the processing of EELS through robust PCA and least-squares regression, and test this scheme on biological samples. Finally, we take the idea of robust PCA and apply the technique of kernel PCA to perform robust manifold learning. We derive the problem and present an algorithm for its solution. There is also discussion of the differences with RPCA that make theoretical guarantees difficult.

Guided Migration and Collective Behavior: Cell Dynamics during Cancer Progression

This dissertation focuses on gaining understanding of cell migration and collective behavior through a combination of experiment, analysis, and modeling techniques. Cell migration is a ubiquitous process that plays an important role during embryonic development and wound healing as well as in diseases like cancer, which is a particular focus of this work. As cancer cells become increasingly malignant, they acquire the ability to migrate away from the primary tumor and spread throughout the body to form metastatic tumors. During this process, changes in gene expression and the surrounding tumor environment can lead to changes in cell migration characteristics. In this thesis, I analyze how cells are guided by the texture of their environment and how cells cooperate with their neighbors to move collectively. The emergent properties of collectively moving groups are a particular focus of this work as collective cell dynamics are known to change in diseases such as cancer. The internal machinery for cell migration involves polymerization of the actin cytoskeleton to create protrusions that---in coordination with retraction of the rear of the cell---lead to cell motion. This actin machinery has been previously shown to respond to the topography of the surrounding surface, leading to guided migration of amoeboid cells. Here we show that epithelial cells on nanoscale ridge structures also show changes in the morphology of their cytoskeletons; actin is found to align with the ridge structures. The migration of the cells is also guided preferentially along the ridge length. These ridge structures are on length scales similar to those found in tumor microenvironments and as such provide a system for studying the response of the cells' internal migration machinery to physiologically relevant topographical cues. In addition to sensing surface topography, individual cells can also be influenced by the pushing and pulling of neighboring cells. The emergent properties of collectively migrating cells show interesting dynamics and are relevant for cancer progression, but have been less studied than the motion of individual cells. We use Particle Image Velocimetry (PIV) to extract the motion of a collectively migrating cell sheet from time lapse images. The resulting flow fields allow us to analyze collective behavior over multiple length and time scales. To analyze the connection between individual cell properties and collective migration behavior, we compare experimental flow fields with the migration of simulated cell groups. Our collective migration metrics allow for a quantitative comparison between experimental and simulated results. This comparison shows that tissue-scale decreases in collective behavior can result from changes in individual cell activity without the need to postulate the existence of subpopulations of leader cells or global gradients. In addition to tissue-scale trends in collective behavior, the migration of cell groups includes localized dynamic features such as cell rearrangements. An individual cell may smoothly follow the motion of its neighbors (affine motion) or move in a more individualistic manner (non-affine motion). By decomposing individual motion into both affine and non-affine components, we measure cell rearrangements within a collective sheet. Finally, finite-time Lyapunov exponent (FTLE) values capture the stretching of the flow field and reflect its chaotic character. Applying collective migration analysis techniques to experimental data on both malignant and non-malignant human breast epithelial cells reveals differences in collective behavior that are not found from analyzing migration speeds alone. Non-malignant cells show increased cooperative motion on long time scales whereas malignant cells remain uncooperative as time progresses. Combining multiple analysis techniques also shows that these two cell types differ in their response to a perturbation of cell-cell adhesion through the molecule E-cadherin. Non-malignant MCF10A cells use E-cadherin for short time coordination of collective motion, yet even with decreased E-cadherin expression, the cells remain coordinated over long time scales. In contrast, the migration behavior of malignant and invasive MCF10CA1a cells, which already shows decreased collective dynamics on both time scales, is insensitive to the change in E-cadherin expression.

Guided Migration and Collective Behavior: Cell Dynamics during Cancer Progression

This dissertation focuses on gaining understanding of cell migration and collective behavior through a combination of experiment, analysis, and modeling techniques. Cell migration is a ubiquitous process that plays an important role during embryonic development and wound healing as well as in diseases like cancer, which is a particular focus of this work. As cancer cells become increasingly malignant, they acquire the ability to migrate away from the primary tumor and spread throughout the body to form metastatic tumors. During this process, changes in gene expression and the surrounding tumor environment can lead to changes in cell migration characteristics. In this thesis, I analyze how cells are guided by the texture of their environment and how cells cooperate with their neighbors to move collectively. The emergent properties of collectively moving groups are a particular focus of this work as collective cell dynamics are known to change in diseases such as cancer. The internal machinery for cell migration involves polymerization of the actin cytoskeleton to create protrusions that---in coordination with retraction of the rear of the cell---lead to cell motion. This actin machinery has been previously shown to respond to the topography of the surrounding surface, leading to guided migration of amoeboid cells. Here we show that epithelial cells on nanoscale ridge structures also show changes in the morphology of their cytoskeletons; actin is found to align with the ridge structures. The migration of the cells is also guided preferentially along the ridge length. These ridge structures are on length scales similar to those found in tumor microenvironments and as such provide a system for studying the response of the cells' internal migration machinery to physiologically relevant topographical cues. In addition to sensing surface topography, individual cells can also be influenced by the pushing and pulling of neighboring cells. The emergent properties of collectively migrating cells show interesting dynamics and are relevant for cancer progression, but have been less studied than the motion of individual cells. We use Particle Image Velocimetry (PIV) to extract the motion of a collectively migrating cell sheet from time lapse images. The resulting flow fields allow us to analyze collective behavior over multiple length and time scales. To analyze the connection between individual cell properties and collective migration behavior, we compare experimental flow fields with the migration of simulated cell groups. Our collective migration metrics allow for a quantitative comparison between experimental and simulated results. This comparison shows that tissue-scale decreases in collective behavior can result from changes in individual cell activity without the need to postulate the existence of subpopulations of leader cells or global gradients. In addition to tissue-scale trends in collective behavior, the migration of cell groups includes localized dynamic features such as cell rearrangements. An individual cell may smoothly follow the motion of its neighbors (affine motion) or move in a more individualistic manner (non-affine motion). By decomposing individual motion into both affine and non-affine components, we measure cell rearrangements within a collective sheet. Finally, finite-time Lyapunov exponent (FTLE) values capture the stretching of the flow field and reflect its chaotic character. Applying collective migration analysis techniques to experimental data on both malignant and non-malignant human breast epithelial cells reveals differences in collective behavior that are not found from analyzing migration speeds alone. Non-malignant cells show increased cooperative motion on long time scales whereas malignant cells remain uncooperative as time progresses. Combining multiple analysis techniques also shows that these two cell types differ in their response to a perturbation of cell-cell adhesion through the molecule E-cadherin. Non-malignant MCF10A cells use E-cadherin for short time coordination of collective motion, yet even with decreased E-cadherin expression, the cells remain coordinated over long time scales. In contrast, the migration behavior of malignant and invasive MCF10CA1a cells, which already shows decreased collective dynamics on both time scales, is insensitive to the change in E-cadherin expression.