Search

Timing violations in high performance communication channels in system-on-chips (SoC) may occur in the late stages of the physical design process. To address that, latency insensitive systems (LISs) employ pipelining in the communication channels through the insertion of relay stations. Although the functionality of an LIS is robust with respect to the communication latencies, imbalances in relay station insertion may degrade the throughput of the system. While having a large number of buffer queues can eliminate such performance loss, the system may not have adequate area to accommodate these buffers. The problem of buffer queue sizing for maximizing throughput while meeting buffer area constraints has been solved using a mixed-integer linear program (MILP) formulation; however, such an approach is not scalable. In this work, we formulate the buffer queue sizing 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 a minimum cycle mean algorithm to determine from which edges buffers can be removed safely. Experimental results on large LISs suggest that the proposed approach is scalable. Moreover, quality of the solutions, in terms of the throughput and the size of buffer queues, is observed to be as good as that of the MILP-based approach.

Clock trees can be constructed based on static arrival time constraints or dynamic implied skew constraints. Dynamic implied skew constraints allow the full timing margins to be utilized. However, the dynamic skew constraints require a high run-time complexity to be evaluated. In contrast, static arrival time constraints are more restrictive but can be evaluated in constant time. Consequently, there is a tradeoff between timing margin utilization and run-time. In this paper, a scalable clock tree synthesis (CTS) framework is proposed for the construction of low-cost useful skew trees (USTs) with high timing quality. The scalability is based on combining the use of arrival time constraints with virtual minimum and maximum delay offsets, which facilitates that a pair of smaller subtrees can be joined into a larger subtree in constant time. The ability to quickly join subtrees is leveraged to perform a high degree of solution space exploration, which translates into the construction of USTs with low-cost. In particular, clock trees with various routing tree topologies, buffer tree topologies, buffer sizes, and stem wire lengths are explored. Moreover, the arrival time constraints are specified with the objective of being the least restrictive to reduce cost. Furthermore, the constraints are respecified throughout the tree construction process using a slack graph (SG) to expose additional timing margins. The high timing quality is obtained by seamlessly integrating arbitrary timing models using the SG. Finally, the proposed CTS framework is integrated with a clock tree optimization framework to demonstrate that the constructed USTs are capable of meeting timing constraints under the influence of on-chip variations.

Coflow scheduling improves data-intensive application performance by improving their networking performance. State-of-the-art Coflow schedulers in essence approximate the classic online Shortest-Job-First (SJF) scheduling, designed for a single CPU, in a distributed setting, with no coordination among how the flows of a Coflow at individual ports are scheduled, and as a result suffer two performance drawbacks: (1) The flows of a Coflow may suffer the out-of-sync problem -- they may be scheduled at different times and become drifting apart, negatively affecting the Coflow completion time (CCT); (2) FIFO scheduling of flows at each port bears no notion of SJF, leading to suboptimal CCT. We propose SAATH, an online Coflow scheduler that overcomes the above drawbacks by explicitly exploiting the spatial dimension of Coflows. In SAATH, the global scheduler schedules the flows of a Coflow using an all-or-none policy which mitigates the out-of-sync problem. To order the Coflows within each queue, SAATH resorts to a Least-Contention-First (LCoF) policy which we show extends the gist of SJF to the spatial dimension, complemented with starvation freedom. Our evaluation using an Azure testbed and simulations of two production cluster traces show that compared to Aalo, SAATH reduces the CCT in median (P90) cases by 1.53x (4.5x) and 1.42x (37x), respectively.

Clock networks are required to be constructed with adequate safety margins in the skew constraints to operate correctly even under the influence of variations. In this work, a scalable clock scheduler is developed to drive a synthesis framework that constructs useful skew clock trees with large safety margins that are tailored to the tree topology. Sequential elements are clustered early in the topology, if it is impossible provide adequate robustness to variations using only safety margins. Compared to earlier studies, the proposed framework performs the clock scheduling one to two orders of magnitude faster and improves yield and capacitive cost on several synthesized circuits.

