bluuebunny/crossref_metadata_2025 huggingface dataset:
Prefetch unit for vector operations on scalar computers (abstract)
Authors: Sklenar Ivan
Published: July 2004

Current caches are not adequate for vector operations. A new kind of support for vector operations, called prefetch unit, is designed to improve the performance of the scalar (SISD) processors. The prefetch unit can be used for any SISD architecutre and also for many kinds of MIMD architectures. It may run in parallel and asynchronously with other parts of processor. It keeps trace of the history of memory references, and initializes rarely any superfluous prefetches.
Enhancing boosting with semantic register in a superscalar processor (abstract)
Authors: Lai Feipei , Chang Meng-chou
Published: July 2004

IAS-S Supports boosting with “semantic register” and boosting boundary register to remove the dependences caused by conditional branches. In IAS-S, there is no dedicated shadow register file, and multiple levels of boosting is supported without multiple copies of register files. Any general-purpose register in IAS-S can be regarded as a sequential register or a shadow register flexibly. Furthermore, multi-way jump mechanism is combined with boosting to reduce the penalty due to frequent control transfers.
Data path issues in a highly concurrent machine (abstract)
Authors: Uht Augustus K. , Johnson Darin B.
Published: July 2004

It is desirable to achieve high read bandwidths for the processing elements of highly concurrent SISD computers, both while keeping the register and memory write bandwidths low, and while keeping the interconnection networks simple. Solutions to these problems are proposed, simulated, verified, and measured. New techniques called write elimination and write liberation are presented that also greatly reduce the complexity of the data cache. The elimination of addressable hardware registers is also achieved.
Memory management support for tiled array organization (abstract)
Authors: Newman Gary
Published: July 2004

A novel method is described which adds support for sub-array ordered (tiled) arrays to a conventional MMU. The resulting pages contain two dimensional tiles of data rather than one dimensional strips, making tiled virtual memory transparently available to general purpose application programs. The method is further extended to support sub-arrays with three or more dimensions. The image MMU of the Kodak Prophecy Color Publishing System is shown as a product implementation for color picture arrays.
Performance of multiple-bus multiprocssor under non-uniform memory reference model (abstract)
Authors: Sayeed M. A. , Atiquzzaman M.
Published: July 2004

Performance evaluation of multiple-bus multiprocessor systems is usually carried out under the assumption of uniform memory reference model. Hot spots arising in multiprocessor systems due to the use of shared variable, synchronization primitives etc., give rise to non-uniform memory reference patterns. The objective of this paper is to study the performance of multiple bus multiprocessor system in the presence of hot spots. Analytic expressions for the average memory bandwidth and probability of acceptance of prioritized processors have been derived. The results are validated by simulation results.
Seamless - a latency-tolerant RISC-based multiprocessor architecture (abstract)
Authors: Fineberg Samuel A. , Casavant Thomas L. , Pease Brent H.
Published: July 2004

The Seamless parallel system being developed at the University of Iowa ECE Department provides a method for providing latency tolerance in physically-distributed memory systems utilizing “off-the-shelf” RISC CPU's without incurring the overhead of multithreading. Seamless encompasses an evolutionary new programming model emphasizing data locality that views communication as data movement rather than message passing I/O. A hardware Locality Manager is added to each processing element to perform this data movement concurrently with computation.
Performance improvement for vector pipeline multiprocessor systems using a disordered execution model(abstract)
Authors: Kechadi M. Tahar , Dekeyser J-L. , Marquet Ph. , Preux Ph.
Published: July 2004

Memory contention may cause dramatic loss of performance in vector pipeline multiprocessor systems. To enhance memory performance, the disordered execution model aims at scheduling vector element accesses in order to avoid memory conflicts. This scheduling relies on memory bank activities at access issue time. A disordered pipeline execution is associated with disordered memory access in order to maintain the chaining of all processor functional units. An analytical model and simulations demonstrate the interest of this model.
Pipelining and bypassing in a VLIW processor (abstract)
Authors: Abnous Arthur , Bagherzadeh Nader
Published: July 2004

