bluuebunny/crossref_metadata_2025 huggingface dataset:
A comparison of full and partial predicated execution support for ILP processors
Authors: Mahlke Scott A. , Hank Richard E. , McCormick James E. , August David I. , Hwu Wen-Mei W.
Published: July 2004

One can effectively utilize predicated execution to improve branch handling in instruction-level parallel processors. Although the potential benefits of predicated execution are high, the tradeoffs involved in the design of an instruction set to support predicated execution can be difficult. On one end of the design spectrum, architectural support for full predicated execution requires increasing the number of source operands for all instructions. Full predicate support provides for the most flexibility and the largest potential performance improvements. On the other end, partial predicated execution support, such as conditional moves, requires very little change to existing architectures. This paper presents a preliminary study to qualitatively and quantitatively address the benefit of full and partial predicated execution support. With our current compiler technology, we show that the compiler can use both partial and full predication to achieve speedup in large control-intensive programs. Some details of the code generation techniques are shown to provide insight into the benefit of going from partial to full predication. Preliminary experimental results are very encouraging: partial predication provides an average of 33% performance improvement for an 8-issue processor with no predicate support while full predication provides an additional 30% improvement.
Using hybrid branch predictors to improve branch prediction accuracy in the presence of context switches
Authors: Evers Marius , Chang Po-Yung , Patt Yale N.
Published: July 2004

Pipeline stalls due to conditional branches represent one of the most significant impediments to realizing the performance potential of deeply pipelined, superscalar processors. Many branch predictors have been proposed to help alleviate this problem, including the Two-Level Adaptive Branch Predictor, and more recently, two-component hybrid branch predictors.In a less idealized environment, such as a time-shared system, code of interest involves context switches. Context switches, even at fairly large intervals, can seriously degrade the performance of many of the most accurate branch prediction schemes. In this paper, we introduce a new hybrid branch predictor and show that it is more accurate (for a given cost) than any previously published scheme, especially if the branch histories are periodically flushed due to the presence of context switches.
An analysis of dynamic branch prediction schemes on system workloads
Authors: Gloy Nicolas , Young Cliff , Chen J. Bradley , Smith Michael D.
Published: July 2004

Recent studies of dynamic branch prediction schemes rely almost exclusively on user-only simulations to evaluate performance. We find that an evaluation of these schemes with user and kernel references often leads to different conclusions. By analyzing our own Atom-generated system traces and the system traces from the Instruction Benchmark Suite, we quantify the effects of kernel and user interactions on branch prediction accuracy. We find that user-only traces yield accurate prediction results only when the kernel accounts for less than 5% of the total executed instructions. Schemes that appear to predict well under user-only traces are not always the most effective on full-system traces: the recently-proposed two-level adaptive schemes can suffer from higher aliasing than the original per-branch 2-bit counter scheme. We also find that flushing the branch history state at fixed intervals does not accurately model the true effects of user/kernel interaction.
Correlation and aliasing in dynamic branch predictors
Authors: Sechrest Stuart , Lee Chih-Chieh , Mudge Trevor
Published: July 2004

Previous branch prediction studies have relied primarily upon the SPECint89 and SPECint92 benchmarks for evaluation. Most of these benchmarks exercise a very small amount of code. As a consequence, the resources required by these schemes for accurate predictions of larger programs have not been clear. Moreover, many of these studies have simulated a very limited number of configurations. Here we report on simulations of a variety of branch prediction schemes using a set of relatively large benchmark programs that we believe to be more representative of likely system workloads. We have examined the sensitivity of these prediction schemes to variation in workload, in resources, and in design and configuration. We show that for predictors with small available resources, aliasing between distinct branches can have the dominant influence on prediction accuracy. For global history based schemes, such as GAs and gshare, aliasing in the predictor table can eliminate any advantage gained through inter branch correlation. For self-history based prediction scheme, such as PAs, it is aliasing in the buffer recording branch history, rather than the predictor table, that poses problems. Past studies have sometimes confused these effects and allocated resources incorrectly.
Missing the memory wall
Authors: Saulsbury Ashley , Pong Fong , Nowatzyk Andreas
Published: July 2004

Current high performance computer systems use complex, large superscalar CPUs that interface to the main memory through a hierarchy of caches and interconnect systems. These CPU-centric designs invest a lot of power and chip area to bridge the widening gap between CPU and main memory speeds. Yet, many large applications do not operate well on these systems and are limited by the memory subsystem performance.This paper argues for an integrated system approach that uses less-powerful CPUs that are tightly integrated with advanced memory technologies to build competitive systems with greatly reduced cost and complexity. Based on a design study using the next generation 0.25µm, 256Mbit dynamic random-access memory (DRAM) process and on the analysis of existing machines, we show that processor memory integration can be used to build competitive, scalable and cost-effective MP systems.We present results from execution driven uni- and multi-processor simulations showing that the benefits of lower latency and higher bandwidth can compensate for the restrictions on the size and complexity of the integrated processor. In this system, small direct mapped instruction caches with long lines are very effective, as are column buffer data caches augmented with a victim cache.
The difference-bit cache
Authors: Juan Toni , Lang Tomás , Navarro Juan J.
Published: July 2004

