bluuebunny/crossref_metadata_2025 huggingface dataset:
Systolic implementations of a move-to-front text compressor
Authors: Thomborson Clark D. , Wei Belle W.-Y.
Published: July 2004

We give systolic implementations for three variants of the move-to-front coding algorithm discussed in recent journal articles by Ryabko, Elias, and Bentley, Sleator, Tarjan, and Wei. Our intent is to make a simple high-speed text-compression system for both data transmission and data storage devices. Comparing our implementations with previously-proposed software and hardware devices for these applications, we conclude that our implementations should operate at much higher bandwidth than any known high-compression algorithm, and at higher bandwidth and comparable compression to the Lempel-Ziv-Welch and Smith-Storer hardware.
The chaos router
Authors: Konstantinidou S. , Snyder L.
Published: July 2004

We present the chaos router, an asynchronous adaptive router, which under certain circumstances can send messages farther from their destinations. The chaos router greatly simplifies the routing logic by removing the livelock protection of previous schemes. Through an effective use of randomness, whose sources include that due to the adaptively processed load, the natural timing differences of selftimed circuitry and explicitly injected randomization, the chaos router avoids long message routes with high probability. In this paper the router is described, it is argued that the chaos router is deadlock free and probabilistically live-lock and starvation free, and simulation results are presented showing that the chaos router performs well.
Asynchronous shared memory parallel computation (preliminary version)
Authors: Nishimura Naomi
Published: July 2004

The contributions of this paper are twofold. First, we outline criteria by which any model of asynchronous shared memory parallel computation can be judged. Previous models are considered with respect to these factors. Next, we introduce a new model, and show that this model fulfils all the listed requirements. We also analyze in our model the complexity of several fundamental parallel algorithms.
FLIP-FLOP
Authors: Grabienski Peter
Published: July 2004

Many research and application fields are today computationally very demanding. This requirement has influenced the development of high-performance processors, vector processors and multiprocessor engines. This paper describes the development of the multiprocessing system FLIP-FLOP (Fast Link Periphery for a Forth Language Oriented Processor) which combines a stack oriented processor kernel and a communication coprocessor for message passing.In the past many muliprocessor systems based on available microprocessors have been built, for example the iPSC or the BBN Butterfly. On the other hand special processors were constructed for building multiprocessing systems like the INMOS Transputer [1]. The FLIP-FLOP system belongs to the second class and there are several similarities between FLIP-FLOP and the Transputers. The kernel of FLIP-FLOP uses a stack as a central data structure, but this stack is potentially unlimited. All data manipulations use this stack. One additional stack is available for handling adresses (subroutines, loops). Due to the independence between both stack many operations can take place in parallel. An example is the possibility of overlapping a subroutine return with an arbitrary other instruction. This dual stack architecture directly supports the stack oriented language FORTH and as it will be shown leads to high performance using small chip area.Therefore it is possible to integrate the communication coprocessor FLIP together with FLOP on one chip. FLIP was designed to be as simple as possible without loosing performance in message passing. This "RISC philosophy" is nevertheless safe against deadlocks. Messages are sent as packets and are routed completely by the hardware over up to 16 links without affecting the FLOP part. One FLIP-FLOP involves four links (dedicated connections between two processors) which are able to transfer byte parallel data in both directions at the same time (duplex mode). Using a clocking frequency of 10 MHz up to 40 MByte of data can be transferred. Incoming messages are stored in the main memory via DMA into a special adress region (input mail-box), outgoing messages are taken from another adress region (output mailbox). This especially supports algorithms using asynchronous message exchange. One example algorithm is Time Warp driven discrete distributed simulation.It will be shown that the stack architecture and the message passing principle are working well together. This leads to a short response time to incoming messages. The RISC like design of both parts FLIP and FLOP requires small chip area and makes it possible to implement a whole FLIP-FLOP system with a VLSI semi-custom design system onto one chip.
A parallel pipelined processor with conditional instruction execution
Authors: Adams Rod , Steven Gordon
Published: July 2004