This paper describes issues involved in the bypassing mechanism for a VLIW processor and its relation to the pipeline structure of the processor. We will first describe the pipeline structure of our processor and analyze its performance and compare it to typical RISC-style pipeline structures given the context of a processor with multiple functional units. Next, we shall study the performance effects of various bypassing schemes in terms of their effectiveness in resolving pipeline data hazards and their effect on the processor cycle time.
Synthesis of application-specific heterogeneous multiprocessor systems (abstract)
Authors: Prakash Shiv , Parker Alice C.
Published: July 2004

Heterogeneous systems can achieve enhanced performance and/or cost-effectiveness over homogeneous systems. SOS, a formal method to synthesize optimal heterogeneous systems for given applications, involves creation and solution of a mixed integer-linear programming model. A primary component of the model is the set of relations to be satisfied to ensure proper ordering of various events in the task execution, and completeness and correctness. Experiments indicate SOS can be useful in designing heterogeneous systems.
Expanded delta networks for very large parallel computers
Authors: Alleyne Brian D. , Scherson Isaac D.
Published: July 2004

We analyze a generalization of the traditional delta network, dubbed
Expanded Delta Network
(EDN), which provides multiple paths that can be exploited to reduce contention. In massively parallel SIMD computers, the trend is to put a large number of processors on a chip, but due to I/O constraints only a subset of the processors may have access to the network at any time. This leads to the Restricted Access Expanded Delta Network of which the MasPar MP-1 router network is an example.
Directory-based cache coherency protocol for a ring-connected multiprocessor-array
Authors: Michael Wisam
Published: July 2004

The main goal of this paper is to demonstrate that a multiporcessor with very fast point-to-point interconnection can be 10 times faster than a bus-based one. In this work, we presented a two-dimensional ring-connected system where the processing-nodes are arranged in rows and columns and interconnected through horizontal and vertical unidirectional 64-bit links (similar to the Illiac 4). After presenting the architecture for the processing-nodes, the pipelined feature of the network and the cache-coherency protocol, we discussed some implementation issues for the system. Using trace-driven simulation, some performance results for the new system and for a bus-based two-dimensional system (similar to the Wisconsin multicube) were presented to show the superiority of using point-to point interconnections instead of buses.
Revisit the case for direct-mapped chaches
Authors: Wang Wen-Hann , Quinlan Jim , Lai Konrad
Published: July 2004

In this paper we argue that a two-way second-level cache is a better design choice than a direct-mapped organization. We show two-way caches are as simple to implement as direct-mapped caches. If the cache controller contains tags, the data array can be organized as a single bank of standard SRAM. Otherwise, both tags and data can be organized as a single SRAM bank. Our simulation results show these novel two-way organizations outperform the direct-mapped approach.
Integrated computer architecture development system
Authors: Burkhardt Walter H. , Rust Stefan
Published: July 2004

Development in systems architecture of separate soft-and hardware components introduces high inefficiencies, due to redundancies and seldom used functions on the levels of implementation. A better approach offers a methodology for an integrated software, firmware, and hardware design. Required are, however, immense computer resources with graphical capabilities. But it gives help in the development under constraints. We present such a system and show its capabilities in the development of a defect-free sorter module.
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.
Survey of commercial parallel machines
Authors: Ramanathan Gowri , Oren Joel
Published: July 2004

We have presented in this paper the survey of the parallel machines that are marketed today. The survey includes the latest machines available from Kendell Square Research, Thinking Machines Corporation, MasPar Computer Corporation, NCUBE Corporation, Sequent Computer Systems and Parsytec. We have provided the topology, architecture, cache coherence, synchronization and performance in MFLOPs for each of the machines subject to the availability of information.
Overview of the Vesta parallel file system
Authors: Corbett Peter F. , Baylor Sandra Johnson , Feitelson Dror G.
Published: July 2004