Previous studies on human-pose estimation (HPE) rely on the design of factors to represent underlying probability distributions that model human poses. However, designing those factors manually is laborious. Moreover, manually designed factors might not represent underlying probability distributions properly. In this paper, we utilize feedforward neural networks (NNs) to design factors of our previous work on HPE and build an NN-based HPE system. We first propose a mapping that converts a Bayesian network to a feedforward NN. Then, the system is built based on the proposed mapping that consists of two steps: 1) structure identification and 2) parameter learning. In the structure identification, we develop a bottom-up approach to build a feedforward NN while preserving a Bayesian-network structure. In the parameter learning, we create a part-based approach to learn synaptic weights by decomposing a feedforward NN into parts. Using the proposed mapping, our previous work of an action-mixture model (AMM) for HPE is converted to a feedforward NN called NN-AMM. Based on the concept of distributed representation, NN-AMM is further modified to a scalable feedforward NN called NND-AMM. The NN-based HPE system is then built by using viewpoint-and-shape-feature-histogram features extracted from 3-D-point-cloud input and NND-AMM to estimate 3-D human poses. The results showed that the proposed mapping could design AMM factors automatically. NND-AMM could provide more accurate human-pose estimates with fewer hidden neurons than both AMM and NN-AMM could. Both NN-AMM and NND-AMM could adapt to different types of input, showing the adaptability of using feedforward NNs to design factors.

Clock trees are commonly used to deliver clock signals to sequential elements in circuits. However, by construction, tree structures are inherently prone to failure caused by variations. The robustness of a clock tree can be improved by inserting redundancy in the form of cross links or multilevel fusion trees. Such near-tree structures can provide robustness at low cost. In this paper, we establish that the locations of the inserted redundancy are crucial in providing cost-effective robustness. We present two methods to systematically insert redundancy. The redundancy is realized by either inserting cross links or performing local merges. Moreover, we present a vertex reduction method that reduces the amount of redundancy that needs to be inserted in our near-tree structures. Empirical results show that our structures are more robust to variations and have lower power consumption compared to the state-of-the-art clock networks. Furthermore, our near-tree structures provide smooth trade-offs between cost and robustness, reducing clock skews by 11%–39% at an expense of 3%–68% higher power consumption.

There are striking differences between constructing clock trees based on dynamic implied skew constraints and based on static arrival time constraints. Dynamic implied skew constraints allow the full timing margins to be utilized, but the constraints are required to be updated (with high time complexity). In contrast, static arrival time constraints are decoupled and are not required to be updated. Therefore, the constraints can be obtained in constant time, which facilitates the exploration of various tree topologies. On the other hand, arrival time constraints do not allow the full timing margins to be utilized. Consequently, there is a trade-off between topology exploration and timing margin utilization. In this paper, the advantages of static arrival time constraints are leveraged to construct clock trees with useful skew while exploring various tree topologies. Moreover, the constraints are specified and respecified throughout the synthesis process reduce the cost of the constructed clock trees. It is experimentally demonstrated that the proposed approach results in clock trees with 16% lower average capacitive cost compared with clock trees constructed based on dynamic implied skew constraints.

This paper focuses on human-pose estimation using a stationary depth sensor. The main challenge concerns reducing the feature ambiguity and modeling human poses in high-dimensional human-pose space because of the curse of dimensionality. We propose a 3-D-point-cloud system that captures the geometric properties (orientation and shape) of the 3-D point cloud of a human to reduce the feature ambiguity, and use the result from action classification to discover low-dimensional manifolds in human-pose space in estimating the underlying probability distribution of human poses. In the proposed system, a 3-D-point-cloud feature called viewpoint and shape feature histogram (VISH) is proposed to extract the 3-D points from a human and arrange them into a tree structure that preserves the global and local properties of the 3-D points. A nonparametric action-mixture model (AMM) is then proposed to model human poses using low-dimensional manifolds based on the concept of distributed representation. Since human poses estimated using the proposed AMM are in discrete space, a kinematic model is added in the last stage of the proposed system to model the spatial relationship of body parts in continuous space to reduce the quantization error in the AMM. The proposed system has been trained and evaluated on a benchmark dataset. Computer-simulation results showed that the overall error and standard deviation of the proposed 3-D-point-cloud system were reduced compared with some existing approaches without action classification.