In a recent paper by Smith, Lam and Horowitz [1] the concept of 'boosting' was introduced, where instructions from one of the possible instruction streams following a conditional branch were scheduled by the compiler for execution in the basic block containing the branch itself. This paper describes how code from both instruction streams following a conditional branch can be considered for execution in the basic block containing the branch. Branch conditions are stored in Boolean registers and all instructions are conditionally executed based on the value in a Boolean register. The two instruction streams can therefore be executed on complementary values of the same Boolean register.
A novel single instruction computer architecture
Authors: Laplante P. A.
Published: July 2004

A single processing computer system using only half-adder circuits is described. In addition, it is shown that only a single hard-wired instruction is needed in the control unit to obtain a complete [1] instruction set for this general purpose computer. Such a system has several advantages. First it is intrinsically a RISC machine-in fact the "ultimate RISC" machine. Second, because only a single type of logic element is employed the entire computer system can be easily realized on a single, highly integrated chip. Finally, due to the homogeneous nature of the computer's logic elements, the computer has possible implementations as an optical or chemical machine. This in turn suggests possible paradigms for neural computing and artificial intelligence. This approach was inspired by a paper by van der Poel [5] in which a single instruction is used to furnish a complete set [1] of general purpose instructions.
Performance variation across benchmark suites
Authors: Ponder Carl
Published: July 2004

The performance ratio between two systems tends to vary across different benchmarks. Here we study this variation as a "signature" or "fingerprint" of the systems under consideration. This "fingerprint" can be used to guess the performance of programs not represented in a benchmark suite, assess the breadth and credibility of the benchmark suite, and infer details of the system design.
A cost-effective reliable multipath interconnection network
Authors: Morris Todd D. , Gehringer Edward F.
Published: July 2004

A new class of multistage interconnection networks is proposed. A network in this class consists of a standard multistage network, such as an omega network, augmented by multiplexers at the source nodes and demultiplexers at the destination. In addition, the first several stages are capable of adapting their routing decisions to avoid faults elsewhere in the network. The terminal reliability of this network is derived, and it is shown to have superior reliability, at a much lower cost than previous networks of similar fault tolerance. It is demonstrated that the proposed network's probability of acceptance, a common measure of performance for circuit-switched networks, is comparable to other networks of similar cost, but the greater number of paths it provides between source and destination should give it better performance under non-uniform traffic conditions.
How many operation units are adequate?
Authors: Matthes Wolfgang
Published: July 2004

A uniprocessor superscalar architecture is proposed which comprises four universal operation units arranged according to a tree-shaped dataflow graph, instruction issuing hardware, and oper and selection means. The control principles are based on VLIW, microprogramming, and dataflow concepts. The proposal emerged mainly from investigations of inherent mathematical structures of application problems, especially from the analysis of dataflow graphs of elementary mathematical fromulas (arithmetic of intervals, complex and rational numbers etc.). The particular operation unit itself is an ensemble of high-performance processing resources which may be compared to state-of-the-art processors (e. g. 1860). It may require a silicon budget from one to five million transistors. The whole processor may require 10 to 50 million transistors, thus being a suitable implementation target for IC technologies of the 90's.
An argument against scalable cache coherency
Authors: Matloff Norman
Published: July 2004

Recently there has been considerable interest in cache coherency protocols in shared-memory multiprocessor systems, particularly in protocols which are scalable, i.e. efficient in very large systems. In this position paper, it will be argued that in most multiprocessor applications scalability---or for that matter, systemwide cache coherency itself---is unnecessary, no matter how large the system is. Since even an efficient protocol will be a significant inhibitor of performance, it is then argued that systems
not
be built with systemwide coherency. Instead, a concept of "local coherency" is proposed. In this approach, though the shared-memory paradigm is retained and the system is still assumed to consist of a very large number of processors, hardware support for accessing shared variables exists only within
groups
of processors. Accordingly, it is asserted that the main research in cache coherency protocols should concentrate on developing efficient protocols for small and medium numbers of caches rather than on scalability.
SPIRE
Authors: Wajda Eligiusz
Published: July 2004

