bluuebunny/crossref_metadata_2025 huggingface dataset:
Compilation of out-of-core data parallel programs for distributed memory machines
Authors: Thakur Rajeev , Bordawekar Rajesh , Choudhary Alok
Published: July 2004

We are developing a compiler and runtime support system called PASSION (Parallel And Scalable Software for Input-Output), to translate out-of-core programs written in a data parallel language like HPF to message passing node programs with explicit parallel I/O. This paper describes the basic model of the compiler and the various steps involved in the compilation. We also discuss the runtime routines used by the compiler for I/O and communication. The working of the compiler is illustrated using the example of an out-of-core Laplace equation solver, with performance results on the Intel Touchstone Delta.
An experimental active memory based I/O subsystem
Authors: Asthana Abhaya , Cravatts Mark , Krzyzanowski Paul
Published: July 2004

We describe an I/O subsystem based on an active memory called SWIM, designed for efficient storage and manipulation of data structures. The key architectural idea in SWIM is to put some processing logic inside each memory chip that allows it to perform data manipulation operations locally and to communicate with a disk or a communication line through a backend port. The processing logic is specially designed to perform operations such as pointer dereferencing, memory indirection, searching and bounds checking efficiently. The I/O subsystem is built using an interconnected ensemble of such memory logic pairs. This allows a complex I/O task to be distributed between a large number of small memory processors each doing a sub-task, while still retaining a common locus of control for higher level functions. This enables more powerful, scalable and robust designs for storage and communications subsystems that can support emerging network services, multimedia workstations and wireless PCS systems. A complete parallel hardware and software system constructed using an array of SWIM elements has been operational for over a year. We present the application of SWIM to three network functions that we have currently implemented: a national phone database server, a high performance IP router, and a call screening agent.
DR-nets
Authors: Yokota Haruo
Published: July 2004

We propose DR-nets, Data-Reconstruction networks, to construct massively parallel disk systems with large capacity, wide bandwidth and high reliability. Each node of a DR-net has disks, and is connected by links to form an interconnection network. To realize the high reliability, nodes in a sub-network of the interconnection network organize a group of parity calculation proposed for RAIDs. Inter-node communication for calculating parity keeps the locality of data transfer in DR-nets, and it inhibits bottlenecks from occurring, even if the size of the network becomes very large. Overlapped two types of parity groups on the network make the system able to handle multiple disk-drive failures. A
5 × 5
torus DR-net recovers data 100% with two damaged disk drives located in any place, 95% with four damaged drives, and can recover with up to nine damaged drives.
Are multiport memories physically feasible?
Authors: Forsell Martti J.
Published: July 2004

Parallel Random Access Machine (PRAM) is a popular model for parallel computation that promises easy programmability and great parallel performance, but only if efficient shared main memories can be built. This won't 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 building block of efficient PRAM-style shared main memory. Two possible structures of multiport memory chips are presented. We will also give preliminary cost-effectivity and performance analysis of memory systems using proposed multiport RAMs. Results are encouraging: At least small size multiport memories look physically feasible. Also the power of PRAM model can be fully exploited by computer systems with multiport memories.
A case for the multithreaded processor architecture
Authors: Chaudhry Ghulam , Li Xuechang
Published: July 2004

As cache based shared-memory multiprocessors are scaled (the number of processors are increased), there will be an increase in the network latency, due to cache coherence and synchronization delays. These parameters can cause a significant drop in processor utilization. Once a process has remote procedure call or need data from remote side, the processor has to be idle or make context switch to load the next process in which the CPU (Central Processing Unit) time is wasted.By maintaining the multiple threads in the hardware, and switching among them, the multithreaded processor can overlap the waiting time for the synchronization delay so that it decreases the processor idle time.This correspondence describes the multithreaded processor architecture, in which there are a number of hardware contexts per processor. It uses coarsegrain method to schedule threads and two-phase waiting algorithm to synchronize the waiting threads. From this architecture, we can study how many hardware contexts are needed, so the processor utilization can be increased. Moreover, we can study the effect on the utilization by changing the cache miss ratio.
Evaluating stream buffers as a secondary cache replacement
Authors: Palacharla S. , Kessler R. E.
Published: July 2004