Clock trees must be constructed to function even under the influence of on-chip variations (OCV). Bounding the latency of a clock tree, i.e., the maximum delay from the tree root to any sequential element, is important because the latency correlates with the maximum magnitude of the skews caused by OCV. In this paper, a latency constraint graph (LCG) that captures the latencies of a set of subtrees and the skew constraints between the subtrees is introduced. The minimum latency of a clock tree that can be constructed from the corresponding subtrees is equal to the (negative of the) length of a shortest path in the LCG, which can be computed in $O(VE)$. Based on the LCG, we propose a framework that consists of a latency-aware clock tree synthesis (CTS) phase and a clock tree optimization (CTO) phase to construct latency-bounded clock trees. When applied to a set of synthesized circuits, the framework is capable of constructing latency-bounded clock trees that have higher yield compared to clock trees constructed in previous studies.

It is of critical importance to efficiently and accurately predict global resonances of a 3-D integrated circuit system that involves arbitrarily shaped lossy conductors and inhomogeneous materials. A quadratic eigenvalue solver of linear complexity and electromagnetic accuracy is developed in this paper to fulfill this task. Without sacrificing accuracy, the proposed eigenvalue solver has shown a clear advantage over state-of-the-art eigenvalue solvers in fast CPU time. It successfully solves a quadratic eigenvalue problem of over 2.5 million unknowns associated with a large-scale 3-D on-chip circuit embedded in inhomogeneous materials in 40 min on a single 3 GHz 8222SE AMD Opteron processor.

As on-track double vias take less routing resources and have better electrical characteristics, we study in this paper the problem of double via insertion with a preference for on-track double vias (DVI/ON) in a postrouting stage. The primary goal is to insert as many double vias as possible, and maximizing the number of on-track double vias is a secondary objective. We present a zero-one integer linear program-based approach to optimally solve the DVI/ON problem. Moreover, we also discuss a special case of the DVI/ON problem and present a maximum-weighted bipartite matching-based optimal approach. Experimental results indicate that our approaches outperform existing algorithms in terms of solution quality.

The wave-propagation problem in an on-chip interconnect network can be modeled as a generalized eigenvalue problem. For solving such a generalized eigenvalue problem, the computational complexity of Arnoldi iteration is at best O(k 2 N), where k is the number of dominant eigenvalues and N is the matrix size. In this paper, we reduce the computational complexity of the Arnoldi iteration for interconnect extraction from O(k 2 N) to O(N), thus paving the way for full-wave extraction of very large scale on-chip interconnects, of which a typical value of k is on the order of hundreds of thousands. Numerical and experimental results have demonstrated the accuracy and efficiency of the proposed fast eigenvalue solver.

This paper proposes a linear-time complex-valued eigenvalue solver for solving large-scale on-chip interconnect problems. The fast eigenvalue solution is achieved by eigenvalue clustering, fast system reduction with negligible computational cost, and fast linear-time solution of the reduced system. Numerical and experimental results are presented to demonstrate the accuracy and efficiency of the proposed method.

One important trend in today's microprocessor architectures is the increase in size of the processor caches. These caches also tend to be set associative. As technology scales, process variations are expected to increase the fault rates of the SRAM cells that compose such caches. As an important component of the processor, the parametric yield of SRAM cells is crucial to the overall performance and yield of the microchip. In this article, we propose a microarchitectural solution, called the buddy cache that permits large, set-associative caches to tolerate faults in SRAM cells due to process variations. In essence, instead of disabling a faulty cache block in a set (as is the current practice), it is paired with another faulty cache block in the same set—the buddy. Although both cache blocks are faulty, if the faults of the two blocks do not overlap, then instead of losing two blocks, buddying will yield a functional block from the nonfaulty portions of the two blocks. We found that with buddying, caches can better mitigate the negative impacts of process variations on performance and yield, gracefully downgrading performance as opposed to catastrophic failure. We will describe the details of the buddy cache and give insights as to why it is both more performance and yield resilient to faults.

