In this paper, we consider an automatic warehouse, in which rc-k palettes are arranged two-dimensionally on a grid with r rows c columns. The palettes in the warehouse can slide independently and simultaneously with the use of k spaces, unless they come into collision. Then, we show the minimum number of sliding operations required to move a specified palette to a specified position, where one sliding operation is a set of slides of palettes which are executed simultaneously in a unit time withouto any collision.

The statistical static timing analysis has been studied intensively in the last decade so as to deal with the process variability, and various techniques to represent distributions of timing information, such as a gate delay, a signal arrival time, and a slack, have been proposed. Among them, the Gaussian mixture model is distinguished from the others in that it can handle various correlations, non-Gaussian distributions, and slew distributions easily. However, the previous algorithm of computing the statistical maximum for Gaussian mixture models, which is one of key operations in the statistical static timing analysis, 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 new algorithm for statistical maximum (minimum) operation for Gaussian mixture models. It takes the 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 with the use of statistical approaches. We also show some experimental results to evaluate the performance of the proposed method.

We propose a hierarchical multi-layer global router for Sea-Of-Gates VLSI's, which is different from the conventional global routers, in that routing and layering are executed simultaneously. The main problems to be solved in the global routing for a multi-layer VLSI are which wire segments are laid out on upper layers and how they are connected to terminals located on lower layers. The main objective is to minimize the maximum of local congestions of all layers. We solve these problems in a hierarchical manner by routing from upper layers to lower layers.

In this paper, we present a new algorithm for statistical static timing analysis of a CMOS combinatorial circuit, which takes correlations into account to improve accuracy of the distribution of the maximum delay of the circuit. The correlations treated in the algorithm are not only the one between distributions of arrival times of input signals to a logic gate but also correlation between switching delays of a logic gate and correlation between interconnect delays of a net. We model each delay by a normal distribution, and use a normal distribution of two stochastic variables with a coefficient of correlation for computing the maximum of two delays. Since the algorithm takes the correlation into account, the time complexity is O(m2) in the worst-case, where m is the number of edges of the graph representing a given circuit. But, for real combinatorial circuits, the complexity is expected to be less than this.

The long-term degradation due to aging such as NBTI (Negative Bias Temperature Instability) is a hot issue in the current circuit design using nanometer process technologies, since it causes a delay fault in the field. In order to resolve the problem, we must estimate delay variation caused by long-term degradation in design stage, but over estimation must be avoided so as to make timing design easier. If we can treat such a variation statistically, and if we treat it together with delay variations due to process variability, then we can reduce over margin in timing design. Moreover, such a statistical static timing analyzer treating process variability and long-term degradation together will help us to select an appropriate set of paths for which field testing are conducted to detect delay faults. In this paper, we propose a new delay model with a half triangular distribution, which is introduced for handling a random factor with unknown distribution such as long term degradation. Then, we show an algorithm for finding the statistical maximum, which is one of key operations in statistical static timing analysis. We also show a few experimental results demonstrating the effect of the proposed model and algorithm.

With the advent of the deep submicron age, circuit performance is strongly impacted by process variations and the influence on the circuit delay to the power-supply voltage increases more and more due to CMOS feature size shrinkage. Power grid optimization which considers the timing error risk caused by the variations and IR drop becomes very important for stable and hi-speed operation of system-on-chip. Conventionally, a lot of power grid optimization algorithms have been proposed, and most of them use IR drop as their object functions. However, the IR drop is an indirect metric and we suspect that it is vague metric for the real goal of LSI design. In this paper, first, we propose an approach which uses the "timing error risk caused by IR drop" as a direct objective function. Second, the critical path map is introduced to express the existence of critical paths distributed in the entire chip. The timing error risk is decreased by using the critical path map and the new objective function. Some experimental results show the effectiveness.