The Vesta parallel file system provides parallel access from compute nodes to files distributed across I/O nodes in a massively parallel computer. Vesta is intended to solve the I/O problems of massively parallel computers executing numerically intensive scientific applications. Vesta has three interesting characteristics: First, it provides a user defined parallel view of file data, and allows user defined partitioning and repartitioning of files without moving data among I/O nodes. The parallel file access semantics of Vesta directly support the operations required by parallel language I/O libraries. Second, Vesta is scalable to a very large number (many hundreds) of I/O and compute nodes and does not contain any sequential bottlenecks in the data-access path. Third, it provides user-directed checkpointing of files during continuing program execution with very little processing overhead.
A note on “Diagnosabilities of hypercubes under the pessimistic one-step diagnosis strategy”
Authors: Wang Dajin
Published: July 2004

We point out an unconsidered case in the proof for Theorem 3 in [4] and provide the proof for that case. To this end, a new property of
n
-hypercube is observed and made use of.
A model and an architecture for a relational knowledge base
Authors: Yokota H. , Itoh H.
Published: July 2004

A relational knowledge base model and an architecture which manipulates the model are presented. An item stored in the relational knowledge base is called a term. A unification operation on terms in the relational knowledge base is used as the retrieval mechanism. The relational knowledge base architecture we propose consists of a number of unification engines, several disk systems, a control processor, and a multiport page-memory. The system has a knowledge compiler to support a variety of knowledge representations.
Memory requirements for balanced computer architectures
Authors: Kung H. T.
Published: July 2004

One particular result is that to balance an array of
p
linearly connected PEs for performing matrix computations such as matrix multiplication and matrix triangularization, the size of each PE's local memory must grow linearly with
p
. Thus, the larger the array is, the larger each PE's local memory must be.
ATUM: a new technique for capturing address traces using microcode
Authors: Agarwal A. , Sites R. L. , Horowitz M.
Published: July 2004

Trace-driven simulation is often used in the design of computer systems, especially caches and translation lookaside buffers. Capturing address traces to drive such simulations has been problematic, often involving 1000:1 software overhead to trace a target workload, and/or mechanisms that cause significant distortions in the recorded data. A new technique for capturing address traces has been developed to use a processor's microcode to record addresses in a reserved part of main memory as a side effect of normal execution. An experimental implementation of this technique on a VAX
1
8200 processor shows a number of advantages over previous techniques, including fewer distortions of the address trace and a hundred times faster recording. With this technique, it is possible to gather full operating-system traces of multi-tasking workloads.
Exploiting parallelism in a switch-level simulation machine
Authors: Frank E. H.
Published: July 2004

The parallelism inherent in actual circuits suggests that this parallelism might be exploited in a switch-level simulation machine, in order to reduce total simulation time. This paper explores the extent to which this parallelism exists and the extent to which it can be exploited. The exploration is done in the context of a proposed multiprocessor simulation machine called the Fast-1. The Fast-1 is a form of data-flow machine in which switch-level circuits are represented as programs consisting of transistor and node instructions. In a multiprocessor Fast-1 these programs are partitioned onto one or more processors. Using a simulation of the Fast-1, experiments were performed using thirteen circuits, ranging in size from 78 to 20233 transistors. The most parallel circuit measured in these experiements potentially could be simulated almost 200 times faster on a multiprocessor than on a uniprocessor, assuming one instruction per processor and no-cost interprocessor communication. Using 64 processors, an atual speedup of 28 was achieved using contention-free interconnect, while a speedup of 12 was achieved when the 64 processors were connected by a broadcast bus for which they had to arbitrate.
A hardware accelerator for speech recognition algorithms
Authors: Anantharaman T. S. , Bisiani R.
Published: July 2004

This paper describes two custom architectures tailored to a speech recognition beam search algorithm. Both architectures have been simulated using real data and the results of the simulation are presented. The paper also describes the design process of the custom architectures and presents a number of ideas on the automatic design of custom systems for data dependent computations.
Modular architecture for high performance implementation of FFT algorithm
Authors: Sapiecha K. , Jarocki R.
Published: July 2004

The paper presents two new versions of the FFT algorithm. Based on these versions a new VLSI oriented architecture for implementing of the FFT algorithm is introduced. It consists of a homogenous structure of processing elements. The structure has a performance equal to 1/t
B
transforms per second, where t
B
is the time needed for execution of a single butterfly computation.

