With operating frequencies entering the multi-gigahertz range, inductance has become an important consideration in the design and analysis of on-chip interconnects. In this paper, we present an accurate and efficient inductance modeling and analysis methodology for high-performance interconnect. We determine the critical elements for a PEEC based model by analyzing the current flow in the power grid and signal interconnect. The proposed model includes distributed interconnect resistance, inductance and capacitance, device decoupling capacitances, quiescent switching currents in the grid, pad connections, and pad/package inductance. We propose an efficient methodology for extracting these elements, using statistical models for on-chip decoupling capacitance and switching currents. Simulation results show the importance of various elements for accurate inductance analysis. We also demonstrate the accuracy of the proposed model compared to the traditional loop-based inductance approach. Since the proposed model can consist of hundreds of thousands of RLC elements, and a fully dense mutual inductance matrix, we propose a number of acceleration techniques that enable efficient analysis of large interconnect structures.

A new technique for design centering and polytope approximation of the feasible region for a design are presented. In the first phase, the feasible region is approximated by a convex polytope, using a method based on a theorem on convex sets. As a natural consequence of this approach, a good approximation to the design center is obtained. In the next phase, the exact design center is estimated using one of two techniques that we present in this paper. The first inscribes the largest Hessian ellipsoid, which is known to be a good approximation to the shape of the polytope, within the polytope. This represents an improvement over previous methods, such as simplicial approximation, where a hypersphere or a crudely estimated ellipsoid is inscribed within the approximating polytope. However, when the probability density functions of the design parameters are known, the design center does not necessarily correspond to the center of the largest inscribed ellipsoid. Hence, a second technique is developed that incorporates the probability distributions of the parameters, under the assumption that their variation is modeled by Gaussian probability distributions. The problem is formulated as a convex programming problem and an efficient algorithm is used to calculate the design center, using fast and efficient Monte Carlo methods to estimate the yield gradient. An example is provided to illustrate how ellipsoid-based methods fail to incorporate the probability density functions and is solved using the convex programming-based algorithm.>

Two new geometrical algorithms for design centering are presented. In each case, the feasible region is first approximated by a convex polytope. The first algorithm inscribes the largest Hessian ellipsoid within the approximating polytope. The second assumes Gaussian parameter distributions, formulates the problem as a convex programming problem, and uses an efficient algorithm to perform the optimization.

A general sequential circuit consists of a number of combinational stages that lie between latches. For the circuit to meet a given clocking specification, it is necessary for each combinational stage to satisfy a certain delay requirement. Roughly speaking, increasing the sizes of some transistors in a stage reduces the delay, with the penalty of increased area. The problem of transistor sizing is to minimize the area of a combinational stage, subject to its delay being less than a given specification. Although this problem has been recognized as a convex programming problem, most existing approaches do not take full advantage of this fact, and often give nonoptimal results. An efficient convex optimization algorithm has been used here. This algorithm is guaranteed to find the exact solution to the convex programming problem. We have also improved upon existing methods for computing the circuit delay as an Elmore time constant, to achieve higher accuracy, CMOS circuit examples, including a combinational circuit with 832 transistors are presented to demonstrate the efficacy of the new algorithm.>

The transistor sizing problem of minimizing the circuit area, subject to the circuit delay being less than a given specification, is formulated as a convex programming problem. An efficient convex programming algorithm is then used to obtain the exact solution. Experimental results on a variety of circuits show that, for a given delay specification this approach is able to produce circuits with significantly smaller area when compared with TILOS.>

