bluuebunny/crossref_metadata_2025 huggingface dataset:
Data buffering: run-time versus compile-time support
Authors: Mulder H.
Published: July 2004

Data-dependency, branch, and memory-access penalties are main constraints on the performance of high-speed microprocessors. The memory-access penalties concern both penalties imposed by external memory (e.g. cache) or by under utilization of the local processor memory (e.g. registers). This paper focuses solely on methods of increasing the utilization of data memory, local to the processor (registers or register-oriented buffers).

A utilization increase of local processor memory is possible by means of compile-time software, run-time hardware, or a combination of both. This paper looks at data buffers which perform solely because of the compile-time software (single register sets); those which operate mainly through hardware but with possible software assistance (multiple register sets); and those intended to operate transparently with main memory implying no software assistance whatsoever (stack buffers). This paper shows that hardware buffering schemes cannot replace compile-time effort, but at most can reduce the complexity of this effort. It shows the utility increase of applying register allocation for multiple register sets. The paper also shows a potential utility decrease inherent to stack buffers. The observation that a single register set, allocated by means of interprocedural allocation, performs competitively with both multiple register set and stack buffer emphasizes the significance of the conclusion
A real-time support processor for ada tasking
Authors: Roos J.
Published: July 2004

Task synchronization in Ada causes excessive run-time overhead due to the complex semantics of the rendezvous. To demonstrate that the speed can be increased by two orders of magnitude by using special purpose hardware, a single chip VLSI support processor has been designed. By providing predictable and uniformly low overhead for the entire semantics of a rendezvous, the powerful real-time constructs of Ada can be used freely without performance degradation.

The key to high performance is the set of primitive operations implemented in hardware. Each operation is complex enough to replace a considerable amount of code was designed to execute with a minimum of communication overhead. Task control blocks are stored on-chip as well as headers for entry, delay and ready queues. All necessary scheduling is integrated in the operations. Delays are handled completely on-chip using an internal real-time clock.

A multilevel design strategy, based on silicon compilation, made it possible to run actual Ada programs on a functional emulator of the chip and use the results to verify the detailed design. A high degree of parallelism and pipelining together with an elaborate internal addressing scheme has reduced the number of clock cycles needed to perform each operation. Using 2 μm CMOS, the processor can run at 20 MHz. A complex rendezvous, including the calling sequence and all necessary scheduling, can be performed in less than 15 μs.
The runtime environment for Scheme, a Scheme implementation on the 88000
Authors: Vegdahl Steven R. , Pleban Uwe F.
Published: July 2004

We are implementing a Scheme development system for the Motorola 88000. The core of the implementation is an optimizing native code compiler, together with a carefully designed runtime system. This paper describes our experiences with the 88000 as a target architecture. We focus on the design decisions concerning the runtime system, particularly with respect to data type representations, tag checking, procedure calling protocol, generic arithmetic, and the handling of continuations. We also discuss rejected design alternatives, and evaluate the strengths and weaknesses of the instruction set with respect to our constraints.
Program optimization for instruction caches
Authors: McFarling S.
Published: July 2004

This paper presents an optimization algorithm for reducing instruction cache misses. The algorithm uses profile information to reposition programs in memory so that a direct-mapped cache behaves much like an optimal cache with full associativity and full knowledge of the future. For best results, the cache should have a mechanism for excluding certain instructions designated by the compiler. This paper first presents a reduced form of the algorithm. This form is shown to produce an optimal miss rate for programs without conditionals and with a tree call graph, assuming basic blocks can be reordered at will. If conditionals are allowed, but there are no loops within conditionals, the algorithm does as well as an optimal cache for the worst case execution of the program consistent with the profile information. Next, the algorithm is extended with heuristics for general programs. The effectiveness of these heuristics are demonstrated with empirical results for a set of 10 programs for various cache sizes. The improvement depends on cache size. For a 512 word cache, miss rates for a direct-mapped instruction cache are halved. For an 8K word cache, miss rates fall by over 75%. Over a wide range of cache sizes the algorithm is as effective as increasing the cache size by a factor of 3 times. For 512 words, the algorithm generates only 32% more misses than an optimal cache. Optimized programs on a direct-mapped cache have lower miss rates than unoptimized programs on set-associative caches of the same size.
The design of nectar: a network backplane for heterogeneous multicomputers
Authors: Arnould Emmanuel , Kung H. T. , Bitz Francois , Sansom Robert D. , Cooperm Eric C.
Published: July 2004

Nectar is a “network backplane” for use in heterogeneous multicomputers. The initial system consists of a star-shaped fiber-optic network with an aggregate bandwidth of 1.6 gigabits/second and a switching latency of 700 nanoseconds. The system can be scaled up by connecting hundreds of these networks together.