Today's commodity microprocessors require a low latency memory system to achieve high sustained performance. The conventional high-performance memory system provides fast data access via a large secondary cache. But large secondary caches can be expensive, particularly in large-scale parallel systems with many processors (and thus many caches).We evaluate a memory system design that can be both cost-effective as well as provide better performance, particularly for scientific workloads: a single level of (on-chip) cache backed up only by Jouppi's stream buffers [10] and a main memory. This memory system requires very little hardware compared to a large secondary cache and doesn't require modifications to commodity processors. We use trace-driven simulation of fifteen scientific applications from the NAS and PERFECT suites in our evaluation. We present two techniques to enhance the effectiveness of Jouppi's original stream buffers:
filtering
schemes to reduce their memory bandwidth requirement and a scheme that enables stream buffers to prefetch data being accessed in large strides. Our results show that, for the majority of our benchmarks, stream buffers can attain hit rates that are comparable to typical hit rates of secondary caches. Also, we find that as the data-set size of the scientific workload increases the performance of streams typically improves relative to secondary cache performance, showing that streams are more scalable to large data-set sizes.
Characterization of alpha AXP performance using TP and SPEC workloads
Authors: Cvetanovic Z. , Bhandarkar D.
Published: July 2004

The characteristics of several commercial and technical workloads on the DEC 7000 AXP system are compared using built-in hardware monitors. The data analyzed include total instructions, cycles, multiple-issued instructions, stall components, cache misses, and instruction types. The data indicates that the two classes of workloads have vastly different characteristics and impose different requirements on the system design. Compared to VAX, Alpha AXP takes advantage of lower cycles per instruction and cycle time to achieve a significant performance advantage. The cache and memory interconnect subsystems are expected to play a crucial role in the performance of future systems. A simple model for evaluating the effects of various design tradeoffs based on the data collected by using hardware monitors is proposed.
Measurement-based characterization of global memory and network contention, operating system and parallelization overheads
Authors: Natarajan C. , Sharma S. , Iyer R. K.
Published: July 2004

This study presents a characterization of (1) the global memory and interconnection network contention overhead, (2) the operating system overheads, and (3) the runtime system parallelization overheads for the Cedar shared-memory multiprocessor. The measurements were obtained using five representative compute-intensive, scientific, loop parallel applications from the Perfect Benchmark Suite. The overheads were measured for a range of Cedar configurations from 1 processor to the full 4-cluster/32-processor configuration, thus characterizing the effect of this scaling on the overheads. For the full 4-cluster Cedar, the operating system overhead was found to constitute 5--21% of the total completion time of an application. The parallelization overhead accounts for 10--25% of the application completion time, and the overhead due to global memory and network contention contributes 8--21% of the application completion time.
A comparison of message passing and shared memory architectures for data parallel programs
Authors: Klaiber A. C. , Levy H. M.
Published: July 2004

Shared memory and message passing are two opposing communication models for parallel multicomputer architectures. Comparing such architectures has been difficult, because applications must be hand-crafted for each architecture, often resulting in radically different sources for comparison. While it is clear that shared memory machines are currently easier to program, in the future, programs will be written in high-level languages and compiled to the specific parallel target, thus eliminating this difference.In this paper, we evaluate several parallel architecture alternatives --- message passing, NUMA, and cachecoherent shared memory --- for a collection of scientific benchmarks written in C*, a data-parallel language. Using a single suite of C* source programs, we compile each benchmark and simulate the interconnect for the alternative models. Our objective is to examine underlying, technology-independent costs inherent in each alternative. Our results show the relative work required to execute these data parallel programs on the different architectures, and point out where some models have inherent advantages for particular data-parallel program styles.
Branch with masked squashing in superpipelined processors
Authors: Su C.-L , Despain A. M.
Published: July 2004

The performance of a superpipeline processor heavily relies on its branch performance. Traditional branch strategies used in pipelined processors are delayed branches and branch with squashing. Delayed branches use safe instructions to fill delay slots. However, for a deeply pipelined processor, a compiler may not be able to find sufficient safe instructions to fill the branch delay slots. Branch with squashing takes advantage of using instructions in target basic blocks to fill the branch delay slots. However, the penalty of branch misprediction is large in superpipelined processors.In this paper, we proposed a novel branch scheme, named branch with masked squashing, which takes advantage of both delayed branch and branch with squashing. The basic idea is to fill delay slots with safe instructions which may come from above or after the branch. For the remaining unfilled delay slots, we fill with instructions from the predicted target path. In the case of misprediction, only unsafe instructions are annulled. The safe instructions in branch delay slots are always executed. Simulation results show that this branch strategy performs better than traditional delayed branch and branch with squashing.
Virtual memory mapped network interface for the SHRIMP multicomputer
Authors: Blumrich M. A. , Li K. , Alpert R. , Dubnicki C. , Felten E. W. , Sandberg J.
Published: July 2004