The parallel complexity of solving linear programming problems is studied in the context of interior point methods. If n and m, respectively, denote the number of variables and the number of constraints in the given problem, an algorithm that solves linear programming problems in O((mn)/sup 1/4/ (log 1 n)/sup 3/L) time using O(M(n)m/n+1n/sup 3/) processors is given. (M(n) is the number of operations for multiplying two n*n matrices). This gives an improvement in the parallel running time for n=o(m). A typical case in which n=o(m) is the dual of the uncapacitated transportation problem. The algorithm solves the uncapacitated transportation problem in O((VE)/sup 1/4/(log V)/sup 3/ (log V gamma )) time using O(V/sup 3/) processors, where V (E) is the number of nodes (edges) and gamma is the largest magnitude of an edge cost or a demand at a node. As a by-product, a better parallel algorithm for the assignment problem for graphs of moderate density is obtained.>

The author presents an algorithm for solving linear programming problems that requires O((m+n)/sup 1.5/nL) arithmetic operations in the worst case, where m is the number of constraints, n the number of variables, and L a parameter defined in the paper. This result improves on the best known time complexity for linear programming by about square root n. A key ingredient in obtaining the speedup is a proper combination and balancing of precomputation of certain matrices by fast matrix multiplication and low-rank incremental updating of inverses of other matrices. Specializing the algorithm to problems such as minimum-cost flow, flow with losses and gains, and multicommodity flow leads to algorithms whose time complexity closely matches or is better than the time complexity of the best known algorithms for these problems.>

An algorithm for minimizing a convex function over a convex set is given. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope is central to the algorithm. The algorithm has a much better rate of global convergence than the ellipsoid algorithm. A by-product of the algorithm is an algorithm for solving linear programming problems that performs a total of O(mn/sup 2/L+M(n)nL) arithmetic operations in the worst case, where m is the number of constraints, n the number of variables, and L a certain parameter. This gives an improvement in the time complexity of linear programming for m>n/sup 2/. >

This paper investigates the question of (storage) space-(retrieval) time trade-off for orthogonal range queries on a static data base. Each record in the data base consists of a key that is a d-tuple of integers, and a data value that is an element in a commutative semigroup G. An orthogonal range query is specified by a d-dimensional parallelepiped (box). Two types of response to such a query are considered: one where the output is the semigroup sum of the data values whose keys are located in the query parallelepiped, and the other where the output is a list of all the records whose keys lie in the query parallelepiped. This paper studies two models, the arithmetic model and the tree model and obtains lower bounds on the product of retrieval time and storage space in both models.

A set of $2n$ points on the plane induces a complete weighted undirected graph as follows. The points are the vertices of the graph, and the weight of an edge between any two points is the distance between the points under some metric. The problem of finding a minimum weight complete matching (MWCM) in such a graph is studied. An $O(n^{2.5} (\log n)^4 )$ algorithm is given for finding an MWCM in such a graph, for the $L_1 $ (manhattan ), the $L_2 $ (Euclidean), and the $L_\infty $ metrics. The bipartite version of the problem is also studied, where half the points are painted with one color and the other half with another color, and the restriction is that a point of one color may be matched only to a point of another color. An $O(n^{2.5} \log n)$ algorithm for the bipartite version, for the $L_1 $, $L_2$, and $L_\infty $ metrics, is presented. The running time for the bipartite version can be further improved to $O(n^2 (\log n)^3 )$ for the $L_1 $ and $L_\infty $ metrics.

The authors present the first sub-linear-time deterministic parallel algorithms for bipartite matching and several related problems, including maximal node-disjoint paths, depth-first search, and flows in zero-one networks. The results are based on a better understanding of the combinatorial structure of the above problems, which lead to new algorithmic techniques. In particular, it is shown how to use maximal matching to extend, in parallel, a current set of node-disjoint paths and how to take advantage of the parallelism that arises when a large number of nodes are active during an execution of a push/relabel network flow algorithm. It is also shown how to apply the techniques to design parallel algorithms for the weighted versions of the above problems.>