The Nectar architecture provides a flexible way to handle heterogeneity and task-level parallelism. A wide variety of machines can be connected as Nectar nodes and the Nectar system software allows applications to communicate at a high level. Protocol processing is off-loaded to powerful communication processors so that nodes do not have to support a suite of network protocols.

We have designed and built a prototype Nectar system that has been operational since November 1988. This paper presents the motivation and goals for Nectar and describes its hardware and software. The presentation emphasizes how the goals influenced the design decisions and led to the novel aspects of Nectar.
Analysis of cache invalidation patterns in multiprocessors
Authors: Weber W. , Gupta A.
Published: July 2004

To make shared-memory multiprocessors scalable, researchers are now exploring cache coherence protocols that do not rely on broadcast, but instead send invalidation messages to individual caches that contain stale data. The feasibility of such directory-based protocols is highly sensitive to the cache invalidation patterns that parallel programs exhibit. In this paper, we analyze the cache invalidation patterns caused by several parallel applications and investigate the effect of these patterns on a directory-based protocol. Our results are based on multiprocessor traces with 4, 8 and 16 processors. To gain insight into what the invalidation patterns would look like beyond 16 processors, we propose a classification scheme for data objects found in parallel applications and link the invalidation traffic patterns observed in the traces back to these high-level objects. Our results show that synchronization objects have very different invalidation patterns from those of other data objects. A write reference to a synchronization object usually causes invalidations in many more caches. We point out situations where restructuring the application seems appropriate to reduce the invalidation traffic, and others where hardware support is more appropriate. Our results also show that it should be possible to scale “well-written” parallel programs to a large number of processors without an explosion in invalidation traffic.
Available instruction-level parallelism for superscalar and superpipelined machines
Authors: Jouppi N. P. , Wall D. W.
Published: July 2004

Superscalar machines can issue several instructions per cycle. Superpipelined machines can issue only one instruction per cycle, but they have cycle times shorter than the latency of any functional unit. In this paper these two techniques are shown to be roughly equivalent ways of exploiting instruction-level parallelism. A parameterizable code reorganization and simulation system was developed and used to measure instruction-level parallelism for a series of benchmarks. Results of these simulations in the presence of various compiler optimizations are presented. The
average degree of superpipelining
metric is introduced. Our simulations suggest that this metric is already high for many machines. These machines already exploit all of the instruction-level parallelism available in many non-numeric applications, even without parallel instruction issue or higher degrees of pipelining.
Limits on multiple instruction issue
Authors: Smith M. D. , Johnson M. , Horowitz M. A.
Published: July 2004

This paper investigates the limitations on designing a processor which can sustain an execution rate of greater than one instruction per cycle on highly-optimized, non-scientific applications. We have used trace-driven simulations to determine that these applications contain enough instruction independence to sustain an instruction rate of about two instructions per cycle. In a straightforward implementation, cost considerations argue strongly against decoding more than two instructions in one cycle. Given this constraint, the efficiency in instruction fetching rather than the complexity of the execution hardware limits the concurrency attainable at the instruction level.
IOBENCH: a system independent IO benchmark
Authors: Wolman B. , Olson T. M.
Published: July 2004

IOBENCH is an operating system and processor independent synthetic input/output (IO) benchmark designed to put a configurable IO and processor (CP) load on the system under test. It is meant to stress the system under test in a manner consistent with the way in which Oracle, Ingres, Prime INFORMATION or other data management products do IO. The IO and CP load is generated by background processes doing as many "transactions" as they can on a specified set of files during a specified time interval. By appropriately choosing and varying the benchmark parameters, IOBENCH can be configured to approximate the IO access patterns of real applications. IOBENCH can be used to compare different hardware platforms, different implementations of the operating system, different disk buffering mechanisms, and so forth. IOBENCH has proven to be a very good indicator of system IO performance. Use of IOBENCH has enabled us to pinpoint operating system bugs and bottlenecks.IOBENCH currently runs on PRIMOS and a number of UNIX systems; this paper discusses the UNIX versions. IOBENCH can be ported to a new platform in a few days. Prime proposes that IOBENCH and a standard spectrum of runs be adopted as an industry standard for measuring IO performance. Sources and documentation for IOBENCH will be made available free of charge.
Instruction-path coprocessing to solve some RISC problems
Authors: Debaere E. H.
Published: July 2004

Recent research in computer architecture has led to the development of Reduced Instruction Set Computers (RISCs). Such computers exploit the fast execution of a low number of low-level instructions. However, two problems arise: (
i
) as the RISC instruction set architectures are completely new and use specific look-ahead techniques, optimizing code generators of compilers must be developed from scratch to allow high level language programming; (
ii
) the high execution rate and low semantic instruction content inherent to RISCs requires extremely high instruction bandwidth in order to achieve maximal throughput. In this paper we propose to apply the concept of coprocessing in the instruction path and show how this technique, in particular in the RISC-case, greatly contributes to the solution of the two above problems.
Representation of logic functions by if-then clauses
Authors: Chiu P. K.
Published: July 2004

