7956430
Online Routing in Convex Subdivisions
We consider online routing algorithms for finding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no randomization, (2) no equivalent result is possible for convex subdivisions, (3) there is no competitive online routing algorithm under the Euclidean distance metric in arbitrary triangulations, and (4) there is no competitive online routing algorithm under the link distance metric even when the input graph is restricted to be a Delaunay, greedy, or minimum-weight triangulation.
5595756
Bounds for Frequency Estimation of Packet Streams
We consider the problem of approximating the frequency of frequently occurring elements in a stream of length n using only a memory of size m n. This models the process of gathering statistics on Internet packet streaming using a memory that is small relative to the number of classes (e.g. IP addresses) of packets. We show that when some data item a occurs αn times in a stream of length n, the FREQUENT algorithm of Demaine et al. [4], can approximate a’s frequency with an error of no more than (1−α)n/m. We also give a lower-bound of (1−α)n/(m+1) on the accuracy of any deterministic packet counting algorithm, which implies the FREQUENT algorithm is nearly optimal. Finally, we show that randomized algorithms can not be significantly more accurate since there is a lower bound of (1−α)Ω(n/m) on the expected accuracy of any randomized packet counting algorithm.
38367030
Partitions of complete geometric graphs into plane trees
Consider the following question: does every complete geometric graph K"2"n have a partition of its edge set into n plane spanning trees? We approach this problem from three directions. First, we study the case of convex geometric graphs. It is well known that the complete convex graph K"2"n has a partition into n plane spanning trees. We characterise all such partitions. Second, we give a sufficient condition, which generalises the convex case, for a complete geometric graph to have a partition into plane spanning trees. Finally, we consider a relaxation of the problem in which the trees of the partition are not necessarily spanning. We prove that every complete geometric graph K"n can be partitioned into at most n-n/12 plane trees. This is the best known bound even for partitions into plane subgraphs.
11217048
Computing nice sweeps for polyhedra and polygons
This paper does not deal with the sweeping paradigm itself; it deals with testing polygons and polyhedra to determine if they have a certain property. The properties that we consider are related to sweeping. We will test for a simple polygon or polyhedron if it can be swept by a line or plane such that every cross-section has a property like being convex or simply-connected. For example, to determine for a simple polygon (with interior) in the plane whether there is a sweep direction such that every cross-section is simplyconnected (a point, line segment, or empty) is the well-known question of determining whether a simple polygon is monotone in some direction. We solve two extensions of this problem in 3-space, and solve another extension in the plane. The first question we address applies to a polyhedron in 3space. We want to determine if there is a vector , such that if a sweeping plane with normal passes over , every cross-section of is convex. Toussaint [7] calls this property weakly monotonic in the convex sense. Obviously, for convex polyhedra, any vector gives only convex cross-sections during the sweep. For many nonconvex polyhedra no such vector exists. We give an time algorithm to find a vector if one exists, for a simple polyhedron with vertices. In case we allow more than one convex polygon in the cross-section, but no refle x vertices, we solve the problem in linear time. The second question deals with cross-sections of simple polyhedra that are always simply-connected. This property is called weakly monotonic [7]. Again the problem is to determine a vector , if one exists, such that any plane normal to intersects in a simple polygon. This cross-section may degenerate into a line segment, single point, or be empty. The cross-section may not become disconnected, nor may it contain a hole. We solve the problem in time. Thirdly, we consider sweeping a simple polygon with a line, but we allow the line to change its orientation. The problem is to determine if such a sweep exists that passes over the polygon , such that every cross-section is connected (generally, a single line segment). The problem is solved in quadratic time, also if we require additionally that the sweep line never goes back over any point of .
45018692
The Grid Placement Problem
We consider the problem of placing a regular grid over a set of points in order to minimize (or maximize) the number of grid cells not containing any points. We give an O(n log n) time and O(n) space algorithm for this problem. As part of this algorithm we develop a new data structure for solving a problem on intervals that is interesting in its own right and may have other applications.
1566102
On simplifying dot maps
Dot maps--drawings of point sets--are a well known cartographic method to visualize density functions over an area. We study the problem of simplifying a given dot map: given a set P of points in the plane, we want to compute a smaller set Q of points whose distribution approximates the distribution of the original set P.We formalize this using the concept of e-approximations, and we give efficient algorithms for computing the approximation error of a set Q of m points with respect to a set P of n points (with m ≤ n) for certain families of ranges, namely unit squares, arbitrary squares, and arbitrary rectangles.If the family R of ranges is the family of all possible unit squares, then we compute the approximation error of Q with respect to P in O(n log n) time. If R is the family of all possible rectangles, we present an O(mn log n) time algorithm. If R is the family of all possible squares, then we present a simple O(m2n + n log n) algorithm and an O(n2 √n log n) time algorithm which is more efficient in the worst case.Finally, we develop heuristics to compute good approximations, and we evaluate our heuristics experimentally.
37031042
Architectural timing verification and test for super scalar processors
We address the problem of verification and testing of super scalar processors, from the point of view of correctness of [Bprogram execution time. Trace-driven architectural si[Bmulation methods are commonly used in current industrial practice to estimate cycles-per-instruction performance of a candidate processor organization, prior to actual implementation. We present a novel set of strategies for testing the timing correctness of processors as represented in an architectural timing model ("timer"). We focus on two main aspects of the theory: (a) deriving architectural test sequences to cover possible failure modes, defined in the context of a pipeline flow state transition fault model; and (b) deriving loop test kernels to verify steady-state (periodic) behavior of pipeline flow, against analytically predicted signatures. We develop the theory in the context of an example super scalar processor and its timer model.<<ETX>>
2521753
A circuit level implementation of an adaptive issue queue for power-aware microprocessors
Increasing power dissipation has become a major constraint for future performance gains in the design of microproces sors In this paper we present the circuit design of an issue queue for a superscalar processor that leverages transmis sion gate insertion to provide dynamic low cost con gura bility of size and speed A novel circuit structure dynami cally gathers statistics of issue queue activity over intervals of instruction execution These statistics are then used to change the size of an issue queue organization on the y to improve issue queue energy and performance When applied to a xed full size issue queue structure the result is up to a reduction in energy dissipation The complexity of the additional circuitry to achieve this result is almost neg ligible Furthermore self timed techniques embedded in the adaptive scheme can provide a decrease in cycle time of the CAM array read of the issue queue when we change the adaptive issue queue size from entries largest possible to entries smallest possible in our design
2688591
Interactive program improvement via EAVE: an expert adviser for vectorization
An example of a state-of-the-art high-end mainframe is the IBM 3090 VF; its associated compiler, the IBM VS Fortran (version 2) compiler, incorporates some of the latest techniques in automatic vectorization and code optimization. Advances in compiler technology not withstanding, a potential limitation is the “knowledge gap” which exists between the typical end user and the compiler/machine sub-system. In particular, the user often does not know how to write source code which will result in generation of efficient, high performance object code. In this paper, we address the issue of providing interactive aids for program development and transformation as a means to bridge this knowledge gap. We show how heuristic program changes, guided by the knowledge of a particular compiler-machine pair, help approach achievable peak performance through enhanced vectorization/parallelization. We present our techniques and results in terms of an implemented expert system, called EAVE, which has been designed to help users tune their programs for enhanced performance on the IBM 3090 VF.
45287
Early-Stage Definition of LPX: A Low Power Issue-Execute Processor
We present the high-level microarchitecture of LPX: a low-power issue-execute processor prototype that is being designed by a joint industry-academia research team. LPX implements a very small subset of a RISC architecture, with a primary focus on a vector (SIMD) multimedia extension. The objective of this project is to validate some key new ideas in power-aware microarchitecture techniques, supported by recent advances in circuit design and clocking.
12711823
Parallel Simulation and Test of VLSI Array Logic
We consider the task of accelerating existing array logic CAD software by running them under parallel processing environments. We restrict our discussion to VLSI programmable logic arrays (PLAs); we present results based on fault simulation/test generation software implemented for PLAs. Due to the regular layout of such array logic, considerable parallelism is expected in any data processing problem involving these modules. However, depending on the underlying machine model, and the adopted programming model, varying levels of speed-up are exhibited. We first consider a typical pipelined, vector mainframe like the IBM 3090 VF. Through a combination of novel problem reformulation strategies, and educated coding guidelines for vector machines, we show how an original scalar program can be efficiently speeded up on such machines. The other machine model considered is that of a shared memory parallel processing system. Our results here are based on experiments run under an experimental multi-processor VM environment (VM/EPEX) which has been set up to predict the possible speed-up on a parallel processor such as RP3. The overall processing environment is assumed to be constrained to a scientific/engineering one, with Fortran as the primary coding medium and the hardware biased toward numerically-intensive applications.