Existing exact closed-form expressions for the scalar mutual and self-potential coefficients for rectangular conductors may be ill-conditioned for certain geometries. We propose new, exact, closed-form expressions for potential coefficients that are much better-conditioned. The basic idea is to express all potential coefficients as weighted sums of mutual and self-potential coefficients of suitably defined virtual plates. Experimental results are presented to demonstrate the improved numerical stability of the new formulas

The authors present a novel wire duplication-based interconnect modeling technique. The proposed modeling technique exploits the sparsity of the L/sup -1/ matrix, where L is the inductance matrix, and constructs a sparse and stable equivalent circuit by windowing the original inductance matrix. The resulting circuit model is sparse and exhibits the same stability property as the K method. Numerical results show that the proposed wire duplication model has high accuracy and is more efficient than many existing techniques.

In this brief, we propose a new exact closed-form mutual inductance equation for rectangular conductors. We express the mutual inductance between two parallel rectangular conductors as a weighted sum of self inductances. We do not place any restrictions on the alignment of the two parallel rectangular conductors. Moreover, they could be coplanar or reside on different layers. Most important, experimental results show that our formula is numerically more stable than that derived by Hoer and Love.

We investigate the problem of decoupling capacitance (decap) allocation for power supply noise suppression at floorplan level. First, we assume that a floorplan is given and consider the decap placement as a postfloorplan step. Second, we consider the decap placement as an integral part of a floorplanning methodology (noise-aware floorplanning). In both cases, the objective is to minimize the floorplan area while suppressing the power supply noise below the specified limit. Experimental results on MCNC benchmark circuits show that, for postfloorplan decap placement, the white space allocated for decap is about 6%-9% of the chip area for the 0.25-/spl mu/m technology. The power-supply noise is kept below the specified limit. Compared to postfloorplan approach, the peak power-supply noise can be reduced by as much as 40% and the decap budget can be reduced by as much as 21% by using noise-aware floorplanning methodology. The total area is also reduced due to the reduced total decap budget gained from reduced power supply noise.

In this paper, we present a repeater block planning algorithm for interconnect-centric floorplanning. We introduce the concept of independent feasible regions for repeaters and derive an analytical formula for their computation. We develop a routability-driven repeater clustering algorithm to perform repeater block planning based on iterative deletion. The goal is to obtain a high-quality solution for the repeater block locations so that performance-driven interconnect synthesis at the routing stage can be carried out with ease while minimizing the chip area. Experimental results show that our method increases the percentage of all global nets that meet their target delays from 67.5% to 85%. Moreover, our approach minimizes the expected routing congestion, making it easier for performance-driven routers to synthesize global nets that require the insertion of repeaters to meet timing constraints.

Three-dimensional (3-D) technology promises higher integration density and lower interconnection complexity and delay. At present, however, not much work on circuit applications has been done due to lack of insight into 3-D circuit architecture and performance. One of the purposes of realizing 3-D integration is to reduce the interconnect complexity and delay of two dimensions (2-D), which are widely considered as the barriers to continued performance gains in future technology generations. Thus, understanding the interconnect and its related issues, such as the impact on circuit performance, is key to 3-D circuit applications. In this paper, we present a stochastic 3-D interconnect model and study the impact of 3-D integration on circuit performance and power consumption. To model 3-D interconnect, we divide 3-D wires into two parts (horizontal wires and vertical wires) and derive their stochastic distributions. Based on those distributions, we estimate the delay distribution. We show that 3-D structures effectively reduce the number of long delay nets, significantly reduce the number of repeaters, and dramatically improve circuit performance. With 3-D integration, circuits can be clocked at frequencies much higher (double or even triple) than 2-D.

