bluuebunny/crossref_metadata_2025 huggingface dataset:
Performance of cached DRAM organizations in vector supercomputers
Authors: Hsu W.-C. , Smith J. E.
Published: July 2004

DRAMs containing cache memory are studied in the context of vector supercomputers. In particular, we consider systems where processors have no internal data caches and memory reference streams are generated by vector instructions. For this application, we expect that cached DRAMs can provide high bandwidth at relatively low cost.

We study both DRAMs with a single, long cache line and with smaller, multiple cache lines. Memory interleaving schemes that increase data locality are proposed and studied. The interleaving schemes are also shown to lead to non-uniform bank accesses, i.e. hot banks. This suggest there is an important optimization problem involving methods that increase locality to improve performance, but not so much that hot banks diminish performance. We show that for uniprocessor systems, both types of cached DRAMs work well with the proposed interleave methods. For multiprogrammed multiprocessors, the multiple cache line DRAMs work better.
Odd memory systems may be quite interesting
Authors: Seznec André , Lenfant Jacques
Published: July 2004

Using a prime number of N of memory banks on a vector processor allows a conflict-free access for any slice of N consecutive elements of a vector stored with a stride not multiple of N.

To reject the use of a prime (or odd) number N of memory banks, it is generally advanced that address computation for such a memory system would require systematic Euclidean Division by the number N. We first show that the well known Chinese Remainder Theorem allows to define a very simple mapping of data onto the memory banks for which address computation does not require any Euclidean Division.

Massively parallel SIMD computers may have several thousands of processors. When the memory on such a machine is globally shared, routing vectors from memory to the processors is a major difficulty; the control for the interconnection network cannot be generally computed at execution time. When the number of memory banks and processors is a product of prime numbers, the family of permutations needed for routing vectors for memory to the processors through the interconnection network have very specific properties. The Chinese Remainder Network presented in the paper is able to execute all these permutations in a single path and may be self-routed.
Linear logic and permutation stacks—the Forth shall be first
Authors: Baker Henry G.
Published: July 2004

Girard's linear logic can be used to model programming languages in which each bound variable name has exactly one "occurrence"---i.e., no variable can have implicit "fan-out"; multiple uses require explicit duplication. Among other nice properties, "linear" languages need no garbage collector, yet have no dangling reference problems. We show a natural equivalence between a "linear" programming language and a stack machine in which the top items can undergo arbitrary permutations. Such permutation stack machines can be considered combinator abstractions of Moore's
Forth
programming language.
Distributed scheduling algorithms to improve the performance of parallel data transfers
Authors: Durand Dannie , Jain Ravi , Tseytlin David
Published: July 2004

The cost of data transfers, and in particular of I/O operations, is a growing problem in parallel computing. A promising approach to alleviating this bottleneck is to schedule parallel I/O operations explicitly. We develop a class of decentralized algorithms for scheduling parallel I/O operations, where the objective is to reduce the time required to complete a given set of transfers. These algorithms, based on edge-coloring and matching of bipartite graphs, rely upon simple heuristics to obtain shorter schedules. We present simulation results indicating that the best of our algorithms can produce schedules whose length is within 2--20% of the optimal schedule, a substantial improvement on previous decentralized algorithms. We discuss theoretical and experimental work in progress and possible extensions.
The effect of compiler-flag tuning on SPEC benchmark performance
Authors: Chan Yin , Sudarsanam Ashok , Wolfe Andrew
Published: July 2004

The SPEC CINT92 and CFP92 benchmark suites are application-based system benchmarks primarily intended for workstation-class system performance measurements. The SPEC CPU benchmark results are widely disseminated by system vendors and as such have become the de-facto standard for comparing system performance. Recently, many observers have expressed concerns about the suitability of published SPEC benchmark results in representing application performance on typical systems. The most outspoken concern is that there is too much freedom permitted in the manipulation of compiler flags. This has resulted in revisions to the SPEC reporting procedure.This paper presents and discusses many of the issues concerning the tuning of benchmarks through manipulation of compiler flags. We attempt to quantify the impact of these procedures through controlled experiments. Baseline performance results, using a set of uniform, common optimizations are compared to published data. Further experiments measure the performance of the SPEC benchmarks in the other common usage scenarios. These are a centralized file storage configuration and a system using common binaries among several implementations of the same architecture. Despite the great concern over the use of compiler flags in the SPEC community, our experiments show only a modest impact on performance. The more significant performance differential shown in the other experiments draws into question the utility of current SPEC data to many users.
Fast and accurate instruction fetch and branch prediction
Authors: Calder B. , Grunwald D.
Published: July 2004