For given undirected graph G[V,E] and vertices s and t, a minimal s-t separating set denoted by Ec & Vc is a minimal set of elements (edges and/or vertices) such that deletion of the elements from G breaks all the paths between s and t, where Ec and Vc are sets of edges and vertices, respectively. In this paper, we consider a problem of generating all minimal s-t separating sets, and show that the problem can be solved in O(µ(mt(n,n))) time, where m|E|, n|V|, µ is the number of minimal s-t separating sets of G, and t(p,q) is the time needed for finding q lowest common ancestors for q pairs of vertices in a rooted tree with p vertices. Since t(n,n) can be O(n), we can generate all minimal s-t separating in linear time per s-t separating set. However, the linear time algorithm for finding the lowest common ancestors is complicated, so that it is not efficient for a moderate size graph. Therefore, we use an O(nα (n))-time algorithm for finding the lowest common ancestors, and propose an algorithm to generate all minimal s-t separating sets in O(mnα(n)) time per s-t separating set, where α(n) is the pseudo-inverse of Ackermann function.

The mapping from a global routing to a feasible detailed routing in a number of 2D array routing structures has been shown to be an NP-complete problem. These routing structures include the Xilinx style routing architecture, as well as architectures with significantly higher switching flexibility. In response to this complexity, a different class of FPGA routing structures called Greedy Routing Architectures (GRAs) have been proposed. On GRAs, optimally routing each switch box, in a specified order, leads to an optimal chip routing. Because routing each switch box takes polynomial time, the mapping problem on GRAs can be solved in polynomial time. In particular, an H-tree GRA with W2+2W switches per switch box (SpSB) and a 2D array GRA with 4W2+2W SpSB have been proposed. In this paper, we improve on these results by introducing an H-tree GRA with W2/2+2W SpSB and a 2D array GRA with 3.5W2+2W SpSB. These new GRAs have the same desirable mapping properties of the previously described GRAs, but use fewer switches.

In this paper, we propose a hybrid hierarchical global router for multi-layer VLSI's, which executes routing and layering simultaneously. This novel approach, a hybrid hierarchical global router, is a combination of a topdown and a bottomup hierarchical routers, and may be one of interesting routing techniques. We also show experimental results, which demonstrate the superiority of the hybrid hierarchical approach. This approach may have many possibilities to be used in a various fields.

The problem of calculating parasitic capacitances between two interconnects is investigated dedicatedly for liquid crystal displays, with the main focus put on the approximate expressions of the capacitances caused at the intersection and the parallel running of two interconnects. To derive simple and accurate approximate expressions, the interconnects in these structures are divided into a few basic coupling regions in such a way that the electro-magnetic field in each region can be calculated by a 2-D capacitance model. Then the capacitance in such a region is represented by a simple expression adjusted to the results computed by an electro-magnetic field solver. The total capacitance obtained by summing the capacitances in all regions is evaluated in comparison with the one obtained by using a 3-D field solver, resulting in a relative error of less than 5%.

As process technologies decrease below a hundred nanometers, the variability of circuit parameters increases, and statistical timing analysis, which analyzes the distribution of the critical delay of a circuit, is receiving a great deal of attention. In such statistical approaches, correlations between random variables are important to the accuracy of analysis. Since interconnect delays dominate 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 interconnect delays with the use of Gaussian distributions. Our algorithm is efficient and yields reasonable results for correlations between interconnect delays of different nets. In order to evaluate the performance of the proposed algorithm, we show experimental results compared against Monte-Carlo simulations using SPICE.

A parallel detailed router based on the area division is one of important tools to overcome the increase of CPU time required for routing of a very large multilayer SOG. In order to conduct routing in each divided area independently, fictitious terminals are introduced on the border of each divided area, and routes connected to the fictitious terminals are concatenated to complete the final detailed routes. In this paper, we consider a problem how to position such fictitious terminals on borders, so as to make each detailed routing in a divided area easy. We formulate this problem as a minimum cost assignment problem, and propose an iterative improvement algorithm. We also give some experimental results which indicate the effectiveness of the algorithm.

