We propose a global placement algorithm that employs size scaling of circuit components to provide continuity during placement. In the context of mixed-size placement, size scaling is utilized to handle significant variations among the sizes of the components, thereby avoiding additional complexity that is often associated with multiple levels of smoothing. By using the optimal region approach to first determine an initial placement, the size scaling approach allows the global placement algorithm to converge to better placement solutions.

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.

We introduce a technique that utilizes distributing computing resources for the efficient optimization of a traditional physical design problem. Specifically, we present a detailed placement strategy designed to exploit distributed computing environments, where the additional computing resources are employed in parallel to improve the optimization time. A Mixed Integer Programming (MIP) model and branch-and-cut optimization strategy are employed to solve the standard cell placement problem. By exploiting the problem structure, our algorithm improves upon the solutions afforded by existing optimization algorithms. First, an efficient batch-branching technique can eliminate several integer decision variables during each step of the optimization procedure. This batch-branching scheme can be performed serially or in parallel. In addition, custom cutting-planes are shown to significantly reduce the run time for optimizations as they efficiently refine the feasible region in order to quickly produce integer solutions. Our serial branch-and-cut strategies allow for significant reductions in wirelength, relative to the state-of-the-art commercial software package CPLEX, assuming a fixed allotment of time. Furthermore, we show that distributed computing resources can be used to significantly reduce the time required to achieve reductions in wirelength.

An algorithm is presented 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. The new dimension of flexibility provided by our algorithm allows for a more accurate analysis of power/ground mesh structures using resistance, inductance, capacitance, 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. Our algorithm shows substantial computational improvement over the best known direct and iterative numerical techniques that are applicable to these large-scale simulation problems.

This paper studies the effects of clustering as a pre-processing step and routability estimation in the placement flow. The study shows that when clustering and routability estimation are considered, the placer effectively improves the routed wirelength for the circuits of IBM-PLACE 2.0 standard-cell Benchmark Suite [1] and results in the best average routed wirelength when compared against state-of-the-art academic placers.

This paper presents an efficient technique for the estimation of the routed wirelength during global placement using the wire density of the net. The proposed method identifies congested regions of the chip and incorporates the model of the routed wirelength into the objective function in order to effectively alleviate these regions from congestion. The method is integrated in the analytical placement framework and the two-level structure improves the scalability of the placer and speeds up the algorithm. The proposed analytical placer provides the best-so-far average routed wirelength in the IBM version2 benchmark suite.

We present an efficient technique for the fast and accurate extraction of inductance of large-scale on-chip interconnects. Several simulation techniques exploit the sparsity of L−1for reducing storage and computational costs during computation. Recently, band matching technique was introduced for sparsification of L−1. We extend the band-matching technique for inductance extraction problems. We introduce an efficient technique to invert the approximate band-matched impedance matrix Rƒ + jω̃Lƒ. The new technique relies on a numerically stable and efficient representation for inverses of banded matrices. Numerical results show that our approach is both accurate as well as computationally efficient, with orders-of-magnitude improvement over traditional techniques.

Balanced truncation (BT), as applied to date in model order reduction (MOR), is known for its superior accuracy and computable error bounds. Positive-real BT (PRBT) is a particular BT procedure that preserves passivity and stability and imposes no structural constraints on the original state space. However, PRBT requires solving two algebraic Riccati equations (AREs), whose computational complexity limits its practical use in large-scale systems. This paper introduces a novel quadratic extension of the alternating direction implicit (ADI) iteration, which is called quadratic ADI (QADI), that efficiently solves an ARE. A Cholesky factor version of QADI, which is called CFQADI, exploits low-rank matrices and further accelerates PRBT.

We present a technique for the fast and accurate simulation of large-scale VLSI interconnects with nonlinear devices, called SASIMI. The numerical efficiency of this technique is realized through linear-algebraic techniques that exploit the sparsity and structure of the matrices that are encountered in VLSI structures. Numerical results show that SASIMI is up to 1400 times as fast as commercial-grade SPICE, for moderate-size circuits, with little sacrifice in simulation accuracy.

We present a new algorithm for discretizing interconnects, a step that is typically performed to account for the nonuniformity of current flow at high frequencies. The algorithm is based on an easily-computable measure that correlates well with the model accuracy. This measure is used to refine the discretization of interconnects in an adaptive scheme so as to systematically trade off computation against model accuracy. We apply the proposed discretization technique on two classes of problems in the analysis of VLSI interconnects: simulation and frequency-dependent inductance extraction. Numerical results establish that with the interconnect discretizations generated by our algorithm, a reduction in simulation and extraction times by a factor between three and seven can be realized with negligible sacrifice in model accuracy (<1% error)