Accurate branch prediction is critical to performance; mispredicted branches mean that ten's of cycles may be wasted in superscalar architectures. Architectures combining very effective branch prediction mechanisms coupled with modified branch target buffers (BTB's) have been proposed for wide-issue processors. These mechanisms require considerable processor resources. Concurrently, the larger address space of 64-bit architectures introduce new obstacles and opportunities. A larger address space means branch target buffers become more expensive. In this paper, we show how a combination of less expensive mechanisms can achieve better performance than BTB's. This combination relies on a number of design choices described in the paper. We used trace-driven simulation to show that our proposed design, which uses fewer resources, offers better performance than previously proposed alternatives for most programs, and indicate how to further improve this design.
Speculative disambiguation
Authors: Huang A. S. , Slavenburg G. , Shen J. P.
Published: July 2004

Ambiguous memory references have always been one of the main sources of performance bottlenecks. Many papers have addressed this problem using static disambiguation. These methods work extremely well when the memory access pattern is linear and predictable. However they are ineffective when the memory access pattern is nonlinear or when the access pattern cannot be determined statically. For these difficult problems, this paper presents speculative disambiguation, a compilation technique for architectures supporting instruction level parallelism and either speculative execution or conditional execution (or both). This technique produces specialized code at compile time to disambiguate memory references at run time. It is shown that on machines with sufficient resources, the technique will always result in lower execution time. Speculative disambiguation has been implemented for a VLIW architecture with guarded execution. Preliminary results indicate that it can help bridge a significant fraction of the performance gap between a good and a perfect static disambiguator. Occasionally it can outperform the perfect static disambiguator.
The impact of unresolved branches on branch prediction scheme performance
Authors: Talcott A. R. , Yamamoto W. , Serrano M. J. , Wood R. C. , Nemirovsky M.
Published: July 2004

In this paper, we examine the benefits of the early resolution of branch instructions and the impact of unresolved branches on history-based branch prediction schemes by using two new metrics that are more revealing than branch prediction accuracy alone. We first briefly review a number of branch prediction schemes and introduce two new branch prediction scheme performance metrics. We then utilize these metrics to gauge the improvement in branch prediction scheme performance when only the outcomes of unresolved branches are predicted. Finally, we examine two approaches for handling multiple unresolved branches in history-based branch prediction schemes, and determine that prediction accuracy remains quite stable when older branch histories are used.
Tradeoffs in two-level on-chip caching
Authors: Jouppi N. P. , Wilton S. J. E.
Published: July 2004

The performance of two-level on-chip caching is investigated for a range of technology and architecture assumptions. The area and access time of each level of cache is modeled in detail. The results indicate that for most workloads, two-level cache configurations (with a set-associative second level) perform marginally better than single-level cache configurations that require the same chip area once the first-level cache sizes are 64KB or larger. Two-level configurations become even more important in systems with no off-chip cache and in systems in which the memory cells in the first-level caches are multiported and hence larger than those in the second-level cache. Finally, a new replacement policy called two-level exclusive caching is introduced. Two-level exclusive caching improves the performance of two-level caching organizations by increasing the effective associativity and capacity.
Architectural support for performance tuning
Authors: Singhal A. , Goldberg A. J.
Published: July 2004

Latency hiding techniques such as multilevel cache hierarchies yield high performance when applications map well onto hierarchy implementations, but performance can suffer drastically when they do not. Identifying and reducing mismatches between an application and the memory hierarchy is difficult without insight into the actual behavior of the hardware implementation. We advocate the use of hardware event counters, as a cheap, effective and practical way to tune applications for a given hardware platform. We take a case study approach, focussing on the counters available on the SPARCcenter 2000, a 20 processor, shared-bus based multiprocessor. We describe the tools we built to relate hardware event counts to user applications and give examples to illustrate how these tools are useful in practice. We conclude with a critique of the current hardware counters, offering a user's perspective on how they could be redesigned to be more effective.
Software versus hardware shared-memory implementation
Authors: Cox A. L. , Dwarkadas S. , Keleher P. , Lu H. , Rajamony R. , Zwaenepoel W.
Published: July 2004

We compare the performance of software-supported shared memory on a general-purpose network to hardware-supported shared memory on a dedicated interconnect.Up to eight processors, our results are based on the execution of a set of application programs on a SGI 4D/480 multiprocessor and on TreadMarks, a distributed shared memory system that runs on a Fore ATM LAN of DECstation-5000/240s. Since the DECstation and the 4D/480 use the same processor, primary cache, and compiler, the shared-memory implementation is the principal difference between the systems. Our results show that TreadMarks performs comparably to the 4D/480 for applications with moderate amounts of synchronization, but the difference in performance grows as the synchronization frequency increases. For applications that require a large amount of memory bandwidth, TreadMarks can perform better than the SGI 4D/480.Beyond eight processors, our results are based on execution-driven simulation. Specifically, we compare a software implementation on a general-purpose network of uniprocessor nodes, a hardware implementation using a directory-based protocol on a dedicated interconnect, and a combined implementation using software to provide shared memory between multiprocessor nodes with hardware implementing shared memory within a node. For the modest size of the problems that we can simulate, the hardware implementation scales well and the software implementation scales poorly. The combined approach delivers performance close to that of the hardware implementation for applications with small to moderate synchronization rates and good locality. Reductions in communication overhead improve the performance of the software and the combined approach, but synchronization remains a bottleneck.
Guarded execution and branch prediction in dynamic ILP processors
Authors: Pnevmatikatos D. N. , Sohi G. S.
Published: July 2004