The network interfaces of existing multicomputers require a significant amount of software overhead to provide protection and to implement message passing protocols. This paper describes the design of a low-latency, high-bandwidth, virtual memory-mapped network interface for the SHRIMP multicomputer project at Princeton University. Without sacrificing protection, the network interface achieves low latency by using virtual memory mapping and write-latency hiding techniques, and obtains high bandwidth by providing a user-level block data transfer mechanism. We have implemented several message passing primitives in an experimental environment, demonstrating that our approach can reduce the message passing overhead to a few user-level instructions.
Architecture and evaluation of a high-speed networking subsystem for distributed-memory systems
Authors: Steenkiste P. , Hemy M. , Mummert T. , Zill B.
Published: July 2004

Achieving high-speed network I/O on distributed-memory systems is difficult because their architecture is in general ill-suited for communication processing. Some of the common problems are: inability to do protocol processing, inefficient handling of data distribution, and poor management of the I/O. In this paper we present an I/O architecture that addresses these problems and supports high-speed network I/O on distributed-memory systems. The key to good performance is to partition the work appropriately between the system and the network interface. We perform some communication tasks on the distributed-memory parallel system since it is more powerful, and less likely to become a bottleneck than the network interface. Tasks that do not parallelize well are performed on the network interface and hardware support is provided for the most time-critical operations. We emphasize the use of simple I/O mechanisms that can be used by programming tools that map applications on the distributed-memory system to implement efficient I/O for the class of applications they support.This architecture has been implemented for the iWarp distributed-memory system. We describe this implementation and present performance results.
Software-extended coherent shared memory
Authors: Chaiken D. , Agarwal A.
Published: July 2004

This paper evaluates the tradeoffs involved in the design of the software-extended memory system of Alewife, a multiprocessor architecture that implements coherent shared memory through a combination of hardware and software mechanisms. For each block of memory, Alewife implements between zero and five coherence directory pointers in hardware and allows software to handle requests when the pointers are exhausted. The software includes a flexible coherence interface that facilitates protocol software implementation. This interface is indispensable for conducting experiments and has proven important for implementing enhancements to the basic system.Simulations of a number of applications running on a complete system (with up to 256 processors) demonstrate that the hybrid architecture with five pointers achieves between 71% and 100% of full-map directory performance at a constant cost per processing element. Our experience in designing the software protocol interfaces and experiments with a variety of system configurations lead to a detailed understanding of the interaction of the hardware and software components of the system. The results show that a small amount of shared memory hardware provides adequate performance: One-pointer systems reach between 42% and 100% of full-map performance on our parallel benchmarks. A software-only directory architecture with no hardware pointers has lower performance but minimal cost.
Optimal allocation of on-chip memory for multiple-API operating systems
Authors: Nagle D. , Uhlig R. , Mudge T. , Sechrest S.
Published: July 2004

The allocation of die area to different processor components is a central issue in the design of single-chip microprocessors. Chip area is occupied by both core execution logic, such as ALU and FPU datapaths, and memory structures, such as caches, TLBs, and write buffers. This work focuses on the allocation of die area to memory structures through a cost/benefit analysis. The cost of memory structures with different sizes and associativities is estimated by using an established area model for on-chip memory. The performance benefits of selecting a given structure are measured through a collection of methods including on-the-fly hardware monitoring, trace-driven simulation and kernel-based analysis. Special consideration is given to operating systems that support multiple application programming interfaces (APIs), a software trend that substantially affects on-chip memory allocation decisions.
Results:
Small adjustments in cache and TLB design parameters can significantly impact overall performance. Operating systems that support multiple APIs, such as Mach 3.0, increase the relative importance of on-chip instruction caches and TLBs when compared against single-APl systems such as Ultrix.
Distributed directory tags
Authors: Saha Avijit , Malik Nadeem
Published: July 2004

This paper concerns a new directory scheme that can be used as an alternative to the current three types of directory schemes; direct mapped, set associative and fully associative. Both direct mapped and fully associative cache directories can be considered as a special case of the set associative directory since in the direct mapped case there are N congruent classes with a set size of 1 while in the fully associative case there are N sets and only 1 congruent class. However, irrespective of which class of directory scheme is used, since memory or cache directories generally provide a many-to-one mapping of a large address space to a small fast storage, a tag field must be associated with each element to identify one of the many addresses which actually map to the current value in the cache element. Thus, there are as many tags as there are total elements in the directory. The Distributed Directory Tag scheme described here uses the direct mapping of the addresses and distribution of the tags over the directory elements and thereby reduces the storage requirement for the directory tags by a significant factor. Our early findings indicate that addresses from application programs follow a particular distribution, with a strong bias towards less frequent change in the higher order bits. It is this observation that is exploited in the scheme described in this paper. The actual savings depend on the particular distribution chosen for an implementation, but in general, a factor of three reduction can be obtained while providing a hit ratio comparable to the other directory schemes. This savings in the tag bits is achieved while still providing set associativity within each congruent class. This scheme is particularly useful when cost/performance tradeoffs are a consideration. Thus, this novel directory design adds another type to the three existing cache directory schemes.
HTGL
Authors: Beckmann Carl J.
Published: July 2004