A set of 2n points on the plane induces a complete weighted undirected graph as follows: The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under some metric. We study the problem of finding a minimum weight complete matching (MWCM) in such a graph. We give an Ο(n23 (logn)4) algorithm for finding an MWCM in such a graph, for the L1 (manhattan), the L2 (euclidean), and the L∞ metrics. We also study the bipartite version of the problem, where half the points are painted with one color and the other half are painted with another color, and the restriction is that a point of one color may be matched only to a point of another color. We present an Ο(n2.5 logn) algorithm for the bipartite version, for the L1, L2, and L∞, metrics. The running time for the bipartite version can be further improved to Ο(n2 (logn)3) for the L1 and L∞ metrics.

We study the problem of finding a minimum spanning tree in the complete graph on a set V of n points in k-dimensional space. The points are the vertices of this graph and the weight of an edge between two points is the distance between the points under some $L_q $ metric. We give an $O(\varepsilon ^{ - k} n\log n)$ algorithm for finding an approximate minimum spanning tree in such a graph; the weight of the approximate minimum spanning tree is guaranteed to be at most $(1 + \varepsilon )$ times the weight of a minimum spanning tree. We also present an algorithm to find a minimum spanning tree in the complete graph on V. Under the assumption that V consists of n random points, independently and uniformly distributed in the unit k-cube $[0,1]^k $, the expected running time of this minimum spanning tree algorithm is shown to be $O(n\alpha (cn,n))$ where c is a constant dependent on k and $\alpha $ is the inverse Ackermann function.

The problem of finding a rectilinear shortest path amongst obstacles may be stated as follows: Given a set of obstacles in the plane find a shortest rectilinear (L1) path from a point s to a point t which avoids all obstacles. The path may touch an obstacle but may not cross an obstacle. We study the rectilinear shortest path problem for the case where the obstacles are non-intersecting simple polygons, and present an Ο(n (logn)2) algorithm for finding such a path, where n is the number of vertices of the obstacles. We also study the case of rectilinear obstacles in three dimensions, and show that L1 shortest paths can be found in Ο(n2(log n)3) time.

We present an algorithm for linear programming which requires Ο(((m + n) n2 + (m + n)1.5 n) L) arithmetic operations where m is the number of inequalities, and n is the number of variables. Each operation is performed to a precision of Ο (L) bits. L is bounded by the number of bits in the input.

Given a set V of n points in k-dimensional space, and an Lq-metric (Minkowski metric), the All-Nearest-Neighbors problem is defined as follows: For each point p in V, find all those points in V-{p} that are closest to p under the distance metric Lq. We give an O(nlogn) algorithm for the All-Nearest-Neighbors problem, for fixed dimension k and fixed metric Lq. Since there is an Ω(n logn) lower bound, in the algebraic decision tree model of computation, on the time complexity of any algorithm that solves the All-Nearest-Neighbors problem (for k = 1), the running time of our algorithm is optimal upto a constant.

Article Free Access Share on Fast algorithms for convex quadratic programming and multicommodity flows Authors: S Kapoor Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, ILView Profile , P M Vaidya Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, ILView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 147–159https://doi.org/10.1145/12130.12145Published:01 November 1986Publication History 48citation820DownloadsMetricsTotal Citations48Total Downloads820Last 12 Months64Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We investigate the question of (storage) space - (retrieval) time tradeoff for orthogonal range queries on a static database. Lower bounds on the product of retrieval time and storage space are obtained in the arithmetic and tree models.

We study the problem of finding a minimum spanning tree on the complete graph on n points in Ek, with the weight of an edge between any two points being the distance between the two points under some distance metric. A fast algorithm, which finds an approximate minimum spanning tree with weight at most (1+ϵ) times optimal O(nlogn((logn)k+ log (ϵ-1)(logn)k-1ϵ-(k-1))) time, is developed for the Lq, q =2,3, ..., distance metrics. Moreover, if the n points are assumed to be independently and uniformly distributed in the box [0,l]k, then the probability that the approximate minimum spanning tree found is an exact minimum spanning tree is shown to be (1 -o(l/n)).