We evaluate the effects of guarded (or conditional, or predicated) execution on the performance of an instruction level parallel processor employing dynamic branch prediction. First, we assess the utility of guarded execution, both qualitatively and quantitatively, using a variety of application programs. Our assessment shows that guarded execution significantly increases the opportunities, for both compiler and dynamic hardware, to extract and exploit parallelism. However, existing methods of specifying guarded execution have several drawbacks that limit its use. Second, we study the interaction of guarded execution and dynamic branch prediction and show that the use of guarded execution significantly increases the number of instructions between mispredicted branches. Third, we propose a new method of specifying guarded execution. The proposed method uses special GUARD instructions, which can be used to incorporate guarded execution into existing instruction sets. GUARD instructions realize the full power of guarded execution, without the drawbacks of existing methods of specifying guarded execution.
Complexity/performance tradeoffs with non-blocking loads
Authors: Farkas K. I. , Jouppi N. P.
Published: July 2004

Non-blocking loads are a very effective technique for tolerating the cache-miss latency on data cache references. In this paper, we describe several methods for implementing non-blocking loads. A range of resulting hardware complexity/performance tradeoffs are investigated using an object-code translation and instrumentation system. We have investigated the SPEC92 benchmarks and have found that for the integer benchmarks, a simple hit-under-miss implementation achieves almost all of the available performance improvement for relatively little cost. However, for most of the numeric benchmarks, more expensive implementations are worthwhile. The results also point out the importance of using a compiler capable of scheduling load instructions for cache misses rather than cache hits in non-blocking systems.
Crosshatch disk array for improved reliability and performance
Authors: Ng S. W.
Published: July 2004

Redundant disk array architecture provides fault tolerance against disk drive failures. However, a storage subsystem consists of more than just disk drives. There must also be controllers for interfacing with the disk drives, cabling for providing data/control paths, power supplies, etc. For the subsystem to be fault tolerant, it must also be able to tolerate failure in any one of these components. While currently known array architectures can be designed to be tolerant to single failure in the support hardware, little attention has been paid to performance in the event of such failures. The recovery procedures required after such failures have been repaired were also not fully considered. In this paper a new array architecture is presented which outperforms other currently known array architectures when some supporting hardware such as a controller or cable has failed. Furthermore, this architecture is fault tolerant to at least double failures in the support hardware and is, therefore, a more reliable and robust architecture.
METRO
Authors: DeHon A. , Chong F. , Becker M. , Egozy E. , Minsky H. , Peretz S. , Knight T. F.
Published: July 2004

The
Multipath Enhanced Transit Router Organization
(
METRO
) is a flexible routing architecture for high-performance, tightly-coupled, multiprocessors and routing hubs. A
METRO
router is a dilated cross-bar routing component supporting half-duplex bidirectional, pipelined, circuit-switched connections. Each
METRO
router is self-routing and supports dynamic message traffic. The routers works in conjunction with source-responsible network interfaces to achieve reliable end-to-end data transmission in the presence of heavy network congestion and dynamic faults.
METRO
separates the fundamental architectural characteristics from implementation parameters. Simplicity of routing function coupled with freedom in the implementation parameters allows
METRO
implementations fully exploit available technology to achieve low-latency and high-bandwidth. We illustrate the effects of this implementation freedom by summarizing the performance which various
METRO
configurations can extract from some modern CMOS technologies. Included in our illustrations is
METROJR-ORBIT
, a minimal instance of the
METRO
architecture we constructed in a
1.2
μ gate-array technology.
Ariadne—an adaptive router for fault-tolerant multicomputers
Authors: Allen J. D. , Gaughan P. T. , Schimmel D. E. , Yalamanchili S.
Published: July 2004

Adaptive routing has been proposed as a means of improving performance and fault-tolerance in multicomputer networks. While a number of algorithms have been proposed, few adaptive routers have been implemented in hardware. This paper presents the design and implementation of Ariadne --- a prototype single chip, hardware router. The primary motivation is tolerance to link and router failures, while reconciling conflicting demands on performance. This is achieved by implementing the
m
-misroute backtracking protocol (MB-
m
) using the pipelined circuitswitching (PCS) communication mechanism[17]. Ariadne implements two virtual data channels and one virtual control channel per physical link. The router is self-timed with single flit buffering at the input and output ports, and is fully adaptive.
The Stanford FLASH multiprocessor
Authors: Kuskin J. , Ofelt D. , Heinrich M. , Heinlein J. , Simoni R. , Gharachorloo K. , Chapin J. , Nakahira D. , Baxter J. , Horowitz M. , Gupta A. , Rosenblum M. , Hennessy J.
Published: July 2004

