bluuebunny/crossref_metadata_2025_split huggingface dataset:
Interleaved parallel schemes
Authors: Seznec André , Lenfant Jacques 
Published: July 2004

On many commercial supercomputers, several vector register processors share a global highly interleaved memory in a MIMD mode. When all the processors are working on a single vector loop, a significant part of the potential memory throughput may be wasted due to the asynchronism of the processors.
In order to limit this loss of memory throughput, a SIMD synchronization mode for vector accesses to memory may be used. But an important part of the memory bandwidth may be wasted when accessing vectors with an even stride.
In this paper, we present IPS, an interleaved parallel scheme, which ensures an equitable distribution of elements on a highly interleaved memory for a wide range a vector strides. We show how to organize access to memory, such that unscrambling of vectors from memory to the vector register processors requires a minimum number of passes through the interconnection network.
Low-latency message communication support for the AP1000
Authors: Shimizu Toshiyuki , Horie Takeshi , Ishihata Hiroaki 
Published: July 2004

Low-latency communication is the key to achieving a high-performance parallel computer. In using state-of-the-art processors, we must take cache memory into account. This paper presents an architecture for low-latency message comunication and implementation, and performance evaluation.
We developed a message controller (MSC) to support low-latency message passing communication for the AP1000, to minimize message handling overhead. MSC sends messages directly from cache memory and automatically receives messages in the circular buffer. We designed communication functions between cells and evaluated communication performance by running benchmark programs such as the Pingpong benchmark, the LINPACK benchmark, the SLALOM benchmark, and a solver using the scaled conjugate gradient method.
Monitoring program behaviour on SUPRENUM
Authors: Siegle Markus , Hofmann Richard 
Published: July 2004

It is often very difficult for programmers of parallel computers to understand how their parallel programs behave at execution time, because there is not enough insight into the interactions between concurrent activities in the parallel machine. Programmers do not only wish to obtain statistical information that can be supplied by profiling, for example. They need to have detailed knowledge about the functional behaviour of their programs. Considering performance aspects, they need timing information as well. Monitoring is a technique well suited to obtain information about both functional behaviour and timing. Global time information is essential for determining the chronological order of events on different nodes of a multiprocessor or of a distributed system, and for determining the duration of time intervals between events from different nodes. A major problem on multiprocessors is the absence of a global clock with high resolution. This problem can be overcome if a monitor system capable of supplying globally valid time stamps is used.
In this paper, the behaviour and performance of a parallel program on the SUPRENUM multiprocessor is studied. The method used for gaining insight into the runtime behaviour of a parallel program is hybrid monitoring, a technique that combines advantages of both software monitoring and hardware monitoring. A novel interface makes it possible to measure program activities on SUPRENUM. The SUPRENUM system and the ZM4 hardware monitor are briefly described. The example program under study is a parallel ray tracer. We show that hybrid monitoring is an excellent method to provide programmers with valuable information for debugging and tuning of parallel programs.
Dynamic dependency analysis of ordinary programs
Authors: Austin Todd M. , Sohi Gurindar S. 
Published: July 2004

A quantitative analysis of program execution is essential to the computer architecture design process. With the current trend in architecture of enhancing the performance of uniprocessors by exploiting fine-grain parallelism, first-order metrics of program execution, such as operation frequencies, are not sufficient; characterizing the exact nature of dependencies between operations is essential.
This paper presents a methodology for constructing the dynamic execution graph that characterizes the execution of an ordinary program (an application program written in an imperatibve language such as C or FORTRAN) from a serial execution trace of the program. It then uses the methodology to study parallelism in the SPEC benchmarks. We see that the prallelism can be bursty in nature (periods of lots of parallelism followed by periods of little parallelism), but the average parallelism is quite high, ranging from 13 to 23,302 operations per cycle. Exposing this parallelism requires renaming of both registers and memory, though renaming registers alone exposes much of this parallelism. We also see that fairly large windows of dynamic instructions would be required to expose this parallelism from a sequential instruction stream.
Performance of the SCI ring
Authors: Scott Steven L. , Goodman James R. , Vernon Mary K. 
Published: July 2004

The Scalable Coherent Interface (SCI) is an emerging IEEE standard that provides computer-bus-like services to a set of nodes via fast, unidirectional links. This paper presents the first detailed performance study of the SCI ring, using both analytical models and simulation. Performance is analyzed for uniform and nonuniform traffic, and the effect of the ring's flow control protocol is studied.
The queueing model is based on an M/G/1 queue, augmented to include the effect of packet trains on the mean and variance of the source transmission time. The model is validated against simulation results, and shown to be quantitatively accurate for uniform workloads, and at least qualitatively accurate for nonuniform workloads. The flow control mechanism is shown to effectively prevent node starvation and reduce the ability of nodes to unfairly consume ring bandwidth, but at the cost of decreased overall ring utilization. The SCI ring is also compared to a standard bus, modeled with a simple M/G/1 queue, and shown to provide substantially higher throughputs and lower latency than a bus with realistic clock speeds.
Performance evaluation of disk subsystems
Authors: Yomtov Ruben 
Published: July 2004