This paper describes an abstract language called HTGL used to model the parallel structure and behavior of programs. These abstract models can be used as input to simulators and analysis tools for more accurate simulation than analytic or queueing models, without the unnecessary burden of compiling actual programs. It can also be used as a rapid software prototyping tool, for easily measuring the inherent parallelism in a parallel algorithm prior to actual coding, or for implementing certain compiler optimizations on the simplified data structures of the abstract language. Source code is publicly available and includes a reusable software library.
On structured data handling in parallel processing
Authors: Lafitte Jean-Louis
Published: July 2004

The model we have developed at Université de Genève allows one to handle irregular data in parallel processing. It achieves much smoother data-driven parallel processing allowing far less discontinuities of the well-known pipeline "bubbles" type. This model is presented, along with some pre-liminary results.
μ-EP-1
Authors: Ulmann B.
Published: July 2004

This article describes a very simple but quite powerful 32-bit architecture ideally suited for experimental and educational purposes in computer architecture design. It employs a very orthogonal instruction set in conjunction with 16 general purpose registers and a simple interrupt capability. It was developed at the University of Mainz, Germany and a prototype using standard TTL-circuits is being developed --- large parts of the microcode are written and simple assembler and an emulator written in FORTRAN already exists.
The unconventional replacement algorithms
Authors: Khalid Humayun
Published: July 2004

This work proposes several new schemes for the replacement of cache lines/blocks in high performance computer systems. Our algorithms rely on judiciously chosen neural networks for accurate real-time statistical predictions. These algorithms, therefore, provide better cache performance as compared to the conventional LRU (Least Recently Used) algorithm. Simulation results indicate that the proposed set of replacement strategies can provide a performance improvement of as much as 16.4711% over the LRU algorithm for our selected benchmark trace files. The results are based on an experimentation involving 6 neural network paradigms and 21 different cache configurations. Excellent performance of the neural network-based replacement strategies means that this new approach can be studied as an alternative to the existing page replacement and prefetching algorithms in virtual memory systems.
Truth in SPEC benchmarks
Authors: Mirghafori Nikki , Jacoby Margret , Patterson David
Published: July 2004

The System Performance Evaluation Cooperative (SPEC) benchmarks are a set of integer and floating-point programs that are intended to be “effective and fair in comparing the performance of high performance computing systems”. SPEC ratings are often quoted in company advertising and have been trusted as the de facto measure of comparison for computer systems. Recently, there has been some concern regarding the
fairness
and the
value
of these benchmarks for comparing computer systems.

In this paper we investigate the following two questions regarding the SPEC92 benchmark suite: 1) How sensitive are the SPEC ratings to various tunings? 2) How reproducible are the published results? For six vendors, we compare the published SPECpeak and SPECbase ratings, and observe an 11% average improvement in the SPECpeak ratings due to changes in the compiler flags alone. In our own attempt to reproduce the published SPEC ratings, we came across various “explicit” and “hidden” tuning parameters that we consider unrealistic. We suggest a new unit called
SPECsimple
that requires using only the -O compiler optimization flag, shared libraries, and standard system configuration. SPECsimple is designed to better match the performance experienced by a typical user. Our measured SPECsimples are 65-86% of the advertised SPECpeak performance. We conclude this paper by citing cases compiler optimizations specifically designed for SPEC programs, in which performance decreases drastically or the computed results are incorrect if the compiled program does not
exactly
match the SPEC benchmark program. These findings show that the fairness and value of the popular SPEC benchmarks are questionable.
The MIT Alewife machine
Authors: Agarwal Anant , Bianchini Ricardo , Chaiken David , Johnson Kirk L. , Kranz David , Kubiatowicz John , Lim Beng-Hong , Mackenzie Kenneth , Yeung Donald
Published: July 2004