Besides high performance the architecture is modular and makes it possible to design a system which performs the DFT of any size with constant performance and without any extra circuitry. Moreover, the system can provide a built-in self test.
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.
HPSm, a high performance restricted data flow architecture having minimal functionality
Authors: Hwu W. , Patt Y. N.
Published: July 2004

Our recent work in microarchitecture has identified a new model of execution, restricted data flow, in which data flow techniques are used to coordinate out-of-order execution of sequential instruction streams. We believe that the restricted data flow model has great potential for implementing very high performance computing engines. This paper defines a minimal functionality variant of our model, which we are calling HPSm. The instruction set, data path, timing and control of HPSm are all described. A simulator for HPSm has been written, and some of the Berkeley RISC benchmarks have been executed on the simulator. We report the measurements obtained from these benchmarks, along with the measurements obtained for the Berkeley RISC II. The results are encouraging.
Scan line array processors for image computation
Authors: Fisher A. L.
Published: July 2004

This paper describes the scan line array processor (SLAP), a new architecture designed for high-performance yet low-cost image computation. A SLAP is a SIMD linear array of processors, and hence is easy to build and scales well with VLSI technology; yet appropriate special features and programming techniques make it efficient for a surprisingly wide variety of low and medium level computer vision tasks. We describe the basic SLAP concept and some of its variants, discuss a particular planned implementation, and indicate its performance on computer vision and other applications.
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.
Multiprocessor cache synchronization: issues, innovations, evolution
Authors: Bitar P. , Despain A. M.
Published: July 2004

Many options are possible in a cache synchronization (or consistency) scheme for a
broadcast
system. We clarify basic concepts, analyze the handling of shared data, and then describe a protocol that we are currently exploring. Finally, we analyze the evolution of options that have been proposed under
write-in
(or write-back) policy. We show how our protocol extends this evolution with new methods for efficient busy-wait locking, waiting, and unlocking. The
lock
scheme allows locking and unlocking to occur in zero time, eliminating the need for test-and-set. The scheme also integrates processor atomic read-modify-write instructions and programmer/compiler busy-wait-synchronized operations under the same mechanism. The
wait
scheme eliminates all unsuccessful retries from the bus, and allows a process to work while waiting.
Architectural requirements of parallel scientific applications with explicit communication
Authors: Cypher R. , Ho A. , Konstantinidou S. , Messina P.
Published: July 2004

This paper studies the behavior of scientific applications running on distributed memory parallel computers. Our goal is to quantify the floating point, memory, I/O and communication requirements of highly parallel scientific applications that perform explicit communication. In addition to quantifying these requirements for fixed problem sizes and numbers of processors, we develop analytical models for the effects of changing the problem size and the degree of parallelism for several of the applications. We use the results to evaluate the trade-offs in the design of multicomputer architectures.
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.
The architecture of a fault-tolerant cached RAID controller
Authors: Menon Jai , Cortney Jim
Published: July 2004

RAID-5 arrays need 4 disk accesses to update a data block—2 to read old data and parity, and 2 to write new data and parity. Schemes previously proposed to improve the update performance of such arrays are the Log-Structured File System [10] and the Floating Parity Approach [6]. Here, we consider a third approach, called Fast Write, which eliminates disk time from the host response time to a write, by using a Non-Volatile Cache in the disk array controller. We examine three alternatives for handling Fast Writes and describe a hierarchy of destage algorithms with increasing robustness to failures. These destage algorithms are compared against those that would be used by a disk controller employing mirroring. We show that array controllers require considerably more (2 to 3 times more) bus bandwidth and memory bandwidth than do disk controllers that employ mirroring. So, array controllers that use parity are likely to be more expensive than controllers that do mirroring, though mirroring is more expensive when both controllers and disks are considered.
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.
Register relocation
Authors: Waldspurger Carl A. , Weihl William E.
Published: July 2004

