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>>
18281114
Performance and functional verification of microprocessors
We address the problem of verifying the correctness of pre-silicon models of a microprocessor. We touch on the latest advances in this area by considering two different aspects of the validation problem: (a) verifying the functional integrity of the model and (b) testing the model for timing accuracy at the architectural level. The latter area, that of performance verification, is of increasing importance in the design of server-class processor chips, with one or more high performance cores on a single die. We show how simulation-based test cases can be generated under a unified defect and coverage model to detect both performance and functional bugs. We present and discuss examples of such integrated validation methodologies used in real processor development projects.
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
9413783
Optimal Code Generation for Expressions on Super Scalar Machines
31462412
Performance evaluation and validation of microprocessors
The domain of early performance analysis and microarchitecture definition is limited largely to a onedimensional perspective of net performance: that of cyclesper-instnrction (CPI). Traceor execution-driven cycle-bycycle simulators [l] are the most common toolsets used at this stage. These are often coded in a systems programming language (e.g. C, C++, PWl or Pascal). They are performance-only models in that the register and memory data values and their state changes are not modelled; only the complex pipeline flow and concurrent instruction processing semantics are simulated. The goal here is to assess CPIcentric performance and bottlenecks to aid early definition, not to ensure functional integrity. Such a simulator, which we call a CPI timer; can be implemented to run at speeds greater than 50,000 instructions per second [21. This is achieved in modelling a future processor with the simulator running on a current generation uniprocessor workstation.
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>>
755945
Online Routing in Triangulations
We consider online routing strategies for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing strategies, one that works for all Delaunay triangulations and the other that works for all regular triangulations, (2) a randomized memoryless strategy that works for all triangulations, (3) an O(1) memory strategy that works for all convex subdivisions, (4) an O(1) memory strategy that approximates the shortest path in Delaunay triangulations, and (5) theoretical and experimental results on the competitiveness of these strategies.
100844
Computing constrained minimum-width annuli of point sets
We study the problem of determining whether a manufactured disk of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of the manufactured object, compute the thinnest annulus whose outer (or inner, or median) radius is r and that contains all the probe points. Our algorithms run in O(nlogn) time.
12068034
An Improved Algorithm for Subdivision Traversal without Extra Storage
We describe an algorithm for enumerating all vertices, edges and faces of a planar subdivision stored in any of the usual pointer-based representations, while using only a constant amount of memory beyond that required to store the subdivision. The algorithm is a refinement of a method introduced by de Berg et al (1997), that reduces the worst case running time from O(n2) to O(n log n). We also give experimental results that show that our modified algorithm runs faster not only in the worst case, but also in many realistic cases.
12387977
Testing the Quality of Manufactured Balls
We consider the problem of testing the roundness of a manufactured ball, using the finger probing model of Cole and Yap [4]. When the center of the object is known, a procedure requiring O(n2) probes and O(n2) computation time is described. (Here n = |1/q|, where q is the quality of the object.) When the center of the object is not known, the procedure requires O(n2) probes and O(n4) computation time. We also give lower bounds that show that the number of probes used by these procedures is optimal.
287038
Efficient algorithms for Petersen's matching theorem
Petersen's theorem is a classic result in matching theory from 1891, stating that every 3-regular bridgeless graph has a perfect matching. Our work explores efficient algorithms for finding perfect matchings in such graphs. Previously, the only relevant matching algorithms were for general graphs, and the fastest algorithm ran in O(n3/2) time for 3-regular graphs. We have developed an O(nlog4n)-time algorithm for perfect matching in a 3-regular bridgeless graph. When the graph is also planar, we have as the main result of our paper an optimal O(n)-time algorithm. We present three applications of this result: terrain guarding, adaptive mesh refinement, and quadrangulation.