In this short paper, an alternative representation of logic functions is proposed. Instead of using Boolean expressions to represent logic functions, a set of
if-then
clauses is used. It is shown how a Boolean expression can be translated to the equivalent form in general. This representation of logic functions speeds up the logic simulation and solves the deadlock problem in logic simulation using concurrent processes such as OCCAM.
ParcBench: a benchmark for shared-memory architectures
Authors: Gunther N. J. , Noga M. T.
Published: July 2004

P
ARC
Bench is a non-synthetic, multi-component benchmark written in C and directed at Unix-based shared-memory multiprocessor architectures. Unlike most conventional benchmarks P
ARC
Bench generates multivariate data to produce a characterization of shared-memory architectures which necessarily goes beyond the single timing datum.
The UT1000 microprogramming simulator: an educational tool
Authors: Cornett F.
Published: July 2004

The concepts of microprogramming and firmware are frequently difficult to explain to computer science students. The subject of firmware is normally introduced in a beginning course of the computer science curriculum, usually as one of many terms for which a definition is memorized, but rarely understood. Even in advanced courses in computer organization or architecture, the concept may remain somewhat abstract to the student. Just as the practice of writing and executing programs in high level languages develops an increased understanding of those languages, writing and executing microprograms aids the student in understanding this concept. This paper describes the UT1000 microprogramming simulator, a software emulator for writing and executing microprograms on a simulated 16 bit CPU built using AMD2901 ALU/register slices and an AMD2910 microprogramming sequencer. The simulator package described here executes on the IBM PC/AT and PS/2 models of microcomputers. In addition to learning microprogramming concepts, the student is exposed to the principles of bit slice architecture, as well.
Multi-level shared caching techniques for scalability in VMP-M/C
Authors: Cheriton D. R. , Goosen H. A. , Boyle P. D.
Published: July 2004

The problem of building a scalable shared memory multiprocessor can be reduced to that of building a scalable memory hierarchy, assuming interprocessor communication is handled by the memory system. In this paper, we describe the VMP-MC design, a distributed parallel multi-computer based on the VMP multiprocessor design, that is intended to provide a set of building blocks for configuring machines from one to several thousand processors. VMP-MC uses a memory hierarchy based on shared caches, ranging from on-chip caches to board-level caches connected by busses to, at the bottom, a high-speed fiber optic ring. In addition to describing the building block components of this architecture, we identify the key performance issues associated with the design and provide performance evaluation of these issues using trace-drive simulation and measurements from the VMP.

This work was sponsored in part by the Defense Advanced Research Projects Agency under Contract N00014-88-K-0619.
Exploiting data parallelism in signal processing on a dataflow machine
Authors: Nitezki P.
Published: July 2004

This paper will show that the massive data parallelism inherent to most signal processing tasks may be easily mapped onto the parallel structure of a data flow machine. A special system called STRUCTFLOW has been designed to optimize the static data flow model for hardware efficiency and low latency. The same abstractions from the general purpose data flow model that lead to a quasi systolic operation of the processing elements make explicit flow control of the data tokens as they pass through the arcs of the flow graph obsolete. We will describe the architecture of the system and discuss the restrictions on the structure of the flow graphs.
A dynamic storage scheme for conflict-free vector access
Authors: Harper D. T. , Linebarger D. A.
Published: July 2004

Previous investigations into data storage schemes have focused on finding a storage scheme that permits conflict-free access for a set of frequently encountered access patterns. This paper considers an alternative approach. Rather than forcing a single storage scheme to be used for all access patterns, conflict-free accesses of any constant stride can be made by selecting a storage scheme for each vector based on the accessing patterns used with that vector.

By factoring the stride into two components, one a power of 2 and the other relatively prime to 2, a storage scheme can be synthesized which allows conflict-free access to the vector using the specified stride. All such schemes are based on a variation of the row rotation mechanism proposed by Budnik and Kuck[1]. Each storage scheme is based on two parameters, one describes the type of rotation to perform and the other describes the amount of memory to be rotated as a single block. Hardware required to implement this storage scheme is efficient.

The performance of the memory under access strides other than the stride used to specify the storage scheme is also considered. This models a vector being accessed with multiple strides, in particular the row/column access of a matrix, and situations when the stride can not be determined prior to initializing the vector. Simulation results show that if a single buffer is added to each memory port then the average performance of the dynamic scheme surpasses that of the interleaved scheme for arbitrary stride accesses.

