970409
Fine-grain access control for distributed shared memory
This paper discusses implementations of fine-grain memory access control, which selectively restricts reads and writes to cache-block-sized memory regions. Fine-grain access control forms the basis of efficient cache-coherent shared memory. This paper focuses on low-cost implementations that require little or no additional hardware. These techniques permit efficient implementation of shared memory on a wide range of parallel systems, thereby providing shared-memory codes with a portability previously limited to message passing.
This paper categorizes techniques based on where access control is enforced and where access conflicts are handled. We incorporated three techniques that require no additional hardware into Blizzard, a system that supports distributed shared memory on the CM-5. The first adds a software lookup before each shared-memory reference by modifying the program's executable. The second uses the memory's error correcting code (ECC) as cache-block valid bits. The third is a hybrid. The software technique ranged from slightly faster to two times slower than the ECC approach. Blizzard's performance is roughly comparable to a hardware shared-memory machine. These results argue that clusters of workstations or personal computers with networks comparable to the CM-5's will be able to support the same shared-memory interfaces as supercomputers.
8256982
Memory system behavior of Java-based middleware
In this paper, we present a detailed characterization of the memory system, behavior of ECperf and SPECjbb using both commercial server hardware and Simics full-system simulation. We find that the memory footprint and primary working sets of these workloads are small compared to other commercial workloads (e.g. on-line transaction processing), and that a large fraction of the working sets are shared between processors. We observed two key differences between ECperf and SPECjbb that highlight the importance of isolating the behavior of the middle tier. First, ECperf has a larger instruction footprint, resulting in much higher miss rates for intermediate-size instruction caches. Second, SPECjbb's data set size increases linearly as the benchmark scales up, while ECperf's remains roughly constant. This difference can lead to opposite conclusions on the design of multiprocessor memory systems, such as the utility of moderate sized (i.e. 1 MB) shared caches in a chip multiprocessor.
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%.
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.
3338486
TLC: Transmission Line Caches
It is widely accepted that the disproportionate scalingof transistor and conventional on-chip interconnect performancepresents a major barrier to future high performancesystems. Previous research has focused on wire-centricdesigns that use parallelism, locality, and on-chipwiring bandwidth to compensate for long wire latency.An alternative approach to this problem is to exploitnewly-emerging on-chip transmission line technology toreduce communication latency. Compared to conventionalRC wires, transmission lines can reduce delay by up to afactor of 30 for global wires, while eliminating the needfor repeaters. However, this latency reduction comes at thecost of a comparable reduction in bandwidth.In this paper, we investigate using transmission linesto access large level-2 on-chip caches. We propose a familyof Transmission Line Cache (TLC) designs that representdifferent points in the latency/bandwidth spectrum.Compared to the recently-proposed Dynamic Non-UniformCache Architecture (DNUCA) design, the base TLCdesign reduces the required cache area by 18% andreduces the interconnection network's dynamic powerconsumption by an average of 61%. The optimized TLCdesigns attain similar performance using fewer transmis-sionlines but with some additional complexity. Simulationresults using full-system simulation show that TLC providesmore consistent performance than the DNUCAdesign across a wide variety of workloads. TLC caches arelogically simpler than DNUCA designs, but requiregreater circuit and manufacturing complexity.
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%.
2153940
The Distance Geometry of Deep Rhythms and Scales
We characterize which sets of k points chosen from n points spaced evenly around a circle have the property that, for each i = 1, 2, . . . , k−1, there is a nonzero distance along the circle that occurs as the distance between exactly i pairs from the set of k points. Such a set can be interpreted as the set of onsets in a rhythm of period n, or as the set of pitches in a scale of n tones, in which case the property states that, for each i = 1, 2, . . . , k − 1, there is a nonzero time [tone] interval that appears as the temporal [pitch] distance between exactly i pairs of onsets [pitches]. Rhythms with this property are called Erdős-deep. The problem is a discrete, one-dimensional (circular) analog to an unsolved problem posed by Erdős in the plane.
11947788
Context-Dependent L Forms
The notions of an EIL form and its interpretations are introduced. The resulting families of L systems and languages are studied from a number of different points of view. Some of the main results are: the family of context-free languages is generated by an EIL form (contrary to the earlier results concerning context-free L forms) and, as regards reducibility in the amount of context, EIL forms lie between IL and EIL systems.
39838781
Context-Free Grammar Forms with Strict Interpretations
This paper begins a systematic investigation of context-free grammar forms using the mechanism of “strict” interpretations: the interpretations of terminal letters are defined exactly as those of nonterminal letters. Thus, strict interpretations are more closely related to the master grammar than the g-interpretations investigated in the original grammar form paper [A. Cremers and S. Ginsburg, Context-free grammar forms, J. Comput. System Sci. 11 (1975), 86–116]. The main results of this paper concern reducibility, closure properties, generators and hierarchies of language families, as well as the characterization of grammar forms generating (under strict interpretation) the families of regular and linear languages.
2475557
Three-Dimensional Grid Drawings with Sub-quadratic Volume
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 are pairwise non-crossing. A \(\mathcal{O}(n^{3/2})\) volume bound is proved for three-dimensional grid drawings of graphs with bounded degree, graphs with bounded genus, and graphs with no bounded complete graph as a minor. The previous best bound for these graph families was \(\mathcal{O}(n^{2})\). These results (partially) solve open problems due to Pach, Thiele, and Toth [Graph Drawing 1997] and Felsner, Liotta, and Wismath [Graph Drawing 2001].
32158792
An Algorithm for Three-Dimensional Orthogonal Graph Drawing
In this paper we present an algorithm for 3-dimensional orthogonal graph drawing based on the movement of vertices from an initial layout along the main diagonal of a cube. For an n-vertex m-edge graph with maximum degree six, the algorithm produces drawings with bounding box volume at most 2:37n3 and with a total of 7m/3 bends, using no more than 4 bends per edge route. For maximum degree five graphs the bounding box has volume n3 and each edge route has two bends. These results establish new bounds for 3-dimensional orthogonal graph drawing algorithms and improve on some existing bounds.