Alewife is a multiprocessor architecture that supports up to 512 processing nodes connected over a scalable and cost-effective mesh network at a constant cost per node. The MIT Alewife machine, a prototype implementation of the architecture, demonstrates that a parallel system can be both scalable and programmable. Four mechanisms combine to achieve these goals: software-extended coherent shared memory provides a global, linear address space; integrated message passing allows compiler and operating system designers to provide efficient communication and synchronization; support for fine-grain computation allows many processors to cooperate on small problem sizes; and latency tolerance mechanisms --- including block multithreading and prefetching --- mask unavoidable delays due to communication.Microbenchmarks, together with over a dozen complete applications running on the 32-node prototype, help to analyze the behavior of the system. Analysis shows that integrating message passing with shared memory enables a cost-efficient solution to the cache coherence problem and provides a rich set of programming primitives. Block multithreading and prefetching improve performance by up to 25% individually, and 35% together. Finally, language constructs that allow programmers to express fine-grain synchronization can improve performance by over a factor of two.
Boosting the performance of hybrid snooping cache protocols
Authors: Dahlgren Fredrik
Published: July 2004

Previous studies of bus-based shared-memory multiprocessors have shown hybrid write-invalidate/write-update snooping protocols to be incapable of providing consistent performance improvements over write-invalidate protocols. In this paper, we analyze the deficiencies of hybrid snooping protocols under release consistency, and show how these deficiencies can be dramatically reduced by using write caches and read snarfing.Our performance evaluation is based on program-driven simulation and a set of five scientific applications with different sharing behaviors including migratory sharing as well us producer-consumer sharing. We show that a hybrid protocol, extended with write caches as well as read snarfing, manages to reduce the number of coherence misses by between 83% and 95% as compared to a write-invalidate protocol for all five applications in this study. In addition, the number of bus transactions is reduced by between 36% and 60% for four of the applications and by 9% for the fifth application. Because of the small implementation cost of the hybrid protocol and the two extensions, we believe that this combination is an effective approach to boost the performance of bus-based multiprocessors.
Unconstrained speculative execution with predicated state buffering
Authors: Ando Hideki , Nakanishi Chikako , Hara Tetsuya , Nakaya Masao
Published: July 2004

Speculative execution is execution of instructions before it is known whether these instructions should be executed. Compiler-based speculative execution has the potential to achieve both a high instruction per cycle rate and high clock rate. Pure compiler-based approaches, however, have greatly limited instruction scheduling due to a limited ability to handle side effects of speculative execution. Significant performance improvement is, thus, difficult in non-numerical applications. This paper proposes a new architectural mechanism, called predicating, which provides unconstrained speculative execution. Predicating removes restrictions which limit the compiler's ability to schedule instructions. Through our hardware support, the compiler is allowed to move instructions past multiple basic block boundaries from any succeeding control path. Predicating buffers the side effects of speculative execution with its predicate, and the buffered predicate efficiently commits or squashes the side effects. The mechanism also provides a speculative exception handling scheme. The scheme, called the future condition, properly postpones speculative exceptions and efficiently restarts the process. We show that our mechanism can be implemented through a modest amount of hardware with little complexity. The evaluation results show that our mechanism significantly improves performance, and achieves a 2.45x speedup over scalar machines.
Reducing TLB and memory overhead using online superpage promotion
Authors: Romer Theodore H. , Ohlrich Wayne H. , Karlin Anna R. , Bershad Brian N.
Published: July 2004

Modern microprocessors contain small TLBs that maintain a cache of recently used translations. A TLB's
coverage
is the sum of the number of bytes mapped by each entry. Applications with working sets larger than the TLB coverage will perform poorly due to high TLB miss rates. Superpages have been proposed as a mechanism for increasing TLB coverage. A
superpage
is a virtual memory page with size and alignment that are a power of two multiple of the system's base page size. In this paper, we describe online policies for superpage management that monitor TLB miss traffic to decide when a superpage should be constructed. Our policies take into account both the benefit of a superpage promotion (potential for preventing future misses) and the cost (page copying). Although our approach increases the cost of each TLB miss, the net effect is to improve total execution time by eliminating a large number of misses without significantly increasing memory usage, thereby improving system performance.
Speeding up irregular applications in shared-memory multiprocessors
Authors: Zhang Zheng , Torrellas Josep
Published: July 2004

While many parallel applications exhibit good spatial locality, other important codes in areas like graph problem-solving or CAD do not. Often, these irregular codes contain small records accessed via pointers. Consequently, while the former applications benefit from long cache lines, the latter prefer short lines. One good solution is to combine short lines with prefetching. In this way, each application can exploit the amount of spatial locality that it has. However, prefetching, if provided, should also work for the irregular codes. This paper presents a new prefetching scheme that, while usable by regular applications, is specifically targeted to irregular ones:
Memory Binding
and
Group Prefetching.
The idea is to hardware-bind and prefetch together groups of data that the programmer suggests are strongly related to each other. Examples are the different fields in a record or two records linked by a permanent pointer. This prefetching scheme, combined with short cache lines, results in a memory hierarchy design that can be exploited by both regular and irregular applications. Overall, it is better to use a system with short lines (16-32 bytes) and our prefetching than a system with long lines (128 bytes) with or without our prefetching. The former system runs 6 out of 7 Splash-class applications faster. In particular, some of the most irregular applications run 25-40% faster.
Configurable flow control mechanisms for fault-tolerant routing
Authors: Dao Binh Vien , Duato Jose , Yalamanchili Sudhakar
Published: July 2004

