15151643
QMBF: a QoS-aware multicast routing protocol
Many multicast applications, such as video-on-demand and tele-education, desire quality of service (QoS) support from the underlying network. Recently, many QoS-based multicast protocols have been proposed to meet this requirement. However, few of them can achieve high success ratios while maintaining good scalability. In this paper, we propose a new QoS-aware multicast protocol based on a bounded flooding technique (QMBF). In this protocol, every network node maintains the knowledge of a local network cell (LNC) topology as well as QoS state information (collected from the bounded flooding messages). QMBF utilizes this knowledge to increase the probability and accuracy of finding a feasible branch which connects a new member to an existing multicast tree. The protocol exploits two approaches to find feasible branches: repeatedly computing partial feasible branches using the LNC information and searching multiple paths. The design of QMBF allows it to operate on top of any unicast routing protocol or cooperate with a QoS-based unicast routing protocol. Results obtained using NS-2 simulator demonstrate high success ratio for locating feasible branches for multicast paths.
206924248
The impact of topology on overlay routing service
A moderate amount of recent work has been dedicated to using overlay network to support value-added network service, such as overlay multicast, OverQoS, etc. Overlay service network is a generic service framework which is designed to provide a variety of services to overlay service customers. To design an overlay service network, the first step is to choose an overlay topology connecting all the overlay service nodes. For example, RON [Anderson, DG et al., 2001] has used full mesh topology connecting all the nodes. In this paper, we did a study on the impact of topology on the overlay routing service. We found that the overlay topology has significant impact on the overlay routing in terms of routing performance and routing overhead. For example, the full mesh topology does not always give us the best performance. Moreover, the physical topology information can benefit us a lot to construct an efficient overlay topology. In addition, some alternative topologies can provide us with better performance when considering both the routing performance and overhead.
1327847
On achieving maximum multicast throughput in undirected networks
The transmission of information within a data network is constrained by the network topology and link capacities. In this paper, we study the fundamental upper bound of information dissemination rates with these constraints in undirected networks, given the unique replicable and encodable properties of information flows. Based on recent advances in network coding and classical modeling techniques in flow networks, we provide a natural linear programming formulation of the maximum multicast rate problem. By applying Lagrangian relaxation on the primal and the dual linear programs (LPs), respectively, we derive a) a necessary and sufficient condition characterizing multicast rate feasibility, and b) an efficient and distributed subgradient algorithm for computing the maximum multicast rate. We also extend our discussions to multiple communication sessions, as well as to overlay and ad hoc network models. Both our theoretical and simulation results conclude that, network coding may not be instrumental to achieve better maximum multicast rates in most cases; rather, it facilitates the design of significantly more efficient algorithms to achieve such optimality.
23434511
A Compiler-Assisted Scheme for Adaptive Cache Coherence Enforcement
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],
3173724
Buffer insertion in large circuits with constructive solution search techniques
Most existing buffer insertion algorithms, such as van Ginneken's algorithm, consider only individual nets. As a result, these algorithms tend to over buffer when applied to combinational circuits, since it is difficult to decide how many buffers to insert in each net. Recently, Sze, et al. (Sze, 2005) proposed a path-based algorithm for buffer insertion in combinational circuits. However their algorithm is inefficient for large circuits when there are many critical paths. In this paper, we present a new buffer insertion algorithm for combinational circuits such that the timing requirements are met and the buffer cost is minimized. Our algorithm iteratively inserts buffers in the circuit to improve the circuit delay. The core of this algorithm is simple but effective technique that guides the search for a good buffering solution. Experimental results on ISCAS85 circuits show that our new algorithm on average uses 36% less buffers and runs 3 times faster than Sze's algorithm
1229745
Fast Video Shot Retrieval with Luminance Field Trace Indexing and Geometry Matching
Efficient indexing is a key in content-based video retrieval solutions. In this paper we represent video sequences as traces in an appropriate low dimensional space via luminance field scaling and PCA projection, and develop an efficient indexing scheme and trace geometry matching algorithms for fast and robust video retrieval. Simulation results demonstrate that the proposed solution is very fast and accurate in retrieval performance.