8147536
Active memory: a new abstraction for memory-system simulation
This paper describes the active memory abstraction for memory-system simulation. In this abstraction---designed specifically for on-the-fly simulation, memory references logically invoke a user-specified function depending upon the reference's type and accessed memory block state. Active memory allows simulator writers to specify the appropriate action on each reference, including "no action" for the common case of cache hits. Because the abstraction hides implementation details, implementations can be carefully tuned for particular platforms, permitting much more efficient on-the-fly simulation than the traditional trace-driven abstraction.Our SPARC implementation, Fast-Cache, executes simple data cache simulations two or three times faster than a highly-tuned trace-driven simulator and only 2 to 7 times slower than the original program. Fast-Cache implements active memory by performing a fast table look up of the memory block state, taking as few as 3 cycles on a SuperSPARC for the no-action case. Modeling the effects of Fast-Cache's additional lookup instructions qualitatively shows that Fast-Cache is likely to be the most efficient simulator for miss ratios between 3% and 40%.
11025508
Hardware Support for Flexible Distributed Shared Memory
Workstation-based parallel systems are attractive due to their low cost and competitive uniprocessor performance. However, supporting a cache-coherent global address space on these systems involves significant overheads. We examine two approaches to coping with these overheads. First, DSM-specific hardware can be added to the off the-shelf component base to reduce overheads. Second, application-specific coherence protocols can avoid some overheads by exploiting programmer (or compiler) knowledge of an application's communication patterns. To explore the interaction between these approaches, we simulated four designs that add DSM acceleration hardware to a collection of off-the-shelf workstation nodes. Three of the designs support user-level software coherence protocols, enabling application-specific protocol optimizations. To verify the feasibility of our hardware approach, we constructed a prototype of the simplest design. Measured speedups from the prototype match simulation results closely. We find that, even with aggressive DSM hardware support, custom protocols can provide significant speedups for some applications. In addition, the custom protocols are generally effective at reducing the impact of other overheads, including those due to less aggressive hardware support and larger network latencies. However, for three of our benchmarks, the additional hardware acceleration provided by our most aggressive design avoid the need to develop more efficient custom protocols.
5462033
Accuracy vs. performance in parallel simulation of interconnection networks
Parallel simulation is emerging as the dominant technique for studying parallel computers. However the interconnection networks of these machines can be modeled at many different levels of abstraction, allowing researchers to trade off accuracy and performance. We use the Wisconsin Wind Tunnel, a parallel simulator for cache-coherent shared-memory machines, to study the trade-offs of accuracy versus performance for six different network simulation models. We evaluate these models for a variety of parallel applications, cache-coherence protocols, and topologies. We show that only the two most expensive models-which model contention at individual links-are robust in the presence of high network loads or non-uniform traffic patterns.<<ETX>>
5292175
Adaptive cache compression for high-performance processors
Modern processors use two or more levels of cache memories to bridge the rising disparity between processor and memory speeds. Compression can improve cache performance by increasing effective cache capacity and eliminating misses. However, decompressing cache lines also increases cache access latency, potentially degrading performance. In this paper, we develop an adaptive policy that dynamically adapts to the costs and benefits of cache compression. We propose a two-level cache hierarchy where the L1 cache holds uncompressed data and the L2 cache dynamically selects between compressed and uncompressed storage. The L2 cache is 8-way set-associative with LRU replacement, where each set can store up to eight compressed lines but has space for only four uncompressed lines. On each L2 reference, the LRU stack depth and compressed size determine whether compression (could have) eliminated a miss or incurs an unnecessary decompression overhead. Based on this outcome, the adaptive policy updates a single global saturating counter, which predicts whether to allocate lines in compressed or uncompressed form. We evaluate adaptive cache compression using full-system simulation and a range of benchmarks. We show that compression can improve performance for memory-intensive commercial workloads by up to 17%. However, always using compression hurts performance for low-miss-rate benchmarks - due to unnecessary decompression overhead - degrading performance by up to 18%. By dynamically monitoring workload behavior, the adaptive policy achieves comparable benefits from compression, while never degrading performance by more than 0.4%.
1542232
Three-Dimensional Orthogonal Graph Drawing with Optimal Volume
AbstractAn orthogonal drawing of a graph is an embedding of the graph in the 
rectangular grid, with vertices represented by axis-aligned boxes, 
and edges represented by paths in the grid that only possibly 
intersect at common endpoints. In this paper we study 
three-dimensional orthogonal drawings and provide lower bounds for 
three scenarios:
(1) drawings where the vertices have a bounded aspect ratio, 
(2) drawings where the surfaces of vertices are proportional to their 
degrees, and
(3) drawings without any such restrictions. Then we show that these 
lower bounds are asymptotically optimal, by providing constructions
that in all scenarios match the lower bounds within a constant 
factor.
5331533
Balanced vertex-orderings of graphs
In this paper we consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbors of each vertex v are as evenly distributed to the left and fight of v as possible. This problem, which has applications in graph drawing for example, is shown to be NP- hard, and remains NP- hard for bipartite simple graphs with maximum degree six. We then describe and analyze a number of methods for determining a balanced vertex-ordering, obtaining optimal orderings for directed acyclic graphs, trees, and graphs with maximum degree three. For undirected graphs, we obtain a 13/8-approximation algorithm. Finally we consider the problem of determining a balanced vertex-ordering of a bipartite graph with a fixed ordering of one bipartition. When only the imbalances of the fixed vertices count, this problem is shown to be NP-hard. On the other hand, we describe an optimal linear time algorithm when the final imbalances of all vertices count. We obtain a linear time algorithm to compute an optimal vertex-ordering of a bipartite graph with one bipartition of constant size.
45540830
Image tracking in real-time: a transputer emulation of some early mammalian vision processes
By emulating some of the 'early' vision processes believed to occur in the visual cortex of mammals, dramatic savings can be made in the com­ putational efforts usually associated with image processing. This paper describes the design and implementation of a low-cost visual tracking sys­ tem that uses no special signal processing, vector processing nor floating­ point hardware. Its effectiveness relies only on the parallel replication of fast scaler integer processors with low latency communications. The current implementation uses 10 T425 transputers, processes 544 x 544 byte-pixel images at camera frame rates and provides 100 Hz. tracking feedback signals to the camera pan-and-tilt motors with a latency of no more than one-fifth of a second. The system will track any object that occupies the (majority of the) centre of the field of view moving against any background - no special lighting conditio~s or artificial scenery are required. The design and implementation follow naturally parallel struc­ tures and are expressed at all levels in occam.
125792
Upward Three-Dimensional Grid Drawings of Graphs
A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line segments representing the edges do not cross. Our aim is to produce three-dimensional grid drawings with small bounding box volume. Our first main result is that every $n$-vertex graph with bounded degeneracy has a three-dimensional grid drawing with $\mathcal{O}\left({n^{3/2}}\right)$ volume. This is the largest known class of graphs that have such drawings. A three-dimensional grid drawing of a directed acyclic graph (dag) is upward if every arc points up in the $\textsf{z}$-direction. We prove that every dag has an upward three-dimensional grid drawing with $\mathcal{O}\left({n^3}\right)$ volume, which is tight for the complete dag. The previous best upper bound was $\mathcal{O}\left({n^4}\right)$. Our main result concerning upward drawings is that every $c$-colourable dag ($c$ constant) has an upward three-dimensional grid drawing with $\mathcal{O}\left({n^2}\right)$ volume. This result matches the bound in the undirected case, and improves the best known bound from $\mathcal{O}\left({n^3}\right)$ for many classes of dags, including planar, series parallel, and outerplanar. Improved bounds are also obtained for tree dags. We prove a strong relationship between upward three-dimensional grid drawings, upward track layouts, and upward queue layouts. Finally, we study upward three-dimensional grid drawings with bends in the edges.
7215582
Light edges in degree-constrained graphs
Let @a denote the average degree, and @d denote the minimum degree of a graph. An edge is light if both its endpoints have degree bounded by a constant depending only on @a and @d. A graph is degree-constrained if @a<2@d. The primary result of this paper is that every degree-constrained graph has a light edge. Most previous results in this direction have been for embedded graphs. This result is extended in a variety of ways. First it is proved that there exists a constant c(@a,@d) such that for every 0=<@e