26499349
Early performance estimation of super scalar machine models
A novel methodology and software tool for estimating the performance of high-performance machine models with concurrent, pipelined execution modes are presented. Such performance assessment is typically useful at early stages of the design cycle. Critical design decisions made with the aid of early estimators of the kind discussed can be expected to yield near-optimal final designs.<<ETX>>
39390134
Ensuring dependable processor performance: an experience report on pre-silicon performance validation
The focus of today's processor validation methodology is primarily on ensuring functional integrity. Increasingly, however, pre-silicon performance validation is becoming part of the design verification challenge. Identification and elimination of performance deficiencies and bugs in the design prior to tape-out is an important aspect of building robust and dependable hardware. Many performance bugs are caused by latent functional defects in the pre-silicon software model of the machine. Besides, robust performance can be a key determinant of quality of service in applications like Web-serving. The authors review the performance validation methodology that they have developed and experimented with over the past few years. They also present examples and experimental results illustrating the use of this methodology in high end PowerPC processor development projects. The scope of the paper is limited to architectural performance, measured by metrics like instructions per cycle (IPC) or its inverse, CPI.
9135721
Fast approximations for sums of distances, clustering and the Fermat-Weber problem
We describe two data structures that preprocess a set S of n points in Rd (d constant) so that the sum of Euclidean distances of points in S to a query point q can be quickly approximated to within a factor of e. This preprocessing technique has several applications in clustering and facility location. Using it, we derive an O(n log n) time deterministic and O(n) time randomized e-approximation algorithm for the so called Fermat-Weber problem in any fixed dimension.
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.
23672359
Station Layouts in the Presence of Location Constraints
In wireless communication, the signal of a typical broadcast station is transmitted from a broadcast center p and reaches objects at a distance, say, r from it. In addition there is a radius r0, r0 < r, such that the signal originating from the center of the station is so strong that human habitation within distance r0 from the center p should be avoided. In other words, points within distance r0 from the station comprise a hazardous zone. We consider the following station layout proble: Cover a given planar region that includes a collection of buildings with a minimum number of stations so that every point in the region is within the reach of a station, while at the same time no interior point of any building is within the hazardous zone of a station. We give algorithms for computing such station layouts in both the one- and two-dimensional cases.
1055189
Constructing Plane Spanners of Bounded Degree and Low
Weight
Abstract Given a set S of n points in the plane, we give an O(n log
 n)-time algorithm that constructs a plane t-spanner for S, with
 t ≈ 10, such that the degree of each point of S is
 bounded from above by 27, and the total edge length is proportional
 to the weight of a minimum spanning tree of S. Previously, no
 algorithms were known for constructing plane t-spanners of bounded
 degree.
32119598
Location Oblivious Distributed Unit Disk Graph Coloring
We present the first location oblivious distributed unit disk graph coloring algorithm having a provable performance ratio of three (i.e. the number of colors used by the algorithm is at most three times the chromatic number of the graph). This is an improvement over the standard sequential coloring algorithm since we present a new lower bound of 10/3 for the worst-case performance ratio of the sequential coloring algorithm. The previous greatest lower bound on the performance ratio of the sequential coloring algorithm was 5/2. Using simulation, we also compare our algorithm with other existing unit disk graph coloring algorithms.