7022714
Simulating a $2M Commercial Server on a $2K PC
As dependence on database management systems and Web servers increases, so does the need for them to run reliably and efficiently-goals that rigorous simulations can help achieve. Execution-driven simulation models system hardware. These simulations capture actual program behavior and detailed system interactions. The authors have developed a simulation methodology that uses multiple simulations, pays careful attention to the effects of scaling on workload behavior, and extends Virtutech AB's Simics full system functional simulator with detailed timing models. The Wisconsin Commercial Workload Suite contains scaled and tuned benchmarks for multiprocessor servers, enabling full-system simulations to run on the PCs that are routinely available to researchers.
12937575
Application-specific protocols for user-level shared memory
Recent distributed shared memory (DSM) systems and proposed shared-memory machines have implemented some or all of their cache coherence protocols in software. One way to exploit the flexibility of this software is to tailor a coherence protocol to match an application's communication patterns and memory semantics. This paper presents evidence that this approach can lead to large performance improvements. It shows that application-specific protocols substantially improved the performance of three application programs-appbt, em3d, and barnes-over carefully tuned transparent shared memory implementations. The speed-ups were obtained on Blizzard, a fine-grained DSM system running on a 32-node Thinking Machines CM-5.<<ETX>>
7972983
Using speculation to simplify multiprocessor design
Summary form only given. Modern multiprocessors are complex systems that often require years to design and verify. A significant factor is that engineers must allocate a disproportionate share of their effort to ensure that rare corner-case events behave correctly. We propose using "speculation for simplicity " to enable designers to focus on common-case scenarios. Our approach is to speculate that rare events will not occur and rely on an efficient recovery mechanism to undo the effects of misspeculations. We illustrate the potential of speculation to simplify multiprocessor design with three examples. First, we simplify the design of a directory cache coherence protocol by speculatively relying on point-to-point ordering of messages in an adoptively routed interconnection network. Second, we simplify a snooping cache coherence protocol by treating a rare coherence state transition as a misspeculation. Third, we simplify interconnection network design by removing the virtual channels and then recovering from deadlocks when they occur. Experiments with full-system simulation and commercial workloads show that speculation is a viable approach for simplifying system design. Systems can incur as many as ten recoveries per second due to misspeculations without significantly degrading performance, and our speculatively simplified designs incur far fewer recoveries.
14219279
Full-system timing-first simulation
Computer system designers often evaluate future design alternatives with detailed simulators that strive for functional fidelity (to execute relevant workloads) and performance fidelity (to rank design alternatives). Trends toward multi-threaded architectures, more complex micro-architectures, and richer workloads, make authoring detailed simulators increasingly difficult. To manage simulator complexity, this paper advocates decoupled simulator organizations that separate functional and performance concerns. Furthermore, we define an approach, called timing-first simulation, that uses an augmented timing simulator to execute instructions important to performance in conjunction with a functional simulator to insure correctness. This design simplifies software development, leverages existing simulators, and can model micro-architecture timing in detail.We describe the timing-first organization and our experiences implementing TFsim, a full-system multiprocessor performance simulator. TFsim models a pipelined, out-of-order micro-architecture in detail, was developed in less than one person-year, and performs competitively with previously-published simulators. TFsim's timing simulator implements dynamically common instructions (99.99% of them), while avoiding the vast and exacting implementation efforts necessary to run unmodified commercial operating systems and workloads. Virtutech Simics, a full-system functional simulator, checks and corrects the timing simulator's execution, contributing 18-36% to the overall run-time. TFsim's mostly correct functional implementation introduces a worst-case performance error of 4.8% for our commercial workloads. Some additional simulator performance is gained by verifying functional correctness less often, at the cost of some additional performance error.
6984741
Bandwidth adaptive snooping
This paper advocates that cache coherence protocols use a bandwidth adaptive approach to adjust to varied system configurations (e.g., number of processors) and workload behaviors. We propose Bandwidth Adaptive Snooping Hybrid (BASH), a hybrid protocol that ranges from behaving like snooping (by broadcasting requests) when excess bandwidth is available to behaving like a directory protocol (by unicasting requests) when bandwidth is limited. BASH adapts dynamically by probabilistically deciding to broadcast or unicast on a per request basis using a local estimate of recent interconnection network utilization. Simulations of a microbenchmark and commercial and scientific workloads show that BASH robustly performs as well or better than the best of snooping and directory protocols as available bandwidth is varied. By mixing broadcasts and unicasts, BASH outperforms both snooping and directory protocols in the mid-range where a static choice of either is inefficient.
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%.
12322077
Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing
A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine), and an assignment of edges to half-planes with the spine as boundary (the pages), so that edges assigned to the same page can be drawn on that page without crossings. Given a graph G = (V,E), let f : V → ℕ be a function such that 1 ≤ f(υ) ≤ deg(υ). We present a Las Vegas algorithm which produces a book embedding of G with \( O(\sqrt {|E| \cdot \max _\upsilon \left\lceil {\deg (\upsilon )/f(\upsilon )} \right\rceil } ) \) pages, such that at most f(v) edges incident to a vertex v are on a single page. This algorithm generalises existing results for book embeddings. We apply this algorithm to produce 3-D orthogonal drawings with one bend per edge and O(∣V ∣3/2∣E∣) volume, and single-row drawings with two bends per edge and the same volume. In the produced drawings each edge is entirely contained in some Z-plane; such drawings are without so-called cross-cuts, and are particularly appropriate for applications in multilayer VLSI. Using a different approach, we achieve two bends per edge with O(∣V ∣∣E∣) volume but with cross-cuts. These results establish improved bounds for the volume of 3-D orthogonal graph drawings.
341729
Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings
In this paper we present the first non-trivial lower bounds for the total number of bends in 3-D orthogonal drawings of maximum degree six graphs. In particular, we prove lower bounds for the number of bends in 3-D orthogonal drawings of complete simple graphs and multigraphs, which are tight in most cases. These result are used as the basis for the construction of infinite classes of c-connected simple graphs and multigraphs (2 ≤ c ≤ 6) of maximum degree Δ (3 ≤ Δ ≤ 6) with lower bounds on the total number of bends for all members of the class. We also present lower bounds for the number of bends in general position 3-D orthogonal graph drawings. These results have significant ramifications for the '2-bends' problem, which is one of the most important open problems in the field.
1926264
L Codes and Number Systems
Abstract The notion of an L code is introduced as a generalization of the customary notion of a code. Attention is focused on unary L codes. where the target alphabet consists of one letter only. Unary L codes can be identified with such number systems where the representation is unique. Surprisingly many unary morphisms are L codes. Furthermore, even for non-L-codes there is only one ‘exceptional length’ We also give a complete classification for the binary case.
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.
8780088
Dimension-Exchange Algorithms for Load Balancing on Trees
This paper considers dimension-exchange algorithms for load balancing on trees with finitely-divisible loads (token distribution). We present improved analysis of an existing protocol, and in particular, establish a logarithmic upper bound on the discrepancy of the final distribution. Our second contribution is a new algorithm, which assuming each node has knowledge of the total number of nodes, determines a perfectly balanced distribution.