This paper presents a multi-shift generalization of the recently proposed quadratic alternating direction implicit (QADI) iteration. QADI and its Cholesky Factor (CF) variant, CFQADI, have been shown to be efficient ways of solving the large-scale algebraic Riccati equations (AREs) required in positive-real balanced truncation (PRBT). However, only their single-shift implementations have been considered so far. Using linear fractional transformation (LFT), we present elegant multi-shift extensions of both QADI and CFQADI, thereby enabling even faster and more accurate PRBT.

Recent successful techniques for the efficient simulation of largescale interconnect models rely on the sparsification of the inverse of the inductance matrix L. While there are several techniques for sparsifying L-1, the stability of these approximations for general interconnect structures has not been established, i.e., the sparsified reluctance and inductance matrices are not guaranteed to be positive-definite. In this paper, we present a novel technique for reluctance sparsification for general interconnect structures that enjoys several advantages: First, the resulting sparse approximation is guaranteed to be positive definite. Second, the approximation is optimal, in a certain well-defined sense. Third, owing to its computational efficiency and numerical stability, the algorithm is applicable for very large problem sizes. Finally our approach yields a compact representation of both inductance and reluctance matrices for general cases.

This paper presents two recently developed algorithms for efficient model order reduction. Both algorithms enable the fast solution of continuous-time algebraic Riccati equations (CAREs) that constitute the bottleneck in the passivity-preserving balanced stochastic truncation (BST). The first algorithm is a Smith-method-based Newton algorithm, called Newton/Smith CARE, that exploits low-rank matrices commonly found in physical system modeling. The second algorithm is a project-and-balance scheme that utilizes dominant eigenspace projection, followed by a simultaneous solution of a pair of dual CAREs through completely separating the stable and unstable invariant subspaces of a Hamiltonian matrix. The algorithms can be applied individually or together. Numerical examples show the proposed algorithms offer significant computational savings and better accuracy in reduced-order models over those from conventional schemes.

The sparsification of the reluctance matrix L-1 (where L denotes the usual inductance matrix L) has been widely used in several recent investigations to make the problem of simulation of interconnects tractable. Although these sparsification techniques work well in practice, the stability of these approximations has not been established, i.e., the sparsified reluctance and inductance matrices are not guaranteed to be positive-definite. In this work, we propose a band matching method that enjoys two advantages: First, we exploit the elegant structure of the inverse of banded matrices so as to construct an approximate inductance matrix L whose band entries match the band entries of original L, and whose inverse is a banded matrix. This approach yields a compact representation of both inductance and reluctance matrices. Second, we establish that the compact approximant L is guaranteed to be positive-definite. Simulation results show that our approach enjoys an approximation accuracy that is comparable to that of existing methods.

We present a statistical based non-tree clock distribution construction algorithm that starts with a tree and incrementally insert cross links, such that the skew variation of the final clock network is within a certain confidence interval under variations in wire width. Monte Carlo simulations show that the robustness of the final clock network can be significantly improved with a small increase in wire length.

Balanced truncation (BT) model order reduction (MOR) is known for its superior accuracy and computable error bounds. Balanced stochastic truncation (BST) is a particular BT procedure that provides a general, structure-independent MOR framework to preserve both passivity and stability of original models. Its application toward large scale systems, however, has been limited by the complexity of solving large size continuous time algebraic Riccati equations (CAREs). This paper introduces a novel quadratic extension of the alternating direction implicit (ADI) iteration, called QADI, that efficiently solves a CARE. A Cholesky factor variant of QADI, called CFQADI, further exploits low rank matrices and and produces solution in factor form that greatly accelerates BST. Remarkable efficiency of the proposed BST/(CF)QADI integration is demonstrated with numerical examples.

This paper presents an efficient t o-stage project-and-balance scheme for passivity-preserving model order reduction. Orthogonal dominant eigenspace projection is implemented by integrating the Smith method and Krylov subspace iteration. It is followed by stochastic balanced truncation herein a novel method, based on the complete separation of stable and unstable invariant subspaces of a Hamiltonian matrix, is used for solving two dual algebraic Riccati equations at the cost of essentially one. A fast-converging quadruple-shift bulge-chasing SR algorithm is also introduced for this purpose. Numerical examples confirm the quality of the reduced-order models over those from conventional schemes.

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.

This work introduces an efficient and accurate interconnect simulation technique. A new formulation for typical VLSI interconnect structures is proposed which, in addition to providing a compact set of modeling equations, also offers a potential for exploiting sparsity at the simulation level. Simulations show that our approach can achieve 50 /spl times/ improvement in computation time and memory over INDUCTWISE (which in turn has been shown to be 400 /spl times/ faster than SPICE) while preserving simulation accuracy.

The determination of the set (or window) of segments that are inductively coupled to a significant degree with a given segment plays a fundamental role in window-based techniques for the extraction of the susceptance of interconnect structures. We present a measure that quantifies the degree of coupling between segments in a window, thereby paving the way for an adaptive scheme for determining the coupling window associated with each segment. This measure has the properties that: (i)~it is well-correlated with the simulation error that is inherent in window-based susceptance extraction techniques, and (ii)~it can be computed efficiently using incremental and computation reuse techniques.