In statistical approaches such as statistical static timing analysis, the distribution of the maximum of plural distributions is computed by repeating a maximum operation of two distributions. Moreover, since each distribution is represented by a linear combination of several explanatory random variables so as to handle correlations efficiently, sensitivity of the maximum of two distributions to each explanatory random variable, that is, covariance between the maximum and an explanatory random variable, must be calculated in every maximum operation. Since distribution of the maximum of two Gaussian distributions is not a Gaussian, Gaussian mixture model is used for representing a distribution. However, if Gaussian mixture models are used, then it is not always possible to make both variance and covariance of the maximum correct simultaneously. We propose a new algorithm to determine covariance without deteriorating the accuracy of variance of the maximum, and show experimental results to evaluate its performance.

For given integerp, a flow networkNwithn vertices, and sources inN, a problem of finding location ofp sinks inN which maximize the value of maximum flow from sources to sinks is calledp-collection problem. This problem is NP-hard even if a given network is a tree, but a pseudo-polynomial time algorithm is possible for such a network. This paper proposes a new pseudo-polynomial time algorithm for a tree-type network, which is simpler and more efficient than the previous algorithm, and has time complexity of O(p2n2Cc min {Cc,Cd}), whereCc andCd are the maximum edge capacity and the maximum vertex weight, respectively.

In the design of an active matrix LCD (Liquid Crystal Display), the ratio of the pixel voltage to the video voltage (RPV) of a pixel is an important factor of the performance of the LCD, since the pixel voltage of each pixel determines its transmitted luminance. Thus, of practical importance is the issue of how to maintain the admissible allowance of RPV of each pixel within a prescribed narrow range. This constraint on RPV is analyzed in terms of circuit parameters associated with the sampling switch and sampling pulse of a column driver in the LCD. With the use of a minimal set of such circuit parameters, a design procedure is described dedicatedly for the sampling switch, which intends to seek an optimal sampling switch as well as an optimal sampling pulse waveform. A number of experimental results show that an optimal sampling switch attained by the proposed procedure yields a source driver with almost 18% less power consumption than the one by manual design. Moreover, the percentage of the RPVs within 1001% among 270 cases of fluctuations is 88.1% for the optimal sampling switch, but 46.7% for the manual design.

Design automation of LCD driver circuits is not sophisticatedly established. Display fineness of an LCD panel depends on a performance metric, ratio of pixel voltage to video voltage (RPV). However, there are several other important metrics, such as area, and the best circuit cannot be decided uniquely. This paper proposes a design automation technique for a LCD column driver to provide several circuit design results with different performance so that designers can select an appropriate design among them. The proposed technique is evaluated with an actual design data, and experimental results show that the proposed method successfully performs technology migration by transistor sizing. Also, the proposed technique is experimentally verified from points of solution quality and computational time.

In statistical methods, such as statistical static timing analysis, Gaussian mixture model (GMM) is a useful tool for representing a non-Gaussian distribution and handling correlation easily. In order to repeat various statistical operations such as summation and maximum for GMMs efficiently, the number of components should be restricted around two. In this paper, we propose a method for reducing the number of components of a given GMM to two (2-GMM). Moreover, since the distribution of each component is represented often by a linear combination of some explanatory variables, we propose a method to compute the covariance between each explanatory variable and the obtained 2-GMM, that is, the sensitivity of 2-GMM to each explanatory variable. In order to evaluate the performance of the proposed methods, we show some experimental results. The proposed methods minimize the normalized integral square error of probability density function of 2-GMM by the sacrifice of the accuracy of sensitivities of 2-GMM.

In order to improve the performance of the existing statistical timing analysis, slew distributions must be taken into account and a mechanism to propagate them together with delay distributions along signal paths is necessary. This paper introduces Gaussian mixture models to represent the slew and delay distributions, and proposes a novel algorithm for statistical timing analysis. The algorithm propagates a pair of delay and slew in a given circuit graph, and changes the delay distributions of circuit elements dynamically by propagated slews. The proposed model and algorithm are evaluated by comparing with Monte Carlo simulation. The experimental results show that the accuracy improvement in µ+3σ value of maximum delay is up to 4.5 points from the current statistical timing analysis using Gaussian distributions.