For dynamic storage schemes to be effective, the compiler must be able to detect information about the stride of vector accesses. In general, this is within the capabilities of current vectorizing compilers. Dynamic storage schemes also may allow more flexibility in program transformation performed by vectorizing compilers during optimization.
SIMP (Single Instruction stream/Multiple instruction Pipelining): a novel high-speed single-processor architecture
Authors: Murakami K. , Irie N. , Tomita S.
Published: July 2004

SIMP is a novel multiple instruction-pipeline parallel architecture. It is targeted for enhancing the performance of SISD processors drastically by exploiting both temporal and spatial parallelisms, and for keeping program compatibility as well. Degree of performance enhancement achieved by SIMP depends on; i) how to supply multiple instructions continuously, and ii) how to resolve data and control dependencies effectively. We have devised the outstanding techniques for instruction fetch and dependency resolution. The instruction fetch mechanism employs unique schemes of; i) prefetching multiple instructions with the help of branch prediction, ii) squashing instructions selectively, and iii) providing
multiple conditional modes
as a result. The dependency resolution mechanism permits
out-of-order execution
of sequential instruction stream. Our out-of-order execution model is based on
Tomasulo's algorithm
which has been used in single instruction-pipeline processors. However, it is greatly extended and accommodated to multiple instruction pipelining with; i) detecting and identifying multiple dependencies simultaneously, ii) alleviating the effects of control dependencies with both
eager execution
and
advance execution,
and iii) ensuring a precise machine state against branches and interrupts. By taking advantage of these techniques, SIMP is one of the most promising architectures toward the coming generation of high-speed single processors.
Task migration in hypercube multiprocessors
Authors: Chen M.-S. , Shin K. G.
Published: July 2004

Allocation and deallocation of subcubes usually result in a fragmented hypercube where even if a sufficient number of hypercube nodes are available, they do not form a subcube large enough to execute an incoming task. As the fragmentation in conventional memory allocation can be handled by memory compaction, the fragmentation problem in a hypercube can be solved by
task migration
, i.e., relocating tasks within the hypercube to remove the fragmentation. The procedure for task migration closely depends on the subcube allocation strategy used, since active tasks must be relocated in such a way that the availability of subcubes can be detected by that allocation strategy.

In this paper, we develop a task migration strategy for the subcube allocation policy based on the binary reflected Gray code. A goal configuration (of destination subcubes) without fragmentation is determined first. Then, the node-mapping between the source and destination subcubes is derived. Finally, a routing procedure to achieve shortest deadlock-free paths for relocating tasks is developed.
Characteristics of performance-optimal multi-level cache hierarchies
Authors: Przybylski S. , Horowitz M. , Hennessy J.
Published: July 2004

The increasing speed of new generation processors will exacerbate the already large difference between CPU cycle times and main memory access times. As this difference grows, it will be increasingly difficult to build single-level caches that are both fast enough to match these fast cycle times and large enough to effectively hide the slow main memory access times. One solution to this problem is to use a multi-level cache hierarchy. This paper examines the relationship between cache organization and program execution time for multi-level caches. We show that a first-level cache dramatically reduces the number of references seen by a second-level cache, without having a large effect on the number of second-level cache misses. This reduction in the number of second-level cache hits changes the optimal design point by decreasing the importance of the cycle-time of the second-level cache relative to its size. The lower the first-level cache miss rate, the less important the second-level cycle time becomes. This change in relative importance of cycle time and miss rate makes associativity more attractive and increases the optimal cache size for second-level caches over what they would be for an equivalent single-level cache system.
Inexpensive implementations of set-associativity
Authors: Kessler R. E. , Jooss R. , Lebeck A. , Hill M. D.
Published: July 2004

The traditional approach to implementing wide set-associativity is expensive, requiring a wide tag memory (directory) and many comparators. Here we examine alternative implementations of associativity that use hardware similar to that used to implement a direct-mapped cache. One approach scans tags serially from most-recently used to least-recently used. Another uses a partial compare of a few bits from each tag to reduce the number of tags that must be examined serially. The drawback of both approaches is that they increase cache access time by a factor of two or more over the traditional implementation of set-associativity, making them inappropriate for cache designs in which a fast access time is crucial (e.g. level one caches, caches directly servicing processor requests).

These schemes are useful, however, if (1) the low miss ratio of wide set-associative caches is desired, (2) the low cost of a direct-mapped implementation is preferred, and (3) the slower access time of these approaches can be tolerated. We expect these conditions to be true for caches in multiprocessors designed to reduce memory interconnection traffic, caches implemented with large, narrow memory chips, and level two (or higher) caches in a cache hierarchy.
Organization and performance of a two-level virtual-real cache hierarchy
Authors: Wang W. H. , Baer J.-L. , Levy H. M.
Published: July 2004