In this paper, we study the interconnect layout optimization problem under a higher order resistance-inductance-capacitance model to optimize not only delay, but also waveform for interconnects with nonmonotone signal response in the context of multichip-module global routing. We propose a unified approach that considers topology optimization and waveform optimization simultaneously. Using a new incremental moment-computation algorithm, we interleave topology construction with moment computation to facilitate accurate delay calculation and evaluation of waveform quality. Our algorithm considers a large class of routing topologies, ranging from shortest path Steiner trees to bounded-radius Steiner trees and Steiner routings. We construct a set of required arrival-time Steiner (RATS) trees, providing smooth tradeoffs among signal delay, waveform, and routing area. When combined with the MINOTAUR MCM global router (Cong and Madden, 1998), (Madden, 1998) that we have developed, the RATS-tree solutions prove to be effective in reducing overall routing congestion.

Estimating human poses is an important step towards developing robots that can understand human motions and improving their cognitive capabilities. This paper presents a geometric feature for estimating human poses from a 3D point cloud input. The proposed feature can be considered as an extension of the idea of visual features, such as color/edge, of color/grayscale images, and it contains the geometric structure of the point cloud. It is derived by arranging the 3D points into a tree structure, which preserves the global and local properties of the 3D points. Shown experimentally, the tree structure (spatial ordering) is particularly important for estimating human poses (i.e., articulated objects). The 3D orientation (pan, tilt and yaw angles) and shape features are then extracted from each node in the tree to describe the geometric distribution of the 3D points. The proposed feature has been evaluated on a benchmark dataset and compared with two existing geometric features. Experimental results show that the proposed feature has the lowest overall error in human-pose estimation.

This paper presents a comprehensive survey of existing techniques for interconnect optimization during the VLSI physical design process, with emphasis on recent studies on interconnect design and optimization for high-performance VLSI circuit design under the deep submicron fabrication technologies. First, we present a number of interconnect delay models and driver/gate delay models of various degrees of accuracy and efficiency which are most useful to guide the circuit design and interconnect optimization process. Then, we classify the existing work on optimization of VLSI interconnect into the following three categories and discuss the results in each category in detail: (i) topology optimization for high-performance interconnects, including the algorithms for total wire length minimization, critical path length minimization, and delay minimization; (ii) device and interconnect sizing, including techniques for efficient driver, gate, and transistor sizing, optimal wire sizing, and simultaneous topology construction, buffer insertion, buffer and wire sizing; (iii) high-performance clock routing, including abstract clock net topology generation and embedding, planar clock routing, buffer and wire sizing for clock nets, non-tree clock routing, and clock schedule optimization. For each method, we discuss its effectiveness, its advantages and limitations, as well as its computational efficiency. We group the related techniques according to either their optimization techniques or optimization objectives so that the reader can easily compare the quality and efficiency of different solutions.

The simulation of realistically sized devices under the Non-Equilibrium Greens Function (NEGF) formalism typically requires prohibitive amounts of memory and computation time. In order to meet the rising computational challenges associated with quantum-scale device simulation we offer a 2-D domain decomposition technique. This technique is applicable to a large class of atomistic and spatial simulation problems. Considering a decomposition along both the cross section and length of the device, the framework presented in this work ensures efficient distribution of both memory and computation based upon the underlying device structure. As an illustration we stably generate the density of states and transmission, under the NEGF formalism, for the atomistic-based simulation of square 5 nm cross section silicon nanowires consisting of over one million atomic orbitals.

It has been predicted that a processor's caches could occupy as much as 90% of chip area for technology nodes from the current. In this paper, we study the use of multi-level spin-transfer torque RAM (STT-RAM) cells in the design of processor caches. Compared to the traditional SRAM caches, a multi-level cell (MLC) STT-RAM cache design is denser, fast, and consumes less energy. However, a number of critical issues remains to be solved before MLC STT-RAM technology can be deployed in processor caches. In this paper, we shall offer solutions to the issue of bit encoding as well as tackle the write endurance problem. The latter has been neglected in previous works on STT-RAM caches. We propose a set remapping scheme that can potentially prolong the lifetime of a MLC STT-RAM cache by 80× on average. Furthermore, a method for recovering the performance that may be lost in some applications due to set remapping is introduced.