Multithreading is an important technique that improves processor utilization by allowing computation to be overlapped with the long latency operations that commonly occur in multiprocessor systems. This paper presents register relocation, a new mechanism that efficiently supports flexible partitioning of the register file into variable-size contexts with minimal hardware support. Since the number of registers required by thread contexts varies, this flexibility permits a better utilization of scarce registers, allowing more contexts to be resident, which in turn allows applications to tolerate shorter run lengths and longer latencies. Our experiments show that compared to fixed-size hardware contexts, register relocation can improve processor utilization by a factor of two for many workloads.
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.
Mechanisms for cooperative shared memory
Authors: Wood David A. , Chandra Satish , Falsafi Babak , Hill Mark D. , Larus James R. , Lebeck Alvin R. , Lewis James C. , Mukherjee Shubhendu S. , Palacharla Subbarao , Reinhardt Steven K.
Published: July 2004

This paper explores the complexity of implementing directory protocols by examining their
mechanisms
primitive operations on directories, caches, and network interfaces. We compare the following protocols:
Dir
1
B
,
Dir
4
B
,
Dir
4
NB
,
Dir
n
NB
[2],
Dir
1
SW
[9] and an improved version of
Dir
1
SW (
Dir
1
SW
+
). The comparison shows that the mechanisms and mechanism sequencing of
Dir
1
SW
and
Dir
1
SW
+
are simpler than those for other protocols.

We also compare protocol performance by running eight benchmarks on 32 processor systems. Simulations show that
Dir
1
SW
+
s performance is comparable to more complex directory protocols. The significant disparity in hardware complexity and the small difference in performance argue that
Dir
1
SW
+
may be a more effective use of resources. The small performance difference is attributable to two factors: the low degree of sharing in the benchmarks and Check- In/Check-Out (CICO) directives [9].
Cache write policies and performance
Authors: Jouppi Norman P.
Published: July 2004

This paper investigates issues involving writes and caches. First, tradeoffs on writes that miss in the cache are investigated. In particular, whether the missed cache block is fetched on a write miss, whether the missed cache block is allocated in the cache, and whether the cache line is written before hit or miss is known are considered. Depending on the combination of these polices chosen, the entire cache miss rate can vary by a factor of two on some applications. The combination of no-fetch-on-write and write-allocate can provide better performance than cache line allocation instructions. Second, tradeoffs between write-through and write-back caching when writes hit in a cache are considered. A mixture of these two alternatives, called
write caching
is proposed.
Write caching
places a small fully-associative cache behind a write-through cache. A write cache can eliminate almost as much write traffic as a write-back cache.
Hierarchical performance modeling with MACS
Authors: Boyd Eric L. , Davidson Edward S.
Published: July 2004

The MACS performance model introduced here can be applied to a Machine and Application of interest, the Compiler-generated workload, and the Scheduling of the workload by the compiler. The Ma, MAC, and MACS bounds each fix the named subset of M, A, C, and S while freeing the bound from the constraints imposed by the others. A/X performance measurement is used to measure access-only and execute-only code performance. Such hierarchical performance modeling exposes the gaps between the various bounds, the A/X measurements, and the actual performance, thereby focusing performance optimization at the appropriate levels in a systematic and goal-directed manner. A simple, but detailed, case study of the Convex C-240 vector mini-supercomputer illustrates the method.
The cedar system and an initial performance study
Authors: Kuck D. , Davidson E. , Lawrie D. , Sameh A. , Zhu C. Q. , Veidenbaum A. , Konicek J. , Yew P. , Gallivan K. , Jalby W. , Wijshoff H. , Bramley R. , Yang U. M. , Emrath P. , Padua D. , Eigenmann R. , Hoeflinger J. , Jaxon G. , Li Z. , Murphy T. , Andrews J.
Published: July 2004

In this paper, we give an overview of the Cedar multiprocessor and present recent performance results. These include the performance of some computational kernels and the Perfect Benchmarks. We also present a methodology for judging parallel system performance and apply this methodology to Cedar, Cray YMP-8, and Thinking Machines CM-5.
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.
Register connection
Authors: Kiyohara Tokuzo , Mahlke Scott , Chen William , Bringmann Roger , Hank Richard , Anik Sadun , Hwu Wen-Mei
Published: July 2004