We propose and analyze a two-level cache organization that provides high memory bandwidth. The first-level cache is accessed directly by virtual addresses. It is small, fast, and, without the burden of address translation, can easily be optimized to match the processor speed. The virtually-addressed cache is backed up by a large physically-addressed cache; this second-level cache provides a high hit ratio and greatly reduces memory traffic. We show how the second-level cache can be easily extended to solve the synonym problem resulting from the use of a virtually-addressed cache at the first level. Moreover, the second-level cache can be used to shield the virtually-addressed first-level cache from irrelevant cache coherence interference. Finally, simulation results show that this organization has a performance advantage over a hierarchy of physically-addressed caches in a multiprocessor environment.
High performance communications in processor networks
Authors: Jesshope C. R. , Miller P. R. , Yantchev J. T.
Published: July 2004

In order to provide an arbitrary and fully dynamic connectivity in a network of processors, transport mechanisms must be implemented, which provide the propagation of data from processor to processor, based on addresses contained within a packet of data. Such data transport mechanisms must satisfy a number of requirements - deadlock and livelock freedom, good hot-spot performance, high throughput and low latency. This paper proposes a solution to these problems, which allows deadlock free, adaptive, high throughput packet routing to be implemented on networks of processors. Examples are given which illustrate the technique for 2-D array and toroidal networks. An implementation of this scheme on arrays of transputers is described. The scheme also serves as a basis for a very low latency routing strategy named the
mad postman
, a detailed implementation of which is described here as well.
Introducing memory into the switch elements of multiprocessor interconnection networks
Authors: Mizrahi H. E. , Baer J. L. , Lazowska E. D. , Zahorjan J.
Published: July 2004

As VLSI technology continues to improve, circuit area is gradually being replaced by pin restrictions as the limiting factor in design. Thus, it is reasonable to anticipate that on-chip memory will become increasingly inexpensive since it is a simple, regular structure than can easily take advantage of higher densities.

In this paper we examine one way in which this trend can be exploited to improve the performance of multistage interconnection networks (MINs). In particular, we consider the performance benefits of placing significant memory in each MIN switch. This memory is used in two ways: to store (the unique copies of) data items and to maintain directories. The data storage function allows data to be placed nearer processors that reference it relatively frequently, at the cost of increased distance to other processors. The directory function allows data items to migrate in reaction to changes in program locality. We call our MIN architecture the Memory Hierarchy Network (MHN).

In a preliminary investigation of the merits of this design [8] we examined the performance of MHNs under the simplifying assumption that an unlimited amount of memory was available in each switch. We found that despite the longer switch processing times of the MHN, system performance is improved over simpler, conventional schemes based on caching.

In this paper we refine the earlier model to account for practical storage limitations. We study ways to reduce the amount of directory storage required by keeping only partial information regarding the current location of data items. The price paid for this reduction in memory requirement is more complicated (and in some circumstances slower) protocols. We obtain comparative performance estimates in an environment containing a single global memory module and a tree-structured MIN. Our results indicate that the MHN organization can have substantial performance benefits and so should be of increasing interest as the enabling technology becomes available.
Using feedback to control tree saturation in multistage interconnection networks
Authors: Scott S. L. , Sohi G. S.
Published: July 2004

In this paper, we propose the use of feedback schemes in multiprocessors which use an interconnection network with distributed routing control. We show that by altering system behavior so as to minimize the occurrence of a performance-degrading situation in the network, the overall throughout of the system can be improved.

As an example, we have considered the problem of tree saturation caused by hot spots in multistage interconnection networks. Tree saturation degrades the performance of all processors in a system, including those not participating in the hot spot activity. We see that feedback schemes can be used to control tree saturation, reduce degradation to memory requests that are not to the hot memory module and increase overall system bandwidth. As a companion to feedback schemes, damping schemes are also considered. Simulation studies presented in this paper show that feedback schemes can improve overall system performance significantly in many cases.
KCM: a knowledge crunching machine
Authors: Benker H. , Beacco J. M. , Dorochevsky M. , Jeffré Th. , Pöhlmann A. , Noyé J. , Poterie B. , Syre J. C. , Thibault O. , Watzlawik G.
Published: July 2004

KCM (Knowledge Crunching Machine) is a high-performance back-end processor which, coupled to a UNIX
*
desk-top workstation, provides a powerful and user-friendly Prolog environment catering for both development and execution of significant Prolog applications. This paper gives a general overview of the architecture of KCM stressing some new features like a 64-bit tagged architecture, shallow backtracking and an original memory management unit. Some early benchmark results obtained on prototype machines are presented. They show that KCM, which runs at a peak speed of 833 Klips on list concatenation, compares favorably with other dedicated Prolog machines and available commercial systems running on fast general purpose processors.
A high performance Prolog processor with multiple function units
Authors: Singhal A. , Patt Y. N.
Published: July 2004