The difference-bit cache is a two-way set-associative cache with an access time that is smaller than that of a conventional one and close or equal to that of a direct-mapped cache. This is achieved by noticing that the two tags for a set have to differ at least by one bit and by using this bit to select the way. In contrast with previous approaches that predict the way and have two types of hits (primary of one cycle and secondary of two to four cycles), all hits of the difference-bit cache are of one cycle. The evaluation of the access time of our cache organization has been performed using a recently proposed on-chip cache access model.
Application and architectural bottlenecks in large scale distributed shared memory machines
Authors: Holt Chris , Singh Jaswinder Pal , Hennessy John
Published: July 2004

Many of the programming challenges encountered in small to moderate-scale hardware cache-coherent shared memory machines have been extensively studied. While work remains to be done, the basic techniques needed to efficiently program such machines have been well explored. Recently, a number of researchers have presented architectural techniques for scaling a cache coherent shared address space to much larger processor counts. In this paper, we examine the extent to which applications can achieve reasonable performance on such large-scale, cache-coherent, distributed shared address space machines, by determining the problems sizes needed to achieve a reasonable level of efficiency. We also look at how much programming effort and optimization is needed to achieve high efficiency, beyond that needed at small processor counts. For each application, we discuss the main architectural bottlenecks that prevent smaller problem sizes or less optimized programs from achieving good efficiency. Our results show that while there are some applications that either do not scale or must be heavily optimized to do so, for most of the applications we studied it is not necessary to heavily modify the code or restructure algorithms to scale well upto several hundred processors, once the basic techniques for load balancing and data locality are used that are needed for small-scale systems as well. Programs written with some care perform well without substantially compromising the ease of programming advantage of a shared address space, and the problem sizes required to achieve good performance are surprisingly small. It is important to be careful about how data structures and layouts interact with system granularities, but these optimizations are usually needed for moderate-scale machines as well.
High-bandwidth address translation for multiple-issue processors
Authors: Austin Todd M. , Sohi Gurindar S.
Published: July 2004

In an effort to push the envelope of system performance, microprocessor designs are continually exploiting higher levels of instruction-level parallelism, resulting in increasing bandwidth demands on the address translation mechanism. Most current microprocessor designs meet this demand with a multi-ported TLB. While this design provides an excellent hit rate at each port, its access latency and area grow very quickly as the number of ports is increased. As bandwidth demands continue to increase, multi-ported designs will soon impact memory access latency.We present four high-bandwidth address translation mechanisms with latency and area characteristics that scale better than a multiported TLB design. We extend traditional high-bandwidth memory design techniques to address translation, developing interleaved and multi-level TLB designs. In addition, we introduce two new designs crafted specifically for high-bandwidth address translation. Piggyback ports are introduced as a technique to exploit spatial locality in simultaneous translation requests, allowing accesses to the same virtual memory page to combine their requests at the TLB access port. Pretranslation is introduced as a technique for attaching translations to base register values, making it possible to reuse a single translation many times.We perform extensive simulation-based studies to evaluate our designs. We vary key system parameters, such as processor model, page size, and number of architected registers, to see what effects these changes have on the relative merits of each approach. A number of designs show particular promise. Multi-level TLBs with as few as eight entries in the upper-level TLB nearly achieve the performance of a TLB with unlimited bandwidth. Piggyback ports combined with a lesser-ported TLB structure,
e.g.,
an interleaved or multi-ported TLB, also perform well. Pretranslation over a single-ported TLB performs almost as well as a same-sized multi-level TLB with the added benefit of decreased access latency for physically indexed caches.
Rotating combined queueing (RCQ)
Authors: Kim Jae H. , Chien Andrew A.
Published: July 2004

Network service guarantees not only provide significant performance benefits to distributed computing systems (more balanced resource utilization, fast fault recovery, and fair network access), but they are also essential for many new applications requiring real-time communications with continuous data types (audio/video). Most existing algorithms which provide network service guarantees are too complicated to be feasible in high-speed, low-cost switches for multicomputer networks. The simpler algorithms proposed provide only limited service guarantees or waste significant network resources.We present a novel, cost-effective queueing and scheduling algorithm, called
Rotating Combined Queueing
(RCQ), which can efficient]y support a range of service guarantees including deterministic delay bounds and bandwidth guarantees in multicomputer networks. By allowing bursty traffic to utilize unused network resources efficiently, RCQ also can provide competitive performance to best-effort data communications. Such cost-effective service guarantees not only provide substantial benefits to the overall system performance, but can also further expand the domain of multicomputer applications to encompass distributed multimedia applications requiring isochronous communications.
Informing memory operations
Authors: Horowitz Mark , Martonosi Margaret , Mowry Todd C. , Smith Michael D.
Published: July 2004