The FLASH multiprocessor efficiently integrates support for cache-coherent shared memory and high-performance message passing, while minimizing both hardware and software overhead. Each node in FLASH contains a microprocessor, a portion of the machine's global memory, a port to the interconnection network, an I/O interface, and a custom node controller called MAGIC. The MAGIC chip handles all communication both within the node and among nodes, using hardwired data paths for efficient data movement and a programmable processor optimized for executing protocol operations. The use of the protocol processor makes FLASH very flexible --- it can support a variety of different communication mechanisms --- and simplifies the design and implementation.This paper presents the architecture of FLASH and MAGIC, and discusses the base cache-coherence and message-passing protocols. Latency and occupancy numbers, which are derived from our system-level simulator and our Verilog code, are given for several common protocol operations. The paper also describes our software strategy and FLASH's current status.
Tempest and typhoon
Authors: Reinhardt S. K. , Larus J. R. , Wood D. A.
Published: July 2004

Future parallel computers must efficiently execute not only hand-coded applications but also programs written in high-level, parallel programming languages. Today's machines limit these programs to a single communication paradigm, either message-passing or shared-memory, which results in uneven performance. This paper addresses this problem by defining an interface,
Tempest
, that exposes low-level communication and memory-system mechanisms so programmers and compilers can customize policies for a given application.
Typhoon
is a proposed hardware platform that implements these mechanisms with a fully-programmable, user-level processor in the network interface. We demonstrate the utility of Tempest with two examples. First, the
Stache
protocol uses Tempest's finegrain access control mechanisms to manage part of a processor's local memory as a large, fully-associative cache for remote data. We simulated Typhoon on the Wisconsin Wind Tunnel and found that Stache running on Typhoon performs comparably (±30%) to an all-hardware Dir
N
NB cache-coherence protocol for five shared-memory programs. Second, we illustrate how programmers or compilers can use Tempest's flexibility to exploit an application's sharing patterns with a custom protocol. For the EM3D application, the custom protocol improves performance up to 35% over the all-hardware protocol.
A study of single-chip processor/cache organizations for large numbers of transistors
Authors: Farrens M. , Tyson G. , Pleszkun A. R.
Published: July 2004

This paper presents a trace-driven simulation-based study of a wide range of cache configurations and processor counts. This study was undertaken in an attempt to help answer the question of how best to allocate large numbers of transistors, a question that is rapidly increasing in importance as transistor densities continue to climb. At what point does continuing to increase the size of the on-chip first level cache cease to provide sufficient increases in hit rate and become prohibitively difficult to access in a single cycle? In order to compare different configurations, the concept of an
Equivalent Cache Transistor
is presented. Results indicate that the access time of the first-level data cache is more important than the size. In addition, it appears that once approximately 15 million transistors become available, a two processor configuration is preferable to a single processor with correspondingly larger caches.
A unified architectural tradeoff methodology
Authors: Chen C.-H. , Somani A. K.
Published: July 2004

We present a unified approach to assess the trade-off of architecture techniques that affect mean memory access time. The architectural features we consider include cache hit ratio, processor stalling features, line size, memory cycle time, the external data bus width of a processor, pipelined memory system, and read by-passing write buffers. We demonstrate how each of these features can be traded off to achieve the desired performance. The performance of an architecture feature is quantified in terms of cache hit ratio based on the equivalence of mean memory delay time. This paper investigates the implication of architectural tradeoffs on the pin count, memory system design, and on-chip cache area for microprocessor systems.
Are multiport memories physically feasible?
Authors: Forsell Martti J.
Published: July 2004

A Parallel Random Access Machine (PRAM) is a popular model of parallel computation that promises easy programmability and great parallel performance, but only if efficient shared main memories can be built. This would not be easy, because the complexity of shared memories leads to difficult technical problems. In this paper we consider the idea of true multiport memory that can be used as a building block for efficient PRAM-style shared main memory. Two possible structures for multiport memory chips are presented. We shall also give a preliminary cost-effectivity and performance analysis for memory systems using proposed multiport RAMs. Results are encouraging: At least small size multiport memories seem to be physically feasible.
The Wisconsin Wind Tunnel project
Authors: Hill Mark D. , Larus James R. , Wood David A.
Published: July 2004

