Gaussian mixture model is a useful distribution for statistical methods such as statistical static timing analysis, but the number of components of Gaussian mixture model increases exponentially by repeating statistical operations. Hence, the number of components must be reduced to around 2 in order to repeat operations efficiently and effectively. Although several methods for reducing the number of components have been proposed, each of them has strength and weakness in accuracy and CPU time. Therefore, selecting an appropriate method for an input distribution is a practical way for reducing the number of components. In this paper, we construct selection methods by using support-vector machine and evaluates their performances. Since the input distribution is represented by non-linear functions, it is not easy to select an appropriate method, but support vector machine achieved 94.8% correct selection rate.

Statistical design approaches have been studied intensively in the last decade so as to deal with the process variability, and statistical delay fault testing is one of key techniques for the statistical design. In order to represent the distributions of timing information such as a gate delay, a signal arrival time, and a slack, various techniques have been proposed. Among them, Gaussian mixture model is distinguished from the others in that it can handle any correlation, non-Gaussian distributions, and slew distributions easily. However, the previous method of computing the statistical maximum for Gaussian mixture models has a defect such that it produces a distribution similar to Gaussian in a certain case, although the correct distribution is far from Gaussian. In this paper, we propose a novel method for statistical maximum (minimum) operation for Gaussian mixture models. It takes cumulative distribution function curve into consideration so as to compute accurate criticalities (probabilities of timing violation), which is important for detecting delay faults and circuit optimization. The proposed method reduces the error of criticality almost 80% from the previous method.

This paper introduces a Gaussian mixture model to represent delay and slew distributions in the statistical static timing analysis, and proposes algorithms for propagating them on a given circuit graph. The Gaussian mixture model can represent a non-Gaussian distribution due to the statistical Max operation properly, and any correlation efficiently, since it consists of plural Gaussian distributions. Therefore, not only topological correlations caused by re-convergent paths but also the correlation between each element and the critical delay, which is useful for circuit optimization, are calculated easily. The propagated slews are used to compute delay distributions of circuit elements dynamically so as to improve the accuracy. The proposed Gaussian mixture model is evaluated by comparing with Monte Carlo simulation, and the results show its effectiveness.

As process technologies move into nanoscales, variabilities of circuit parameters increase, and as a result, statistical timing analysis computing distribution of the critical delay of a circuit is receiving a great deal of attention. For these statistical approaches, the correlations between random variables are important to the accuracy of analysis. Since interconnect delays dominates in recent technology, their correlations are of primary concern in statistical timing analysis. In this paper, we propose an efficient algorithm for calculating correlation coefficients between Elmore delays of interconnects under the assumption of Gaussian distributions. Our algorithm yields correlation coefficients with less than 2% errors to those obtained by Monte-Carlo simulations. Moreover, the correlation coefficients are compared with 50% SPICE delays calculated by Monte-Carlo simulations.

This paper discusses interconnect capacitance extraction for system LCD circuits, where coupling capacitance is much significant since a ground plane locates far away unlike LSI interconnects. We focus on a pattern matching method with interpolation to implement an accurate and efficient capacitance extraction system, and present good implementations that are suitable for system LCD circuits. To reduce computational cost, interconnect structures are spatially divided into several sub-regions considering capacitance coupling range, and analyzed in each sub-region using a capacitance database pre-characterized by a 3-D field solver. This paper evaluates tradeoff curves between characterization cost and extraction accuracy for four division methods in lattice structures that are basic and common structures in LCD driver circuits. Experimental results reveal efficient division methods for accurate capacitance extraction.

In this paper, we present a new algorithm for the statistical static timing analysis of a CMOS combinatorial circuit, which can treat correlations of arrival times of input signals to a logic gate and correlations of switching delays in a logic gate. We model each switching delay by a normal distribution, and use a normal distribution of two stochastic variables with a coefficient of correlation for computing the distribution of output delay of a logic gate. Since the algorithm takes the correlation into account, the time complexity is O(n*m) in the worst-case, where n and m are the numbers of vertices and edges of the acyclic graph representing a given combinatorial circuit.

&% '# ( ) * $# + -, .)/ 0 ) 1 2 3 4 5% ') * $# + 6 "7 98 9: <; $= ?>A@ CB &; ED &> F> HG I J7 LK MB M