Mainframe Central Processor Unit (CPU) speed/performance has increased by more than two orders of magnitude since the 1970's. However, the I/O subsystem performance has only quadrupled in the same period of time. There is a need for a computer architecture with an effective storage hierarchy to complement improvements made in the CPU performance.
This paper presents a technique to calculate the I/O performance of disk subsystems with and without disk cache buffers. Through a series of calculation it is shown that the best way to improve I/O performance is to increase the number of data paths and use disk memory caching.
Performance evaluation for various configuration of superscalar processors
Authors: Inoue Atsushi , Takeda Kenji 
Published: July 2004

We present evaluation results on configuration of superscalar processors. We have developed tools for evaluating superscalar processors, which consists of an optimizing compiler and a configurable simulator. These tools can accept architectural parameters which characterize the configuration of target superscalar processors. We can estimate the most optimal performance of each configuration, as the compiler extracts the parallelism in application programs maximally and the execution on the simulator reflects the actual behavior of the target processor. By comparing exectution results on various configuration of processors, we can observe the effect of each architectural parameter and get optimal configuration of superscalar processor.
We have evaluated the performance varying the following specification of superscalar processors; (1) The number of instructions the processor can issue maximally on each cycle (2) The number of functional units and memory ports (3) Latency of instructions. The results show that four instruction issue per cycle attains enough performance and the integer unit should have two ALUs and two memory ports for most integer programs tested here. For floating point programs, if programs are highly optimized, reducing instruction latency is more effective than having more functional units, in order to enhance the performance of superscalar processors.
Computing size-independent matrix problems on systolic array processors
Authors: Navarro J. J. , Llaberia J. M. , Valero M. 
Published: July 2004

A methodology to transform dense to band matrices is presented in this paper. This transformation, is accomplished by triangular blocks partitioning, and allows the implementation of solutions to problems with any given size, by means of contraflow systolic arrays, originally proposed by H.T. Kung. Matrix-vector and matrix-matrix multiplications are the operations considered here.
The proposed transformations allow the optimal utilization of processing elements (PEs) of the systolic array when dense matrix are operated. Every computation is made inside the array by using adequate feedback. The feedback delay time depends only on the systolic array size.
Software-controlled caches in the VMP multiprocessor
Authors: Cheriton D. R. , Slavenburg G. A. , Boyle P. D. 
Published: July 2004

VMP is an experimental multiprocessor that follows the familiar basic design of multiple processors, each with a cache, connected by a shared bus to global memory. Each processor has a synchronous, virtually addressed, single master connection to its cache, providing very high memory bandwidth. An unusually large cache page size and fast sequential memory copy hardware make it feasible for cache misses to be handled in software, analogously to the handling of virtual memory page faults. Hardware support for cache consistency is limited to a simple state machine that monitors the bus and interrupts the processor when a cache consistency action is required.
In this paper, we show how the VMP design provides the high memory bandwidth required by modern high-performance processors with a minimum of hardware complexity and cost. We also describe simple solutions to the consistency problems associated with virtually addressed caches. Simulation results indicate that the design achieves good performance providing data contention is not excessive.
Optimal pipelining in supercomputers
Authors: Kunkel S. R. , Smith J. E. 
Published: July 2004

This paper examines the relationship between the degree of central processor pipelining and performance. This relationship is studied in the context of modern supercomputers. Limitations due to instruction dependencies are studied via simulations of the CRAY-1S. Both scalar and vector code are studied. This study shows that instruction dependencies severely limit performance for scalar code as well as overall performance.
The effects of latch overhead are then considered. The primary cause of latch overhead is the difference between maximum and minimum gate propagation delays. This causes both the skewing of data as it passes along the data path, and unintentional clock skewing due to clock fanout logic. Latch overhead is studied analytically in order to lower bound the clock period that may be used in a pipelined system. This analysis also touches on other points related to latch clocking. This analysis shows that for short pipeline segments both the Earle latch and polarity hold latch give the same clock period bound for both single-phase and multi-phase clocks. Overhead due to data skew and unintentional clock skew are each added to the CRAY-1S simulation model. Simulation results with realistic assumptions show that eight to ten gate levels per pipeline segment lead to optimal overall performance. The results also show that for short pipeline segments data skew and clock skew contribute about equally to the degradation in performance.
Working sets, cache sizes, and node granularity issues for large-scale multiprocessors
Authors: Rothberg Edward , Singh Jaswinder Pal , Gupta Anoop 
Published: July 2004