Fault-tolerant routing protocols in modern interconnection networks rely heavily on the network flow control mechanisms used. Optimistic flow control mechanisms such as wormhole routing (WR) realize very good performance, but are prone to deadlock in the presence of faults. Conservative flow control mechanisms such as pipelined circuit switching (PCS) insures existence of a path to the destination prior to message transmission, but incurs increased overhead. Existing fault-tolerant routing protocols are designed with one or the other, and must accommodate their associated constraints. This paper proposes the use of configurable flow control mechanisms. Routing protocols can then be designed such that in the vicinity of faults, protocols use a more conservative flow control mechanism, while the majority of messages that traverse fault-free portions of the network utilize a WR like flow control to maximize performance. Such protocols are referred to as two-phase protocols, where routing decisions are provided some control over the operation of the virtual channels. This ability provides new avenues for optimizing message passing performance in the presence of faults. A fully adaptive two-phase protocol is proposed and compared via simulation to those based on WR and PCS. The architecture of a network router supporting configurable flow control is described, and the paper concludes with avenues for future research.
A comparison of architectural support for messaging in the TMC CM-5 and the Cray T3D
Authors: Karamcheti Vijay , Chien Andrew A.
Published: July 2004

Programming models based on messaging continue to be an important programming model for parallel machines. Messaging costs are strongly influenced by a machine's network interface architecture. We examine the impact of architectural support for messaging in two machines --- the TMC CM-5 and the Cray T3D --- by exploring the design and performance of several messaging implementations. The additional features in the T3D support remote operations: memory access, fetch-and-increment, atomic swaps, and prefetch.Experiments on the CM-5 show that requiring processor involvement for message reception can increase the communication overheads from 60% to 300% for moderate variations in computation grain size at the destination. In contrast, the T3D hardware for remote operations decouples message reception from processor activity, producing high-performance messaging independent of computation grain size or variability.In addition, hardware support for a shared address space in the T3D can be used to solve the output contention problem (output hot spots), producing messaging implementations that are robust over a wide variety of traffic patterns. Atomic swap hardware can be used to build a distributed message queue, enabling a "pull" messaging scheme where the destination requests data transfer upon receive. This scheme uses prefetches to mask receive latency. While this yields performance robust over output contention, its base cost is competitive only for small messages (up to 64 bytes) because of the high cost of issuing and resolving prefetches in the T3D. Emulation shows that if the interaction costs can be reduced by a factor of eight (250ns to 31ns), perhaps by moving the prefetch queue on chip, and there is a corresponding increase in the prefetch queue size, the pull scheme can give superior performance in all eases.
Optimizing memory system performance for communication in parallel computers
Authors: Stricker T. , Gross T.
Published: July 2004

Communication in a parallel system frequently involves moving data from the memory of one node to the memory of another; this is the standard communication model employed in message passing systems. Depending on the application, we observe a variety of patterns as part of communication steps, e.g., regular (i.e. blocks of data), strided, or irregular (indexed) memory accesses. The effective speed of these communication steps is determined by the network bandwidth
and
the memory bandwidth, and measurements on current parallel supercomputers indicate that the performance is limited by the
memory bandwidth
rather than the
network bandwidth.
Current systems provide a wealth of options to perform communication, and a compiler or user is faced with the difficulty of finding the communication operations that best use the available memory and network bandwidth. This paper provides a framework to evaluate different solutions for inter-node communication and presents the
copy-transfer model;
this model captures the contributions of the memory system to inter-node communication. We demonstrate the usefulness of this simple model by applying it to two commercial parallel systems, the Cray T3D and the Intel Paragon.In particular we identify two methods to transfer data between nodes in these two machines. In
buffer-packing
transfers, a contiguous block of data is transferred across the network. If the data are not stored contiguously, they are copied to (gathering) or from (scattering) buffers in local memory before and after the transfer.
Chained
transfers perform gathering, transfer and scattering in one step, reading the data elements with some non-sequential pattern and immediately transferring them on to the destination.Our model and measurements indicate that chaining of the gather, transfer, and scatter operations results in better performance than buffer packing for many important access patterns. Most standard message passing libraries (like MPI, PVM or NX) force the parallelizing compiler (or the programmer) to employ the buffer-packing communication operations. However, the addition of hardware support dedicated to communication (e.g., DMAs, line-transfer units) now gives the compiler a wider range of options.
Instruction fetching
Authors: Uhlig Richard , Nagle David , Mudge Trevor , Sechrest Stuart , Emer Joel
Published: July 2004