It has been observed experimentally that the mapping of global to detailed routing in a conventional FPGA routing architecture (2D array) yields unpredictable results. A different class of FPGA structures called greedy routing architectures (GRAs), where a locally optimal switch box routing can be extended to an optimal entire-chip routing, were investigated by Wu et al. (1994), Takashima et al. (1996) and Wu et al. (1996). It was shown that GRAs have good mapping properties. An H-tree GRA with W/sup 2/+2W switches per switch box (SpSB) and a 2D array GRA with 4W/sup 2/+2W SpSB were proposed by those authors (W is the number of tracks in each switch box). We continue this work by introducing an H-tree GRA with W/sup 2//2+2W SpSB and a 2D array GRA with 3.5 W/sup 2/+2 W SpSB. These new GRAs have the same good mapping properties but use fewer switches. We also show a class of FPGA architectures in which the mapping problem remains NP-complete, even with 6(W-1)/sup 2/+6W/sup 2/ SpSB (this is close to the maximum number of SpSB, which is 6W/sup 2/). Thus, more switches do not necessarily result in more routability.

In this paper, we study the two-dimensional FPGA, Xilinx-like routing architectures and present the first known computational complexity results for them. The routing problem is formulated as a two-dimensional interval packing problem and is proved to be NP-complete with or without doglegs. Next, we consider other routing structures obtained from the industrial one by arbitrarily changing switch box connection topology while maintaining the same connection flexibility. There is an exponentially large number of such routing structures. We further prove that there does not exist a better routing architecture among the members of this large domain. In addition, we prove that there is no constant bound on the mapping ratio of a track number required by a detailed routing to a global routing channel density for the studied architectures. Finally, we show two directions of changing the routing architectures which yield polynomial time mapping solutions and constant bounded mapping ratios. Our theoretical analysis is intended to give some insight to, and understanding of this new routing problem's fundamental properties.

In this paper, we consider the problem of mapping a given global route to a detailed route for two dimensional homogeneous FPGAs. It has been shown that this problem is NP-complete on a popular Xilinx-4000-like routing architecture. Here, we further prove that this problem remains NP-complete for an arbitrary fixed switch box topology of the same connection flexibility, with or without doglegs allowed in detailed routes.>

A global router for gate array LSI's is described, which is intended to perform an interaction between placement and routing such that the features of one may be incorporated into those of another. This router is to generate for each net an interconnection pattern of channel segments in such a unified way of taking all interrelated interconnection requirements into account at once. A main objective of the router is not only to minimize the maximum of the local routing densities but also to distribute all the wiring requirements over channels evenly, in order to attain 100-percent interconnections within a limited area. An implementation result of the router is also shown.

This paper deals with the layering problem of multilayer PWB wiring, associated with single-row routing. The problem to be considered is restricted to the special case of street capacities up to two in each layer, and it is reduced to a problem of the interval graph by relaxing some restrictions in the original problem. Then, a heuristic algorithm is proposed for this problem.

Abstract Problems on layout for ICs (integrated circuits) and PCBs (printed circuit boards) are usually solved by heuristic approaches because they are complex. This article considers a special problem of double‐row planar routing. The problem represents a generalization of the permutation layout problem to which estimation of bounds and some algorithms have been proposed recently. Our approach is based on the interval graphical representation introduced in the single‐row single‐layer PCB problem. The objective function for minimization is the breadth of the realization, i.e., the total number of vertical tracks required to realize a given net list specified in terms of terminals on two parallel rows. The problem is shown to be intractable in the sense of NP‐completeness; however, a polynomial‐time heuristic algorithm is proposed. An upper bound for the breadth for an initial solution is given. Iterative improvement is next used. The algorithm has been programmed in FORTRAN and ran on the VAX 11/780 computer.

Thts paper deals wRh the problem of enumerating all the cutsets or all the s-t cutsets separatmg two spectfied verttces s and t m an undirected graph A vanety of approaches have been proposed for this problem, among which one based on the partmon era set of veruces rote two sets is the most effi¢ienL It is first shown that an algorithm of this type has time complexity O((n + m)(n -log2#)#), and two new algorithms with ume complexity O((n + m)O + I)) are then proposed One of these new algorithms has space complexity O(nZ), and the other has space complexity O(n + m), where n and m are the numbers of veraces and edges, respectively, and ta ts the number ofs-t cutsets m a given graph The results of some computatmnal experiments are also described.An mvest~gaUon ~s made of the extent to whtch the new algorithms are better, and how good the performance of the old algorithm is, especmlly when a given graph is "dense," t e, 2m/(n(n -1)) _> 0.4.

The problem of generating all the maximal independent sets (or maximal cliques) of a given graph is fundamental in graph theory and is also one of the most important in terms of the application of graph theory. In this paper, we present a new efficient algorithm for generating all the maximal independent sets, for which processing time and memory space are bounded by $O(nm\mu)$ and $O(n+m)$, respectively, where n, m, and $\mu$ are the numbers of vertices, edges, and maximal independent sets of a graph.