The eight papers in this special section highlight several studies on contemporary and emerging issues in physical design.

Search engines have greatly influenced the way people access information on the Internet as such engines provide the preferred entry point to billions of pages on the Web. Therefore, highly ranked web pages generally have higher visibility to people and pushing the ranking higher has become the top priority for webmasters. As a matter of fact, search engine optimization(SEO) has became a sizeable business that attempts to improve their clients’ ranking. Still, the natural reluctance of search engine companies to reveal their internal mechanisms and the lack of ways to validate SEO’s methods have created numerous myths and fallacies associated with ranking algorithms; Google’sin particular. In this paper, we focus on the Google ranking algorithm and design, implement, and evaluate a ranking system to systematically validate assumptions others have made about this popular ranking algorithm. We demonstrate that linear learning models, coupled with a recursive partitioning ranking scheme, are capable of reverse engineering Google’s ranking algorithm with high accuracy. As an example, we manage to correctly predict 7 out of the top 10 pages for 78% of evaluated keywords. Moreover, for content-only ranking, our system can correctly predict 9 or more pages out of the top 10 ones for 77% of search terms. We show how our ranking system can be used to reveal the relative importance of ranking features in Google’s ranking function, provide guidelines for SEOs and webmasters to optimize their web pages, validate or disapprove new ranking features, and evaluate search engine ranking results for possible ranking bias.

We present an algorithm for the fast and accurate simulation of power/ground mesh structures. Our method is a direct (non-iterative) approach for simulation based upon a parallel matrix inversion algorithm. Through the use of additional computational resources, this distributed computing technique facilitates the simulation of large-scale power/ground networks. In addition, the new dimension of flexibility provided by our algorithm allows for a more accurate analysis of power/ground mesh structures using RLC interconnect models. Specifically, we offer a method that employs a sparse approximate inverse technique to consider more reluctance coupling terms for increased accuracy of simulation. The inclusion of additional coupling terms, however, does not lead to an increase in either time or memory requirements associated with the primary computational task in transient simulation, thus making the simulation procedure scalable. The parallel matrix inversion algorithm shows substantial computational improvement over the best known direct and iterative numerical techniques that are applicable to these large-scale simulation problems.

There has been much work on the next generation of memory technologies such as MRAM, RRAM and PRAM. Most of these are non-volatile in nature, and compared to SRAM, they are often denser, just as fast, and have much lower energy consumption. Using 3-D stacking technology, it has been proposed that they can be used instead of SRAM in large level 2 caches prevalent in today's microprocessors. However, one of the key challenges in the use of these technologies, such as MRAM, is their higher fault probabilities arising from the larger process variation, defects in its fabrication, and the fact that the cache is much larger. This seriously affect yield. In this paper, we propose a fault resilient set associative cache architecture which we called the salvage cache. In the salvage cache, a faulty cache block is sacrificed and used to repair faults found in other blocks. We will describe in detail the architecture of the salvage cache as well as provide results of yield simulations that show that a much higher yield can be achieved viz-a-viz other fault tolerant techniques. We will also show the performance savings that arise from the use of a large next-generation L2 cache.

State-of-the-art integral-equation-based solvers rely on techniques that can perform a matrix-vector multiplication in O(N) complexity. In this work, a fast inverse of linear complexity was developed to solve a dense system of linear equations directly for the capacitance extraction of any arbitrary shaped 3D structure. The proposed direct solver has demonstrated clear advantages over state-of-the-art solvers such as FastCap and HiCap; with fast CPU time and modest memory consumption, and without sacrificing accuracy. It successfully inverts a dense matrix that involves more than one million unknowns associated with a large-scale on-chip 3D interconnect embedded in inhomogeneous materials. Moreover, we have successfully applied the proposed solver to full-wave extraction.