Code optimization and scheduling for superscalar and superpipelined processors often increase the register requirement of programs. For existing instruction sets with a small to moderate number of registers, this increased register requirement can be a factor that limits the effectivess of the compiler. In this paper, we introduce a new architectural method for adding a set of extended registers into an architecture. Using a novel concept of connection, this method allows the data stored in the extended registers to be accessed by instructions that apparently reference core registers. Furthermore, we address the technical issues involved in applying the new method to an architecture: instruction set extension, procedure call convention, context switching considerations, upward compatibility, efficient implementation, compiler support, and performance. Experimental results based on a prototype compiler and execution driven simulation show that the proposed method can significantly improve the performance of superscalar processors with a small or moderate number of registers.
Limitations of cache prefetching on a bus-based multiprocessor
Authors: Tullsen Dean M. , Eggers Susan J.
Published: July 2004

Compiler-directed cache prefetching has the potential to hide much of the high memory latency seen by current and future high-performance processors. However, prefetching is not without costs, particularly on a multiprocessor. Prefetching can negatively affect bus utilization, overall cache miss rates, memory latencies and data sharing. We simulated the effects of a particular compiler-directed prefetching algorithm, running on a bus-based multiprocesssor. We showed that, despite a high memory latency, this architecture is not very well-suited for prefetching. For several variations on the architecture, speedups for five parallel programs were no greater than 39%, and degradations were as high as 7%, when prefetching was added to the workload. We examined the sources of cache misses, in light of several different prefetching strategies, and pinpointed the causes of the performance changes. Invalidation misses pose a particular problem for current compiler-directed prefetchers. We applied two techniques that reduced their impact: a special prefetching heuristic tailored to write-shared data, and restructuring shared data to reduce false sharing, thus allowing traditional prefetching algorithms to work well.
Transactional memory
Authors: Herlihy Maurice , Moss J. Eliot B.
Published: July 2004

A shared data structure is
lock-free
if its operations do not require mutual exclusion. If one process is interrupted in the middle of an operation, other processes will not be prevented from operating on that object. In highly concurrent systems, lock-free data structures avoid common problems associated with conventional locking techniques, including priority inversion, convoying, and difficulty of avoiding deadlock. This paper introduces
transactional memory
, a new multiprocessor architecture intended to make lock-free synchronization as efficient (and easy to use) as conventional techniques based on mutual exclusion. Transactional memory allows programmers to define customized read-modify-write operations that apply to multiple, independently-chosen words of memory. It is implemented by straightforward extensions to any multiprocessor cache-coherence protocol. Simulation results show that transactional memory matches or outperforms the best known locking techniques for simple benchmarks, even in the absence of priority inversion, convoying, and deadlock.
Evaluation of mechanisms for fine-grained parallel programs in the J-machine and the CM-5
Authors: Spertus Ellen , Goldstein Seth Copen , Schauser Klaus Erik , von Eicken Thorsten , Culler David E. , Dally William J.
Published: July 2004

This paper uses an abstract machine approach to compare the mechanisms of two parallel machines: the J-Machine and the CM-5. High-level parallel programs are translated by a single optimizing compiler to a fine-grained abstract parallel machine, TAM. A final compilation step is unique to each machine and optimizes for specifics of the architecture. By determining the cost of the primitives and weighting them by their dynamic frequency in parallel programs, we quantify the effectiveness of the following mechanisms individually and in combination. Efficient processor/network coupling proves valuable. Message dispatch is found to be less valuable without atomic operations that allow the scheduling levels to cooperate. Multiple hardware contexts are of small value when the contexts cooperate and the compiler can partition the register set. Tagged memory provides little gain. Finally, the performance of the overall system is strongly influenced by the performance of the memory system and the frequency of control operations.
The Chinese remainder theorem and the prime memory system
Authors: Gao Q. S.
Published: July 2004