This document lists contributors to the Wisconsin Wind Tunnel Project, gives a brief description of the project, and presents references and abstracts to its principal papers, including how to obtain them online.
A study of MIPS programs
Authors: Unwala Ishaq H. , Cragon Harvey G.
Published: July 2004

Data from a study of both static and dynamic instruction traces of popular workstation type programs for a MIPS processor is presented. The instruction traces were analyzed to extract the branch distances, and instruction sequences of 1, 2, 3, 4, and 5 instructions.
A simple architecture for constant time sorting machines
Authors: Hsu Tsong-Chih , Wang Sheng-De
Published: July 2004

In this paper, we propose a constant time sorting algorithm on an array composed of comparators and single-pole-double-throw switches, which is far more feasible than other constant time sorting algorithms [21]-[23]. Our results shown that the algorithm uses time
T
= Θ(1) and area
A
=
O
(
N
3
). This nearly matches the
AT
2
= Ω(
N
2
log
2
N
) lower bound for sorting in the VLSI model.
SIMD machines
Authors: Parhami Behrooz
Published: July 2004

I volunteered to write this report during the SIMD panel session held on 2/9/95 at Frontiers '95. All panelists cooperated by sending me their transparency masters. A draft report was prepared based on these transparency masters, position statements published in the Frontiers '95 proceedings on pp. 466-469, and my own notes. The draft was e-mailed on 3/17/95 to the panel organizer/moderator and the panelists for their comments. This final version of the report is based on comments and markups received through 3/31/95. I have drawn from the panelists' ideas freely, using quotation marks only when including their statements verbatim.The panel consisted of both academic and industry experts in the field of massively parallel systems (see the table below). All but Tim Bridges, who is currently involved in a large-scale software development project for the MasPar MP-2 SIMD architecture, have built working SIMD machines. The vast practical experience of the panel was quite evident in the insightful presentations and interactions. It is indeed a privilege for me to have worked on this report.
Dynamic self-invalidation
Authors: Lebeck Alvin R. , Wood David A.
Published: July 2004

This paper introduces dynamic self-invalidation (DSI), a new technique for reducing cache coherence overhead in shared-memory multiprocessors. DSI eliminates invalidation messages by having a processor automatically invalidate its local copy of a cache block before a conflicting access by another processor. Eliminating invalidation overhead is particularly important under sequential consistency, where the latency of invalidating outstanding copies can increase a program's critical path.DSI is applicable to software, hardware, and hybrid coherence schemes. In this paper we evaluate DSI in the context of hardware directory-based write-invalidate coherence protocols. Our results show that DSI reduces execution time of a sequentially consistent full-map coherence protocol by as much as 41%. This is comparable to an implementation of weak consistency that uses a coalescing write-buffer to allow up to 16 outstanding requests for exclusive blocks. When used in conjunction with weak consistency, DSI can exploit tear-off blocks---which eliminate both invalidation and acknowledgment messages---for a total reduction in messages of up to 26%.
Performance evaluation of the PowerPC 620 microarchitecture
Authors: Diep Trung A. , Nelson Christopher , Shen John Paul
Published: July 2004

The PowerPC 620™ microprocessor is the most recent and performance leading member of the PowerPC™ family. The 64-bit PowerPC 620 microprocessor employs a two-phase branch prediction scheme, dynamic renaming for all the register files, distributed multi-entry reservation stations, true out-of-order execution by six execution units, and a completion buffer for ensuring precise exceptions. This paper presents an instruction-level performance evaluation of the 620 microarchitecture. A performance simulator is developed using the VMW (Visualization-based Microarchitecture Workbench) retargetable framework. The VMW-based simulator accurately models the microarchitecture down to the machine cycle level. Extensive trace-driven simulation is performed using the SPEC92 benchmarks. Detailed quantitative analyses of the effectiveness of all key microarchitecture features are presented.
Vector multiprocessors with arbitrated memory access
Authors: Peiron Montse , Valero Mateo , Ayguadé Eduard , Lang Tomás
Published: July 2004

The high latency of memory accesses is one of the factors that most contribute to reduce the performance of current vector supercomputers. The conflicts that can occur in the memory modules plus the collisions in the interconnection network in the case of multiprocessors make that the execution time of applications increases significantly. In this work we propose a memory access method that for both cases of vector uniprocessors and multiprocessors allows to perform stream accesses with the smallest possible latency in the majority of the cases. The basic idea is to arbitrate the memory access by defining the order in which the memory modules are visited. The stream elements are requested out of order. In addition, the access method also reduces the cost of the interconnection network.
Optimization of instruction fetch mechanisms for high issue rates
Authors: Conte Thomas M. , Menezes Kishore N. , Mills Patrick M. , Patel Burzin A.
Published: July 2004