We describe the Parallel Unification Machine (PLUM), a Prolog processor that exploits fine grain parallelism using multiple function units executing in parallel. In most cases the execution of bookkeeping instructions is almost completely overlapped by unification, and the performance of the processor is limited only by the available unification parallelism. We present measurements from a register transfer level simulator of PLUM. These results show that PLUM with 3 Unification Units achieves an average speedup of approximately 3.4 over the Berkeley VLSI-PLM, which is usually regarded as the current highest performance special purpose, pipelined Prolog processor. Measurements that show the effects of multiple Unification Units and memory access time on performance are also presented.
Evaluation of memory system for integrated Prolog processor IPP
Authors: Morioka M. , Yamaguchi S. , Bandoh T.
Published: July 2004

This paper discusses an optimal memory system to realize a high performance integrated Prolog processor, the IPP. First, the memory access characteristics of Prolog are analyzed by a simulator, which simulates the execution of a Prolog program at a micro instruction level. The main findings from this analysis are that: the write access ratio of Prolog is larger than that of procedural languages; and performance improvement requires the memory system to process concentrated, large write accesses effectively.

Then the Prolog acceleration strategies for conventional cache memories are discussed. Comparison is made of cache memories (store-swap, store-through) and a stack buffer, regarding not only performance but also reliability, complexity and effects on procedural languages. The advanced store-through cache with a multi-stage write buffer and an interleaved main memory are seen to have the same performance level as the store-swap cache. When considering data reliability, the advanced store-through cache is judged more suitable for the IPP than the store-swap cache. In a comparison between stack buffer and advanced store-through cache, the stack buffer is found to achieve higher peak performance, but this is affected by the program features. On the other hand, the advanced store-through cache constantly gets high performance for Prolog and procedural languages. As a result, it is concluded that the advanced store-through cache is best suited to the IPP.
Achieving high instruction cache performance with an optimizing compiler
Authors: Hwu W. W. , Chang P. P.
Published: July 2004

Increasing the execution power requires a high instruction issue bandwidth, and decreasing instruction encoding and applying some code improving techniques cause code expansion. Therefore, the instruction memory hierarchy performance has become an important factor of the system performance. An instruction placement algorithm has been implemented in the IMPACT-I (Illinois Microarchitecture Project using Advanced Compiler Technology - Stage I) C compiler to maximize the sequential and spatial localities, and to minimize mapping conflicts. This approach achieves low cache miss ratios and low memory traffic ratios for small, fast instruction caches with little hardware overhead. For ten realistic UNIX
*
programs, we report low miss ratios (average 0.5%) and low memory traffic ratios (average 8%) for a 2048-byte, direct-mapped instruction cache using 64-byte blocks. This result compares favorably with the fully associative cache results reported by other researchers. We also present the effect of cache size, block size, block sectoring, and partial loading on the cache performance. The code performance with instruction placement optimization is shown to be stable across architectures with different instruction encoding density.
The impact of code density on instruction cache performance
Authors: Steenkiste P.
Published: July 2004

The widespread use of reduced-instruction-set computers has generated a lot of interest in the tradeoff between the density of an instruction set and the size of the instruction cache. In this paper we present and justify a method that predicts the cache performance for a wide range of architectures, based on the miss rate for a single architecture. When we apply the method to a number of cache organizations we find that changes in code density can have a dramatic impact on memory traffic, but that modest improvements in code density do not reduce program execution time significantly in a well-balanced system.
Exploring the benefits of multiple hardware contexts in a multiprocessor architecture: preliminary results
Authors: Weber W.-D. , Gupta A.
Published: July 2004

A fundamental problem that any scalable multiprocessor must address is the ability to tolerate high latency memory operations. This paper explores the extent to which multiple hardware contexts per processor can help to mitigate the negative effects of high latency. In particular, we evaluate the performance of a directory-based cache coherent multiprocessor using memory reference traces obtained from three parallel applications. We explore the case where there are a small fixed number (2-4) of hardware contexts per processor and the context switch overhead is low. In contrast to previously proposed approaches, we also use a very simple context switch criterion, namely a cache miss or a write-hit to shared data. Our results show that the effectiveness of multiple contexts depends on the nature of the applications, the context switch overhead, and the inherent latency of the machine architecture. Given reasonably low overhead hardware context switches, we show that two or four contexts can achieve substantial performance gains over a single context. For one application, the processor utilization increased by about 46% with two contexts and by about 80% with four contexts.
Run-time checking in Lisp by integrating memory addressing and range checking
Authors: Sato M. , Ichikawa S. , Goto E.
Published: July 2004