The SPIRE-Architecture is designed for high speed uniprocessor execution of sequential problems as well for parallel multiprocessor systems where individual processors perform operations on complex data structures. The idea of SPIRE-Architecture lies in a new instruction format expanded by a dedicated execution clause and compilative instruction execution. To mirror this concept in practice some new components has been added to the hardware.The simulation results show that SPIRE can processes data up to 30 times faster than classic von Neumann processor and profits directly from complexity of used data structures. Programm code is about twice as compact as that of RISC processors. Furthermore, a proposed hardware concept and consistent rules of instruction coding allows compilers to generate very efficient code.
A class of replacement policies for medium and high-associativity structures
Authors: Deville Yannick , Gobert Jean
Published: July 2004

The content of set associative and fully associative structures (such as cache memories, TLBs and main memories) is controlled by a replacement algorithm. Replacing the elements that have not been accessed for a long period yields high performance. This property has been used in the LRU policy, it is also used in this paper, in order to define a new class of replacement policies that provide two improvements over LRU : 1) they exhibit higher performance, 2) they have a lower complexity of implementation : when the associativity increases, their complexity remains unchanged while it increases very rapidly for LRU. Trace-driven simulations show that, in 4-way caches, the performance improvement of one of the proposed policies over LRU is similar to the improvement of LRU over random and FIFO (i.e. about 10 %). For higher associativities, the proposed policies yield much higher performance in a particular range of cache sizes. In fully associative TLBs, the performance improvement is smaller but they yield much simpler implementations.
A graphical comparison of RISC processors
Authors: Esponda Margarita , Rojas Raúl
Published: July 2004

A graphical approach for the comparison of RISC processors is presented in this note. Kiviat graphs summarize some of the most relevant architectural parameters of RISC designs in a more appealing manner as tables of parameters.
Dynamic refresh method for dynamic RAMs
Authors: Matsui Shogo
Published: July 2004

DYNAMIC REFRESH METHOD, a new method of refreshing dynamic RAMs is proposed that may result in a significant reduction in the frequency of refresh. The method is based on a fact that a row of the memory cells array in dynamic RAM is normally refreshed whenever a normal access is made. The method is described as a periodic operation with 1/n intervals of the ordinary method. The number of rows refreshed in one cycle varies dynamically. A definition and an implementation of the method are introduced first, the improvement in frequency of refresh is analyzed, and an application example is given.
Prefetch unit for vector operations on scalar computers
Authors: Sklenář 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 architecture 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 therefore initializes rarely any superfluous prefetches.
A performance study of memory consistency models
Authors: Zucker Richard N. , Baer Jean-Loup
Published: July 2004

Recent advances in technology are such that the speed of processors is increasing faster than memory latency is decreasing. Therefore the relative cost of a cache miss is becoming more important. However, the full cost of a cache miss need not be paid every time in a multiprocessor. The frequency with which the processor must stall on a cache miss can be reduced by using a relaxed model of memory consistency.

In this paper, we present the results of instruction-level simulation studies on the relative performance benefits of using different models of memory consistency. Our vehicle of study is a shared-memory multiprocessor with processors and associated write-back caches connected to global memory modules via an Omega network. The benefits of the relaxed models, and their increasing hardware complexity, are assessed with varying cache size, line size, and number of processors. We find that substantial benefits can be accrued by using relaxed models but the magnitudes of the benefits depend on the architecture being modeled, the benchmarks, and how the code is scheduled. We did not find any major difference in levels of improvement among the various relaxed models.
Hiding memory latency using dynamic scheduling in shared-memory multiprocessors
Authors: Gharachorloo Kourosh , Gupta Anoop , Hennessy John
Published: July 2004

The large latency of memory accesses is a major impediment to achieving high performance in large scale shared-memory multi-processsors. Relaxing the memory consistency model is an attractive technique for hiding this latency by allowing the overlap of memory accesses with other computation and memory accesses. Previous studies on relaxed models have shown that the latency of write accesses can be hidden by buffering writes and allowing reads to bypass pending writes. Hiding the latency of reads by exploiting the overlap allowed by relaxed models is inherently more difficult, however, simply because the processor depends on the return value for its future computation.