This paper presents a highly efficient geometrical approach for designing robust minimum variance (RMV) beamformers against uncertainties in the array steering vector. Instead of the conventional approach of modeling the uncertainty region by a convex closed space, the proposed algorithm exploits the optimization constraint and shows that optimization only needs to be done on the intersection of a hyperplane and a second-order cone (SOC). The problem can then be cast as a second-order cone programming (SOCP) problem so as to enjoy the high efficiency of a class of interior point algorithms. A general case of modeling the uncertainties of an array using complex-plane trapezoids is investigated. The efficiency and tightness of the proposed method over other schemes are demonstrated with numerical examples.

Teleoperated robots in harsh environments have a significant likelihood of failures. It has been shown in previous work that a common type of failure such as that of a joint "locking up," when unidentified by the robot controller, can cause considerable performance degradation in the local behavior of the manipulator even for simple point-to-point motion tasks. The effects of a failure become more critical for a system with a human in the loop, where unpredictable behavior of the robotic arm can completely disorient the operator. In this experimental study involving teleoperation of a graphically simulated kinematically redundant manipulator, two control schemes, the pseudoinverse and a proposed failure-tolerant inverse, were randomly presented under both nonfailure and failure scenarios to a group of operators. Based on performance measures derived from the recorded trajectory data and operator ratings of task difficulty, it is seen that the failure-tolerant inverse kinematic control scheme improved the performance of the human/robot system.

We present a framework for passivity-preserving model reduction for RLC systems that includes, as a special case, the well-known PRIMA model reduction algorithm. This framework provides a new interpretation for PRIMA, and offers a qualitative explanation as to why PRIMA performs remarkably well in practice. In addition, the framework enables the derivation of new error bounds for PRIMA-like methods. We also show how the framework offers a systematic approach to computing reduced-order models that better approximate the original system than PRIMA, while still preserving passivity.

Presents a new passive model reduction algorithm based on the Laguerre expansion of the time response of interconnect networks. We derive expressions for the Laguerre coefficient matrices that minimize a weighted square of the approximation error, and show how these matrices can be computed efficiently using Krylov subspace methods. We discuss the connections between our method and other methods such as PRIMA. Numerical simulations show that our method can better approximate the original model as compared to PRIMA.

We present a new technique to solve array pattern synthesis problems by using semidefinite programming. We first formulate (or reformulate) the array design problems into semidefinite programming problems, and then use the recently developed efficient numerical algorithms and software to compute the numerical solution of antenna array weights. Using this approach, we can directly solve not only the standard synthesis problems for nonuniform arrays, but also the synthesis problems for arrays having power restrictions and uncertainties. Numerical examples are presented to illustrate our approach.

Eigendecomposition-based techniques are popular for a number of computer vision problems, e.g., object and pose detection, because they are purely appearance-based and they require few on-line computations. Unfortunately, they also typically require an unobstructed view of the object whose pose is being detected. The presence of occlusion precludes the use of the normalizations that are typically applied and significantly alters the appearance of the object under detection. This work presents an algorithm that is based on applying eigendecomposition to a quadtree representation of the image dataset used to describe the appearance of an object. This allows decisions concerning the pose of an object to be based on only those portions of the image in which the algorithm has determined that the object is not occluded. The accuracy and computational efficiency of the proposed approach is evaluated on sixteen different objects with up to 50% of the object being occluded.

We present a computationally efficient algorithm for the eigenspace decomposition of correlated images. Our approach is motivated by the fact that for a planar rotation of a two-dimensional (2-D) image, analytical expressions can be given for the eigendecomposition, based on the theory of circulant matrices. These analytical expressions turn out to be good first approximations of the eigendecomposition, even for three-dimensional (3-D) objects rotated about a single axis. In addition, the theory of circulant matrices yields good approximations to the eigendecomposition for images that result when objects are translated and scaled. We use these observations to automatically determine the dimension of the subspace required to represent an image with a guaranteed user-specified accuracy, as well as to quickly compute a basis for the subspace. Examples show that the algorithm performs very well on a number of test cases ranging from images of 3-D objects rotated about a single axis to arbitrary video sequences.

The use of robots in hostile environments significantly increases the likelihood of failures in the robot's subsystems. Existing techniques for developing failure tolerant robots rely on effective failure detection and identification. Since failure identification is itself a difficult process that may not always be successful, it is important to consider the behavior of the robot prior to identification of a fault, or even the possibility of failures remaining unidentified. This work proposes control strategies that improve local measures of failure tolerance for kinematically redundant robots experiencing unidentified locked-joint failures. Measures to evaluate the fault tolerance capability of the various schemes are presented and the performance of the proposed schemes are demonstrated with an example.