The distribution of resources among processors, memory and caches is a crucial question faced by designers of large-scale parallel machines. If a machine is to solve problems with a certain data set size, should it be built with a large number of processors each with a small amount of memory, or a smaller number of processors each with a large amount of memory? How much cache memory should be provided per processor for cost-effectiveness? And how do these decisions change as larger problems are run on larger machines?
In this paper, we explore the above questions based on the characteristics of five important classes of large-scale parallel scientific applications. We first show that all the applications have a hierarchy of well-defined per-processor working sets, whose size, performance impact and scaling characteristics can help determine how large different levels of a multiprocessor's cache hierarchy should be. Then, we use these working sets together with certain other important characteristics of the applications—such as communication to computation ratios, concurrency, and load balancing behavior—to reflect upon the broader question of the granularity of processing nodes in high-performance multiprocessors.
We find that very small caches whose sizes do not increase with the problem or machine size are adequate for all but two of the application classes. Even in the two exceptions, the working sets scale quite slowly with problem size, and the cache sizes needed for problems that will be run in the foreseeable future are small. We also find that relatively fine-grained machines, with large numbers of processors and quite small amounts of memory per processor, are appropriate for all the applications.
Design tradeoffs for software-managed TLBs
Authors: Nagle David , Uhlig Richard , Stanley Tim , Sechrest Stuart , Mudge Trevor , Brown Richard 
Published: July 2004

An increasing number of architectures provide virtual memory support through software-managed TLBs. However, software management can impose considerable penalties, which are highly dependent on the operating system's structure and its use of virtual memory. This work explores software-managed TLB design tradeoffs and their interaction with a range of operating systems including monolithic and microkernel designs. Through hardware monitoring and simulations, we explore TLB performance for benchmarks running on a MIPS R2000-based workstation running Ultrix, OSF/1, and three versions of mach 3.0.
Results: New operating systems are changing the relative frequency of different types of TLB misses, some of which may not be efficiently handled by current architectures. For the same application binaries, total TLB service time varies by as much as an order of magnitude under different operating systems. Reducing the handling cost for kernel TLB misses reduces total TLB service time up to 40%. For TLBs between 32 and 128 slots, each doubling of the TLB size reduces total TLB service time up to 50%.
Architectural support for translation table management in large address space machines
Authors: Huck Jerry , Hays Jim 
Published: July 2004

Virtual memory page translation tables provide mappings from virtual to physical addresses. When the hardware controlled Translation Lookaside Buffers (TLBs) do not contain a translation, these tables provide the translation. Approaches to the structure and management of these tables vary from full hardware implementations to complete software based algorithms.
The size of the virtual address space used by processes is rapidly growing beyond 32 bits of address. As the utilized address space increases, new problems and issues surface. Traditional methods for managing the page translation tables are inappropriate for large address space architectures.
The Hashed Page Table (HPT), described here, provides a very fast and space efficient translation table that reduces overhead by splitting TLB management responsibilities between hardware and software. Measurements demonstrate its applicability to a diverse range of operating systems and workloads and, in particular, to large virtual address space machines. In simulations of over 4 billion instructions, improvement of 5 to 10% were observed.
An adaptive cache coherence protocol optimized for migratory sharing
Authors: Stenström Per , Brorsson Mats , Sandberg Lars 
Published: July 2004

Parallel programs that use critical sections and are executed on a shared-memory multiprocessor with a write-invalidate protocol result in invalidation actions that could be eliminated. For this type of sharing, called migratory sharing, each processor typically causes a cache miss followed by an invalidation request which could be merged with the preceding cache-miss request.
In this paper we propose an adaptive protocol that invokes this optimization dynamically for migratory blocks. For other blocks, the protocol works as an ordinary write-invalidate protocol. We show that the protocol is a simple extension to a write-invalidate protocol.
Based on a program-driven simulation model of an architecture similar to the Stanford DASH, and a set of four benchmarks, we evaluate the potential performance improvements of the protocol. We find that it effectively eliminates most single invalidations which improves the performance by reducing the shared access penalty and the network traffic.
Multiple threads in cyclic register windows
Authors: Hidaka Yasuo , Koike Hanpei , Tanaka Hidehiko 
Published: July 2004