This paper explores the use of dynamically scheduled processors to exploit the overlap allowed by relaxed models for hiding the latency of reads. Our results are based on detailed simulation studies of several parallel applications. The results show that a substantial fraction of the read latency can be hidden using this technique. However, the major improvements in performance are achieved only at large instruction window sizes.
Limits of control flow on parallelism
Authors: Lam Monica S. , Wilson Robert P.
Published: July 2004

This paper discusses three techniques useful in relaxing the constraints imposed by control flow on parallelism: control dependence analysis, executing multiple flows of control simultaneously, and speculative execution. We evaluate these techniques by using trace simulations to find the limits of parallelism for machines that employ different combinations of these techniques. We have three major results. First, local regions of code have limited parallelism, and control dependence analysis is useful in extracting global parallelism from different parts of a program. Second, a superscalar processor is fundamentally limited because it cannot execute independent regions of code concurrently. Higher performance can be obtained with machines, such as multiprocessors and dataflow machines, that can simultaneously follow multiple flows of control. Finally, without speculative execution to allow instructions to execute before their control dependences are resolved, only modest amounts of parallelism can be obtained for programs with complex control flow.
The expandable split window paradigm for exploiting fine-grain parallelsim
Authors: Franklin Manoj , Sohi Gurindar S.
Published: July 2004

We propose a new processing paradigm, called the Expandable Split Window (ESW) paradigm, for exploiting fine-grain parallelism. This paradigm considers a window of instructions (possibly having dependencies) as a single unit, and exploits fine-grain parallelism by overlapping the execution of multiple windows. The basic idea is to connect multiple sequential processors, in a decoupled and decentralized manner, to achieve overall multiple issue. This processing paradigm shares a number of properties of the restricted dataflow machines, but was derived from the sequential von Neumann architecture. We also present an implementation of the Expandable Split Window execution model, and preliminary performance results.
Towards a shared-memory massively parallel multiprocessor
Authors: Litaize Daniel , Mzoughi Abdelaziz , Rochange Christine , Sainrat Pascal
Published: July 2004

A set of ultra high throughput (more than one Gigabits per second) serial links used as processor-memory network can lead to the starting up of a shared-memory massively parallel multiprocessor. The bandwidth of the network is far beyond values found in present shared-memory multiprocessor networks. To feed this network the memory must be serially multiported. Such a multiprocessor can actually be build with current technologies.

This paper analyzes the characteristics of such a novel architecture, presents the solutions that must be considered and the practical problems associated with close of experiments. These results show then the way to effectively build this multiprocessor, taking into account main topics such as data coherency, latency time and scalability.
The DASH prototype
Authors: Lenoski Daniel , Laudon James , Joe Truman , Nakahira David , Stevens Luis , Gupta Anoop , Hennessy John
Published: July 2004

The fundamental premise behind the DASH project is that it is feasible to build large-scale shared-memory multiprocessors with hardware cache coherence. While paper studies and software simulators are useful for understanding many high-level design trade-offs, prototypes are essential to ensure that no critical details are overlooked. A prototype provides convincing evidence of the feasibility of the design allows one to accurately estimate both the hardware and the complexity cost of various features, and provides a platform for studying real workloads. A 16-processor prototype of the DASH multiprocessor has been operational for the last six months. In this paper, the hardware overhead of directory-based cache coherence in the prototype is examined. We also discuss the performance of the system, and the speedups obtained by parallel applications running on the prototype. Using a sophisticated hardware performance monitor, we characterize the effectiveness of coherent caches and the relationship between an application's reference behavior and its speedup.
Performance evaluation of a decoded instruction cache for variable instruction-length computers
Authors: Intrater Gideon , Spillinger Ilan
Published: July 2004

A Decoded INstruction Cache (DINC) serves as a buffer between the instruction decoder and the other instruction-pipeline stages. In this paper we explain how techniques that reduce the branch penalty based on such a cache, can improve CPU performance. We analyze the impact of some of the design parameters of DINCs on variable instruction-length computers, e.g., CISC machines.