Memory latency is an important bottleneck in system performance that cannot be adequately solved by hardware alone. Several promising software techniques have been shown to address this problem successfully in specific situations. However, the generality of these software approaches has been limited because current architectures do not provide a fine-grained, low-overhead mechanism for observing and reacting to memory behavior directly. To fill this need, we propose a new class of memory operations called
informing memory operations,
which essentially consist of a memory operation combined (either implicitly or explicitly) with a conditional branch-and-link operation that is taken only if the reference suffers a cache miss. We describe two different implementations of informing memory operations---one based on a cache-outcome condition code and another based on low-overhead traps---and find that modern in-order-issue and out-of-order-issue superscalar processors already contain the bulk of the necessary hardware support. We describe how a number of software-based memory optimizations can exploit informing memory operations to enhance performance, and look at cache coherence with fine-grained access control as a case study. Our performance results demonstrate that the runtime overhead of invoking the informing mechanism on the Alpha 21164 and MIPS R10000 processors is generally small enough to provide considerable flexibility to hardware and software designers, and that the cache coherence application has improved performance compared to other current solutions. We believe that the inclusion of informing memory operations in future processors may spur even more innovative performance optimizations.
An educational tool for testing hierarchical multilevel caches
Authors: Gómez Pulido J. A. , Sánchez Pérez J. M. , Moreno Zamora J. A.
Published: July 2004

In this work we present a simulator for a multilevel cache memory system on a monoprocessor environment. It has incorporated a full graphic interface operating on a PC-DOS environment. At first, the simulator was conceived as a tool for applying it to teaching of cache memories. However, the potentiality of the developed system has proved its utility on program analysis and design strategies of memory systems. The above characteristics enable the simulator to be used for designing systems that run optimally a determinate kind of programs and improve the operating mode of a determinate architecture
A discussion on non-blocking/lockup-free caches
Authors: Belayneh Samson , Kaeli David R.
Published: July 2004

In our previous contribution in the June 1996 issue of CAN, we presented a discussion on lockup-free caches. The article raised a couple of issues with the audience, which we will attempt to address in this addendum.
Architectural potholes
Authors: Rosenbaum Mark
Published: July 2004

This column consists of selected traffic from the
comp.arch
newsgroup, a forum for discussion of computer architecture on Internet---an international computer network.
Constructing instruction traces from cache-filtered address traces (CITCAT)
Authors: Rose Charlton D. , Flanagan J. Kelly
Published: July 2004

Instruction traces are useful tools for studying many aspects of computer systems, but they are difficult to gather without perturbing the systems being traced. In the past, researchers have collected instruction traces through various techniques, including single-stepping, instruction inlining, hardware monitoring, and processor simulation. These approaches, however, fail to produce accurate traces because they interfere with the processor's normal execution.Because processors are deterministic machines, their behavior can be predicted if their initial states and external inputs are known. We have developed a technique, called "CITCAT," which exploits this fact to generate nearly perfect instruction traces through trace-driven simulation. CITCAT combines the best features of instruction inlining, hardware monitoring, and processor simulation to produce long, accurate instruction traces without perturbing the system being traced. Because CITCAT instruction traces are computed, rather than stored, this hybrid technique delivers not just accurate traces, but also an extremely efficient trace compression algorithm.
A SIMD computer for multigrid methods
Authors: Martín I. , Tirado F.
Published: July 2004

This paper describes briefly a project for building a highly parallel computer for simulating physical phenomena described by partial differential equations. The special-purpose computer implements multigrid algorithms for solving partial differential equations. We show that the multigrid machine is a good alternative to commercial microprocessor-based parallel computers for running grid-based applications
On cacheability of lock-variables in tightly coupled multiprocessor systems
Authors: Bril Reinder J.
Published: July 2004

This paper presents a discussion of the cacheability of lock variables in tightly coupled multiprocessor systems with private cache memories. It shows that lock operations can give rise to a problem even when the requirement for a memory scheme to be coherent is met. This problem is called the
lock consistency problem
.Several solutions are presented to overcome this problem using standard instructions like test-and-set, and optionally a dedicated unlock (or reset) instruction meant to be used for lock-variables exclusively. The feasibility of these solutions depends on the kind of the interconnection network used (i.e., circuit switching or packet switching) and on how a cache memory may get exclusiveness of a block containing a lock-variable.Finally, it Is shown that the lock consistency problem may be solved independently from the cache consistency problem by distinguishing between lock-blocks and non-lock-blocks, facilitating a separation of concerns.
Designing a high performance parallel logic programming system
Authors: Hermenegildo M. V. , Warren R. A.
Published: July 2004