Teleoperated robots in harsh environments have a significant likelihood of failures. A common type of failure such as that of a joint "locking up", when unidentified by the robot controller, can cause considerable performance degradation in the local behavior of the manipulator even for simple point-to-point motion tasks. The effects of a failure become more critical for a system with a human in the loop, where unpredictable behavior of the robotic arm can completely disorient the operator. In this experimental study involving teleoperation of a graphically simulated kinematically redundant manipulator, two control schemes, the pseudo-inverse and a proposed failure-tolerant inverse, were randomly presented under both non-failure and failure scenarios to a group of operators. Based on the performance measures derived from the recorded trajectory data and operator responses, it is seen that the failure-tolerant inverse kinematic control scheme improved the performance of the human/robot system.

Considers real-time fault-tolerant control of kinematically redundant manipulators to single locked-joint failures. The fault-tolerance measure used is a worst-case quantity, given by the minimum, over all single joint failures, of the minimum singular value of the post-failure Jacobians. Given any end-effector trajectory, the goal is to continuously follow this trajectory with the manipulator in configurations that maximize the fault-tolerance measure. The computation required to track these optimal configurations with brute-force methods is prohibitive for real-time implementation. We address this issue by presenting algorithms that quickly compute estimates of the worst-case fault-tolerance measure and its gradient. Comparisons show that the performance of the best method is indistinguishable from that of brute-force implementations. An example demonstrating the real-time performance of the algorithm on a commercially available seven degree-of-freedom manipulator is presented.

We present a computationally efficient algorithm for the eigenspace decomposition of correlated images. Our approach is motivated by the fact that for a planar rotation of a two-dimensional image, analytical expressions can be given for the eigendecomposition, based on the theory of circulant matrices. These analytical expressions turn out to be good first approximations of the eigendecomposition, even for three-dimensional objects rotated about a single axis. We use this observation to automatically determine the dimension of the subspace required to represent an image with a guaranteed user-specified accuracy, as well as to quickly compute a basis for the subspace. Examples show that the algorithm performs very well on a range of test images composed of three-dimensional objects rotated about a single axis.

Robots are frequently used for operations in hostile environments. The very nature of these environments, however, increases the likelihood of robot failures. Common failure tolerance techniques rely on effective failure detection. Since a failure may not always be successfully detected, or even if detected, may not be detected soon enough, it becomes important to consider the behavior of manipulators with undetected failures. This work focuses on developing techniques to analyse a manipulator's workspace and identify regions in which tasks, characterized by sequences of point-to-point moves, can be completed even with such failures. Measures of fault tolerance are formulated to allow for the evaluation of the workspace.

Operations in hazardous or remote environments are invariably performed by robots. The hostile nature of the environments, however, increase the likelihood of failures for robots used in such applications. The difficulty and delay in the detection and consequent correction of these faults makes the post-fault performance of the robots particularly important. This work investigates the behavior of robots experiencing undetected locked-joint failures in a general class of tasks characterized by point-to-point motion. The robot is considered to have "converged" to a task position and orientation if all its joints come to rest when the end-effector is at that position. It is seen that the post-fault behavior may be classified into three categories: (1) the robot converges to the task position; (2) the robot converges to a position other than the task position; or (3) the robot does not converge, but keeps moving forever. The specific conditions for convergence are identified, and the different behaviors illustrated with examples of simple planar manipulators.

This work considers real-time fault-tolerant control of kinematically redundant manipulators with single locked-joint failures. The fault-tolerance measure used is a worst-case quantity, given by the minimum, over all single joint failures, of the minimum singular value of the post-failure Jacobians. Given any end-effector trajectory, the goal is to continuously follow this trajectory with the manipulator in configurations that maximize the fault-tolerance measure. The computation required to track these optimal configurations with brute-force methods is prohibitive for real-time implementation. We address this issue by presenting algorithms that quickly compute estimates of the worst-case fault-tolerance measure and its gradient. Real-time implementations are presented for all these techniques, and comparisons show that the performance of the best is indistinguishable from that of brute-force implementations.

Given a discrete-time, linear, shift-invariant channel with finite impulse response, the problem of designing finite-length input signals with bounded amplitude (l/sub /spl infin// norm) such that the corresponding output signals are maximally separated in amplitude (l/sub /spl infin// sense) is considered. In general, this is a nonconvex optimization problem, and appears to be computationally difficult. An optimization algorithm that seems to perform well is described. Optimized signal sets and associated minimum distances (minimum l/sub /spl infin// separation between two distinct channel outputs) are presented for some example impulse responses. A conjectured upper bound on the minimum distance is given that is easily computed given the impulse response of the channel, the number of inputs, and the input length. This upper bound is shown to be valid for a limited class of impulse response functions.>