Previous research has shown that the SPEC benchmarks achieve low miss ratios in relatively small instruction caches. This paper presents evidence that current software-development practices produce applications that exhibit substantially higher instruction-cache miss ratios than do the SPEC benchmarks. To represent these trends, we have assembled a collection of applications, called the Instruction Benchmark Suite (IBS), that provides a better test of instruction-cache performance. We discuss the rationale behind the design of IBS and characterize its behavior relative to the SPEC benchmark suite. Our analysis is based on trace-driven and trap-driven simulations and takes into full account both the application and operating-system components of the workloads.This paper then reexamines a collection of previously-proposed hardware mechanisms for improving instruction-fetch performance in the context of the IBS workloads. We study the impact of cache organization, transfer bandwidth, prefetching, and pipelined memory systems on machines that rely on the use of relatively small primary instruction caches to facilitate increased clock rates. We find that, although of little use for SPEC, the right combination of these techniques substantially benefits IBS. Even so, under IBS, a stubborn lower bound on the instruction-fetch CPI remains as an obstacle to improving overall processor performance.
A compiler optimization to reduce execution time of loop nest
Authors: Kwon Oh-Young , Park Gi-Ho , Han Tack-Don
Published: July 2004

In this paper, a compiler optimization to reduce the execution time of loop nest is proposed. Loop tiling is used to optimize loop nest. Loop tiling is the well-known optimization for improving locality. However, it has a count result that increases the number of instructions to loop control. These increased instructions disturb the effect of locality optimization. Therefore, the tiling of innermost loop is not perform in order to reduce the instructions for loop control in this paper. This optimization consists of two steps. In the first step, loop permutation is used to maximize the spatial reuse of innermost loop. Because innermost loop tiling is not performed, spatial reuse of innermost loop is exploited to reduce execution time of loop nest. In the second step, the tile size of outer loops is decided using the basic cache parameters. When this optimization is applied to the matrix multiplication, execution time is improved 3 to 4 fold. Also, this optimization technique is easily applied to make a parallelizing and/or optimizing compilers.
Decoupled hardware support for distributed shared memory
Authors: Reinhardt Steven K. , Pfile Robert W. , Wood David A.
Published: July 2004

This paper investigates hardware support for fine-grain distributed shared memory (DSM) in networks of workstations. To reduce design time and implementation cost relative to dedicated DSM systems, we decouple the functional hardware components of DSM support, allowing greater use of off-the-shelf devices.We present two decoupled systems, Typhoon-0 and Typhoon-1. Typhoon-0 uses an off-the-shelf protocol processor and network interface; a custom access control device is the only DSM-specific hardware. To demonstrate the feasibility and simplicity of this access control device, we designed and built an FPGA-based version in under one year. Typhoon-1 also uses an off-the-shelf protocol processor, but integrates the network interface and access control devices for higher performance.We compare the performance of the two decoupled systems with two integrated systems via simulation. For six benchmarks on 32 nodes, Typhoon-0 ranges from 30% to 309% slower than the best integrated system, while Typhoon-1 ranges from 13% to 132% slower. Four of the six benchmarks achieve speedups of 12 to 18 on Typhoon-0 and 15 to 26 on Typhoon-1, compared with 19 to 35 on the best integrated system. Two benchmarks are hampered by high communication overheads, but selectively replacing shared-memory operations with message passing provides speedups of at least 16 on both decoupled systems. These speedups indicate that decoupled designs can potentially provide a cost-effective alternative to complex high-end DSM systems.
COMA
Authors: Morin Christine , Gefflaut Alain , Banâtre Michel , Kermarrec Anne-Marie
Published: July 2004