As we know, the conflict problem is a very important problem in memory system of super computer, there are two kinds of conflict-free memory system approaches: skewing scheme approach and prime memory system approach. Previously published prime memory approaches are complex or wasting 1/p of the memory space for filling the “holes” [17], where p is the number of memory modules. In this paper, based on Chinese remainder theorem, we present a perfect prime memory system which only need to find the d Mod p without wasting any memory space and without computing the quotient.
A comparison of adaptive wormhole routing algorithms
Authors: Boppana Rajendra V. , Chalasani Suresh
Published: July 2004

Improvement of message latency and network utilization in torus interconnection networks by increasing adaptivity in wormhole routing algorithms is studied. A recently proposed partially adaptive algorithm and four new fully-adaptive routing algorithms are compared with the well-known e-cube algorithm for uniform, hotspot, and local traffic patterns. Our simulations indicate that the partially adaptive north-last algorithm, which causes unbalanced traffic in the network, performs worse than the nonadaptive e-cube routing algorithm for all three traffic patterns. Another result of our study is that the performance does not necessarily improve with full-adaptivity. In particular, a commonly discussed fully-adaptive routing algorithm, which uses 2
n
virtual channels per physical channel of a k-ary n-cube, performs worse than e-cube for uniform and hotspot traffic patterns. The other three fully-adaptive algorithms, which give priority to messages based on distances traveled, perform much better than the e-cube and partially-adaptive algorithms for all three traffic patterns. One of the conclusions of this study is that adaptivity, full or partial, is not necessarily a benefit in wormhole routing.
Microcoding an object-oriented instruction set
Authors: Harland David M , Beloff Bruno
Published: July 2004

Most AI applications are still written in LISP, but the recent growth of interest in object oriented programming has given rise to "shell" systems such as LOOPS and KEE, and, thereby, it has emphasised that there is now a need for an AI engine which will efficiently support an arbitrary number of object classes; it seems that it is no Longer sufficient simply to provide for Lists.This paper will demonstrate how the REKURSIV processor and its OBJEKT store can be microcoded to provide an object oriented instruction set like that defined by the SmallTalk-80 virtual machine, and that doing so can lead to an implementation which will run in excess of 250,000 bytecodes/second, a rate which is considerably faster than commerical SmallTalk systems.
Evaluating the memory overhead required for COMA architectures
Authors: Joe T. , Hennessy J. L.
Published: July 2004

Cache only memory architectures (COMA) have an inherent memory overhead due to the organization of main memory as a large cache called an attraction memory. This overhead consists of memory left unallocated for performance reasons as well as additional physical memory required due to the cache organization of memory. In this work, we examine the effect of data reshuffling and data replication on the memory overhead. Data reshuffling occurs when space needs to be allocated to store a remote memory line in the local memory. Data that is reshuffled is sent between memories via replacement messages. A simple mathematical model predicts the frequency of data reshuffling as a function of the attraction memory parameters. Simulation data shows that the frequency of data reshuffling is sensitive to the allocation policy and associativity of the memory but is relatively unaffected by the block size chosen. The simulation data also shows that data replication in the attraction memory is important for good performance, but most gains can be achieved through replication in the processor caches.
Exploring the design space for a shared-cache multiprocessor
Authors: Nayfeh B. A. , Olukotun K.
Published: July 2004

In the near future, semiconductor technology will allow the integration of multiple processors on a chip or multichip-module (MCM). In this paper we investigate the architecture and partitioning of resources between processors and cache memory for single chip and MCM-based multiprocessors. We study the performance of a cluster-based multiprocessor architecture in which processors within a cluster are tightly coupled via a shared cluster cache for various processor-cache configurations. Our results show that for parallel applications, clustering via shared caches provides an effective mechanism for increasing the total number of processors in a system, without increasing the number of invalidations. Combining these results with cost estimates for shared cluster cache implementations leads to two conclusions: 1) For a four cluster multiprocessor with single chip clusters, two processors per cluster with a smaller cache provides higher performance and better cost/performance than a single processor with a larger cache and 2) this four cluster configuration can be scaled linearly in performance by adding processors to each cluster using MCM packaging techniques.