Recent superscalar processors issue four instructions per cycle. These processors are also powered by highly-parallel superscalar cores. The potential performance can only be exploited when fed by high instruction bandwidth. This task is the responsibility of the instruction fetch unit. Accurate branch prediction and low I-cache miss ratios are essential for the efficient operation of the fetch unit. Several studies on cache design and branch prediction address this problem. However, these techniques are not sufficient. Even in the presence of efficient cache designs and branch prediction, the fetch unit must continuously extract multiple, non-sequential instructions from the instruction cache, realign these in the proper order, and supply them to the decoder. This paper explores solutions to this problem and presents several schemes with varying degrees of performance and cost. The most-general scheme, the
collapsing buffer,
achieves near-perfect performance and consistently aligns instructions in excess of 90% of the time, over a wide range of issue rates. The performance boost provided by compiler optimization techniques is also investigated. Results show that compiler optimization can significantly enhance performance across all schemes. The
collapsing buffer
supplemented by compiler techniques remains the best-performing mechanism. The paper closes with recommendations and suggestions for future.
Instruction cache fetch policies for speculative execution
Authors: Lee Dennis , Baer Jean-Loup , Calder Brad , Grunwald Dirk
Published: July 2004

Current trends in processor design are pointing to deeper and wider pipelines and superscalar architectures. The efficient use of these resources requires
speculative execution,
a technique whereby the processor continues executing the predicted path of a branch before the branch condition is resolved.In this paper, we investigate the implications of speculative execution on instruction cache performance. We explore policies for managing instruction cache misses ranging from aggressive policies (always fetch on the speculative path) to conservative ones (wait until branches are resolved). We test these policies and their interaction with
next-line
prefetching by simulating the effects on instruction caches with varying architectural parameters. Our results suggest that an aggressive policy combined with next-line prefetching is best for small latencies while more conservative policies are preferable for large latencies.
MGS
Authors: Yeung Donald , Kubiatowicz John , Agarwal Anant
Published: July 2004

Parallel workstations, each comprising 10-100 processors, promise cost-effective general-purpose multiprocessing. This paper explores the coupling of such small- to medium-scale shared memory multiprocessors through software over a local area network to synthesize larger shared memory systems. We call these systems Distributed Scalable Shared-memory Multiprocessors (DSSMPs).This paper introduces the design of a shared memory system that uses multiple granularities of sharing, and presents an implementation on the Alewife multiprocessor, called MGS. Multigrain shared memory enables the collaboration of hardware and software shared memory, and is effective at exploiting a form of locality called
multigrain locality.
The system provides efficient support for fine-grain cache-line sharing, and resorts to coarse-grain page-level sharing only when locality is violated. A framework for characterizing application performance on DSSMPs is also introduced.Using MGS, an in-depth study of several shared memory applications is conducted to understand the behavior of DSSMPs. We find that unmodified shared memory applications can exploit multigrain sharing. Keeping the number of processors fixed, applications execute up to 85% faster when each DSSMP node is a multiprocessor as opposed to a uniprocessor. We also show that tightly-coupled multiprocessors hold a significant performance advantage over DSSMPs on unmodified applications. However, a best-effort implementation of a kernel from one of the applications allows a DSSMP to almost match the performance of a tightly-coupled multiprocessor.
Memory bandwidth limitations of future microprocessors
Authors: Burger Doug , Goodman James R. , Kägi Alain
Published: July 2004

This paper makes the case that pin bandwidth will be a critical consideration for future microprocessors. We show that many of the techniques used to tolerate growing memory latencies do so at the expense of increased bandwidth requirements. Using a decomposition of execution time, we show that for modern processors that employ aggressive memory latency tolerance techniques, wasted cycles due to insufficient bandwidth generally exceed those due to raw memory latencies. Given the importance of maximizing memory bandwidth, we calculate
effective pin bandwidth,
then estimate optimal effective pin bandwidth. We measure these quantities by determining the amount by which both caches and minimal-traffic caches filter accesses to the lower levels of the memory hierarchy. We see that there is a gap that can exceed two orders of magnitude between the total memory traffic generated by caches and the minimal-traffic caches---implying that the potential exists to increase effective pin bandwidth substantially. We decompose this traffic gap into four factors, and show they contribute quite differently to traffic reduction for different benchmarks. We conclude that, in the short term, pin bandwidth limitations will make more complex on-chip caches cost-effective. For example, flexible caches may allow individual applications to choose from a range of caching policies. In the long term, we predict that off-chip accesses will be so expensive that all system memory will reside on one or more processor chips.
Increasing cache port efficiency for dynamic superscalar microprocessors
Authors: Wilson Kenneth M. , Olukotun Kunle , Rosenblum Mendel
Published: July 2004