In this paper the analysis and design of next-generation VLSI circuits using accurate electromagnetics-based models result in numerical problems of very large scale is presented. Typically, the solution of a problem with N parameters requires at least O(N) computation. With next generation VLSI circuits, however, even O(N) is prohibitively high since N is very large. The method that partially addresses this issue was developed for full-wave modeling of large-scale interconnect structures. In this method, a number of seeds (a seed has a unique cross section) are first recognized from an interconnect structure. In each seed, the original wave propagation problem is represented as a generalized eigenvalue problem. The complexity of solving 3D interconnects of O(N) is then overcome by seeking the solution of a few 2D seeds, which is then post-processed to obtain the solution of the original 3D problem through the development of an on-chip mode-matching technique. The computational bottleneck is the solution of a generalized eigenvalue problem. Efficient algorithms such as ARPACK [2] still require O(M2) storage and operations due to a dense matrix-vector multiplication. We present an algorithm that provides a solution to the generalized eigenvalue problem with O(M) complexity, thus paving the way for the full-wave simulation of next generation VLSI circuits.

In embedded systems, performance and power are important inter-related issues that cannot be decoupled. Expensive and extensive simulations in a processor design space are usually required to verify whether a design meets both performance and power requirements. In this paper, an analytical co-optimization approach based on an integrated workload, performance and power model for modern processors is described and studied. A design space consisting of more than 15 architectural and workload parameters can be quickly explored for co-optimization. Validation with measured results obtained from simulators as well as physical processors showed that the model has a good degree of accuracy. We shall describe the details of approach and the model, and show how to apply the approach to the problem of co-optimizing the power and performance of processor design. With the completeness, flexibility and efficiency, our approach provides clear insights into the tradeoffs of designs for performance and power.

A very fast Smith-method-based Newton algorithm is introduced for the solution of large-scale continuous-time algebraic Riccati equations (CAREs). When the CARE contains low-rank matrices, as is common in the modeling of physical systems, the proposed algorithm, called the Newton/Smith CARE or NSCARE algorithm, offers significant computational savings over conventional CARE solvers. The effectiveness of the algorithm is demonstrated in the context of VLSI model order reduction, wherein stochastic balanced truncation (SBT) is used to reduce large-scale passive circuits. It is shown that the NSCARE algorithm exhibits guaranteed quadratic convergence under mild assumptions. Moreover, two large-sized matrix factorizations and one large-scale singular value decomposition (SVD), necessary for SBT, can be omitted by utilizing the Smith method output in each Newton iteration, thereby significantly speeding up the model reduction process.

In this paper, we propose a metric for effective inductive coupling: the matrix (R + j/spl omega/L)/sup -1/, where R and L are the resistance and inductance matrices. We use this metric to analyze the effectiveness of shields on reducing inductive coupling. Our analysis shows how the resistances of shields affect the effective inductive coupling between signal nets. SPICE simulations are carried out to validate the proposed metric.

The eight papers in this special section are extended versions of papers presented at the 2011 International Symposium on Physical Design (ISPD 2011), held in Santa Barbara, CA.

Through the Non-Equilibrium Green's Function (NEGF) formalism, quantum-scale device simulation can be performed with the inclusion of electron-phonon scattering. However, the simulation of realistically sized devices under the NEGF formalism typically requires prohibitive amounts of memory and computation time. Two of the most demanding computational problems for NEGF simulation involve mathematical operations with structured matrices called semiseparable matrices. In this work, we present parallel approaches for these computational problems which allow for efficient distribution of both memory and computation based upon the underlying device structure. This is critical when simulating realistically sized devices due to the aforementioned computational burdens. First, we consider determining a distributed compact representation for the retarded Green's function matrix $G^{R}$. This compact representation is exact and allows for any entry in the matrix to be generated through the inherent semiseparable structure. The second parallel operation allows for the computation of electron density and current characteristics for the device. Specifically, matrix products between the distributed representation for the semiseparable matrix $G^{R}$ and the self-energy scattering terms in $\Sigma^{