Compilation techniques such as those portrayed by the Warren Abstract Machine
(WAM)
have greatly improved the speed of execution of logic programs. The research presented herein is geared towards providing additional performance to logic programs through the use of parallelism, while preserving the conventional semantics of logic languages. Two areas to which special attention is given are the preservation of sequential performance and storage efficiency, and the use of low overhead mechanisms for controlling parallel execution. Accordingly, the techniques used for supporting parallelism are efficient extensions of those which have brought high inferencing speeds to sequential implementations. At a lower level, special attention is also given to design and simulation detail and to the architectural implications of the execution model behavior. This paper offers an overview of the basic concepts and techniques used in the parallel design, simulation tools used, and some of the results obtained to date.
Use of instruction set simulators to evaluate the LOW RISC
Authors: Short Brian
Published: July 2004

The LOW RISC has been proposed as an HLL architecture for Prolog. This paper describes the development and use of software simulators for evaluation of the LOW RISC instruction set.
Addressable WSI: a non-redundant approach
Authors: Chesley Gilman
Published: July 2004

A taxonomy of configuration techniques for WSI is discussed and a metric for WSI efficiency is derived. A technique called addressable WSI is described which uses addresses to reference only good modules. By not addressing bad modules, fault-tolerance is achieved without redundancy in the conventional sense. It is argued that memory WSI avoids most of the problems of WSI construction and use.
A basic architecture supporting LGDG computation
Authors: Dai Kechang , Giloi Wolfgang K.
Published: July 2004

In order to combine the benefits of dataflow and control-flow computation while avoiding the pitfalls of both, the authors propose a two-level model of large-grain dataflow computation, called LGDG computation. A formalism has been provided in a previous paper to prove the determinism of parallel program execution under this model. The current paper presents the basic LGDG computer architecture which is organized at two levels, called the graph level and the node level. The kernel of the node-level architecture is characterized by its non-branch RISC (N-RISC) feature, which ensures an optimal utilization of pipeline processing. This kernel is supported by various co-processors based on the principle of function migration. We will show in this paper how the graph-level architecture can be reduced to a matching unit, extended by a writable control store, through node migration and node aggregation. As a result, the matching overhead is drastically reduced, thus eliminating the most severe bottleneck of existing 'fine-grain' dataflow computers.
An efficient caching support for critical sections in large-scale shared-memory multiprocessors
Authors: Min Sang Lyul , Baer Jean-Loup , Kim Hyoung-Joo
Published: July 2004

Directory-based and software-assisted schemes are the two main approaches to solving the cache coherence problem in large scale shared-memory multiprocessors. Until now, the emphasis in software-assisted schemes has been on ascertaining consistency within parallel constructs such as DoAll or DoAcross loops. In this paper, we propose a timestamped-based approach which also allows caching within critical sections. This scheme combines the best features of software-assisted and directory-based cache coherence protocols. It is based on a compile time analysis of interactions among critical sections and execution time local detection of cache incoherence by comparing the times when a variable was last written and last updated in the cache. A quantitative evaluation based on synthetic traces shows that this scheme results in hit ratios almost as high as in directory-based solutions while significantly reducing the network traffic.
Parallel ODE solvers
Authors: van der Houwen P. J. , Sommeijer B. P.
Published: July 2004

We are interested in the efficient solution of linear second order Partial Differential Equation (PDE) problems on rectangular domains. The PDE discretisation scheme used is of Finite Element type and is based on quadratic splines and the collocation methodology. We integrate the Quadratic Spline Collocation (QSC) discretisation scheme with a Domain Decomposition (DD) technique. We develop DD motivated orderings of the QSC equations and unknowns and apply the Preconditioned Conjugate Gradient (PCG) method for the solution of the Schur Complement (SC) system. Our experiments show that the SC-PCG-QSC method in its sequential mode is very efficient compared to standard direct band solvers for the QSC equations. We have implemented the SC-PCG-QSC method on the iPSC/2 hypercube and present performance evaluation results for up to 32 processors configurations. We discuss a type of nearest neighbour communication scheme, in which the amount of data transfer per processor does not grow with the number of processors. The estimated efficiencies are at the order of 90%.
Use of parallel level 3 BLAS in LU factorization on three vector multiprocessors the ALLIANT FX/80, the CRAY-2, and the IBM 3090 VF
Authors: Daydé M. J. , Duff I. S.
Published: July 2004