The memory bandwidth demands of modern microprocessors require the use of a multi-ported cache to achieve peak performance. However, multi-ported caches are costly to implement. In this paper we propose techniques for improving the bandwidth of a single cache port by using additional buffering in the processor, and by taking maximum advantage of a wider cache port. We evaluate these techniques using realistic applications that include the operating system. Our techniques using a single-ported cache achieve 91% of the performance of a dual-ported cache.
DCD—disk caching disk
Authors: Hu Yiming , Yang Qing
Published: July 2004

This paper presents a novel disk storage architecture calledDCD,Disk Caching Disk, for the purpose of optimizing I/O performance. The main idea of theDCDis to use a small log disk, referred to ascache-disk,as a secondary disk cache to optimize write performance. While the cache-disk and the normal data disk have the same physical properties, the access speed of the former differs dramatically from the latter because of different data units and different ways in which data are accessed. Our objective is to exploit this speed difference by using the log disk as a cache to build a reliable and smooth disk hierarchy. A small RAM buffer is used to collect small write requests to form a log which is transferred onto the cache-disk whenever the cache-disk is idle. Because of the temporal locality that exists in office/engineering work-load environments, theDCDsystem shows write performance close to the same size RAM (i.e. solid-state disk) for the cost of a disk. Moreover, the cache-disk can also be implemented as a logical disk in which case a small portion of the normal data disk is used as the log disk. Trace-driven simulation experiments are carried out to evaluate the performance of the proposed disk architecture. Under the office/engineering work-load environment, theDCDshows superb disk performance for writes as compared to existing disk systems. Performance improvements of up to two orders of magnitude are observed in terms of average response time for write operations. Furthermore,DCDis very reliable and works at the device or device driver level. As a result, it can be applied directly to current file systems without the need of changing the operating system.
Polling watchdog
Authors: Maquelin Olivier , Gao Guang R. , Hum Herbert H. J. , Theobald Kevin B. , Tian Xin-Min
Published: July 2004

Parallel systems supporting multithreading, or message passing in general, have typically used either polling or interrupts to handle incoming messages. Neither approach is ideal; either may lead to excessive overheads or message-handling latencies, depending on the application. This paper investigates a combined approach---
Polling Watchdog,
where both are used depending on the circumstances. The
Polling Watchdog
is a simple hardware extension that limits the generation of interrupts to the cases where explicit polling fails to handle the message quickly. As an added benefit, this mechanism also has the potential to simplify the interaction between interrupts and the network accesses performed by the program.We present the resulting performance for the
EARTH-MANNA-S
system, an implementation of the EARTH (
Efficient Architecture for Running THreads
) execution model on the MANNA multiprocessor. In contrast to the original EARTH-MANNA system, this system does not use a dedicated communication processor. Rather, synchronization and communication tasks are performed on the same processor as the regular computations. Therefore, an efficient message-handling mechanism is essential to good performance. Simulation results and performance measurements show that the Polling Watchdog indeed performs better than either polling or interrupts alone. In fact, this mechanism allows the EARTH-MANNA-S system to achieve the same level of performance as the original EARTH-MANNA multithreaded system.
Evaluation of multithreaded uniprocessors for commercial application environments
Authors: Eickemeyer Richard J. , Johnson Ross E. , Kunkel Steven R. , Squillante Mark S. , Liu Shiafun
Published: July 2004

As memory speeds grow at a considerably slower rate than processor speeds, memory accesses are starting to dominate the execution time of processors, and this will likely continue into the future. This trend will be exacerbated by growing miss rates due to commercial applications, object-oriented programming and micro-kernel based operating systems. We examine the use of coarse-grained multithreading to address this important problem in uniprocessor on-line transaction processing environments where there is a natural, coarse-grained parallelism between the tasks resulting from transactions being executed concurrently, with no application software modifications required. Our results suggest that multithreading can provide significant performance improvements for uniprocessor commercial computing environments.
Coherent network interfaces for fine-grain communication
Authors: Mukherjee Shubhendu S. , Falsafi Babak , Hill Mark D. , Wood David A.
Published: July 2004

Historically, processor accesses to memory-mapped device registers have been marked uncachable to insure their visibility to the device. The ubiquity of snooping cache coherence, however, makes it possible for processors and devices to interact with cachable, coherent memory operations. Using coherence can improve performance by facilitating burst transfers of whole cache blocks and reducing control overheads (e.g., for polling).This paper begins an exploration of network interfaces (NIs) that use coherence---coherent network interfaces (CNIs)---to improve communication performance. We restrict this study to NI/CNIs that reside on coherent memory or I/O buses, to NI/CNIs that are much simpler than processors, and to the performance of fine-grain messaging from user process to user process.Our first contribution is to develop and optimize two mechanisms that CNIs use to communicate with processors. A cachable device register---derived from cachable control registers [39,40]---is a coherent, cachable block of memory used to transfer status, control, or data between a device and a processor. Cachable queues generalize cachable device registers from one cachable, coherent memory block to a contiguous region of cachable, coherent blocks managed as a circular queue.Our second contribution is a taxonomy and comparison of four CNIs with a more conventional NI. Microbenchmark results show that CNIs can improve the round-trip latency and achievable bandwidth of a small 64-byte message by 37% and 125% respectively on the memory bus and 74% and 123% respectively on a coherent I/O bus. Experiments with five macrobenchmarks show that CNIs can improve the performance by 17-53% on the memory bus and 30-88% on the I/O bus.
Instruction prefetching of systems codes with layout optimized for reduced cache misses
Authors: Xia Chun , Torrellas Josep
Published: July 2004

