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
14558888
An Adaptive Issue Queue for Reduced Power at High Performance
Increasing power dissipation has become a major constraint for future performance gains in the design of microprocessors. In this paper, we present the circuit design of an issue queue for a superscalar processor that leverages transmission gate insertion to provide dynamic low-cost configurability of size and speed. A novel circuit structure dynamically 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-fly to improve issue queue energy and performance. When applied to a fixed, full-size issue queue structure, the result is up to a 70% reduction in energy dissipation. The complexity of the additional circuitry to achieve this result is almost negligible. Furthermore, self-timed techniques embedded in the adaptive scheme can provide a 56% decrease in cycle time of the CAM array read of the issue queue when we change the adaptive issue queue size from 32 entries (largest possible) to 8 entries (smallest possible in our design).
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.
44925839
MHPS-Driven Early Design and Analysis of VLSI CPU Chips
JVe present (1 noid appsoaclz to carry per/i,rinancc analysis arid tiiiiitig of VLSI processors, don(? in the context of higlt-lewl source Iceriicls. U7e illustrate our rnetliodology in 1Crt71.r of a small (exaniph?) super scalas RlSC J ~ S O C ~ S S I ~ S architecture. A pnrantetrized execution 17ic~cIeI is used fhr piforinance eslimniion. IJsing an iterative optimization techniqire, the parameter set can bc locally optiinizcd around a g i i w design point to genesare tlie ininii?itrtn cycles per. iiwtrttction ( V I ) . W e also iiicludc a ctirsory discussion on linking .rirclt a CI’I estiiizntor io an early jloorplanner jhr A f IPS-driven block layout for the processor chb.
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>>
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.
24680353
Facility Location Constrained to a Polygonal Domain
We develop efficient algorithms for locating an obnoxious facility in a simple polygonal region and for locating a desirable facility in a simple polygonal region. Many realistic facility location problems require the facilities to be constrained to lie in a simple polygonal region. Given a set S of m demand points and a simple polygon R of n vertices, we first show how to compute the location of an obnoxious facility constrained to lie in R, in O((m + n) logm + mlog n) time. We then show how to compute the location of a desirable facility constrained to lie in R, also in O((m + n) logm + mlog n) time. Both running times are an improvement over the known algorithms in the literature. Finally, our results generalize to the setting where the facility is constrained to lie within a set of simple polygons as opposed to a single polygon at a slight increase in complexity.
15081913
All Convex Polyhedra can be Clamped with Parallel Jaw Grippers
We study various classes of polyhedra that can be clamped using parallel jaw grippers. We show that all nvertex convex polyhedra can be clamped regardless of the gripper size and present an O(n + k) time algorithm to compute all positions of a polyhedron that allow a valid clamp where k is the number of antipodal pairs of features. We also observe that all terrain polyhedra and orthogonal polyhedra can be clamped and a valid clamp can be found in linear time. Finally we show that all polyhedra can be clamped with some size of gripper.
15757957
Every Set of Disjoint Line Segments Admits a Binary Tree
Given a set of n disjoint line segments in the plane, we show that it is always possible to form a tree with the end-points of the segments such that each line segment is an edge of the tree, the tree has no crossing edges, and the maximum vertex degree of the tree is 3. Furthermore, there exist configurations of line segments where any such tree requires at least degree 3. We provide an O(n log n) time algorithm for constructing such a tree, and show that this 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.
15872429
Characterizing and efficiently computing quadrangulations of planar point sets
Abstract Given a set S of n points in the plane, a quadrangulation of S is a planar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the subdivision (except possibly the outer face) is a quadrilateral. We show that S admits a quadrangulation if and only if S does not have an odd number of extreme points. If S admits a quadrangulation, we present an algorithm that computes a quadrangulation of S in O(nlogn) time even in the presence of collinear points. If S does not admit a quadrangulation, then our algorithm can quadrangulate S with the addition of one extra point, which is optimal. We also provide an Ω(n log n) time lower bound for the problem. Our results imply that a k-angulation of a set of points can be achieved with the addition of at most k − 3 extra points within the same time bound. Finally, we present an experimental comparison between three quadrangulation algorithms which shows that the Spiraling Rotating Calipers (SRC) algorithm produces quadrangulations with the greatest number of convex quadrilaterals as well as those with the smallest difference between the average minimum and maximum angle over all quadrangles.