30650337
An Interlacing Result on Normalized Laplacians
Given a graph G, the normalized Laplacian associated with the graph G, denoted ${\cal L}$(G), was introduced by F. R. K. Chung and has been intensively studied in the last 10 years. For a k-regular graph G, the normalized Laplacian ${\cal L}$ (G) and the standard Laplacian matrix L(G) satisfy L(G) = k {\cal L} (G), and hence they have the same eigenvectors and their eigenvalues are directly related. However, for an irregular graph G, ${\cal L} (G) and L(G) behave quite differently, and the normalized Laplacian seems to be more natural. In this paper, Cauchy interlacing-type properties of the normalized Laplacian are investigated, and the following result is established. Let G be a graph, and let H = G - e, where e is an edge of G. Let $\lambda_1\geq \lambda_2 \geq \cdots \geq \lambda_{n}=0$ be the eigenvalues of ${\cal L}(G)$, and let $\theta_1\geq \theta_2 \geq \cdots \geq \theta_{n}$ be the eigenvalues of ${\cal L}(H)$. Then, $\lambda_{k-1} \geq \theta_{k}\geq \lambda_{k+1}$ for each k = 1, 2, 3, \dots, n, where $\lambda_{0} =2$ and $\lambda_{n+1}=0$. Applications are given for eigenvalues of graphs obtained from special graphs by adding or deleting a few edges. A short proof is given of the result that $G$ is a graph with each component a nontrivial bipartite graph if and only if $2-\lambda$ is an eigenvalue of ${\cal L}(G)$ for each eigenvalue $\lambda$ of ${\cal L }(G)$.
32094418
On Ranks of Matrices Associated with Trees
Abstract.A sign pattern matrix is a matrix whose entries are from the set {+,−,0}. The purpose of this paper is to obtain bounds on the minimum rank of any symmetric sign pattern matrix A whose graph is a tree T (possibly with loops). In the special case when A is nonnegative with positive diagonal and the graph of A is “star-like”, the exact value of the minimum rank of A is obtained. As a result, it is shown that the gap between the symmetric minimal and maximal ranks can be arbitrarily large for a symmetric tree sign pattern A.