High-performing on-chip instruction caches are crucial to keep fast processors busy. Unfortunately, while on-chip caches are usually successful at intercepting instruction fetches in loop-intensive engineering codes, they are less able to do so in large systems codes. To improve the performance of the latter codes, the compiler can be used to lay out the code in memory for reduced cache conflicts. Interestingly, such an operation leaves the code in a state that can be exploited by a new type of instruction prefetching: guarded sequential prefetching.The idea is that the compiler leaves hints in the code as to how the code was laid out. Then, at run time, the prefetching hardware detects these hints and uses them to prefetch more effectively. This scheme can be implemented very cheaply: one bit encoded in control transfer instructions and a prefetch module that requires minor extensions to existing next-line sequential prefetchers. Furthermore, the scheme can be turned off and on at run time with the toggling of a bit in the TLB. The scheme is evaluated with simulations using complete traces from a 4-processor machine. Overall, for 16-Kbyte primary instruction caches, guarded sequential prefetching removes, on average, 66% of the instruction misses remaining in an operating system with an optimized layout, speeding up the operating system by 10%. Moreover, the scheme is more cost-effective and robust than existing sequential prefetching techniques.
Early experience with message-passing on the SHRIMP multicomputer
Authors: Felten Edward W. , Alpert Richard D. , Bilas Angelos , Blumrich Matthias A. , Clark Douglas W. , Damianakis Stefanos N. , Dubnicki Cezary , Iftode Liviu , Li Kai
Published: July 2004

The SHRIMP multicomputer provides virtual memory-mapped communication (VMMC), which supports protected, user-level message passing, allows user programs to perform their own buffer management, and separates data transfers from control transfers so that a data transfer can be done without the intervention of the receiving node CPU. An important question is whether such a mechanism can indeed deliver all of the available hardware performance to applications which use conventional message-passing libraries.This paper reports our early experience with message-passing on a small, working SHRIMP multicomputer. We have implemented several user-level communication libraries on top of the VMMC mechanism, including the NX message-passing interface, Sun RPC, stream sockets, and specialized RPC. The first three are fully compatible with existing systems. Our experience shows that the VMMC mechanism supports these message-passing interfaces well. When zero-copy protocols are allowed by the semantics of the interface, VMMC can effectively deliver to applications almost all of the raw hardware's communication performance.
The case for SRAM main memory
Authors: Machanick Philip
Published: July 2004

The growing CPU-memory gap is resulting in increasingly large cache sizes. As cache sizes increase, associativity becomes less of a win. At the same time, since costs of going to DRAM increase, it becomes more valuable to be able to pin critical data in the cache---a problem if a cache is direct-mapped or has a low degree of associativity. Something else which is a problem for caches of low associativity is reducing misses by using a better replacement policy. This paper proposes that L2 cache sizes are now starting to reach the point where it makes more sense to manage them as the main memory of the computer, and relegate the traditional DRAM main memory to the role of a paging device. The paper details advantages of an SRAM main memory, as well as problems that need to be solved, in managing an extra level of virtual to physical translation.
RISC versus CISC
Authors: Bhandarkar Dileep
Published: July 2004

This paper compares an aggressive RISC and CISC implementation built with comparable technology. The two chips are the Alpha
*
21164 and the Intel Pentium® Pro processor. The paper presents performance comparisons for industry standard benchmarks and uses performance counter statistics to compare various aspects of both designs.
Bi-directional networks for large parallel processors
Authors: Moore Matthew , McDowell Charles
Published: July 2004

In SIMD parallel processors, the interconnection network is the subject of much design effort. A simple trick is presented which allows a multi-stage network to realize more communication patterns with the same wiring topology. Examples are given of bi-directional networks which produce several useful permutations that the standard networks cannot.
Wide channel computers
Authors: Lass Stanley
Published: July 2004

The wide channel design approach integrates vector and general purpose computing. Wide word accesses to a cache move several instructions per access or a few operands per access, thereby allowing a slower and somewhat larger cache. Channel commands control the movement of wide words in wide channels. Wide channels load data, vectors, instructions, and channel commands over wide channels to channel registers. Arithmetic unit operations are performed on the data in channel registers. Wide channels store data and vectors from channel registers.