Multi-threading is often used to compile logic and functional languages, and implement parallel C libraries. Fine-grain multi-threading requires rapid context switching, which can be slow on architectures with register windows. In past, researchers have either proposed new hardware support for dynamic allocation of windows to threads, or have sacrificed fast procedure calls by fixed allocation of windows to threads.
In this paper, a novel window management algorithm, which retains both fast procedure calls and fast context switching, is proposed. The algorithm has been implemented on the SPARC processor by modifying window trap handlers. A quantitative evaluation of the scheme using a multi-threaded application with various concurrency and granularity levels is given. The evaluation shows that the proposed scheme always does better than the other schemes. Some implications for multi-threaded architectures are also presented.
16-bit vs. 32-bit instructions for pipelined microprocessors
Authors: Bunda John , Fussell Don , Athas W. C. , Jenevein Roy 
Published: July 2004

In any stored-program computer system, information is constantly transferred between the memory and the instruction processor. Machine instructions are a major portion of this traffic. Since transfer bandwidth is a limited resource, inefficiency in the encoding of instruction information (low code density) can have definite hardware and performance costs.
Starting with a parameterized baseline RISC design, we compare performance for two instruction encodings for the same instruction processing core. One is a variant of DLX, a typical 32-bit RISC instruction set. The other is a 16-bit format which sacrifices some expressive power while retaining essential RISC features. Using optimizing compilers and software simulation, we measure code density and path length for a suite of benchmark programs, relating performance differences to specific instruction set features. We measure time to completion performance while varying memory latency and instruction cache size parameters. The 16-bit format is shown to have significant cost-performance advantages over the 32-bit format under typical memory system performance constraints.
Vector prefetching
Authors: Gschwind Michael K. , Pietsch Thomas J. 
Published: July 2004

This paper focuses on extending the memory subsystem by integrating a prefetch buffer mechanism. Prefetching allows high-level application knowledge to increase memory performance, which is currently constraining the performance of most system. While prefetching does not reduce the latency of memory accesses, it hides this latency by overlapping memory access and instruction execution.
The first prefetch operation to the buffer is initiated by an explicit fetch instruction. All further prefetch operations are issued automatically whenever a prefetched value is consumed. To efficiently support list and vector processing, the user can specify a stride value at the time the first prefetch operation is initiated.
Supercomputer-based visualization systems used for analyzing output data of a numerical weather prediction model
Authors: Chen Philip C. 
Published: July 2004

Comparison of two supercomputer-based visualization systems developed over a half-year period show that the visualization/animation efficiency is largely dependent upon the efficiencies of individual computers, networking, and memory management.
Using a meteorological database, a case study is presented to illustrate a selection of parameters based on physical laws. Then, three-dimensional animations of selected parameters are made and used for investigating the evolutions of winter cyclone systems. The results indicate an animation with combined parameters that are physically related and reveal important cyclonic development mechanisms that could not have been seen by an animation with an individual parameter.
Pandore
Authors: André Françoise , Pazat Jean-Louis , Thomas Henry 
Published: July 2004

The goal of the Pandore system is to allow the execution of parallel algorithms on DMPCs (Distributed Memory Parallel Computers) without having to take into account the low-level characteristics of the target distributed computer to program the algorithm. No explicit process definition and interprocess communications are needed. Parallelization is achieved through logical data organization. The Pandore system provides the user with a mean to specify data partitioning and data distribution over a domain of virtual processors for each parallel step of his algorithm.
At compile time, Pandore splits the original program into parallel processes. Each process will execute some appropriate parts of the original code, according to the given data decomposition. In order to achieve a correct utilization of the data structures distributed over the processors, the Pandore system provides an execution scheme based on a communication layer, which is an abstraction of a message-passing architecture. This intermediate level is them implemented using the effective primitives of the real architecture (in our specific case, an Intel iPSC/2).
Access conflicts in multiprocessor memories queueing models and simulation studies
Authors: Bucher Ingrid Y. , Calahan Donald A. 
Published: July 2004

The performance of an interleaved common memory accessed uniformly by multiple processors is modeled by queueing methods. The model includes access conflicts at the bank level while assuming an ideal access network.
A scaling relation is derived that is generally valid and indicates that memory access delays are given by the product of the bank reservation time and a function of the memory utilization, which is given by the average number of access requests arriving at a bank per bank reservation time. For light memory traffic, access delays are proportional to the square of the bank reservation time and the ratio of the number of active memory access streams to the number of memory banks.
Assuming random access patterns, an open and a closed queueing model are developed that are validated by simulations. Delay dependence on bank reservation time is quadratic for light loads and linear for very heavy loads.
A heuristic extension of our model for vector accessing of banks in sequential mode is proposed.