This paper describes the BL addressing mode and the address tag in FLATS2 machine, which is a general-purpose MIMD computer now under construction. The BL addressing mode integrates memory accessing and range checking by hardware. Address tag is a bit in word, which indicates the capability for memory access. Combining them together, efficient memory protection is provided at run-time. It reduces the cost of run-time type checking in Lisp by checking the address tag and the address of a pointer against the range of the region associated to a type, in parallel with the memory access. The arithmetic instructions check the address tags of operands to support the generic arithmetic in Lisp. We can also make use of this scheme to check the number of arguments and multiple return values and to check array-bounds to support faster execution of Common Lisp program. These facilities are not specific to Lisp, so that they can be used more generally than other tagged architectures.
Performance measurements on a commercial multiprocessor running parallel code
Authors: Annaratone M. , Rühl R.
Published: July 2004

The multiprocessor Sequent Symmetry was first delivered to customers with write-through caches. Later on each machine was upgraded with copy-back caches. Because all the other architectural parameters were unchanged (main memory, bus, cache organization and size, and so on), this made it possible to measure the performance of a multiprocessor with no caches, write-through caches, and copy-back caches. We also study the impact that the language (FORTRAN and C) has on the performance of the machine
.
Interprocessor communication speed and performance in distributed-memory parallel processors
Authors: Annaratone M. , Pommerell C. , Rühl R.
Published: July 2004

We have simulated several numerical and non-numerical algorithms on five distributed-memory parallel processors (DMPPs). All five DMPPs have the same topology (a torus), and the same number of nodes. The architectures differ only in the communication speed between neighboring nodes, while the computation unit is kept unchanged. The goal of the paper is to quantify the effect that interprocessor communication speed and synchronization overhead have on the performance of the DMPPs. After introducing the rationale for this study and reviewing related work, we present and discuss the results of the simulations.
R256: a research parallel processor for scientific computation
Authors: Fukazawa T. , Kimura T. , Tomizawa M. , Takeda K. , Itoh Y.
Published: July 2004

A scientific parallel processor called the R256 has been developed. The R256 is composed of 16x16 processing elements, and has the outstanding features of a “distributed parallel network” as well as on IEEE 80-bit extended floating point computation ability. The computation accuracy, required by an exhaustive number of iterations in scientific computations, is resolved by the dedicated 80-bit VLSI processor, which was developed here for the R256. The innovative distributed parallel network was designed so as to effectively resolve heavy communication problems, which are found in applications based on the Monte Carlo simulation technique. The R256 network was very economical at a hardware cost of √
N
-folds (16 folds in this case) to that of an ideal full-crossbar switch, at the same time keeping the rates comparable to that of an ideal switch. The R256 demonstrates high performance of 2-GB/s data transfer rates and 500-MFLOPS computation rates on a semiconductor device simulation application.
Perfect Latin squares and parallel array access
Authors: Kim K. , Prasanna-Kumar V. K.
Published: July 2004

A new nonlinear skewing scheme is proposed for parallel array access. We introduce a new Latin square(perfect Latin square) which has several properties useful for parallel array access. A sufficient condition for the existence of perfect Latin squares and a simple construction method for perfect Latin squares are presented. The resulting skewing scheme provides conflict free access to various subsets of an
N
x
N
array using
N
memory modules. When the number of memory modules is an even power of two, address generation is performed in constant time using a simple circuit. This scheme is the first memory scheme that achieves constant time access to rows, columns, diagonals, and
N
1/2
x
N
1/2
subarrays of an
N
x
N
array using the minimum number of memory modules.
Analysis of vector access performance on skewed interleaved memory
Authors: Chen C.-L. , Liao C.-K.
Published: July 2004

Memory interleaving and memory skewing are two hardware approaches to reduce memory access conflict for many advanced computer architectures, while pipelined vector computer covers many commercially available supercomputers. The goal of this paper is to study the vector accessing behavior on skewed interleaved memory under pipelined processing environment.

We establish a criterion, called average time delay, to indicate the performance of a vector access; and a criterion, called aggregate average time delay to indicate the performance of a given memory system. Under these criteria, we analyze some memory design problems. These problems centralize how to design a memory system which is cost-effective and has less conflicts for vector accesses.

We also propose a software approach to reduce memory access conflict, called dimension extension strategy. This strategy performs very well under our analysis.
A cache consistency protocol for multiprocessors with multistage networks
Authors: Stenström P.
Published: July 2004

A hardware based cache consistency protocol for multiprocessors with multistage networks is proposed. Consistency traffic is restricted to the set of caches which have a copy of a shared block. State information is distributed to the caches and the memory modules need not be consulted for consistency actions.

The protocol provides two operating modes: distributed write and global read. Distribution of writes calls for efficient multicast methods. Communication cost for multicasting is analyzed and a novel scheme is proposed.

