6056146
Critical area computation via Voronoi diagrams
In this paper, we present a new approach for computing the critical area for shorts in a circuit layout. The critical area calculation is the main computational problem in very large scale integration yield prediction. The method is based on the concept of Voronoi diagrams and computes the critical area for shorts (for all possible defect radii, assuming square defects) accurately in O(n log n) time, where n is the size of the input. The method is presented for rectilinear layouts and layouts containing edges of slope /spl plusmn/1. As a byproduct, we briefly sketch how to speed up the grid method of Wagner and Koren [1995].
16325574
Finding an Approximate Minimum-Link Visibility Path Inside a Simple Polygon
34901507
A faster algorithm for rubber-band equivalent transformation for planar VLSI layouts
In this paper we consider the problem of transforming a single-layer topological routing of n two-terminal nets into a rubber-band equivalent using rectilinear wires in the presence of rectilinear circuit modules. Given a topological planar VLSI layout sketch with |F| features and |W| noncrossing wire segments connecting n two-terminal nets, we present an O(|F|/spl middot/|W|) time algorithm to do the vertex-disjoint rubber-band equivalent transformation of these n nets if it exists. The algorithm consists of two phases, computing a loose homotopy with four spokes matrices, and computing a vertex-disjoint rubber-band equivalent of the given homotopy, each phase taking O(|F|/spl middot/|W|) time and space. Both complexities are asymptotically optimal in the worst case. From the vertex-disjoint rubber-band equivalent of the given homotopy, one can obtain the detailed routing within the same time complexity. Experimental results are also presented.
10484740
Labeling Points on a Single Line
In this paper, we consider a map labeling problem where the points to be labeled are restricted on a line. It is known that the 1d-4P and the 1d-4S unit-square label placement problem and the Slope-4P unit-square label placement problem can both be solved in linear time and the Slope-4S unit-square label placement problem can be solved in quadratic time in Ref. [8]. We extend the result to the following label placement problem: Slope-4P fixed-height (width) label or elastic label placement problem and present a linear time algorithm for it provided that the input points are given sorted. We further show that if the points are not sorted, the label placement problems have a lower bound of Ω(n log n), where n is the input size, under the algebraic computation tree model. Optimization versions of these point labeling problems are also considered.
18326125
Finding Rectilinear Paths Among Obstacles in a Two-Layer Interconnection Model
Finding the best rectilinear path with respect to the bends and teh lengths of paths connecting two given points in the presence of rectilinear obstacles in a two-layer model is studied in this paper. In this model, rectilinear obstacles on each layer are specified separately, and the orientation of routing in each layer is fixed. An algorithm is presented to transform any problem instance in the two-layer model to one in a one-layer model, so that almost all algorithms for finding rectilinear paths among obstacles in the plane can be applied. The transformation algorithm runs in O(e log e) time where e is the number of edges on obstacles lying on both layers. A direct graph-theoretic approach to finding a shortest path in the two-layer model, which is easier to implement is also presented. The algorithm runs in O(e log2 e) time.
6583254
Rectilinear Path Problems among Rectilinear Obstacles Revisited
Efficient algorithms are presented for finding rectilinear collision-free paths between two given points among a set of rectilinear obstacles. The results improve the time complexity of previous results for finding the shortest rectilinear path, the minimum-bend shortest rectilinear path, the shortest minimum-bend rectilinear path and the minimum-cost rectilinear path. For finding the shortest rectilinear path, a graph-theoretic approach is used and an algorithm is obtained with $O(m\log t+ t\log^{3/2} t)$ running time, where $t$ is the number of extreme edges of given obstacles and $m$ is the number of obstacle edges. Based on this result an $O(N\log N+(m+N)\log t + (t+N)\log^2 (t+N))$ running time algorithm for computing the $L_1$ minimum spanning tree of given $N$ terminals among rectilinear obstacles is obtained. For finding the minimum-bend shortest path, the shortest minimum-bend rectilinear path, and the minimum-cost rectilinear path, we devise a new dynamic-searching approach and derive algorithms that run in $O(m\log^2m)$ time using $O(m\log m)$ space or run in $O(m\log^{3/2}m)$ time and space.
5523767
Closed Partition Lattice and Machine Decomposition
Finite-state machines are widely used to model systems in diverse areas. Often, the modeling machines can be decomposed into smaller component machines and this decomposition can facilitate the system design, implementation and analysis. J. Hartmanis and R.E. Stearns (1966) developed an elegant algebraic theory for machine decomposition that is based on the closed-partition lattice of a machine. In this paper, we study the computation of the closed-partition lattice of finite-state machines for the application to their decomposition. We present efficient algorithms for constructing the closed-partition lattice and for machine decomposition.
14664253
A Bit-Width Optimization Methodology for Polynomial-Based Function Evaluation
We present an automated bit-width optimization methodology for polynomial-based hardware function evaluation. Due to the analytical nature of the approach, overflow protection and precision accurate to one unit in the last place (ulp) can be guaranteed. A range analysis technique based on computing the root of the derivative of a signal is utilized to determine the minimal number of integer bits. Fractional bit requirements are established using an analytical error expression derived from the functions that occur along the data path. Global fractional bit optimization across multiple computation stages is performed using simulated annealing and circuit area estimation functions
12288623
Discontinuity detection from band-limited signals
Abstract The problem of detection, classification, and measurement of discontinuities arises in many applications in science and technology. It is complex because of the noise corrupting the data. It is difficult to distinguish the discontinuities of the underlying structure from the false discontinuities from the noise. Furthermore, in applications such as edge detection from intensity images, due to the effects of the point spread function of the optic system, the discontinuities of the intensity surface of the underlying scene are not well represented in the intensity image, which is band-limited. This introduces additional complication into the discontinuity detection process. We study discontinuity detection from band-limited signals. We propose a discontinuity detector, which consists of a pair of a pattern and a linear filter. We show that for a discontinuity in the signal there is a scaled pattern in the filter response. The location of the pattern is the location of the discontinuity, and the scaling factor of the pattern is the size of the discontinuity. We derive a necessary and sufficient condition for the one-to-one correspondence between the discontinuities of the signal and the scaled patterns in the filter response. Therefore, the problem of discontinuity detection and measurement is reduced to searching for the (scaled) pattern in the filter response. In the presence of noise, the pattern matching is approximate. We propose a statistical method for the pattern search. We study optimal detectors. We show that for white noise the optimal detectors are natural splines. Some issues related to edge detection are discussed.
7421438
A reliable position estimation method of the service robot by map matching
In this paper, a reliable position estimation method of the indoor service robot is proposed. The service robot PSR1 is a wheeled mobile manipulator which navigates in office buildings. Our localization method is a map-matching scheme using scanned range data, without using any artificial landmark. The proposed algorithm can provide solutions for both a global localization problem and a local position tracking. A probabilistic position estimation scheme is designed based on MCL (Monte Carlo localization). Two measure functions are developed for computing positional probabilities. The robot automatically decides whether it uses geometric pattern matching (i.e. walls, pillars) by Hough transform. The proposed scheme shows reliable performance in both polygonal environments and non-polygonal environments even there exist many obstacles. Experimental results demonstrate the validity and feasibility of the proposed localization algorithm for the service robot to navigate in an office building, using the natural environmental characteristics.
29667666
Building a distributed asynchronous control unit through automatic derivation of hierarchically decomposed AFSMs from a CDFG
Although there are several successful asynchronous logic synthesis tools, it is still unwieldy for designers to conceive and describe behaviors for a number of controllers constituting an asynchronous control unit of a target system manually. In this paper, building a distributed asynchronous control unit automatically through automatic derivation of hierarchically decomposed AFSMs from a CDFG is suggested. A resulting control unit consists of small asynchronous controllers and has complete separation of 'execution controllers' and 'execution order controllers'. This distributive feature leads to significant improvements in the aspects of area, performance and synthesis time of derived control circuits.