Our study indicates that tuning the mapping function of the instructions into the cache, can improve the performance substantially. This tuning must be based on the instruction length distribution for a specific architecture. In addition, the associativity degree has a greater effect on the DINC's performance, than on the performance of regular caches. We also discuss the difference between the performance of DINCs and other caches, when longer cache lines are used. The results presented were obtained by both analytical study and trace-driven simulations of several integer UNIX applications.
A simulation based study of TLB performance
Authors: Chen J. Bradley , Borg Anita , Jouppi Norman P.
Published: July 2004

This paper presents the results of a simulation-based study of various translation lookaside buffer (TLB) architectures, in the context of a modern VLSI RISC processor. The simulators used address traces, generated by instrumented versions of the SPEC marks and several other programs running on a DECstation 5000. The performance of two-level TLBs and fully-associative TLBs were investigated. The amount of memory mapped was found to be the dominant factor in TLB performance. Small first-level FIFO instruction TLBs can be effective in two level TLB configurations. For some applications, the cyles-per-instruction (CPI) loss due to TLB misses can be reduced from as much as 5CPI to negligible levels with typical TLB parameters through the use of variable-sized pages.
Alternative implementations of two-level adaptive branch prediction
Authors: Yeh Tse-Yu , Patt Yale N.
Published: July 2004

As the issue rate and depth of pipelining of high performance Superscalar processors increase, the importance of an excellent branch predictor becomes more vital to delivering the potential performance of a wide-issue, deep pipelined microarchitecture. We propose a new dynamic branch predictor (Two-Level Adaptive Branch Prediction) that achieves substantially higher accuracy than any other scheme reported in the literature. The mechanism uses two levels of branch history information to make predictions, the history of the last
k
branches encountered, and the branch behavior for the last
s
occurrences of the specific pattern of these
k
branches. We have identified three variations of the Two-Level Adaptive Branch Prediction, depending on how finely we resolve the history information gathered. We compute the hardware costs of implementing each of the three variations, and use these costs in evaluating their relative effectiveness. We measure the branch prediction accuracy of the three variations of two-Level Adaptive Branch Prediction, along with several other popular proposed dynamic and static prediction schemes, on the SPEC benchmarks. We show that the average prediction accuracy for Two-Level Adaptive Branch Prediction is 97 percent, while the other known schemes achieve at most 94.4 percent average prediction accuracy. We measure the effectiveness of different prediction algorithms and different amounts of history and pattern information. We measure the costs of each variation to obtain the same prediction accuracy.
An elementary processor architecture with simultaneous instruction issuing from multiple threads
Authors: Hirata Hiroaki , Kimura Kozo , Nagamine Satoshi , Mochizuki Yoshiyuki , Nishimura Akio , Nakase Yoshimori , Nishizawa Teiji
Published: July 2004

In this paper, we propose a multithreaded processor architecture which improves machine throughput. In our processor architecture, instructions from different threads (not a single thread) are issued simultaneously to multiple functional units, and these instructions can begin execution unless there are functional unit conflicts. This parallel execution scheme greatly improves the utilization of the functional unit. Simulation results show that by executing two and four threads in parallel on a nine-functional-unit processor, a 2.02 and a 3.72 times speed-up, respectively, can be achieved over a conventional RISC processor.

Our architecture is also applicable to the efficient execution of a single loop. In order to control functional unit conflicts between loop iterations, we have developed a new static code scheduling technique. Another loop execution scheme, by using the multiple control flow mechanism of our architecture, makes it possible to parallelize loops which are difficult to parallelize in vector or VLIW machines.
Thread-based programming for the EM-4 hybrid dataflow machine
Authors: Sato Mitsuhisa , Kodama Yuetsu , Sakai Shuichi , Yamaguchi Yoshinori , Koumura Yasuhito
Published: July 2004