Finally, communication cost for the protocol is compared to other protocols. The two-mode approach limits the upperbound for the communication cost to a value considerably lower than that for other protocols.
On data synchronization for multiprocessors
Authors: Su H.-M. , Yew P.-C.
Published: July 2004

As the grain size becomes smaller, more parallelism can be found in most programs. However, to exploit smaller grain parallelism, more efficient synchronization primitives are needed to reduce the increased synchronization overhead. The granularity of parallelism that can be exploited on a multiprocessor system depends heavily on the type and the efficiency of the synchronization supported by the system. For medium-grain parallelism, ordered dependencies such as data dependencies and control dependencies need to be enforced in order to guarantee the correctness of the parallel execution. Hence, data synchronization is one of the major sources of synchronization overhead in the program execution.

In this paper, we classify the synchronization schemes based on how synchronization variables are used. A new scheme, the process-oriented scheme, is proposed. This scheme requires a very small number of synchronization variables and can be supported very efficiently by simple hardware in the system.
A single cached copy data coherence scheme for multiprocessor systems
Authors: Mendelson A. , Pradhan D. K. , Singh A. D.
Published: July 2004

We present and evaluate a snoopy cache memory protocol, the Single Cache Copy Data Coherence (SCCDC), for multiprocessors that allows only a single cache to hold a given share-d data at any time. The simulations presented here indicate that despite its simplicity, the scheme has the potential for good performance comparable with more complex snoopy cache schemes. We have also shown in related work [8] that the existence of only a single copy of data in cache allows efficient access control to shared data by minimizing the overh-ead caused by critical sections. Thus, with low implementation cost, and the efficient support for important operating system functions, the SCCDC scheme appears attractive for multi-user, multi-thread environments where the actual shared rate is modest, and mostly caused by synchronization mechanisms.
Architecture for a multi-user general-purpose parllel system
Authors: Feitelson Dror G. , Rudolph Larry
Published: July 2004

A multi-user general-purpose parallel system can make good use of the available hardware by sharing it among a mix of jobs with complementary requirements. The central task of the operating system in such an environment is to partition the machine dynamically between these jobs. We propose a new control structure to support this task, called
distributed hierarchical control
, which requires additional control processors to be placed on top of the parallel processors. Thus the processors are effectively organized in a tree structure, where the leaves are user processors and the higher levels are used for operating-system work; note that this structure is orthogonal to the interconneetion pattern between the user processors. Operating system algorithms for this structure are outlined.
Efficient emulations of interconnection networks
Authors: Rosenberg Arnold
Published: July 2004

We describe a graph-theoretic framework for comparing the communication powers of competing interconection networks. The framework attempts to determine how efficiently each of the networks can emulate the other
on general computations
(including pipelining). After briefly surveying a number of studies in the literature that use the described framework, we present a case study that illustrates the strengths of the framework. The study comprises three surprisingly efficient emulations by shuffle-oriented networks (such as the
shuffle-exchange
and
deBruijn
networks) of butterfly-oriented networks (such as the
butterfly
and cube-connected cycles networks). Each emulation is efficient in its own way: The first emulates a butterfly network on a like-sized
deBruijn
network, incurring a slowdown that is
exponentially faster
than previous emulations. (We concentrate on the butterfly and
deBruijn
networks in order to minimize constant factors.) The second emulates a large
butterfly
network on a small deBruijnnetwork, in a way that is
work-preserving
, in that the slowdown × processor-count product is preserved. The third emulates a small
butterfly
network on a large deBruijn network, incurring
optimally small slowdown
.
Working set prefetching for cache memories
Authors: Johnson Eric E.
Published: July 2004

A variety of strategies has been proposed for fetching code and data into cache memories before it is explicitly referenced by a processor (prefetching), including both history-based and "prescient" strategies. Here, a strategy is described which treats cache blocks as components of a working set rather than merely as statistically related entities. Extension of this technique to global memory multiprocessors is discussed as a means to reduce memory contention during synchronized phase transitions.
Massage-passing controllerr for a shared-memory multiprocessor
Authors: Lee K.e H. , Lam C. H.
Published: July 2004

Although message-passing is a versatile communication paradigm in the multiprocessing arena [AthSe88], a pure message-passing mechanism via special communication channels is inefficient. Shared-memory multiprocessor systems are usually much cheaper and efficient. Conventional approaches tend to implement message-passing on top of shared-memory architectures using a pure software approach. Even with special techniques [FinHe88], the performance of such systems is still worse than simple shared-memory communication systems. In this paper, we shall present a hardware approach and new message-passing mechanisms that the pure software approach does not support. Such an approach is quite cost effective. The resulting system is suitable for studying concurrent software, scientific computations and distributed problem solving.