195989392
Process variation dimension reduction based on SVD.
We propose an algorithm based on singular value decomposition (SVD) to reduce the number of process variation variables. With few process variation variables, fault simulation and timing analysis under process variation can be performed efficiently. Our algorithm reduces the number of process variation variables while preserving the delay function with respect to process variation. Compared with the principal component analysis (PCA) method, our algorithm requires less computation time and guarantees the reduced process variation variables are independent. Experimental results on ISCAS85 circuits show that the algorithm works well. 1 INTROCUTION In modern multi-layer VLSI circuits, the dimension of the process variation is large. For example, in a k-metal technology, there are 2k variables for metal width and thickness, k variables for inter-layer dielectric (ILD) thickness, a gate length variable, and some other variables. With such a large number of process variation variables, timing analysis under process variation is very time consuming, and may not find the worst-case process corner [1][2]. In this paper, we propose the novel concept of variation dimension reduction. The idea is originated from the following observation. For different nets, the underlying process variation variables are the same. Therefore, the delays of the nets are correlated. We model the delay from an input pin of a cell to an input pin of a downstream cell, also known as the buffer-to-buffer delay, as a linear function of process variation variables: d = dnominal(1 + a1x1 + a2x2 + ... + anxn), where x1, x2, ..., xn are process variation variables, a1, a2, ..., an are their corresponding coefficients, and dnominal is the nominal delay. For different nets, the coefficients are different, but the process variation variables are the same. The assumption that the delay is linear with respect to each process variation variable is supported by SPICE simulation of real circuits within reasonable ranges of the process variation [3]. There are many forms of process variation [4][5]. In this paper, we only consider systematic process variation and assume the process variation variables among different nets are fully correlated. We assume the following variation ranges: metal thickness ±20%, metal width ±10%, ILD thickness ±40%, and gate length ±10%. To obtain the delay function with respect to process variation, we first extract interconnect parasitic from the layout and compute the nominal buffer-to-buffer delay for all nets. Then for each process variation variable, we modify the layout or the technology file by varying a specified amount (for example, +10% for metal1 thickness), and perform RC extraction and delay evaluation for the modified layout. The coefficient for this process variation variable is obtained by interpolating the two delays. Recently, the principal component analysis (PCA) method was used to reduce the dimension of process variation [7]. It was shown to be effective for analyzing analog circuits under process variation. However, the PCA method is inefficient for digital circuits, because the PCA method constructs and solves a correlation matrix of size mn×mn, where n is the number of process variation variables and m is the number of nets or devices. For digital circuits, m is easily in hundreds or thousands. In this paper, we propose a new method based on singular value decomposition (SVD) [6]. Our algorithm detects the linear dependence and reduces the number of process variation variables, while minimizing the average error of the delay. Note that although the PCA method also uses SVD, their matrix is size mn×mn while ours is size m×n. To make the reduced process variables linearly/statistically independent, which is desirable for fault simulation and timing analysis, we also propose a sub-matrix SVD method. In Section 2, the SVD method and sub-matrix SVD method for dimension reduction are given. In Section 3, we show the experimental results. It shows that if we simply pick the most important process variation variables and discard the rest, then the average error of net delay is twice as much as the average error produced by our algorithm. 2 ALGORITHM 2.1 Singular Value Decomposition (SVD) The SVD method is based on the following theorems [6]. Theorem 1 If A is an m×n matrix, then there exist orthogonal m×m matrix U=[u1,...,um] and n×n matrix V=[v1,...,vn], such that U·A·V=diag(σ1,...,σp), which is an m×n matrix, p=min{m,n}, and σ1 ≥ σ2 ≥...≥ σp ≥ 0. The σi’s are the singular values of A, and vectors ui and vi are the ith left and right singular vector, respectively. The process to find U and V is called SVD. It can be done by the Golub-Reinsch algorithm of time complexity O(mn+mn+n) [6] (pp. 254). To compute U(:,1:n) =[u1,...,un], which is an m×n (m>n) matrix, the time complexity is O(mn+n) [6]. Theorem 2 Let the SVD of m×n matrix A be defined in Theorem 1. If r < rank(A) and let ∑ = = r i T i i i v u A 1 * σ , then 1 2 * 2 ) ( min + = = − = − r r B rank A A B A σ . In other words, A is the best 2-norm approximation of A among all rank r matrices. 2.2 Application to Dimension Reduction We are given the delay of m nets represented as Ax, where A is an m×n matrix, n is the number of process variation variables, x=[x1,...,xn] is the vector of process variation variables, and xi’s are independent of each other. From Theorem 2, A=U(:,1:r)·S·V(:,1:r), where S=diag(σ1,...,σr), U(:,1:r)=[u1,...,ur], and V(:,1:r) =[v1,...,vr]. Therefore, Ax≈Ax=U(:,1:r)·S·V(:,1:r)x=Bz, where B=U(:,1:r)·S is an m×r matrix and z=V(:,1:r)x is an r×1 vector. Since the dimension of B is much less than the dimension of A, we use Bz to approximate Ax. If we just want to reduce the number of process variation variables, then Bz is the resulting delay function, and z is the vector of new process variation variables. However, we often have an additional requirement from circuit simulation that the new process variation variables z1, ..., zr must be independent. For example, if z1=x1−x2+x3 and z2=x1+x2−x3, then z1 and z2 are not independent although the number of variables is reduced from 3 to 2. 2.3 Sub-Matrix SVD (SMSVD) We propose a sub-matrix SVD method (SMSVD) to ensure the independence between zi’s. The basic idea is to partition columns of A into r sub-matrices, and then use SVD on each sub-matrix. The following is the algorithm: 1) Partition A into sub-matrices A1, A2, ..., Ar, where A=[A1, A2,..., Ar]. Ai is an m×qi matrix, i=1,..., r. 2) For i=1,..., r, compute the approximation matrix Ai of Ai through SVD in which the approximation rank is 1. Define SVD of Ai as Ui·Ai·Vi=diag(σi1,...,σip), then Ai=Ui(:,1)·σi1·Vi(:,1) and ║Ai−Ai║2=σi2. 3) Construct B=[U1(:,1)σ11, U2(:,1)σ21, ..., Ur(:,1)σr1],
207107821
Different Retinal Ganglion Cells have Different Functional Goals
In mammalian retina, the Y (or M) ganglion cells are significantly more transient in response, more selective to stimuli of low spatial and high temporal frequencies and less selective to spectral information than the X (or P) cells. It is shown that these differences in cell properties can be explained by a model that assigns different functional goals to the different ganglion cell types. In this model, the goal of the Y cells is to extract as fast as possible the minimum amount of information necessary for quick responses. In contrast, the goal of the X cells is to extract as much information as possible. Temporal characteristics of the information extraction by the two cell groups are also derived.
12268086
Integrating Parallelizing Compilation Technology and Processor Architecture for Cost-Effective Concurrent multithreading
As the number of transistors on a single chip continues to grow, it is important to think beyond the traditional approaches of compiler optimizations for deeper pipelines and wider instruction issue units to improve performance. This single-threaded execution model limits these approaches to exploiting only the relatively small amount of instruction-level parallelism available in application programs. While integrating an entire multiprocessor onto a single chip is feasible, this architecture is limited to exploiting only relatively coarse-grained parallelism. We propose a concurrent multi-threaded architecture, called the superthreaded architecture, as an alternative. As a hybrid of a wide-issue superscalar processor and a multiprocessor-on-a-chip, this new concurrent multithread-ing architecture can leverage the best of existing and future parallel hardware and compilation technologies. By combining compiler-directed thread-level speculation for control and data dependences with run-time checking of data dependences, the superthreaded architecture can exploit the multiple granularities of parallelism available in general-purpose application programs to reduce the execution time of a single program.
19202401
Making fast buffer insertion even faster via approximation techniques
26251695
Grasp analysis as linear matrix inequality problems
Three important problems in the study of grasping and manipulation by multi-fingered robotic hands are: 1) given a grasp characterised by a set of contact points and the associated contact models, determine if the grasp has force closure; 2) if the grasp does not have force closure, determine if the fingers are able to apply a specified resultant wrench on the object; and 3) compute "optimal" contact forces if the answer to problem (2) is affirmative. In this paper, based on an early result by Buss-Hashimoto-Moore (1996), which transforms the nonlinear friction cone constraints into positive definiteness of certain symmetric matrices, we further cast the friction cone constraints into linear matrix inequalities (LMIs) and formulate all three of the problems stated above as a set of convex optimization problems involving LMIs. We perform simulation studies to show the simplicity and efficiency of the LMI formulation to the three problems.