Due to the increasing number of their components, Scalable Shared Memory Multiprocessors (SSMMs) have a very high probability of experiencing failures. Tolerating node failures therefore becomes very important for these architectures particularly if they must be used for long-running computations. In this paper, we show that the class of Cache Only Memory Architectures (COMA) are good candidates for building fault-tolerant SSMMs. A backward error recovery strategy can be implemented without significant hardware modification to previously proposed COMA by exploiting their standard replication mechanisms and extending the coherence protocol to transparently manage recovery data. Evaluation of the proposed fault-tolerant COMA is based on execution driven simulations using some of the Splash applications. We show that, for the simulated architecture, the performance degradation caused by fault-tolerance mechanisms varies from 5% in the best case to 35% in the worst case. The standard memory behavior is only slightly perturbed. Moreover, results also show that the proposed scheme preserves the architecture scalability and that the memory overhead remains low for parallel applications using mostly shared data.
Evaluation of design alternatives for a multiprocessor microprocessor
Authors: Nayfeh Basem A. , Hammond Lance , Olukotun Kunle
Published: July 2004

In the future, advanced integrated circuit processing and packaging technology will allow for several design options for multiprocessor microprocessors. In this paper we consider three architectures: shared-primary cache, shared-secondary cache, and shared-memory. We evaluate these three architectures using a complete system simulation environment which models the CPU, memory hierarchy and I/O devices in sufficient detail to boot and run a commercial operating system. Within our simulation environment, we measure performance using representative hand and compiler generated parallel applications, and a multiprogramming workload. Our results show that when applications exhibit fine-grained sharing, both shared-primary and shared-secondary architectures perform similarly when the full costs of sharing the primary cache are included.
Don't use the page number, but a pointer to it
Authors: Seznec André
Published: July 2004

Most newly announced high performance microprocessors support 64-bit virtual addresses and the width of physical addresses is also growing. As a result, the size of the address tags in the L1 cache is increasing. The impact of on chip area is particularly dramatic when small block sizes are used. At the same time, the performance of high performance microprocessors depends more and more on the accuracy of branch prediction and for reasons similar to those in the case of caches the size of the Branch Target Buffer is also increasing linearly with the address width.In this paper, we apply the simple principle stated in the title for limiting the tag size of on-chip caches. In the resulting indirect-tagged cache, the duplication of the page number in processors (in TLB and in cache tags) is removed. The tag check is then simplified and the tag cost does not depend on the address width. Applying the same principle to Branch Target Buffers, we propose the Reduced Branch Target Buffer. The storage size in a Reduced Branch Target Buffer does not depend on the address width and is dramatically smaller than the size of the conventional implementation of a Branch Target Buffer.
Understanding application performance on shared virtual memory systems
Authors: Iftode Liviu , Singh Jaswinder Pal , Li Kai
Published: July 2004

Many researchers have proposed interesting protocols for shared virtual memory (SVM) systems, and demonstrated performance improvements on parallel programs. However, there is still no clear understanding of the performance potential of SVM systems for different classes of applications. This paper begins to fill this gap, by studying the performance of a range of applications in detail and understanding it in light of application characteristics.We first develop a brief classification of the inherent data sharing patterns in the applications, and how they interact with system granularities to yield the communication patterns relevant to SVM systems. We then use detailed simulation to compare the performance of two SVM approaches---Lazy Released Consistency (LRC) and Automatic Update Release Consistency (AURC)---with each other and with an all-hardware CC-NUMA approach. We examine how performance is affected by problem size, machine size, key system parameters, and the use of less optimized program implementations. We find that SVM can indeed perform quite well for systems of at leant up to 32 processors for several nontrivial applications. However, performance is much more variable across applications than on CC-NUMA systems, and the problem sizes needed to obtain good parallel performance are substantially larger. The hardware-assisted AURC system tends to perform significantly better than the all-software LRC under our system assumptions, particularly when realistic cache hierarchies are used.
Exploiting choice
Authors: Tullsen Dean M. , Eggers Susan J. , Emer Joel S. , Levy Henry M. , Lo Jack L. , Stamm Rebecca L.
Published: July 2004

Simultaneous multithreading is a technique that permits multiple independent threads to issue multiple instructions each cycle. In previous work we demonstrated the performance potential of simultaneous multithreading, based on a somewhat idealized model. In this paper we show that the throughput gains from simultaneous multithreading can be achieved
without
extensive changes to a conventional wide-issue superscalar, either in hardware structures or sizes. We present an architecture for simultaneous multithreading that achieves three goals: (1) it minimizes the architectural impact on the conventional superscalar design, (2) it has minimal performance impact on a single thread executing alone, and (3) it achieves significant throughput gains when running multiple threads. Our simultaneous multithreading architecture achieves a throughput of 5.4 instructions per cycle, a 2.5-fold improvement over an unmodified superscalar with similar hardware resources. This speedup is enhanced by an advantage of multithreading previously unexploited in other architectures: the ability to favor for fetch and issue those threads most efficiently using the processor each cycle, thereby providing the "best" instructions to the processor.