In this paper, we present a thread-based programming model for the EM-4 hybrid dataflow machine, where parallelism and synchronization among threads of sequential execution are described explicitly by the programmer. Although EM-4 was originally designed as a dataflow machine, we demonstrate that it provides effective architectural support for a variety of programming styles, including message passing and distributed data sharing in imperative languages. Our approach allows the programmer to control the parallelism and maintain data locality explicitly to achieve high performance. EM-4 can be thought of as a multi-threaded architecture that can exploit both von Neumann and dataflow compiling technology. Thread-based programming provides the first step to explore better programming/compiling technology for a hybrid dataflow machine as well as EM-4.
T
Authors: Nikhil R. S. , Papadopoulos G. M. , Arvind
Published: July 2004

What should the architecture of each node in a general purpose, massively parallel architecture (MPA) be? We frame the question in concrete terms by describing two fundamental problems that must be solved well in any general purpose MPA. From this, we systematically develop the required logical organization of an MPA node, and present some details of
*
T (pronounced
Start
, a concrete architecture designed to these requirements.
*
T is a direct descendant of dynamic dataflow architectures, and unifies them with von Neumann architectures. We discuss a hand-compiled example and some compilation issues.
Adjustable block size coherent caches
Authors: Dubnicki Czarek , LeBlanc Thomas J.
Published: July 2004

Several studies have shown that the performance of coherent caches depends on the relationship between the granularity of sharing and locality exhibited by the program and the cache block size. Large cache blocks exploit processor and spatial locality, but may cause unnecessary cache invalidations due to false sharing. Small cache blocks can reduce the number of cache invalidations, but increase the nuber of bus or network transactions required to load data into the cache. In this paper we describe a cache organization that dynamically adjusts the cache block size according to recently observed reference behavior. Cache blocks are split across cache lines when false sharing occurs, ad merged back into a single cache line to explit spatial locality. To evaluate this cache organization, we simulate a scalable multiprocessor with coherent caches, using a suite of memory reference traces to model program behavior. We show that for evry fixed block size, some program suffers a 33% increase in the average waiting time per reference, and a factor of 2 increase in the average number of words transferred per reference, when compared against the performance of an adjustable block size cache. In the few cases where adjusting the block size does not provide superior performance, it comes within 7% of the best fixed block size alternative. We conclude that an adjustable block size cache offers significantly better performance than every fixed block size cache, especially when there is variability in the granularity of sharing exhibited by applications.
Performance optimization of pipelined primary cache
Authors: Olukotun Kunle , Mudge Trevor , Brown Richard
Published: July 2004

The CPU cycle time of a high-performance processor is usually determined by the access time of the primary cache. As processors speeds increase, designers will have to increase the number of pipeline stages used to fetch data from the cache in order to reduce the dependence of CPU cycle time on cache access time. This paper studies the performance advantages of a pipelined cache for a GaAs implementation of the MIPS based architecture using a design methodology that includes long traces of multiprogrammed applications and detailed timing analysis. The study evaluates instruction and data caches with various pipeline depths, cache sizes, block sizes, and refill penalties. The impact on CPU cycle time of these alternatives is also factored into the evaluation. Hardware-based and software-based strategies are considered for hiding the branch and load delays which may be required to avoid pipeline hazards. The results show that software-based methods for mitigating the penalty of branch delays can be as successful as the hardware-based
branch-target buffer
approach, despite the code-expansion inherent in the software methods. The situation is similar for load delays; while hardware-based dynamic methods hide more delay cycles than do static approaches, they may give up the advantage by extending the cycle time. Because these methods are quite successful at hiding small numbers of branch and load delays, and because processors with pipelined caches also have shorter CPU cycle times and larger caches, a significant performance advantage is gained by using two to three pipeline stages to fetch data from the cache.
Instruction-level parallelism in Prolog
Authors: De Gloria Alessandro , Faraboschi Paolo
Published: July 2004

The demand of increasing computation power for symbolic processing has given a strong impulse to the development of ASICs dedicated to the execution of prolog. Unlike past microcoded implementation based on the Warren machine model, novel trends in high performance Prolog processors suggest the implementation of RISC-based processors committed to prolog only through the adoption of a few basic dedicated features, like the Berkeley Abstract Machine (BAM) processor.

Following the idea of using a smart compiler for a simple instruction set, the SYMBOL project represents an experiment in applying global compaction techniques and VLIW design philosophy to the static exploitation of instruction-level parallelism in Prolog.

This paper presents code analysis results and shows how we can approach the theoretical speed-up limit (about 3) imposed by Amdahl's law on shared memory models, by means of global code optimizations and a suitable architectural support. In addition, we show implementation details and some preliminary data of a VLSI prototype architecture.
Memory latency effects in decoupled architectures with a single data memory module
Authors: Kurian Lizyamma , Hulina Paul T. , Coraor Lee D.
Published: July 2004

Decoupled computer architectures partition the memory access and execute functions in a computer program and achieve high performance by exploiting the fine-grain parallelism between the two. These architectures make use of an access processor to perform the data fetch ahead of demand by the execute process and hence are often less sensitive to memory access delays than conventional architectures. Past performance studies of decoupled computers used memory systems that are interleave or pipelined. We undertake a simulation study of the latency effects in decoupled computers when connected to a single, conventional non-interleaved data memory module so that the effect of decoupling is isolated from the improvement caused by interleaving. We compare decoupled computer performance to single processors with caches, study the memory latency sensitivity of the decoupled systems, and also perform simulations to determine the significance of data caches in a decoupled computer architecture. The Lawrence Livermore Loops and two signal processing algorithms are used as the simulation benchmark.
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.
Active messages
Authors: von Eicken Thorsten , Culler David E. , Goldstein Seth Copen , Schauser Klaus Erik
Published: July 2004

The design challenge for large-scale multiprocessors is (1) to minimize communication overhead, (2) allow communication to overlap computation, and (3) coordinate the two without sacrificing processor cost/performance. We show that existing message passing multiprocessors have unnecessarily high communication costs. Research prototypes of message driven machines demonstrate low communication overhead, but poor processor cost/performance. We introduce a simple communication mechanism,
Active Messages
, show that it is intrinsic to both architectures, allows cost effective use of the hardware, and offers tremendous flexibility. Implementations on nCUBE/2 and CM-5 are described and evaluated using a split-phase shared-memory extension to C,
Split
-C. We further show that active messages are sufficient to implement the dynamically scheduled languages for which message driven machines were designed. With this mechanism, latency tolerance becomes a programming/compiling concern. Hardware support for active messages is desirable and we outline a range of enhancements to mainstream processors.
The turn model for adaptive routing
Authors: Glass Christopher J. , Ni Lionel M.
Published: July 2004

We present a model for designing wormhole routing algorithms that are deadlock free, livelock free, minimal or nonminimal, and maximally adaptive. A unique feature of this model is that it is not based on adding physical or virtual channels to network topologies (though it can be applied to networks with extra channels). Instead, the model is based on analyzing the directions in which packets can turn in a network and the cycles that the turns can form. Prohibiting just enough turns to break all of the cycles produces routing algorithms that are deadlock free, livelock free, minimal or nonminimal, and maximally adaptive for the network. In this paper, we focus on the two most common network topologies for wormhole routing,n-dimensional mesh, just a quarter of the turns must be prohibited to prevent deadlock. The remaining three quarters of the turns permit partial adaptiveness in routing. Partially adaptive routing algorithms are described for 2D meshes,n-dimensional meshes,k-aryn-cubes, and hypercubes. Simulations of partially adaptive and nonadaptive routing algorithms for 2D meshes and hypercubes show that which algorithm has the lowest latencies and highest sustainable throughput depends on the pattern of message traffic. For nonuniform traffic, partially adaptive routing algorithms perform better than non-adaptive ones.
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.
Futurebus+ as an I/O bus
Authors: Aichinger Barbara P.
Published: July 2004

The IEEE Futurebus+ is a very fast (3GB/sec.), industry standard backplane bus specification for computer systems. Futurebus+ was designed independent of any CPU architecture so it is truly open. With this open architecture Futurebus+ can be applied to many different computing applications. Profile B is a subset of the IEEE 896 Futurebus+ standard and targets high performance, general purpose computer I/O applications. This paper describes how and why the functional, electrical, mechanical and environmental characteristics were chosen.
Comparison of sparing alternatives for disk arrays
Authors: Menon Jai , Mattson Dick
Published: July 2004

This paper explores how choice of sparing methods impacts the performance of RAID level 5 (or parity striped) disk arrays. The three sparing methods examined are dedicated sparing, distributed sparing, and parity sparing. For database type workloads with random single block reads and writes, array performance is compared in four different modes - normal mode (no disks have failed), degraded mode (a disk has failed and its data has not been reconstructed), rebuild mode (a disk has failed and its data is being reconstructed), and copyback mode(which is needed for distributed sparing and parity sparing when failed disks are replaced with new disks). Attention is concentrated on small disk subsystems (fewer than 32 disks) where choice of sparing method has significant impact on array performance, rather than large disk subsystems (64 or more disks). It is concluded that, for disk subsystems with a small number of disks, distributed sparing offers major advantages over dedicated sparing in normal, degraded and rebuild modes of operation, even if one has to pay a copyback penalty. Furthermore, it is better than parity sparing in rebuild mode and similar to it in other operating modes, making it the sparing method of choice.
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.
Evaluation of the WM architecture
Authors: Wulf Wm. A.
Published: July 2004

This report describes the results of studies of the WM architecture—its performance, the values of some of its key architectural parameters, the difficulty of compiling for it, and hardware implementation complexity. The studies confirm that, with comparable chip area and without heroic compiler technology, WM is capable of outperforming traditional scalar architectures by factors of 2-9. They also underscore the need to devise higher bandwidth memory systems.
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.
Tradeoffs in supporting two page sizes
Authors: Talluri Madhusudhan , Kong Shing , Hill Mark D. , Patterson David A.
Published: July 2004

As computer system main memories get larger and processor cycles-per-instruction (CPIs) get smaller, the time spent in handling translation lookaside buffer (TLB) misses could become a performance bottleneck. We explore relieving this bottleneck by (a) increasing the page size and (b) supporting two page sizes.

We discuss how to build a TLB to support two page sizes and examine both alternatives experimentally with a dozen uniprogrammed, user-mode traces for the SPARC architecture. Our results show that increasing the page size to 32KB causes both a significant increase in average working set size (e.g., 60%) and a significant reduction in the TLB's contribution to CPI,

CPI
TLB

, (namely a factor of eight) compared to using 4KB pages. Results for using two page sizes, 4KB and 32KB pages, on the other hand, show a small increase in working set size (about 10%) and variable decrease in

CPI
TLB

, (from negligible to as good as found with the 32KB page size).

CPI
TLB

when using two page sizes is consistently better for fully associative TLBs than for set-associative ones.

Our results are preliminary, however, since (a) our traces do not include multiprogramming or operating system behavior, and (b) our page-size assignment policy may not reflect a real operating system's policy.
OPAC (abstract)
Authors: Seznec André , Courtel Karl
Published: July 2004

In many applications, the main part of the computations may be encapsulated in compute-bounds kernels. Achieving high performance on compute-bound primitives at a low hardware cost has become an important challenge. OPAC was designed as the basic cell of a floating-point coprocessor dedicated to the execution of compute-bound kernels. Due to efficient hardware mechanisms for controlling and sequencing a pipeline performance close to a floating-point multiply-add percycle per cell is reached on applications such as solving linear systems, FFTs correlations in a microprocessor environment.
Architecture of a graphics processor (abstract)
Authors: Singh Gautam B.
Published: July 2004

The design principles that were applied in the design of the integer-RISC machine, are applied to the design of the Reduced Instruction Set Graphics Processor. The processor instruction is defined after critical evaluation of the common graphics operations. Single cycle operation (in a pure RISC style) are performed through instructions for primitive graphics as well as general purpose computations. This processor is envisioned to become the CPU of choice for the ergonomic applications that rely heavily on graphics capabilities for user interface bandwidth improvement. The motivation for integrating graphics with general-purpose computations stems from the performance enhancement acheived due to increased integration levels, and the program portability offered by a single processor

based systems.
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.