We show how to transform the B-spline curve and surface fitting problems into suffix computations of continued fractions. Then a parallel substitution scheme is introduced to compute the suffix values on a newly proposed mesh-of-unshuffle network. The derived parallel algorithm allows the curve interpolation through
n
points to be solved in Ο(log
n
) time using Θ
n
/log
n
) processors and allows the surface interpolation through
m
x
n
points to be solved in Ο(log
m
log
n
) time using Θ (
mn
/(log
m
log
n
)) processors. Both interpolation algorithms are cost-optimal for their respective problems. Besides, the surface fitting problem can be even faster solved in Ο(log
m
+ log
n
) time if Θ(
mn
) processors are used in the network.
Cost-optimal parallel B-spline interpolations
Authors: Chung Kuo-Liang , Lin Ferng-Ching , Chen Wen-Chin
Published: July 2004

We show how to transform the B-spline curve and surface fitting problems into suffix computations of continued fractions. Then a parallel substitution scheme is introduced to compute the suffix values on a newly proposed mesh-of-unshuffle network. The derived parallel algorithm allows the curve interpolation through
n
points to be solved in
O
(log
n
) time using Θ(
n
/log
n
processors and allows the surface interpolation through
m
×
n
points to be solved in
O
(log
m
log
n
) time using Θ(
mn
/(log
m
log
n
)) processors. Both interpolation algorithms are cost-optimal for their respective problems. Besides, the surface fitting problem can be even faster solved in
O
(log
m
+ log
n
) time if Θ(
mn
) processors are used in the network.
POSC—a partitioning and optimizing SISAL compiler
Authors: Sarkar Vivek , Cann David
Published: July 2004

Single-assignment languages like SISAL offer parallelism at all levels—among arbitrary operations, conditionals, loop iterations, and function calls. All control and data dependencies are local, and can be easily determined from the program. Various studies of SISAL programs have shown that they contain massive amounts of
potential parallelism
. There are two major challenges in converting this potential parallelism into real speedup on multiprocessor systems. First, it is important to carefully select the
useful parallelism
in a SISAL program, so as to obtain good speedup by trading off parallelism with overhead. Second, it is important to do
sequential optimizations
, so that the sequential components (tasks) of the SISAL program have comparable execution times with sequential languages such as Fortran, Pascal and C. The POSC compiler system described in this paper addresses both issues by integrating previous work on efficient sequential implementation of SISAL programs with previous work on selecting the useful parallelism in a SISAL program. The combined approach is validated by real speedup measurements on a Sequent Balance multiprocessor.
Loop optimization for horizontal microcoded machines
Authors: Bodin François , Charot François
Published: July 2004

Long Instruction Word (LIW) architectures exploit parallelism between various functional units. In order to produce efficient code for such an architecture, the microcode compiler will have to expose a relatively large degree of fine grain parallelism and it will have to take into account the fine level characteristics of the architecture. This paper aims at describing a microcode compiler developed at IRISA for such architectures. After a brief overview of the compilation process, we focus on loop scheduling techniques. The software pipelining algorithm is firstly described. Then a new unrolling-based optimization algorithm is introduced and compared to the classical software pipelining algorithm. This algorithm differs from the traditional loop unrolling algorithm because the unrolling of the loop is only used to find a cyclic scheduling of the loop, then this scheduling allows a software pipelining to be constructed.
On the perfect accuracy of an approximate subscript analysis test
Authors: Klappholz David , Psarris Kleanthis , Kong Xiangyun
Published: July 2004

The Banerjee test is commonly considered to be the more accurate of the two major approximate data dependence tests used in automatic vectorization/parallelization of loops, the other being the GCD test. From its derivation, however, there is no simple explanation of why the Banerjee test should be nearly as accurate as it is given credit for. We present a set of sufficient conditions for the Banerjee test's accuracy, and explain its perceived accuracy in actual practice by proving that under circumstances which occur extremely frequently in actual code, the Banerjee test is, in fact, not approximate, but perfectly accurate.
Performance degradation due to multiprogramming and system overheads in real workloads
Authors: Dimpsey R. T. , Iyer R. K.
Published: July 2004

In this paper, performance degradation specifically due to the multiprogramming (MP) overhead in a parallel execution environment is quantified. In addition, total system overhead is also measured. A methodology, which estimates the MP overhead present in real workloads, is illustrated with real measurements taken on an Alliant FX/80 running Xylem (Cedar's operating system). It is found that MP overhead usually consumes between 10% and 23% of the processing power available to parallel programs. Total system overhead usually consumes between 12% and 30% of the parallel environment processing power, but is found to be as high as 82.1%. The mean MP overhead is determined to be 16% which is well over half the total system overhead executed on the system (the mean system overhead is determined to be 24% of the processing power). It is found that MP overhead, total system overhead, and application completion time are all moderately correlated. Relationships between the characteristics of a workload and the overhead measurements indicate that processor utilization and to a lesser degree paging are moderately correlated with the overhead present in the workload. It is also found that MP overhead is statistically independent of the number of parallel jobs in the system, while total system overhead is not.
Supercomputer performance evaluation and the Perfect Benchmarks
Authors: Cybenko George , Kipp Lyle , Pointer Lynn , Kuck David
Published: July 2004

In the past three years, the Perfect Benchmark

TM

Suite has evolved from a supercomputer performance evaluation plan, presented by Kuck and Sameh at the 1987 International Conference on Supercomputing, to a vigorous international activity. This paper surveys the current state of this supercomputer performance evaluation effort with particular focus on the adopted methodology. While there has been considerable success in achieving the goals of the plan, some issues remain unresolved, and new questions have surfaced.
Elastodynamics on clustered vector multiprocessors
Authors: Zecca V. , Kamel A.
Published: July 2004

We present the parallelization of an elastodynamic code on a firmly coupled configuration consisting of two IBM 3090-600 VF, a total of 12 processors, joined with a connection facility. The programming environment used is Clustered FORTRAN which is a facility for writing and executing parallel programs on two coupled IBM 3090 vector multiprocessors (VMP). Clustered FORTRAN provides extensions to FORTRAN so that a single application program can execute across multiple 3090 systems as well as across the processors of a single 3090 system. To exploit parallelism on each VMP, we used the parallel DO LOOP construct and to exploit parallelism across VMP we used the SCHEDULE statement allowing concurrent execution of subprograms. It is shown that such a problem, characterized by sufficiently large amounts of arithmetic operations within the parallel tasks, can be efficiently parallelized obtaining average speed-ups of more than five on one 3090-600 VF and nearly ten on a two 3090-600 VF cluster with a small programming effort.
Implementation of 5-point/9-point multi-level methods on hypercube architectures
Authors: Eijkhout Victor
Published: July 2004

Computational complexity of implementing 5/9-point multi-level methods on hypercube architectures is considered. The embedding of the nested red/black structures of these methods is described, and an analysis is made of data distances involved
.
Supercomputer-based visualization systems used for analyzing output data of a numerical weather prediction model
Authors: Chen Philip C.
Published: July 2004

Comparison of two supercomputer-based visualization systems developed over a half-year period show that the visualization/animation efficiency is largely dependent upon the efficiencies of individual computers, networking, and memory management.

Using a meteorological database, a case study is presented to illustrate a selection of parameters based on physical laws. Then, three-dimensional animations of selected parameters are made and used for investigating the evolutions of winter cyclone systems. The results indicate an animation with combined parameters that are physically related and reveal important cyclonic development mechanisms that could not have been seen by an animation with an individual parameter.
Parallel automated wire-routing with a number of competing processors
Authors: Takahashi Yoshizo , Sasaki Shigetaka
Published: July 2004

The purpose of the automated wire routing for VLSI and printed circuit board design is to connect a number of terminal pairs distributed throughout wiring plane with net paths which do not intersect each other. Although maze running and line search are well known algorithms used for this purpose, they need a considerable computing time. To reduce it we have developed a new parallel routing algorithm in which a number of processors compete in wiring different nets independent of each other, and one master processor verifies their results and judges. The master processor also delivers an assignment message to the processors. The efficiency of this algorithm was evaluated on a binary-tree multicomputer and more than 50 times of speedup was obtained when 3000 random nets were routed by using 63 processing elements.
Parallelization of FORTRAN code on distributed-memory parallel processors
Authors: Rühl Roland , Annaratone Marco
Published: July 2004

This paper presents some preliminary results toward the automatic parallelization of uniprocessor FORTRAN code on distributed-memory parallel processors (DMPPs). The paper introduces Oxygen, a compiler for a DMPP under development at the Laboratory. The design of Oxygen and its parallelization strategy are discussed, and an analysis of its most significant components is presented, together with performance benchmarks. Oxygen carries out data consistency analysis at run-time; our results show that the overhead introduced is acceptable. Run-time data consistency analysis may also be the only viable approach to parallelize certain “hard” algorithms, as we will show in this study.
Compiler-directed data prefetching in multiprocessors with memory hierarchies
Authors: Gornish Edward H. , Granston Elana D. , Veidenbaum Alexander V.
Published: July 2004

Memory hierarchies are used by multiprocessor systems to reduce large memory access times. It is necessary to automatically manage such a hierarchy, to obtain effective memory utilization. In this paper, we discuss the various issues involved in obtaining an optimal memory management strategy for a memory hierarchy. We present an algorithm for finding the earliest point in a program that a block of data can be prefetched. This determination is based on the control and data dependencies in the program. Such a method is an integral part of more general memory management algorithms. We demonstrate our method's potential by using static analysis to estimate the performance improvement afforded by our prefetching strategy and to analyze the reference patterns in a set of Fortran benchmarks. We also study the effectiveness of prefetching in a realistic shared-memory system using an RTL-level simulator and real codes. This differs from previous studies by considering prefetching benefits in the presence of network contention.
Towards efficient fine-grain software pipelining
Authors: Gao Guang R. , Hum Herbert H. J. , Wong Yue-Bong
Published: July 2004

Dataflow software pipelining
was proposed as a means of structuring fine-grain parallelism and has been studied mostly under an
idealized
dataflow architecture model with infinite resources[9]. In this paper, we investigate the effects of software pipelining under realistic architecture models with finite resources. Our target architecture is the McGill Dataflow Architecture which employs conventional pipelined techniques to achieve fast instruction execution, while exploiting fine-grain parallelism via a data-driven instruction scheduler. To achieve optimal execution efficiency, the compiled code must be able to make a balanced use of both the parallelism in the instruction execution unit and the fine-grain synchronization power of the machine.

A detailed analysis based on simulation results is presented, focusing on two key architectural factors - the fine-grain synchronization capacity and the scheduling mechanism for enabling instructions. On one hand, our results provide experimental evidence that software pipelining is an effective method for exploiting fine-grain parallelism in loops. On the other, the experiments have also revealed the (somewhat pessimistic) fact that even a fully software pipelined code may not achieve good performance if the overhead for fine-grain synchronization exceeds the capacity of the machine.
Pandore
Authors: André Françoise , Pazat Jean-Louis , Thomas Henry
Published: July 2004

The goal of the Pandore system is to allow the execution of parallel algorithms on DMPCs (Distributed Memory Parallel Computers) without having to take into account the low-level characteristics of the target distributed computer to program the algorithm. No explicit process definition and interprocess communications are needed. Parallelization is achieved through logical data organization. The Pandore system provides the user with a mean to specify data partitioning and data distribution over a domain of virtual processors for each parallel step of his algorithm.

At compile time, Pandore splits the original program into parallel processes. Each process will execute some appropriate parts of the original code, according to the given data decomposition. In order to achieve a correct utilization of the data structures distributed over the processors, the Pandore system provides an execution scheme based on a communication layer, which is an abstraction of a message-passing architecture. This intermediate level is them implemented using the effective primitives of the real architecture (in our specific case, an Intel iPSC/2).
Vector performance analysis of the NEC SX-2
Authors: Fatoohi Rod A.
Published: July 2004

This paper presents the results of a series of experiments to study the vector performance of the NEC SX-2. The main object of this study is to understand the architecture and identify its bottlenecks and limiting factors. A simple performance model is used to examine the impact of certain architectural features on the performance of a set of basic operations. The results of implementing this set on the machine for four vector lengths and three memory strides are presented and compared. These results show that the vector length and the ratio of floating point operations to memory references have a great impact on the performance of the machine. Two numerical algorithms are also employed and the results of these algorithms and the basic operations are compared to early results on one processor of the Cray-2 and Cray Y-MP. These comparisons show that the SX-2 is faster than the Cray Y-MP by up to 86% for short vectors and by 2 to 4 times for long vectors. Also, it outperformed the Cray-2 by even bigger factors. Finally, the architecture of the SX-X is presented, and some predictions about its performance are given.
Performance evaluation and prediction for parallel algorithms on the BBN GP1000
Authors: Bodin François , Windheiser Daniel , Jalby William , Atapattu Daya , Lee Mannho , Gannon Dennis
Published: July 2004

The techniques of “load/store” memory reference modeling is based on deriving performance characteristics of the memory architecture of a computer by looking at the behavior of simple sequences of load, store and nop (null operation) instructions. The resulting data base can be used to match load/store templates against algorithm kernels to predict performance or as a source of data for testing analytical models of the architecture. In this paper we study the BBN GP1000 parallel processing system. We show how to build a subset of the load/store kernels needed to characterize the machine and illustrate the behavior of a simple model based on the data.
Access conflicts in multiprocessor memories queueing models and simulation studies
Authors: Bucher Ingrid Y. , Calahan Donald A.
Published: July 2004

The performance of an interleaved common memory accessed uniformly by multiple processors is modeled by queueing methods. The model includes access conflicts at the bank level while assuming an ideal access network.

A scaling relation is derived that is generally valid and indicates that memory access delays are given by the product of the bank reservation time and a function of the memory utilization, which is given by the average number of access requests arriving at a bank per bank reservation time. For light memory traffic, access delays are proportional to the square of the bank reservation time and the ratio of the number of active memory access streams to the number of memory banks.

Assuming random access patterns, an open and a closed queueing model are developed that are validated by simulations. Delay dependence on bank reservation time is quadratic for light loads and linear for very heavy loads.

A heuristic extension of our model for vector accessing of banks in sequential mode is proposed.
A method for parallel program generation with an application to the
Booster
language
Authors: Paalvast Edwin M. , van Gemund Arjan J. , Sips Henk J.
Published: July 2004

This paper describes a translation method for the automatic parallelization of programs based on a separately specified representation of the data. The method unifies the concept of data-representation on the algorithm-level as well as machine-level, based on the so-called view concept. It is shown that given a decomposition of the data, application of the translation method to the view-based
Booster
programming language results in efficient SPMD-code for distributed- as well as shared-memory architectures. It will be argued that the method is not restricted to
Booster
, but can also be applied to other languages.
A run time support system for multiprocessor machines
Authors: Tsoukarellas M. A. , Papatheodorou T. S.
Published: July 2004

We report on the design and development of a Run Time Support System (RTS) which overcomes known disadvantages of other existing systems. The RTS is independent of the configuration - if the system is reconfigured there is no need to change user's processes. It supports both synchronous and asynchronous communication.

A system based on the same design philosophy with this RTS is actually implemented for messages of arbitrary length in the prototype of the PADMAVATI machine, being developed within ESPRIT Project 1219 (967). Experiments were conducted in this environment and performance measurements were obtained and are reported here.
Supercomputing with transputers—past, present and future
Authors: Hey Anthony J. G.
Published: July 2004

The paper traces the development of large multi-transputer systems for high-performance scientific and engineering computing. After defining what we mean by 'supercomputing' in the context of this paper, the past and present state of transputer supercomputing environments is illustrated by a discussion of three specific projects. These are the Esprit 'SuperNode' project or P1085, the Edinburgh Concurrent Supercomputer project and the Victor project at IBM Research in Yorktown Heights. The present parallel programming environments available for transputer systems are also briefly reviewed. The paper concludes with a look to the future. Inmos' announced plans for the next generation transputer, code-named H1, are described along with a comparison with the new Intel iWarp chip. We can classify this Intel component as a 'generic' transputer in that it integrates computing elements, memory elements and communication hardware on a single VLSI chip. Both these new components should make for a bright future for supercomputing with transputer-like building blocks.
A novel trace sampling technique
Authors: Khalid Humayun
Published: July 2004

Trace-driven simulation has been widely used by designers and performance analyst to study and evaluate performance of computer systems. The increasing complexity benchmarks combined with the relatively slow rate of detailed performance analysis has resulted in a widening gap between the size of workloads and the speed of analysis. This has necessitated the use of reduced traces that represent the original workloads. Unfortunately, the existing methods of generating and validating reduced traces does not provide any guarantees regarding the representativeness of such traces. Trace-driven simulations based on unrepresentative reduced/sampled traces may, therefore, produce erroneous timer/simulator results. In this paper, we have presented a new methodology for generating and validating a reduced trace. Experimental results show effectiveness and usefulness of the proposed technique.
NICE
Authors: Ulmann B.
Published: July 2004

The architecture described in the following articel is a direct successor of µ-EP-1 (cf. [1]) and was developed by the author and Robert Linden (Universität Bonn, FB Informatik). NICE is a 32-bit processor, utilizing a fixed instruction format, a register set of sixteen general purpose registers and sat extremely powerful but simple and easy to use instruction set which is supported by a variety of addressing modes. The smallest direct addressable data item in main memory is the 32-bit machine word thus utilizing a simple addressing scheme for instruction operands.The aim of this design is reflected by the acronym "NICE" which means "NICE is charmingly elegant" (Robert Linden).At the moment NICE contains neither any hardware support for memory management nor floating point instructions, but using the instruction selection scheme described below features like these can be added without changing the overall machine design.
LRU-based column-associative caches
Authors: Chung Byung-Kwon , Peir Jih-Kwon
Published: July 2004

The column-associative cache is a direct-mapped cache that may be accessed more than once, each time with a different hash function, to satisfy a memory request. In the column-associative cache, the possible locations that a line can reside in defines the column. The original scheme relies on a rehash bit array to guide the replacement policy within the column. A subsequent proposal uses an index vector to speed up the cache search within the column. In this paper, we consider the idea of using the Least-Recently-Used (LRU) information to guide both the replacement policy and the search order. Results from trace-driven simulations using the SPEC95 benchmark suite show that the LRU-based scheme can achieve better or at least comparable performance.
The effect of instruction fetch bandwidth on value prediction
Authors: Gabbay Freddy , Mendelson Avi
Published: July 2004

Value prediction attempts to eliminate true-data dependencies by dynamically predicting the outcome values of instructions and executing true-data dependent instructions based on that prediction. In this paper we attempt to understand the limitations of using this paradigm in realistic machines. We show that the instruction-fetch bandwidth and the issue rate have a very significant impact on the efficiency of value prediction. In addition, we study how recent techniques to improve the instruction-fetch rate affect the efficiency of value prediction and its hardware organization.