Wednesday, August 30th, Afternoon


Topic 01:
Support Tools and Environments

Session 01-A.1
Topic 01: Support Tools and Environments

Visualization and Computational Steering in Heterogeneous Computing Environments

Sabine Rathmayer

Online visualization and computational steering is an active research issue since quite a few years. The use of high performance scientific applications in heterogeneous computing environments still reveals many problems. With OViD we address problems that arise from distributed applications with no global data access and present additional collaboration features for distributed teams working with one simulation. OViD provides an interface for parallel and distributed scientific applications to send their distributed data to OViD's object pool. Another interface allows multiple visualization systems to attach to a running simulation, access the collected data from the pool, and send steering data back.

A Web-Based Finite Element Meshes Partitioner and Load Balancer

Ching-Jung Liao

In this paper, we present a web-based unstructured mesh partitioner and load balancer (UMPAL). UMPAL is an integrated tool that consists of five components, a partitioner, a load balancer, a simulator, a visualization tool, and a Web interface.

A Framework for an Interoperable Tool Environment

Radu Prodan, John M. Kewley

Software tools have nowadays become indispensable for program development, yet the desire to combine them to provide enhanced functionality has still to be realised. Existing tool environments integrate a number of tools, but do not achieve interoperability and lack extensibility. Integration of new tools can typically necessitate the redesign of the whole system. We describe a new framework for an open tool environment, which facilitates tool development, permits easy tool integration, and allows interoperability. Results consist of a reference model for the system's architecture, a categorisation of supported tools and several interoperability scenarios which need further evaluation.

ToolBlocks: An Infrastructure for the Construction of Memory Hierarchy Analysis Tools

Timothy Sherwood, Brad Calder

In an era dominated by the rapid development of faster and cheaper processors it is difficult both for the application developer and system architect to make intelligent decisions about application interaction with system memory hierarchy. We present ToolBlocks, an object oriented system for the rapid development of memory hierarchy models and analysis. With this system, a user may build cache and prefetching models and insert complex analysis and visualization tools to monitor their performance. A set of commonly used cache and analysis tools are already available, and the system is completely and easily extendible and sharable.

Session 01-A.2
Topic 01: Support Tools and Environments

A Preliminary Evaluation of FINESSE, a Feedback-Guided Performance Enhancement System

Nandini Mukherjee, Graham D. Riley, John R. Gurd

Automatic parallelisation tools implement sophisticated tactics for analysing and transforming application codes but, typically, their ``one-step'' strategy for finding a ``good'' parallel implementation remains naive. In contrast, successful experts at parallelisation attempt to explore the space of possible implementations. Finesse is an environment which supports this exploration by automating many of the tedious steps associated with experiment planning and execution and with the analysis of performance. Finesse also harnesses the sophisticated techniques provided by automatic compilation tools to provide feedback to the user which can be used to guide the exploration. This paper briefly describes Finesse and presents evidence for its effectiveness. The latter has been gathered from the experiences of a small number of users, both expert and non-expert, during their parallelisation efforts on a set of compute-intensive, kernel test codes. The evidence lends support to the hypothesis that users of Finesse can find implementations that achieve performance comparable with that achieved by expert programmers, but in a much shorter time.

On Combining Computational Differentiation and Toolkits for Parallel Scientific Computing

Christian H. Bischof, H. Martin Bücker, Paul D. Hovland

Automatic differentiation is a powerful technique for the evaluation of derivatives of functions defined by computer programs. Here, a program is treated as a sequence of elementary statements to which the chain rule is applied over and over again. Combining automatic differentiation and the organizational structure of toolkits for parallel scientific computing provides a mechanism to exploit mathematical insight on a higher level. Algorithmic structures such as BLAS-like operations, linear and nonlinear solvers, or integrators for ordinary differential equations can be identified by their standardized interfaces and recognized as high-level mathematical objects rather than as a sequence of elementary statements.

Generating Parallel Program Frameworks from Parallel Design Patterns

Steve MacDonald, Duane Szafron, Jonathan Schaeffer, Steven Bromling

Object-oriented programming, design patterns, and frameworks are abstraction techniques that have been used to reduce the complexity of sequential programming. The CO2P3S parallel programming system provides a layered development process that applies these three techniques to the more difficult domain of parallel programming. The system generates correct frameworks from pattern template specifications at the highest layer and provides performance tuning opportunities at lower layers. Each of these features is a solution to a major problem with current parallel programming systems. This paper describes CO2P3S and its highest level of abstraction using an example program to demonstrate the programming model and one of the supported pattern templates. Our results show that the system can be used to quickly generate a correct parallel structure that can be the basis of a parallel program with good performance improvements.


Topic 19:
Metacomputing

Session 19-A.1
Topic 19: Metacomputing

Request Sequencing: Optimizing Communication for the Grid

Dorian C. Arnold, Dieter Bachmann, Jack J. Dongarra

As we research to make the use of Computational Grids seamless, the allocation of resources in these dynamic environments is proving to be very unwieldy. In this paper, we introduce, describe and evaluate a technique we call request sequencing. Request sequencing groups together requests for Grid services to exploit some common characteristics of these requests and minimize network traffic. The purpose of this work is to develop and validate this approach. We show how request sequencing can affect scheduling policies and enable more expedient resource allocation methods.

An Architectural Meta-Application Model for Coarse Grained Metacomputing

Stephan Kindermann, Torsten Fink

The emerging infrastructures supporting transparent use of heterogeneous distributed resources enable the design of a new class of applications. These meta-applications are composed of distributed software components. In this paper we describe a new model for component based meta-application design based on a formal architectural description of the gross organization of an application. This structural description is enriched by a formal process algebraic characterization of component behavior. Using this behavioral model we can formally check meta-applications in an early development phase. We present simple architectural styles developed to support data-flow and control-flow driven meta-application design on top of the Amica metacomputing infrastructure.

Session 19-A.2
Topic 19: Metacomputing

Javelin 2.0: Java-Based Parallel Computing on the Internet

Michael O. Neary, Alan Phipps, Steven Richman, Peter Cappello

Javelin is a Java-based infrastructure for parallel Internet computing. This paper presents Javelin 2.0, focusing on the enhancements that distinguish it from prior versions of Javelin. With regard to architecture, the paper presents enhancements that facilitate aggregating larger sets of host processors. The paper then presents: a branch-and-bound computational model, the supporting Javelin 2.0 architecture, a scalable task scheduler using distributed work-stealing, a distributed eager scheduler, implementing fault tolerance, and the results of performance experiments. Taken as a whole, Javelin 2.0 frees application developers from concerns about complex interprocessor communication and fault tolerance among Internetworked hosts. When all or part of their application can be cast as a piecework or a branch-and-bound computation, Javelin 2.0 allows developers to focus on the underlying application without sacrificing performance.

Data Distribution for Parallel CORBA Objects

Tsunehiko Kamachi, Thierry Priol, Christophe René

The design of application for Computational Grids relies partly on communication paradigms. In most of the Grid experiments, message-passing has been the main paradigm either to let several processes from a single parallel application to exchange data or to allow several applications to communicate between each others. In this article, we advocate the use of a modern approach for programming a Grid. It is based on the use of distributed objects, namely parallel CORBA objects. We focus our attention on the handling of distributed data within parallel CORBA objects. We show some performance results that were obtained using a NEC Cenju-4 parallel machine connected to a PC cluster.

ACCESS: Access to CESCA and CEPBA Supercomputing Facilities through EC Framework V sponsorship

Josep L. Larriba-Pey

t.b.d. (click here for some more information)


Topic 03:
Scheduling and Load Balancing

Session 03-A.1
Topic 03: Scheduling and Load Balancing

A Hierarchical Approach to Irregular Problems

Fabrizio Baiardi, Primo Becuzzi, Sarah Chiti, Paolo Mori, Laura Ricci

Irregular problems require the computation of some properties for a set of elements irregularly distributed in a domain. The distribution may change during the computation in a way that cannot be foreseen in advance. Most irregular problems satisfy a locality property because the properties of an element e depend on the elements "close" to e. We propose a methodology to develop a highly parallel solution based upon a load balancing strategy that respects locality. We also discuss the update of the mapping at run time together with strategies to acquire data on elements mapped onto other processing nodes.

Load Scheduling with Profile Information

Götz Lindenmaier, Kathryn S. McKinley, Olivier Temam

Hardware performance counters in microprocessors can now generate profile data cheaply. Translating aggregate data such as basic block execution frequencies from the executable to the compiler intermediate representation is fairly straight-forward. In this paper, we show how to use Compaq's DCPI tool to determine load latencies which are at a fine, instruction granularity and then use them to provide fodder for improving instruction scheduling. We validate our use of DCPI latency data to classify approximately 75% of loads as hits or misses against simulation numbers, demonstrating that we can gather correct fine grain latencies cheaply at run time. We map our classification into the Multiflow compiler's intermediate representation, and use a locality sensitive Balanced scheduling algorithm. Our experiments illustrate that our algorithm has the potential to improve run times when compared to Balanced scheduling, but that a variety of pitfalls make consistent improvements difficult to attain.

Neighbourhood Preserving Load Balancing: A Self-Organizing Approach

Attila Gürsoy, Murat Atun

We describe a static load balancing algorithm based on Kohonen Self-Organizing Maps (SOM) for a class of parallel computations where the communication pattern exhibits spatial locality and we present initial results. The topology preserving mapping achieved by SOM is used to reduce the communication and a load balancing mechanism is introduced into the SOM algorithm. We also present a preliminary multilevel implementation which resulted in significant improvements. The results are promising to further improve SOM based load balancing for geometric graphs.

Session 03-A.2
Topic 03: Scheduling and Load Balancing

The Impact of Migration on Parallel Job Scheduling for Distributed Systems

Yanyong Zhang, Hubertus Franke, Jose Moreira, Anand Sivasubramaniam

This paper evaluates the impact of task migration on gang-scheduling of parallel jobs for distributed systems. With migration, it is possible to move tasks of a job from their originally assigned set of nodes to another set of nodes, during execution of the job. This additional flexibility creates more opportunities for filling holes in the scheduling matrix. We conduct a simulation-based study of the effect of migration on average job slowdown and wait times for a large distributed system under a variety of loads. We find that migration can significantly improve these performance metrics over an important range of operating points. We also analyze the effect of the cost of migrating tasks on overall system performance.

Memory Management Techniques for Gang Scheduling

William Leinberger, George Karypis, Vipin Kumar

Time-sliced gang scheduling improves the average response time of the jobs in a typical job stream. Recent research has shown that time-slicing is most effective when the jobs admitted for execution fit entirely into physical memory. We investigate two techniques for improving the performance of gang scheduling in the presence of memory pressure: 1) a novel backfill approach which improves memory utilization, and 2) an adaptive multi-programming level which balances processor/memory utilization with job response time performance. Our simulations show that these techniques reduce theslow-down performance metrics over naive FCFS methods on a distributed memory parallel system.

Exploiting Knowledge of Temporal Behaviour in Parallel Programs for Improving Distributed Mapping

Concepció Roig, Ana Ripoll, Miquel A. Senar, Fernando Guirado, Emilio Luque

In the static mapping approach a parallel program is modelled as a task graph characterizing its structure. The models currently in use are the Task Precedence Graph and the Task Interaction Graph. In this paper we use a new model, the Temporal Task Interaction Graph (TTIG), which is automatically generated with a specific tool. The TTIG combines these two previous models by explicitly capturing the temporal behaviour of program tasks. Experimentation was performed in a current PVM environment, for a set of synthetic graphs which exhibit different ratios of computation/communication cost. The execution times when these programs are mapped using the PVM default scheme or using the information contained in the TTIG where compared. The results confirm that with the TTIG model better assignments are obtained, providing improvements of up to 49% compared with the PVM assignments.


Topic 07:
Applications on High-Performance Computers

Session 07-A.1
Topic 07: Applications on High-Performance Computers

An Efficient Algorithm for Parallel 3D Reconstruction of Asymmetric Objects from Electron Micrographs

Robert E. Lynch, Hong Lin, Dan C. Marinescu

We propose a 3D reconstruction algorithm based upon Fourier analysis using Cartesian coordinates. We discuss the accuracy of the algorithm and present comparisons of values computed by a parallel program implementing the algorithm with known solutions. Our results are consistent with the ones produced by a sequential program used for many years for structural biology studies. We report the speedup and the load balancing results for processing cryo-EM data for several viruses. We use a cluster of inexpensive PCs interconnected by a switched Ethernet to carry out the 3D reconstruction. The algorithm is general and can be used for 3D reconstruction of asymmetric objects for applications other than structural biology.

Fast Cloth Simulation with Parallel Computers

Sergio Romero, Luis F. Romero, Emilio L. Zapata

The computational requirements of cloth and other non-rigid solid simulations are high and often the running time is far from real time. In this paper, an efficient solution of the problem on parallel computer is presented. An application, which combines data parallelism with task parallelism has been developed, achieving a good load balancing and minimizing the communication cost. The execution time obtained for a typical problem size, its superlinear speed-up, and the isoscalability shown by the model, will allow to reach real-time simulations in sceneries of growing complexity, using the most powerful multiprocessors.

The Input, Preparation and Distribution of Data for Parallel GIS Operations

Gordon J. Darling, Terence M. Sloan, Connor Mulholland

Geographical Information Systems (GIS) manipulate spatial data. The vector-topological data format retains the topological relationships between geographical features and is commonly used in a range of geographical data analyses. There are a number of characteristics of the format, however, that cause difficulties in the input, manipulation and processing of the data. This paper reports on the performance of a prototype parallel data partitioning algorithm for the input of vector-topological data to parallel processes.

Study of the Load Balancing in the Parallel Training for Automatic Speech Recognition

El Mostafa Daoudi, Pierre Manneback, Abdelouafi Meziane, Yahya Ould Mohamed El Hadj

In this paper we propose a parallel technique of the training phase for automatic speech recognition using the Hidden Markov Models (HMM) which improves the load balancing in the previous proposed parallel implementations. This technique is based on an efficient distribution of sentences of the vocabulary on processors taking into account not only the size of the vocabulary but also the length of each sentence. In this manner the idle time will be reduced. The experimental results show that good performances can be obtained with this distribution

Session 07-A.2
Topic 07: Applications on High-Performance Computers

Pfortran and Co-Array Fortran as Tools for Parallelization of a Large-Scale Scientific Application

Piotr Bala, Terry W. Clark

Parallelization of non-trivial scientific applications remains a nontrivial task typically requiring some programmer assistance. Key considerations for candidate parallel programming paradigms are portability, and intuitive use, at times mutually exclusive features. In this study two similar parallelization tools, Pfortran and Cray's Co-Array Fortran, are discussed in the parallelization of Quantum Dynamics, a non-trivial scientific application.

Sparse Matrix Structure for Dynamic Parallelisation Efficiency

Markus Ast, Cristina Barrado, José M. Cela, Rolf Fischer, Jesús Labarta, Óscar Laborda, Hartmut Manz, Uwe Schulz

The simulated models and requirements of engineering programs like computational fluids dynamics and structural mechanics grow more rapidly than single processor performance. Automatic parallelisation seem to be the obvious approach for huge and historic packages like PERMAS. The approach is based on dynamic scheduling, which is more flexible than domain decomposition, is totally transparent to the end-user and shows good speedups because it is able to extract parallelism where others are not. In this paper we show the need of some preparatory steps on the big input matrices for good performance. We present a new approach for blocking that saves storage and decreases the computation critical path. Also a data distribution step is proposed that drives the dynamic scheduler decisions such that an efficient parallelisation can be achieved even on slow multiprocessor networks. A final and important step is the interleaving of the array blocks that are distributed to different processors. This step is essential to expose the parallelism to the scheduler.

A Multi-color Inverse Iteration for a High Performance Real Symmetric Eigensolver

Ken Naono, Yusaku Yamamoto, Mitsuyoshi Igai, Hiroyuki Hirayama, Nobuhiro Ioki

An implementation of a real symmetric eigensolver on parallel processors is described and evaluated. To achieve better performance in the inverse iteration part, a multi-color framework is introduced, in which the order of the orthogonalizations are rescheduled so that the inverse iterations are executed concurrently. With the blocked tridiagonalization and backtransformation, our real symmetric eigensolver shows good performance and accuracy both on the MPP SR2201 and on the newly developed hybrid machine SR8000.

Parallel Implementation of Fast Hartley Transform (FHT) in Multiprocessor Systems

Felicia Ionescu, Andrei Jalba, Mihail Ionescu

The purpose of this paper is to investigate the efficient parallelization of Fast Hartley Transforn (FHT) algorithm on shared memory multiprocessor systems. The computational dependencies of the sequential FHT algorithm are analyzed, in order to distribute the loops of the algorithm among multiple threads, executed on the available processors of the system. The outer loop of the algorithm carries data dependencies between consecutive iterations and, for parallel execution, synchronization barriers are required. The performances of the parallel FHT algorithm are estimated; the results show a significant speed-up in the parallel execution of the FHT algorithm.


Topic 10:
Programming Languages, Models and Methods

Session 10-A.1: Compilation and Performance Issues
Topic 10: Programming Languages, Models and Methods

HPF vs. SAC - A Case Study

Clemens Grelck, Sven-Bodo Scholz

This paper compares the functional programming language SAC to other data parallel languages, in particular Fortran-90/HPF, with respect to specificational elegance and runtime performance. A well-known benchmark, red/black successive over-relaxation, serves as a case study. After presenting the HPF reference implementation and an initial SAC solution, alternative SAC implementations are discussed that demonstrate the expressive power of the language. Comprehensive performance figures eventually show the ability to compile these highly generic SAC specifications into machine code that clearly outperforms the HPF implementation on a shared memory multiprocessor.

Developing a Communication Intensive Application on the EARTH Multithreaded Architecture

Kevin B. Theobald, Rishi Kumar, Gagan Agrawal, Gerd Heber, Ruppa K. Thulasiram, Guang R. Gao

This paper reports a study of mapping sparse matrix computation, sparse Matrix Vector Multiplication (MVM), on a parallel computing platform based on a fine-grained multithreaded program execution model. Such sparse MVM computation, when parallelized without performing graph partitioning, offers a very high communication to computation ratio, and is well known to have a very limited scalability on traditional distributed memory machines. The particular multithreaded system we use is the EARTH model, which can be implemented from off-the-shelf processors without extensive special hardware support. With the NAS class B input sparse matrix (with 75,000 rows), we observed an absolute speedup of 90 on 120 nodes of a distributed memory configuration. This is achieved without using {\em inspector/executor} or {\em graph partitioning}, or any communication minimization phase, which means that same performance can be achieved on adaptive problems as well. High scalability is achieved because of a number of charactestics of the EARTH architecture: asynchronous execution, low communication overheads, ability to overlap communication and computation and low context-switching costs.

On the Predictive Quality of BSP-Like Cost Functions for NOWs

Mauro Bianco, Geppino Pucci

Networks Of Workstations (NOWs) are a cheaper alternative to achieving high performace over expensive, parallel platforms. The BSP model provides a simple and portable programming discipline that is particularly suitable for coarse-grained parallel systems such as NOWs. We examine the issue of predictivity of the BSP cost model for a NOW consisting of SUN workstations connected through a 10Mbps Ethernet network. In particular, we compare the original BSP cost function with a number of new variants, with the intent of improving predictivity by having the cost function encompass parameters of the hardware/software system which have the largest impact on performance.

Exploiting Data Locality on Scalable Shared Memory Machines with Data Parallel Programs

Siegfried Benkner, Thomas Brandes

OpenMP offers a high-level interface for parallel programming on scalable shared memory (SMP) architectures providing the user with simple work-sharing directives while relying on the compiler to generate parallel programs based on thread parallelism. However, the lack of language features for exploiting data locality often results in poor performance since the non-uniform memory access times on scalable SMP machines cannot be neglected. HPF, the de-facto standard for data parallel programming, offers a rich set of data distribution directives in order to exploit data locality, but has mainly been targeted towards distributed memory machines. In this paper we describe an optimized execution model for HPF programs on SMP machines that avails itself with the mechanisms provided by OpenMP for work sharing and thread parallelism while exploiting data locality based on user-specified distribution directives. This execution model has been implemented in the ADAPTOR HPF compilation system and experimental results verify the efficiency of the chosen approach.

Session 10-A.2: Structured Parallel Programming
Topic 10: Programming Languages, Models and Methods

The Skel-BSP Global Optimizer: Enhancing Performance Portability in Parallel Programming

Andrea Zavanella

The paper describes the Skel-BSP Global Optimizer, a compile-time technique tuning the structure of skeletal programs according to the characteristics of the target architecture. The GO uses a set of optimization rules predicting the costs of each skeleton. The optimization rules refer to a set of implementation templates developed on top of the EdD-BSP (a variant of the BSP model). The paper describes the Program Annotated Tree representation and the set of transformation rules utilized by the GO to modify the starting program. The optimization phases: balancing, scaling and augmenting are presented and explained running the GO on a cluster of PCs for an image analysis toy-program

A Theoretical Framework of Data Parallelism and its Operational Semantics

Philippe Gerner, Eric Violard

We developed a theory in order to address crucial questions of program design methodology. We think that it could unify two concepts of data parallel programming that we consider fundamental as they concern data locality expression: the notions of alignment in HPF and shape in C*. In this article, we aim at measuring the efficiency of programs, and the impact of program transformations on efficiency. For this, we give a formal operational semantics to the statements in the aforementioned theory.

A Pattern Language for Parallel Application Programs

Berna L. Massingill, Timothy G. Mattson, Beverly A. Sanders

A design pattern is a description of a high-quality solution to a frequently occurring problem in some domain. A pattern language is a collection of design patterns that are carefully organized to embody a design methodology. A designer is led through the pattern language, at each step choosing an appropriate pattern, until the final design is obtained in terms of a web of patterns. This paper describes a pattern language for parallel application programs. The goal of our pattern language is to lower the barrier to parallel programming by guiding a programmer through the entire process of developing a parallel program. The main target audience is experienced programmers who may lack experience with parallel programming. The programmer brings to the process a good understanding of the actual problem to be solved, then works through the pattern language to obtain a detailed parallel design or perhaps working code.

Oblivious BSP

J. A. Gonzalez, C. Leon, F. Piccoli, M. Printista, J. L. Roda, C. Rodriguez, F. Sande

A Bulk Synchronous Parallel (BSP) computation consists of a sequence of supersteps, separated by barrier synchronizations. Several authors recognize that a barrier synchronization is expensive in current parallel architectures and propose to expand the BSP software with a zero cost synchronization mechanism, which can be used when the number of messages due to receive is known. This mechanism is usually known as "oblivious synchronization". The use of oblivious synchronizations implies that, opposite to what occurs in the original BSP model, different processors can be in different supersteps at a given time. However, the BSP semantic can be preserved by the underlying BSP software by numbering the supersteps and controlling that, when a message with an invalid number arrives, the receive thread puts it in a queue, where it waits until the correct superstep is reached. An unwanted consequence of these software improvements is a loss of accuracy when using the BSP complexity model to predict the running time. This paper proposes an extension of the BSP complexity model to deal with oblivious barriers and shows its accuracy for a case example.

A Software Architecture for HPC Grid Applications

Steven Newhouse, Anthony Mayer, John Darlington

We introduce a component software architecture designed for demanding grid computing environments that allows the optimal performance of the assembled component applications to be achieved. Performance over the assembled component application is maintained through inter-component static and dynamic optimisation techniques. Having defined an application through both its component task and data flow graphs we are able to use the associated performance models to support application level scheduling. By building grid aware applications through reusable interchangeable software components with integrated performance models we enable the automatic and optimal partitioning of an application across distributed computational resources.


Topic 14:
Instruction-Level Parallelism and Processor Architecture

Session 14-A.1: Instruction Fetch and Memory Access Optimizations
Topic 14: Instruction-Level Parallelism and Processor Architecture

On the Performance of Fetch Engines Running DSS Workloads

Carlos Navarro, Alex Ramírez, Josep-L. Larriba-Pey, Mateo Valero

This paper examines the behavior of current and next generation microprocessors' fetch engines and which parameters of its design are key to overall performance while running DSS workloads. Main fetch engine design decisions are re-evaluated in the context of DSS workloads, and several tradeoffs between them are discussed. In particular, we analyze the effect of the three major aspects that characterize fetch performance, the latency of instructions being fetched, their quality and the number of instructions that the fetch engine provides per access. The second part of our study focuses on the performance benefits of the Software Trace Cache (STC) as a code reordering technique for our DSS workload.

Cost-Efficient Branch Target Buffers

Jan Hoogerbrugge

A typical BTB requires a few kbyte of storage which makes it rather large and, because it is accessed every cycle, rather power consuming. Partial resolution has in the past been proposed to reduce the size of a BTB. A partial resolution BTB stores not all tag bits that would be required to do an exact lookup. The result is a smaller BTB at the price of slightly less accurate branch prediction. This paper proposes to make use of branch locality to reduce the size of a BTB. Short-distance branches need fewer BTB bits than long-distance branches that are less frequent.

Two-Level Address Storage and Address Prediction

Enric Morancho, José María Llabería, Àngel Olivé

The amount of information recorded in the prediction tables of the proposed address predictors turns out to be comparable to the current on-chip cache sizes; for instance, a last-address predictor that records 4.096 64-bit effective addresses uses a 32 Kbytes storage space. Area cost of address predictors is proportional to address width. To reduce their area cost, we will take advantage of the spatial-locality property of the memory references, that is, the high-order bits of several effective addresses recorded in the prediction table are equal. Then, the effective addresses are split in two parts: the high-order bits and the low-order bits. The High-Address Table records the high-order bits and the Low-Address Table records the low-order bits and a link between tables. This organization allows addresses with the same high-order bits to share one entry in the High-Address Table. We use this organization in a last-address predictor and our evaluations show that it produces significant area-cost reductions (28%-60%) without performance losses.

Hashed Addressed Caches For Embedded Pointer Based Codes

Marian Stanca, Stamatis Vassiliadis, Sorin Cotofana, Henk Corporaal

We are proposing a cache addressing scheme based on hashing intended to decrease the miss ratio of small size caches. The main intention is to improve the hit ratio for 'random' patterns pointer memory accesses for embedded (special purpose) system applications. We introduce a hashing scheme, denoted as bit juggling, and measure the effect such a scheme has in the cache access miss ratio. It is shown, for the considered benchmark, that 3-bit bit juggling will reduce the miss ratio for up to 12\%, for associative caches of maximum size of 8KBytes when compared to usual cache addressing schemes.

Session 14-A.2: ILP and Arithmetic Unit Performance Optimizations
Topic 14: Instruction-Level Parallelism and Processor Architecture

BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations

Mihai Budiu, Majd Sakr, Kip Walker, Seth Copen Goldstein

Many important applications perform computations on values of non-standard bit-width; mapping them to word-based processing units is wasteful of resources and results in suboptimal performance. While there are processor architectures which take advantage of varying bit-widths, compiler optimizations lag far behind. We present BitValue, a compiler algorithm which infers reduced widths and discovers constant bits. BitValue performs a forward analysis, which finds constant bits and bits independent of the inputs and a backward analysis, which discovers bits unused by the output. BitValue inference can determine that on average 25% of the bit computations are unnecessary for programs from MediaBench and SPEC95.

General Matrix-Matrix Multiplication Using SIMD Features of the PIII

Douglas Aberdeen, Jonathan Baxter

Generalised matrix-matrix multiplication forms the kernel of many mathematical algorithms. A faster matrix-matrix multiply immediately benefits these algorithms. In this paper we implement efficient matrix multiplication for large matrices using the floating point Intel Pentium SIMD architecture. A description of the issues and our solution is presented, paying attention to all levels of the memory hierarchy. Our results demonstrate an average performance of 1.8 times faster than the leading public domain matrix-matrix multiply routines and comparable performance with Intel's SIMD small matrix-matrix multiply routines.

Redundant Arithmetic Optimizations

Thomas Y. Yéh, Hong Wang

In general, redundant arithmetic speeds up truly dependent arithmetic computations by eliminating unnecessary conversions between intermediate and two's complement forms. Also, it enables a shorter clock cycle by reducing addition latency. Intermediate values during computations are expressed in redundant number representations that use multiple bits to indicate the value of a single digit. By exploiting the dependency of selected operations, significant speedup can be obtained by removing excess sub-operations (conversions). This approach has been extensively explored in the field of DSP and floating-point operations. The carry-free characteristic of redundant arithmetic provides a scalable solution for addition of increased data path width for 64 bit processors. Optimal scheduling for redundant arithmetic requires operand redundancy, opcode, and dependency information. We present the novel concept of the extended carry-save optimization to improve the performance of redundant processing. We also examine the effectiveness of redundant processing by exploring the issue of instruction scheduling. Finally, the framework and methodologies currently used for analysis will be described. Initial data on the potential speedup will be presented while more details are currently being gathered for further analysis.

The Decoupled-Style Prefetch Architecture

Kevin D. Rich, Matthew K. Farrens

Data prefetching is an attractive way to limit the impact of memory latency by reducing the frequency of cache misses. Decoupled processing seeks to dynamically schedule memory accesses in order to tolerate memory latency by prefetching operands. Since decoupled processors can not speculatively issue memory operations, control flow operations can significantly impact their ability to prefetch data. The prefetching architecture proposed here seeks to leverage the dynamic scheduling benefits of decoupled processing while allowing memory operations to be speculatively invoked. Evaluations using the SPEC95 benchmarks resulting in speed-ups of over 40% of peak for most of the inputs.

Exploiting Java Bytecode Parallelism by Enhanced POC Folding Model

Lee-Ren Ton, Lung-Chung Chang, Chung-Ping Chung

Instruction-level parallelism of stack codes like Java is severely limited by accessing the operand stack sequentially. To resolve this problem, our earlier works have presented stack operations folding to reduce the number of push/pop operations in between the operand stack and the local variable. In those studies, Java bytecodes are classified into three major POC types. Statistical data indicates that the 4-foldable strategy of the POC folding model can eliminate 86% of push/pop operations. In this paper, we propose an Enhanced POC (EPOC) folding model to eliminate more than 99% of push/pop operations with an instruction buffer size of 8 bytes and the same 4-foldable strategy. The average issued instructions per cycle for a single pipelined architecture is further enhanced from 1.70 to 1.87.


Thursday, August 31st, Morning


Topic 02:
Performance Evaluation and Prediction

Session 02-B.1: Performance Diagnosis Tools
Topic 02: Performance Evaluation and Prediction

A Callgraph-Based Search Strategy for Automated Performance Diagnosis

Harold W. Cain, Barton P. Miller, Brian J.N. Wylie

We introduce a new technique for automated performance diagnosis, using the program's callgraph. We discuss our implementation of this diagnosis technique in the Paradyn Performance Consultant. Our implementation includes the new search strategy and new dynamic instrumentation to resolve pointer-based dynamic call sites at run-time. We compare the effectiveness of our new technique to the previous version of the Performance Consultant for several sequential and parallel applications. Our results show that the new search method performs its search while inserting dramatically less instrumentation into the application, resulting in reduced application perturbation and consequently a higher degree of diagnosis accuracy.

Automatic Performance Analysis of MPI Applications Based on Event Traces

Felix Wolf, Bernd Mohr

This article presents a class library for detecting typical performance problems in event traces of MPI applications. The library is implemented using the powerful high-level trace analysis language EARL and is embedded in the extensible tool component EXPERT described in this paper. One of EXPERT's essential features is a flexible plug-in mechanism which allows the user to easily integrate performance problem descriptions specific to a distinct parallel application without modifying the tool component.

Pajé: An Extensible Environment for Visualizing Multi-threaded Programs Executions

Jacques Chassin de Kergommeaux, Benhur de Oliveira Stein

This paper describes Pajé, an interactive visualization tool for displaying the execution of parallel applications where a (potentially) large number of communicating threads of various life-times execute on each node of a distributed memory parallel system. Pajé is capable of representing a wide variety of interactions between threads. The main novelty of Pajé is an original combination of three of the most desirable properties of visualisation tools for parallel programs: extensibility, interactivity and scalability. This article mainly focuses on the extensibility property of Pajé. To be easier to extend, Pajé was designed as a data-flow graph of modular components, most of them being independent of the semantics of the parallel programming model of the visualized parallel programs. In addition, application programmers can tailor the visualization to their needs, without having to know any insight nor to modify any component of Pajé.

Session 02-B.2: Performance Prediction and Analysis
Topic 02: Performance Evaluation and Prediction

A Statistical-Empirical Hybrid Approach to Hierarchical Memory Analysis

Xian-He Sun, Kirk W. Cameron

We present a hybrid version of two previous models that perform analysis of memory hierarchies. The original statistical model provides insight into code performance by statistically analyzing the differing parameters across two similar machines. By focusing on statistical differences, the original model provides the ability to isolate performance degradation causes. The original empirical model provides insight into code performance by empirically inferring the stall time actually incurred within codes due to non-overlapped memory accesses. In this way, it quantifies the performance gain and loss due to recently introduced latency hiding techniques. In these ways, both methods have been used to dissect the execution time of scientific applications. In this paper, we combine the positive attributes of both models by interleaving the analysis methods. Furthermore, we analytically link the models to provide a more focused method for analyzing performance contributions due to latency hiding techniques such as outstanding misses and speculative execution.

Use of Performance Technology for the Management of Distributed Systems

D.J. Kerbyson, J.S. Harper, E. Papaefstathiou, D.V. Wilcox, G.R. Nudd

This paper describes a toolset, PACE, that provides detailed predictive performance information throughout the implementation and execution stages of an application. It is structured around a hierarchy of performance models that describes distributed computing systems in terms of its software, parallelisation and hardware components, providing performance information concerning expected execution time, scalability and resource use of applications. A principal aim of the work is to provide a capability for rapid calculation of relevant performance numbers without sacrificing accuracy. The predictive nature of the approach provides both pre- and post- implementation analyses, and allows implementation alternatives to be explored prior to the commitment of an application to a system. Because of the relatively fast analysis times, these techniques can be used at run-time to assist in application steering and efficient management of the available system resources.

Delay Behavior in Domain Decomposition Applications

Marco Dimas Gubitoso, Carlos Humes, Jr.

This paper addresses the problem of estimating the total execution time of a parallel program based domain decomposition. When the execution time of each processor may vary, the total execution time is non-deterministic, specially if the communication to exchange boundary data is asynchronous. We consider the situation where a single iteration on each processor can take two different execution times. We show that the total time depends on the topology of the interconnection network and provide a lower bound for the ring and the grid. This analysis is supported further by a set of simulations and comparisons of specific cases.


Topic 05:
Parallel and Distributed Databases and Applications

Session 05-B.1
Topic 05: Parallel and Distributed Databases and Applications

Database Replication Using Epidemic Communication

JoAnne Holliday, Divyakant Agrawal, Amr El Abbadi

There is an increasing interest in asynchronous replica management protocols in which database transactions are executed locally, and the effects of these transactions are incorporated asynchronously on remote database copies. However, the asynchronous protocols currently in use either do not guarantee consistency and serializability as needed by transactional semantics or they impose restrictions on placement of data and on which data objects can be updated. In this paper we investigate an epidemic update protocol that guarantees consistency and serializability in spite of a write-anywhere capability and conduct simulation experiments to evaluate this protocol. Our results establish that this epidemic approach is indeed a viable alternative to traditional eager update protocols for a distributed database environment where consistency and full serializability are needed.

Evaluating the Coordination Overhead of Replica Maintenance in a Cluster of Databases

Klemens Böhm, Torsten Grabs, Uwe Röhm, Hans-Jörg Schek

We investigate the design of a coordinator for a cluster of databases. We consider the following alternatives: TP-Heavy using the TUXEDO TP-monitor, TP-Lite with the ORACLE 8 database system, and a TP-Less coordinator implemented in Embedded SQL/C++. In more detail, assuming full replication, we investigate the scalability characteristics of the design alternatives with regard to parallel synchronous replication management. It turns out that the TP-Less approach outperforms commercial TP-middleware for small cluster sizes already. Another observation is that synchronous actions within asynchronous two-level transactions should be avoided.

A Communication Infrastructure for a Distributed RDBMS

Michael Stillger, Dieter Scheffner, Johann-Christoph Freytag

We present the concept and implementation of a communication infrastructure for a distributed database system. Within this model we use system components that build a federated multi agent systems (MASs).This work evolved as part of the AQuES project, an agent-based database query evaluation system. First we briefly describe basic concepts for MAS architectures which were smoothly integrated within our new model.Second, we present those parts of the message transport layer which provide an ``easy to handle'', scalable architecture based on the ``p&p'' building block principle. Furthermore we show how the query answering process can be broken up into parts of a complex dialog among distributed subagents. We present a generic dialog manager as part of the message transport layer that enables each individual agent to communicate with the system in multiple concurrent threads of execution. Based on this concept, AQuES agents keep track of the complex evaluation environment in a dynamic, multi-query scenario. Finally, we use a query execution example that demonstrates the communication flow of messages that occurs within and among the AQuES federations.

Distribution, Replication, Parallelism and Efficiency Issues in a Large-Scale Online/Real-Time Information System for Foreign Exchange Trading

Peter Peinl

Design and implementation of a large-scale online/real-time information system for the foreign exchange section of a major world-wide bank, used by hundreds of traders, is described. From the system designer's view, this is a large-scale distributed client/server application. It is shown, how much the specific requirements of data replication and parallel processing matched with the paradigms and features of common off-the-shelp components and why proprietary implementation sometimes seemed inevitable. It is further shown, how the properties of the application, combined with performance requirements, lead to the specific distribution of functionality and processing between the client and server side, resulting in an interesting new calculation scheme on the client side. Some important lessons learnt are reported.


Topic 18:
Cluster Computing

Session 18-B.2
Topic 18: Cluster Computing

Partition Cast - Modelling and Optimizing the Distribution of Large Data Sets in PC Clusters

Felix Rauch, Christian Kurmann, Thomas M. Stricker

Multicasting large amounts of data efficiently to all nodes of a PC cluster is an important operation. In the form of a partition cast it can be used to replicate entire software installations by cloning. Optimizing a partition cast for a given cluster of PCs reveals some interesting architectural tradeoffs, since the fastest solution does not only depend on the network speed and topology, but remains highly sensitive to other resources like the disk speed, the memory system performance and the processing power in the participating nodes. We present an analytical model that guides an implementation towards an optimal configuration for any given PC cluster. The model is validated by measurements on our cluster using Gigabit- and Fast Ethernet links. The resulting simple software tool, Dolly, can replicate an entire 2 GB Windows NT image onto 24 machines in less than 5 minutes.

A New Home-Based Software DSM Protocol for SMP Clusters

Weiwu Hu, Fuxin Zhang, Haiming Liu

As SMP clusters are emerging to be attractive platforms for parallel processing, it is natural to extend the convenient shared address programming model of SMP with software DSM on SMP clusters. This paper introduces an SMP protocol for the home-based software DSM system JIAJIA. In the protocol, intra-node processes in an SMP node share their home pages through hardware coherent sharing so as to take the full advantage of the home effect of home-based software DSMs, i.e., the ability to dispense with page faults for references made by the home node of a given page. In contrast, cached remote pages of a process are not shared by its intra-node partners for the similar reason of separate hardware caches in processors of an SMP. Besides, JIAJIA also implements the shared memory communication among processes within the same SMP node to accelerate intra-node communication. Performance evaluation with some well accepted benchmarks and real applications in a cluster of four two-processor nodes shows that the SMP protocol of JIAJIA reduces remote accesses, diffs, and consequently message amounts in all of the ten benchmarks and as a result obtains noticeable performance improvement in seven.

Encouraging the Unexpected: Cluster Management for OS and Systems Research

Ronan Cunniffe, Brian A. Coghlan

A framework for cluster management is proposed that enables a cluster to be more efficiently utilized within a research environment. It does so by removing cluster management to a management node, leaving the compute nodes as essentially bare machinery. Users may schedule access to one or more of the compute nodes via the management node. At the scheduled time, a previously-saved image of their research environment will be loaded, and the session begun. At the end of the session the user may save a new image of the environment on the management node, to be reloaded at another time. Thus the user may work with a customized environment, which may even be a fledgling operating system, without fear of interference to other researchers. This enables the capital investment of a systems research cluster to be amortized over a greater number of researchers.


Topic 03:
Scheduling and Load Balancing

Session 03-B.1
Topic 03: Scheduling and Load Balancing

Preemptive Task Scheduling for Distributed Systems

Andrei Radulescu, Arjan J.C. van Gemund

Task scheduling in a preemptive runtime environment has potential advantages over the non-preemptive case such as better processor utilization and more flexibility when scheduling tasks. Furthermore, preemptive approaches may need less runtime support (e.g. no task ordering required). In contrast to the non-preemptive case, preemptive task scheduling in a distributed system has not received much attention. In this paper we present a low-cost algorithm, called the Preemptive Task Scheduling algorithm (PTS), which is intended for compile-time scheduling of coarse-grain problems in a preemptive distributed-memory system. We show that we can obtain performance comparable to the performance of non-preemptive algorithms on non-preemptive systems. However, the advantage of using our scheme is that the runtime support for our approach is much simpler, since no task ordering is necessary.

Towards Optimal Load Balancing Topologies

Thomas Decker, Burkhard Monien, Robert Preis

Many load balancing algorithms balance the load according to a topology. Its choice can significantly influence the performance of the algorithm. We consider the two phase balancing model. The first phase calculates a balancing flow with respect to this topology by a diffusion scheme. Its time requirement depends on the maximum node degree and on the number of eigenvalues of the network. The second phase migrates the load according to this flow. A small flow volume and a small diameter of the graph keeps the time requirement of this phase low. We compare and propose several network topologies based on these measurements. Several experiments on a Cray T3E and on a cluster of PCs confirm our cost functions for both balancing phases.

Scheduling Trees with Large Communication Delays on Two Identical Processors

Foto Afrati, Evripidis Bampis, Lucian Finta, Ioannis Milis

We consider the problem of scheduling trees on two identical processors in order to minimize the makespan. We assume that tasks have unit execution times, and arcs are associated with large identical communication delays. We prove that the problem is NP-hard in the strong sense even when restricted to the class of binary trees, and we provide a polynomial-time algorithm for complete binary trees.

Session 03-B.2
Topic 03: Scheduling and Load Balancing

Parallel Multilevel Algorithms for Multi-constraint Graph Partitioning

Kirk Schloegel, George Karypis, Vipin Kumar

Sequential multi-constraint graph partitioning algorithms have been developed to address the load balancing requirements of multi-phase simulations. The efficient execution of large multi-phase simulations on high performance parallel computers requires that the multi-constraint partitionings are computed in parallel. This paper presents a parallel formulation of a recently developed multi-constraint graph partitioning algorithm. We describe this algorithm and give experimental results conducted on a 128-processor Cray T3E. We show that our parallel algorithm is able to efficiently compute partitionings of similar quality to serial multi-constraint algorithms, and can scale to very large graphs.

Experiments with Scheduling Divisible Tasks in Clusters of Workstations

Maciej Drozdowski, Pawel Wolniewicz

We present results of a series of experiments with parallel processing divisible tasks on various cluster of workstations platforms. Divisible task is a new model of scheduling distributed computations. It is assumed that the parallel application can be divided into parts of arbitrary sizes and the parts can be processed independently on distributed computers. The experiments were performed on various applications and distributed computing platforms. Though practical verification of the divisible task scheduling model was the primary goal of the experiments also an insight into the behavior and performance of cluster computing platforms has been gained.

Optimal Mapping of Pipeline Algorithms

Daniel González, Francisco Almeida, Luz Marina Moreno, Casiano Rodríguez

The optimal assignment of computations to processors is a crucial factor determining the effectiveness of a parallel algorithm. We analyze the problem of finding the optimal mapping of a pipeline algorithm on a ring of processors. There are too many variables to consider, the number of virtual processes to be simulated by a physical processor and the size of the packets to be communicated. We provide an analytical model for an optimal approach to these elements. The low errors observed and the simplicity of our proposal makes this mechanism suitable for its introduction in a parallel tool that com-pute the parameters automatically at running time.

Dynamic Load Balancing for Parallel Adaptive Multigrid Solvers with Algorithmic Skeletons

Thomas Richert

Algorithmic skeletons are polymorphic higher-order functions that represent common parallelization patterns. They can be used as the building blocks of parallel applications by integrating them into a sequential language. In this paper we present a parallel implementation of a skeleton-based dynamic load balancing algorithm for parallel adaptive multigrid solvers. It works on refinement trees that arise during adaptive refinement of grids. Furthermore, we discuss properties of the algorithm and compare the used skeletons with a low-level message passing implementation.


Topic 11:
Numerical Algorithms for Linear and Nonlinear Algebra

Session 11-B.1: Numerical Linear Algebra
Topic 11: Numerical Algorithms for Linear and Nonlinear Algebra

Ahnentafel Indexing into Morton-Ordered Arrays, or Matrix Locality for Free

David S. Wise

Definitions for the uniform representation of matrices serially in Morton-order (or Z-order) support both their use with cartesian indices, and their divide-and-conquer manipulation as quaternary trees. This data structure is important because, at once, it relaxes serious problems of locality and latency, and the tree helps schedule multi-processing. It enables algorithms that avoid cache misses and page faults at all levels in hierarchical memory, independently of a specific runtime environment. This paper gathers the properties of Morton order and its mappings to other indexings, and outlines for compiler support of it. Statistics elsewhere show that the new ordering and block algorithms achieve high flop rates and, indirectly, parallelism without any low-level tuning.

An Efficient Parallel Linear Solver with a Cascadic Conjugate Gradient Method: Experience with Reality

Peter Gottschling, Wolfgang E. Nagel

To solve large linear equations with sparse matrices in parallel, there are three factors that contribute to the compute time: the numerical efficiency, the floating point performance and the scalability. On large linear equations, multi-level techniques, like the cascadic conjugate gradient method, require significantly less operations than single-level methods. To yield a fast, massively parallel multi-level solver, we used the fastest available communication and revised the whole computation. The performance improvements contributed to a parallel solver which is able to solve a set of linear equations with more than 16 millions of unknowns in 0.77 seconds on 256 PEs of a Cray T3E. This corresponds to an overall performance of 10.34 GFLOPS.

Session 11-B.2: Algorithms for Partial Differential Equations
Topic 11: Numerical Algorithms for Linear and Nonlinear Algebra

A Fast Solver for Convection Diffusion Equations Based on Nested Dissection with Incomplete Elimination

Michael Bader, Christoph Zenger

We present an approach for the efficient parallel solution of convection diffusion equations. Our solver extends existing iterative nested dissection algorithms by additional elimination of the unknowns. The elimination strategy is derived from physical properties of the convection diffusion equation, but is independent of the discretized operator. The memory requirement of the resulting algorithm grows linearly with the number of unknowns. This also holds for the computational costs for the setup and the relaxation cycles. Numerical examples indicate that the required number of iterations grows only slightly with the number of unknowns, but is independent of the convection field.

Low Communication Parallel Multigrid -- A Fine Level Approach

Marcus Mohr

The most common technique for the parallelization of multigrid methods is grid partitioning. For such methods Brandt and Diskin have suggested the use of a variant of segmental refinement in order to reduce the amount of inter--processor communication. A parallel multigrid method with this technique avoids all communication on the finest grid levels. This article will examine some features of this class of algorithms as compared to standard parallel multigrid methods. In particular, the communication pattern will be analyzed in detail.

Parallelizing an Unstructured Grid Generator with a Space-Filling Curve Approach

Jörn Behrens, Jens Zimmermann

A new parallel load distribution algorithm for unstructured parallel grid generation is presented. This new approach is based on a space-filling curve. The space-filling curve's indices are calculated recursively and in parallel, thus leading to a very efficient, and fast load distribution. The partitions resulting from this distribution are simply connected and the processor boundaries are sufficiently short.


Topic 10:
Programming Languages, Models and Methods

Session 10-B.1: Distributed Applications and Java
Topic 10: Programming Languages, Models and Methods

Satin: Efficient Parallel Divide-and-Conquer in Java

Rob V. van Nieuwpoort, Thilo Kielmann, Henri E. Bal

Satin is a system for running divide and conquer programs on distributed memory systems (and ultimately on wide-area metacomputing systems). Satin extends Java with three simple Cilk-like primitives for divide and conquer programming. The Satin compiler and runtime system cooperate to implement these primitives efficiently on a distributed system, using work stealing to distribute the jobs. Satin optimizes the overhead of local jobs using on-demand serialization, which avoids copying and serialization of parameters for jobs that are not stolen. This optimization is implemented using explicit invocation records. We have implemented Satin by extending the Manta compiler. We discuss the performance of four applications on a Myrinet-based cluster.

Implementing Declarative Concurrency in Java

Rafael Ramirez, Andrew E. Santosa, Lee Wei Hong

We describe the implementation of a high-level language based on first order logic for expressing synchronization in multi-threaded Java programs. The language allows the programmer to declaratively state the system safety properties as temporal constraints on specific program points of interest (events). The constraints are enforced by the run-time environment, i.e. the program points of interest are traversed only in the order specified by the constraints. The implementation is based on the incremental and lazy generation of partial orders among events. Although the implementation reported in this paper is concerned only with the synchronization of Java programs, the general underlying synchronization model we present is language independent in that it allows the programmer to glue together separate concurrent threads regardless of their implementation language and application code.

Building Distributed Applications using Multiple, Heterogeneous Environments

Paul A. Gray, Vaidy S. Sunderam

There continues to be genuine interest in expanding application environments to include geographically-distributed resources and to be able to dynamically re-configure the environment to suit the needs of the application. The expansion of an application's resource pool and dynamicity of the environment introduces fresh nuances in programming paradigms and demands novel characteristics of the substrate exportable to the application. This paper describes our research efforts toward the goal of providing applications with such an environment within the IceT project.

Session 10-B.2: Efficient Implementation Techniques
Topic 10: Programming Languages, Models and Methods

A Multiprotocol Communication Support for the Global Address Space Programming Model on the IBM SP

Jarek Nieplocha, Jialin Ju, T. P. Straatsma

As SMP clusters are becoming increasingly popular, effective communication strategies are needed to take full advantage of this architecture. This paper addresses the SMP-aware communication support for global address space programming model on the IBM SP, a representative example of commercially available SMP-based clusters. Our solution integrates shared memory with active messages, threads and remote memory copy between nodes. The shared memory operations offer substantial performance improvement over LAPI, IBM one-sided communication library, within an SMP node. Based on the experiments with SPLASH-2 LU benchmark and a molecular dynamics simulation, our multiprotocol support for global address space is found to improve performance and scalability of applications.

A Comparison of Concurrent Programming and Cooperative Multithreading

Takashi Ishihara, Tiejun Li, Eugene F. Fodor, Ronald A. Olsson

This paper presents a comparison of the cooperative multithreading models with the general concurrent programming model. It focuses on the execution time performance of a range of standard concurrent programming applications. The results show that in many, but not all, cases programs written in the cooperative multithreading model outperform those written in the general concurrent programming model. The contributions of this paper are a thorough analysis of the performances of applications in the different models and an examination of the parallel cooperative multithreading programming style.

The Multi-architecture Performance of the Parallel Functional Language GPH

Philip W. Trinder, Hans-Wolfgang Loidl, Ed Barry, Jr., M. Kei Davis, Kevin Hammond, Ulrike Klusik, Simon L. Peyton Jones, Álvaro J. Rebón Portillo

In principle functional languages promise straightforward architecture-independent parallelism, because of their high level description of parallelism, dynamic management of parallelism and deterministic semantics. However, these language features come at the expense of a sophisticated compiler and/or runtime-system. The problem we address is whether such an elaborate system can deliver acceptable performance on a variety of parallel architectures. In particular we report performance measurements for the GUM runtime-system on eight parallel architectures, including massively parallel, distributed-memory, shared-memory and workstation networks.


Topic 08:
Parallel Computer Architecture

Session 08-B.2
Topic 08: Parallel Computer Architecture

Coherency Behavior on DSM: A Case Study

Jean-Thomas Acquaviva, William Jalby

This paper addresses characterization of coherency traffic in shared memory scientific applications. In particular, we are focusing on intrinsic (i.e. architecture independent) coherency properties of scientific codes. The major goal of this study is to understand coherency behavior, in particular to determine correlations between the the activities of the key components: processors, cache lines, loops and so on. Based on a systematic experimentation study on the well known Splash 2 benchmarks, we discovered a few key properties of coherency behavior: unbalanced spread of coherency events over memory space, spatial properties of coherency events, data sharing patterns, concentration of coherency events on a very few loops, etc. Characterizing properly these properties is essential for both restructuring applications to improve coherency behavior and/or design new cost effective coherency mechanisms. Consequently, as a result of our characterization we propose various research directions for improving performance of coherency actions.

Hardware Migratable Channels

David May, Henk Muller, Shondip Sen

In this paper we revisit the hardware implementation of channels. Channels as an essential part of the processors instruction set were first launched with the Transputer. Here we have revisited them and have made two major alterations: we have changed the semantics of the input and output instructions in order to overlap communication, and we allow channels to be communicated over channels (higher order communications). We show that all of those operations can be easily implemented in hardware.

Reducing the Replacement Overhead on COMA Protocols for Workstation-Based Architectures

Diego R. Llanos Ferraris, Benjamín Sahelices Fernández, Agustín De Dios Hernández

In this paper we discuss the behaviour of the replacement mechanism of well-known COMA protocols applied to a loosely-coupled multicomputer system sharing a common bus. We also present VSR-COMA, a COMA protocol that uses an advanced replacement mechanism in order to select the destination node of a replacement transaction without introducing penalties due to the increment of the network traffic. Our comparative speedup results confirm the efectiveness of the VSR-COMA protocol for this kind of systems.

Cache Injection: A Novel Technique for Tolerating Memory Latency in Bus-Based SMPs

Aleksandar Milenkovic, Veljko Milutinovic

Cache misses and bus traffic are key obstacles to achieving high performance of bus-based shared memory multiprocessors using invalidation-based snooping caches. To overcome these problems, software-controlled techniques for tolerating memory latency can be used, such as cache prefetching and data forwarding. However, some previous studies have shown that cache prefetching is not so effective in bus-based shared memory multiprocessors, while data forwarding is not easy to implement in this environment. In this paper, we propose a novel technique called cache injection, which combines consumer and producer initiated approach, and broadcasting nature of bus. Performance evaluation based on program-driven simulation and a set of eight parallel benchmark programs shows that cache injection is highly effective in reducing coherence misses and bus traffic.

Adaptive Proxies: Handling Widely-Shared Data in Shared-Memory Multiprocessors

Sarah A. M. Talbot, Paul H. J. Kelly

A performance bottleneck arises in distributed shared-memory multiprocessors when there are many simultaneous requests for the same data. One architectural solution is to distribute read requests to nodes other than the home node: these other nodes act as intermediaries (ie. proxies) in obtaining the data, and combine requests for the same data. The use of adaptive proxies continues until the proxying period has expired, with the length of the proxying period varying depending on the level of run-time congestion. Simulation results show that adaptive proxies give performance improvements for all our benchmark applications.


Topic 14:
Instruction-Level Parallelism and Processor Architecture

Session 14-B.1: Compiler Support for ILP
Topic 14: Instruction-Level Parallelism and Processor Architecture

Cache Remapping to Improve the Performance of Tiled Algorithms

Kristof E. Beyls, Erik H. D'Hollander

With the increasing processing power, the latency of the memory hierarchy becomes the stumbling block of many modern computer architectures. In order to speed-up the calculations, different forms of tiling are used to keep data at the lowest cache level. However, conflict misses cannot easily be avoided using the current techniques. In this paper cache remapping is presented as a new way to eliminate conflict as well as capacity and cold misses in regular array computations. The method uses advanced cache hints which can be exploited at compile time. The results on a set of typical examples are very favorable and it is shown that cache remapping is amenable to an efficient compiler implementation.

Code Partitioning in Decoupled Compilers

Kevin D. Rich, Matthew K. Farrens

Decoupled access/execute architectures seek to maximize performance by dividing a given program into two separate instruction streams and executing the streams on independent cooperating processors. The instruction streams consist of those instructions involved in generating memory accesses (the Access stream) and those that consume the data (the Execute stream). If the access stream is able to get ahead of the execute stream it will dynamic pre-load operands reducing the penalty due to memory accesses. This work describes the partitioning algorithm employed in our decoupled compiler and presents some performance results.

Limits and Graph Structure of Available Instruction-Level Parallelism

Darko Stefanovic, Margaret Martonosi

We reexamine the limits of parallelism available in programs, using run-time reconstruction of program data-flow graphs. While limits of parallelism have been examined in the context of superscalar and VLIW machines, we also study the causes of observed parallelism by examining the structure of the reconstructed data-flow graph. One aspect of structure analysis is the isolation of instructions involved only in address calculations. We find that address calculations present in RISC instruction streams generated by optimizing compilers often significantly reduce available parallelism.

Pseudo-Vectorizing Compiler for the SR8000

Hiroyasu Nishiyama, Keiko Motokawa, Ichiro Kyushima, Sumio Kikuchi

The SR8000 implements a pseudo-vector processing mechanism that enables fast processing of large data sets. It enables fast processing similar to vector processing, provides a continuous data stream to the processor and executes scalar instructions in parallel. The SR8000 incorporates data preloading and prefetching to supply the continuous data stream. We implemented compiler optimizations that effectively utilize pseudo-vector processing. These include access method analysis, data preloading, and data prefetching. In this paper, we describe the compiler algorithms for these optimizations and show the results of evaluations on the SR8000. These evaluations indicate that pseudo-vector processing can effectively hides memory latency.


Thursday, August 31st, Afternoon


Topic 02:
Performance Evaluation and Prediction

Session 02-C.1: Performance Prediction and Simulation
Topic 02: Performance Evaluation and Prediction

Automating Performance Analysis from UML Design Patterns

Omer F. Rana, Dave Jennings

We describe a technique for deriving performance models from design patterns expressed in the Unified Modelling Language (UML) notation. Each design pattern captures a theme within the Aglets mobile agent library. Our objective is to find a middle ground between developing performance models directly from UML, and to deal with a more constrained case based on the use of design patterns. Performance models are compared with an implementation of the ``Meeting'' design pattern in Aglets, to illustrate the concepts involved.

Integrating Automatic Techniques in a Performance Analysis Session

Antonio Espinosa, Tomas Margalef, Emilio Luque

In this paper, we describe the use of an automatic performance analysis tool for describing the behaviour of a parallel application. KappaPi tool includes a list of techniques that may help the non-expert user in finding the most important performance problems of their applications. The tool is used to tune the performance of a parallel simulation of a forest fire propagation model.

Combining Light Static Code Annotation and Instruction-Set Emulation for Flexible and Efficient On-the-fly Simulation

Thierry Lafage, André Seznec

This paper proposes a new cost effective approach for on-the-fly microarchitecture simulations using long running applications. The original program code is lightly annotated to provide a fast (direct) execution mode, and an embedded instruction-set emulator enables on-the-fly simulations. While running, the instrumented-and-emulated program can switch from the fast mode to the emulation mode, and vice-versa. The instrumentation tool, calvin2, and the instruction-set emulator, DICE, presented in this paper, exhibit low execution slowdowns in fast mode (from 1.00 to 3.09 on the SPEC95 benchmarks). This makes our approach well suited to simulate on-the-fly samples spread over long running applications. By way of comparison, our calvin2+DICE system is compared with the dynamic translation method used in Shade.

SCOPE - The Specific Cluster Operation and Performance Evaluation Benchmark Suite

Panagiotis Melas, Ed J. Zaluska

The requirements for High Performance Computing (HPC) have increased dramatically over the years. Parallelism is the only technology which can deliver the required computing performance for very large scale scientific and commercial applications. Recent development in commodity hardware and software has enabled workstation clusters to provide a cost-effective HPC environment which has become increasingly attractive to many users. However, in practice workstation clusters often fail to exploit their potential advantages. Performance on these systems is greatly dependent on the efficient implementation and integration of technologies borrowed from other systems. This work focuses on the performance evaluation of workstation clusters. It introduces a methodology for a comprehensive examination of workstation cluster performance and proposes a tailored benchmark evaluation tool for clusters calle d Specific Cluster Operation and Performance Evaluation (SCOPE)

Implementation Lessons of Performance Prediction Tool for Parallel Conservative Simulation

Chu-Cheow Lim, Yoke-Hean Low, Boon-Ping Gan, Wentong Cai

Performance prediction is a useful thing to do to help parallel programmers answer questions such as speedup scalability. To do performance prediction for parallel simulation, one first has to work out the performance analyzer algorithms for specific simulation protocols. This is only part of the work. In order for the prediction results to be close to what one gets from actual parallel executions, there are further considerations when implementing the analyzer. These include (a) equivalence of code between the sequential program and what might have been in an actual parallel program, and (b) system effects (e.g. cache miss rates and synchronization overheads in an actual parallel execution.) This paper describes our investigations into these issues for a discrete-event simulation program (for wafer fabrication models.) The performance analyzer tries to predict what the speedups will be, if a conservative, "super-step" (synchronous) simulation protocol is used. Because we also have an actual parallel implementation of the simulation program (using the same protocol), we can verify the predictions up to four processors on a Sun SMP. This allows us to be confident of the predicted speedups for more processors. The lessons learnt are also applicable for performance analyzers for other simulation protocols.

A Fast and Accurate Approach to Analyze Cache Memory Behavior

Xavier Vera, Josep Llosa, Antonio González, Nerina Bermudo

The gap between processors and main memory performance increases every year. In order to overcome this problem, cache memories are very useful. Compile-time program transformations can significantly improve the performance of the cache. To apply most of these transformations, the compiler requires a precise knowledge of the locality of the different sections of the code, both before and after being transformed. Cache Miss Equations (CME) allow us to obtain an analytical and precise description of the cache memory behavior for loop-oriented codes. Describing the cache behavior by means of diophantine equations allows us to use mathematical techniques to obtain cache misses. Unfortunately, a direct solution of the CME is computationally intractable due to its NP-hard nature. In this work, we propose a fast and accurate approach to estimate the solution of the CME, which is based on the use of sampling techniques. Statistical techniques allow us to approximate the absolute miss ratio of each reference by analyzing a small subset of the iteration space. The size of the subset, and therefore the analysis time, is determined by the accuracy selected by the user. The results show that only a few seconds are required to analyze most of the SPECfp benchmarks with an error smaller than 0.01.

Session 02-C.2: Performance Modeling of Distributed Systems
Topic 02: Performance Evaluation and Prediction

Impact of PE Mapping on Cray T3E Message-Passing Performance

Eduardo Huedo, Manuel Prieto, Ignacio Martin Llorente, Francisco Tirado

The aim of this paper is to study the influence of process mapping on message passing performance. In particular, we have studied the Cray T3E and the Origin 2000. For this purpose, we have designed an experiment where processes are paired off in a random manner and messages of different sizes are exchanged between them. In view of the results of this experiment, it is obvious that the physical placement must be accounted for. Consequently, a mapping algorithm for the T3E, suited to n-dimensional cartesian topologies, is studied. We conclude by making comparisons between our algorithm and the default mapping.

Performance Prediction of a NAS Benchmark Program with ChronosMix Environment

Julien Bourgeois, François Spies

The Networks of Workstations (NoW) are becoming real distributed execution platforms for scientific applications. Nevertheless, the heterogeneity of these platforms makes complex the design and the optimization of distributed applications. To overcome this problem, we have developed a performance prediction tool called ChronosMix, which can predict the execution time of a distributed algorithm on parallel or distributed architecture. In this article we present the performance prediction of an NAS Benchmark program with the ChronosMix environment. This study aims at emphasizing the contribution of our environment in the performance prediction process.


Topic 18:
Cluster Computing

Session 18-C.1
Topic 18: Cluster Computing

Flow Control in ServerNet Clusters

Vladimir Shurbanov, Dimiter Avresky, Pankaj Mehra, William Watson

This paper investigates the performance implications of several end-to-end flow-control schemes clusters based on the ServerNet system-area network. The static-window (SW) and packet-pair (PP) flow-control techniques are studied. Based on them, the simplified packet-pair (SPP) and the alternating static window (ASW) flow control schemes are defined. The applicability of a packet-pair flow control scheme to wormhole-routing networks is studied. Simulation results for the performance characteristics are obtained and evaluated. It is shown that if high throughput is desired, ASW is the best method for controlling the average latency. On the other hand, if low throughput is acceptable, SPP can be applied to maintain low latencies.

The WMPI Library Evolution: Experience with MPI Development for Windows Environments

Hernâni Pedroso, João Gabriel Silva

The WMPI was the first implementation of the MPI standard for Windows based machines. Originally based on the MPICH implementation, the library suffered several changes during the past years. This paper describes the evolution of the library since its first version. Recent changes have been introduced, which enable the dynamic creation of processes and the usage of simultaneous devices. This paper also describes the trends in the field that drove its evolution and the experience gather through the development of the MPI standard for Windows clusters.

Implementing Explicit and Implicit Coscheduling in a PVM Environment

Francesc Solsona, Francesc Giné, Porfidio Hernández, Emilio Luque

A recent research goal is to build a NOW that runs parallel applications with performance equivalent to a MPP as well as executing sequential tasks as a dedicated uniprocessor with acceptable performance. The viability of coscheduling techniques remains an open question when complex communication structures and protocols, and their corresponding operating environments are considered. Our efforts are directed towards the understanding of the coscheduling mechanism in a NOW system when a parallel job is executed with local workloads, balancing parallel efficiency against the local interactive response. Explicit and implicit coscheduling techniques in a NOW system using PVM has been implemented.Their performance and overheads executing local tasks and representative distributed benchmarks have been analyzed and compared.

A Jini-Based Prototype Metacomputing Framework

Zoltan Juhasz, Laszlo Kesmarki

This paper investigates the possible use of Jini technology for building Java-based metacomputing environments. It gives an overview of Jini and highlights those features that can be used effectively for metacompting. Based on this evaluation the paper then presents the structure of a prototype Jini metacomputing system. The overall working mechanism and some details of the implementation are described. It is shown that Jini is a suitable technology that deserves the interest of the metacomputing research community.

Session 18-C.2
Topic 18: Cluster Computing

SKElib: Parallel Programming with Skeletons in C

Marco Danelutto, Massimiliano Stigliani

We implemented a skeleton library allowing the C programmer to write parallel programs using skeleton abstractions to structure and exploit parallelism. The library exploits and SPMD execution model in order to achieve the correct, parallel execution of the skeleton programs (which are not SPMD) onto workstation cluster architectures. Plain TCP/IP sockets have been used as the process communication mechanism. Experimental results are discussed that demonstrate the effectiveness of our skeleton library.

Token-Based Read/Write-Locks for Distributed Mutual Exclusion

Claus Wagner, Frank Mueller

The contributions of this paper are twofold. First, a protocol for distributed mutual exclusion is introduced using a token-based decentralized approach, which allows either multiple concurrent readers or a single writer to enter their critical sections. This protocol utilizes a dynamic structure incorporating path compression to keep the messages overhead low resulting in an average complexity of O(log n) messages per request. Second, this protocol is evaluated in comparison with another protocol that uses a static structure instead of dynamic path compression. The measurements show that although concurrent readers may require at most one additional message per entry, the concurrent execution of critical sections results in faster responses of up to 30% for short critical sections. For longer critical sections, savings in the overall execution time increase with the fraction of readers to up to 50%. In particular applications with large fractions of readers, e.g., database queries, may exploit these benefits. The results further indicate that problems with fine-grained parallelism are more suitable for the dynamic protocol proposed here while the static protocol used for comparison performs equally well for coarse-grained parallelism. Overall, reader/writer distinction provides promising benefits in both cases.

On Solving a Problem in Algebraic Geometry by Cluster Computing

Wolfgang Schreiner, Christian Mittermaier, Franz Winkler

We describe a parallel solution to the problem of reliably plotting a plane algebraic curve. The original sequential program is implemented in the software library CASA on the basis of the computer algebra system Maple. The new parallel version is based on Distributed Maple, a distributed programming extension written in Java. We evaluate the performance of the program on a heterogeneous cluster of workstations and PCs, on a massively parallel multiprocessor, and on a cluster that couples workstations and multiprocessor.

PCI-DDC Application Programming Interface: Performance in User-Level Messaging

Eric Renault, Pierre David, Paul Feautrier

Many programming interfaces which deal with peripherals (especially network peripherals) need to access the critical ressources of the operating system, and system calls (or drivers) are generally used. Unfortunately, the time spent in such system calls is often higher than those requested for the operations themselves. In the case of the MPC machine, most of these operations do not need an intervention from the system and resources may be available from user applications. Our programming interface provides different levels of integration in the kernel depending on the security and the performances expected by the administrator.

A Clustering Approach for Improving Network Performance in Heterogeneous Systems

Vicente Arnau, Juan M. Orduña, Salvador Moreno, Rodrigo Valero, Aurelio Ruiz

A lot of research has focused in the past few years on solving the problem of task scheduling on heterogeneous systems from the computational point of view. In this paper, we propose on one hand a clustering algorithm that, given a network topology, provides a network partition adapted to the communication requirements of the set of applications running on the machine. On other hand, we propose a criterion to measure the quality of each one of the possible mappings of processes to processors that the provided network partition may generate. Preliminary evaluation results show that these proposals can greatly improve network performance, providing a basis of a communication-aware scheduling technique.


Topic 06:
Complexity Theory and Algorithms

Session 06-C.1
Topic 06: Complexity Theory and Algorithms

Positive Linear Programming Extensions: Parallel Complexity and Applications

Pavlos S. Efraimidis, Paul G. Spirakis

Linear Programming (LP) has found many applications in approximation algorithms for hard combinatorial optimization (CO) problems. However LP-based approximations are usually inherently sequential since even approximating general LP within a constant factor is a P-complete problem. The largest, in several aspects, known general sub-model of LP that admits a very efficient NC approximation scheme (NCAS) is Positive Linear Programming (PLP), the class of LP in packing or covering form where all coefficients of matrix A and vectors b and c are nonnegative. Unfortunately only a very limited number of CO problems admits native PLP formulations. In this work, natural extensions of PLP, which can model a substantially larger class of CO problems while still admitting a NCAS, are discussed. Extended PLP (ePLP) is formally defined and it is shown that ePLP with even one equality constraint is P-hard to be approximated within any constant factor. However simple realistic conditions are identified, under which ePLP formulations of hard CO problems admit relaxed efficient parallel approximations. The approach is used for fast parallel approximation algorithms to Global Routing in gate Arrays, Scheduling Unrelated Machines, the Generalized Assignment problem, and Simple k-Matching in Hypergraphs.

Parallel Shortest Path for Arbitrary Graphs

Ulrich Meyer, Peter Sanders

In spite of intensive research, no work-efficient parallel algorithm for the single source shortest path problem is known which works in sublinear time for arbitrary directed graphs with non-negative edge weights. We present an algorithm that improves this situation for graphs where the ratio d_c/delta between the maximum weight of a shortest path d_c and a ``safe step width'' delta is not too large. We show how such a step width can be found efficiently and give several graph classes which meet the above condition, such that our parallel shortest path algorithm runs in sublinear time and uses linear work. The new algorithm is even faster than a previous one which only works for random graphs with random edge weights [MeyerSanders98]. On those graphs our new approach is faster by a factor of Theta(log n/ loglog n) and achieves an expected time bound of O(log^2 n) using linear work.

Periodic Correction Networks

Marcin Kik

We present a comparator network that sorts sequences obtained by changing a limited number of keys in a sorted sequence. The network that we present is periodic and has a constant depth. The time required by this algorithm is O(log n +k) with a small constant hidden by ``Oh'' notation (n is the length of the sequence, k is the number of changed keys).


Topic 11:
Numerical Algorithms for Linear and Nonlinear Algebra

Session 11-C.1: Ordinary Differential Equations and other Topics
Topic 11: Numerical Algorithms for Linear and Nonlinear Algebra

Solving Discrete-Time Periodic Riccati Equations on a Cluster

Peter Benner, Rafael Mayo, Enrique S. Quintana-Ortí, Vicente Hernández

This paper analyzes the performance of a parallel solver for discrete-time periodic Riccati equations, based on a sequence of orthogonal reordering transformations of the monodromy matrices associated with the equations. Two different approaches, exploiting either coarse-grain or medium-grain parallelism are investigated on a Myrinet cluster of Intel Pentium-II processors.

A Parallel Optimization Scheme for Parameter Estimation in Motor Vehicle Dynamics

Torsten Butz, Oskar von Stryk, Thieß-Magnus Wolter

For calibrating the vehicle model of a commercial vehicle dynamics program a parameter identification tool has been developed which relies on the observed behavior of the physical vehicle. The associated parameter estimation problem may be formulated as a nonlinear least-squares problem which can be solved by means of mathematical optimization algorithms. Due to the complexity of the employed vehicle model the objective derivatives needed for the optimization are approximated by finite differences, thus requiring further evaluations of the objective function. Significant savings in computational time can be achieved, if the additional evaluations are performed simultaneously on a cluster of PCs.

Sliding-Window Compression on the Hypercube

Charalampos Konstantopoulos, Andreas Svolos, Christos Kaklamanis

Dictionary Compression belongs to the class of lossless compression methods and is mainly used for compressing text files. The most known examples of this technique are the algorithms of the LZ coding family whose common feature is the use of an adaptive dictionary which is dynamically adjusting during the algorithm execution. In this paper, we present a parallel algorithm for one of these coding algorithms, namely the LZ77 coding algorithm also known as a sliding-window coding algorithm. We also present a parallel algorithm for the corresponding LZ77 decoding algorithm. Although there exist PRAM algorithms for various dictionary compression methods, their rather irregular structure has discouraged their implementation on practical interconnection networks such as the mesh and hypercube. However in the case of LZ77 coding/decoding, we show how to exploit the specific properties of the algorithm in order to achieve an efficient implementation on the hypercube. Specifically, our algorithm employs only a small number of communication primitives such as shifts, prefix sums and monotone routing. In the literature it has long been established that these primitives can be efficiently executed on the hypercube. In addition, we further enhance the performance of our parallel algorithms by using some known heuristics from the field of text compression.

A Parallel Implementation of a Potential Reduction Algorithm for Box-Constrained Quadratic Programming

Marco D'Apuzzo, Marina Marino, Panos M. Pardalos, Gerardo Toraldo

In this paper we describe a parallel version of the potential reduction algorithm for solving Box-Constrained Quadratic Programming problems on MIMD distributed memory machines. The computational kernels arising at each step of the algorithm are concurrently performed by using standard parallel software environments. This approach is shown to be very effective, in contrast to what happens in the active set strategies where the linear algebra computational kernels represent a serious drawback to an effective parallel implementation. The computational results show the effectiveness of our approach.


Panel Discussion

Session P1-C.2
Panel Discussion

Java in High End Computing

Panelists will be announced

t.b.d.


Topic 12:
European Projects

Session 12-C.2
Topic 12: European Projects

The IST Programme

Renato Campo

t.b.d.

NEPHEW: Applying a Toolset for the Efficient Deployment of a Medical Image Application on SCI-Based Clusters

Wolfgang Karl, Martin Schulz, Martin Völk, Sibylle Ziegler

With the rise of cluster architectures, high--performance parallel computing is available to more users than ever before. The programming of such systems, however, has not yet improved beyond the cumbersome programming style used in message passing libraries like PVM and MPI. In order to open clusters to a broader audience, higher level programming environments have to be designed with the goal of giving the end user an easier access to parallel computing. Such an environment is currently being developed within the NEPHEW project allowing the graphical specification of global dependecies. This work presents the NEPHEW approach and discusses its applicability using an example application from the area of nuclear medical imaging, the reconstruction of PET images.

SEEDS : Airport Management Database System

Tomás Hrúz, Martin Becka, Antonello Pasquarelli

The article describes an airport database management system, which is a part of large simulation environment developed under the ESPRIT project SEEDS. Airport management database is a distributed computing system written entirely in Java and connected to the rest of the SEEDS system through CORBA interface. The majority of the SEEDS modules is written in C++ and communicates through CORBA. The airport management database consists of an application server, three different clients and a CORBA connection module.

HIPERTRANS: High Performance Transport Network Modelling and Simulation

Stephen E. Ijaha, Stephen C. Winter, Nasser Kalantery

HIPERTRANS (High Performance Transport Network Modelling and Simulation) is a fast and visually representative simulator that can predict traffic on urban road networks. It was designed using object-oriented techniques and by re-engineering established road traffic models. It can be interfaced with a range of urban traffic control systems. It was implemented by using a novel parallel programming methodology called SPIDER and runs faster than real time on distributed processors. The simulator provides a powerful graphical user interface for entering road network models, configuring simulation runs, and visualising the results. The system provides helpful traffic diagnostic tools enabling local transport authorities, policy makers, researchers, and UTC manufacturers to gainfully exploit its functionality. The HIPERTRANS project was led by the University of Westminster and funded by the European Commission under the 4th Framework Programme.


Topic 09:
Distributed Systems and Algorithms

Session 09-C.2
Topic 09: Distributed Systems and Algorithms

A Combinatorial Characterization of Properties Preserved by Antitokens

Costas Busch, Neophytos Demetriou, Maurice Herlihy, Marios Mavronicolas

Balancing networks are highly distributed data structures that provide efficient solutions to multiprocessor synchronization problems. Traditionally, balancing networks have been designed to be accessed by tokens, which correspond to increment operations. The distribution of the tokens on a network's output specify the property of the network. However, tokens alone are not adequate for synchronization problems that require decrement operations, such as semaphores and critical regions. For such problems antitokens have been used to represent the decrement operation. It has been shown that several kinds of networks which satisfy the step property, smoothing property, and the threshold property for tokens alone preserve their properties even when antitokens are introduced. Therefore, these networks are able to solve synchronization problems that require decrements. A fundamental question that was left open was to characterize all the properties of balancing networks that are preserved under the introduction of antitokens. In this work, we provide a simple, combinatorial characterization for all properties warranted by balancing networks which are preserved when antitokens are introduced. This characterization serves as a theoretical tool for identifying the properties that are preserved by antitokens.

Searching with Mobile Agents in Networks with Liars

Nicolas Hanusse, Evangelos Kranakis, Danny Krizanc

We present algorithms to search for an item contained in a node of a network, without prior knowledge of its exact location. Each node has a database that will answer queries of the form "how do I to the item?" by responding with the first edge on a shortest path to the item. It may happen that somes nodes, called liars, give bad advice. If the number of liars is bounded, we show different strategies depending on the topology of the network: ring, torus, tree, hypercube ...

Complete Exchange Algorithms for Meshes and Tori Using a Systematic Approach

Luis Díaz de Cerio, Miguel Valero-García, Antonio González

Many authors have considered the design of complete exchange algorithms for a variety of multicomputer architectures. Frequently, algorithms for a given multicomputer architecture cannot be used (or are not efficient) for a different architecture. This paper presents a method which allows the systematic design of complete exchange algorithms for meshes and tori and can be extended to some other architectures that may be interesting in the future. Performance figures obtained by analytical models show that algorithms obtained through the proposed method are efficient for almost all the multicomputer architectures under consideration and outperform the best known algorithms for a significant range of the problem and system parameters.


Topic 10:
Programming Languages, Models and Methods

Session 10-C.1: Novel Parallel Languages and Formalisms
Topic 10: Programming Languages, Models and Methods

Novel Models for Or-Parallel Logic Programs: A Performance Analysis

Vítor Santos Costa, Ricardo Rocha, Fernando Silva

One of the advantages of logic programming is the fact that it offers many sources of {\em implicit} parallelism, such as and-parallelism and or-parallelism. Binding Arrays and Environment Copying are two models that efficiently solve the problem of assigning multiple bindings for shared variables to support or-parallelism. Recently, research in combining independent and-parallelism and or-parallelism within the same system has led to two new binding representation approaches: the Sparse Binding Array (an evolution of binding arrays) and the Copy-On-Write binding models. In this paper, we investigate whether for or-parallelism the newer models are practical alternatives to copying. To address this question, we experimented with YapOr, an or-parallel copying system using the YAP Prolog engine, and we implemented the Sparse Binding Array (SBA) and the Copy-On-Write ($\alpha$COWL) over the original system. The three alternative systems share schedulers and the underlying engine: they do only differ in their binding scheme. We then used a set of well-known all-solutions benchmarks to evaluate how did they perform comparatively.

Executable Specification Language for Parallel Symbolic Computation

Alexander B. Godlevsky, Ladislav Hluchý

A program specification language including a set constructor and an operator of nondeterministic choice of elements from sets is proposed. The language also contains two types of program annotations to point out fragments of program that could be executed in parallel. Sequential and parallel semantics of the language are represented, and correctness of the latter with respect to the former is proved. Reasoning of nondeterministic choice of elements is argued from the point of view of program parallelization possibilities.

Efficient Parallelisation of Recursive Problems Using Constructive Recursion

Magne Haveraaen

Many problems from science and engineering may be nicely formulated recursively. As a problem solving technique this is very efficient. Due to the high cost of computing with programs formulated this way, typically an exponential growth in time complexity, this is rarely done. Constructive recursion promises to deliver a space and time optimal compilation of recursive programs -- under explicit programmer control -- without unduely increasing the cost of writing the program that writing a non-recursive program by hand usually entails. The constructive recursive scheme also straight forwardly generates parallel code on high performance computing architectures.

Development of Parallel Algorithms in Data Field Haskell

Jonas Holmerin, Björn Lisper

Data fields is an abstract data type for indexed entities, which is intended to provide a flexible and highly generic model for collections of data. It should support the early algorithm specification close to the problem domain, the first transitions towards implementations for different architectures, and transformations between dense and sparse solutions. Data Field Haskell is a dialect of the functional language Haskell which provides an instance of data fields and thus an environment for the rapid prototyping of collection-oriented and data parallel algorithms. In this paper we describe Data Field Haskell and exemplify how it can be used in the early phase of parallel program design.

The ParCeL-2 Programming Language

Paul-Jean Cagnard

A semi-synchronous parallel programming language and the corresponding computing model is presented. The language is primarily designed for massively parallel fine grained applications such as cellular automata, finite element methods, partial differential equations or systolic algorithms. In this language it is assumed that the number of parallel processes in a program is much larger than the number of processors of the machine on which it is to be run. The computational model and the communication model of the language is presented. Finally, some example programs are presented to show the main features of the language.


Topic 04:
Compilers for High Performance

Session 04-C.1: Automatic Parallelization
Topic 04: Compilers for High Performance

Improving the Sparse Parallelization using Semantical Information at Compile-Time

Gerardo Bandera, Emilio L. Zapata

This work presents a novel strategy for the parallelization of applications containing sparse matrix references using the data-parallel paradigm. Our approach is a first step to converge to the automatic parallelization by reducing the number of directives on code. We have used the semantical relationship of vectors composing a higher-level data structure to enhance the performance of the parallel code, applying a sparse privatization and a multi-loops analysis. We also study the building/updating of a sparse matrix at run-time, solving the problem of using pointers and some levels of indirections on the left hand side.

Automatic Parallelization of Sparse Matrix Computations : A Static Analysis

Roxane Adle, Marc Aiguier, Franck Delaplace

This article deals with the definition of a new method for the automatic parallelisation of sequential programs working on dense matrices for generating a parallel counterpart working on sparse matrices. Parallelisation of numerical programs dealing with sparse matrices implies a symbolic analysis for defining memory locations where the computation takes place. This symbolic analysis allows us to define a specific dependence analysis which refines the usual Bernstein's conditions. Thus, it provides more parallelism than analysis strictly based on the Bernstein's conditions due to the ``sparsity'' of matrices.

Automatic SIMD Parallelization of Embedded Applications Based on Pattern Recognition

Rashindra Manniesing, Ireneusz Karkowski, Henk Corporaal

This paper investigates the potential for automatic mapping of typical embedded applications to architectures with multimedia instruction set extensions. For this purpose a code transformation engine is used which is based on pattern matching. Experiments based on 10 benchmarks show that about 85% of the loops which are suitable for Single Instruction Multiple Data (SIMD) parallelization can be automatically recognized and mapped.

Session 04-C.2: Compiler Analysis and Transformation
Topic 04: Compilers for High Performance

Temporary Arrays for Distribution of Loops with Control Dependences

Alain Darte, Georges-André Silber

We consider the problem of distribution of loops with control dependences, involving if and do control structures. More precisely, we study how to control the number of temporary arrays that have to be introduced to store conditionals. We show that the traditional superposition of the data dependence graph and of the control dependence graph is not adequate, and we introduce a new representation, the mixed dependence graph. This allows us to develop a distribution algorithm that is parameterized by the maximal allowed dimensions of temporary arrays.

Automatic Generation of Block-Recursive Codes

Nawaaz Ahmed, Keshav Pingali

Block-recursive codes are likely to be the centerpiece of the next generation of numerical linear algebra libraries since they perform better on machines with deep memory hierarchies than existing library codes like LAPACK. In this paper, we describe compiler technology to translate iterative versions of some numerical kernels into block-recursive form. We also study the cache behaviour and performance of these compiler-generated block-recursive codes.

Left-looking to Right-looking and vice versa: An Application of Fractal Symbolic Analysis to Linear Algebra Code Restructuring

Nikolay Mateev, Vijay Menon, Keshav Pingali

We have recently developed a new program analysis strategy called fractal symbolic analysis that addresses some of limitations of techniques such as dependence analysis. In this paper, we show how fractal symbolic analysis can be used to convert between left-looking and right-looking versions of three kernels of central importance in computational science: Cholesky factorization, LU factorization with pivoting, and triangular solve.

Identifying and Validating Irregular Mutual Exclusion Synchronization in Explicitly Parallel Programs

Diego Novillo, Ronald C. Unrau, Jonathan Schaeffer

Existing work on mutual exclusion synchronization is based on a structural definition of mutex bodies. Although correct, this notion of mutex body fails to identify many important locking patterns present in some programs. In this paper we present a novel analysis technique for identifying mutual exclusion synchronization patterns in explicitly parallel programs. We apply this analysis to develop a new technique, called Lock Picking, to detect and eliminate redundant mutex operations. We also show that this new mutex analysis technique can be used as a validation tool in a compiler. Using this analysis, a compiler can detect irregularities like lock tripping, deadlock patterns, incomplete mutex bodies, dangling lock and unlock operations and partially protected code.


Friday, September 1st, Morning


Topic 21:
Problem Solving Environments

Session 21-D.1
Topic 21: Problem Solving Environments

AMANDA - A Distributed System for Aircraft Design

Hans-Peter Kersken, Andreas Schreiber, Martin Strietzel, Michael Faden, Regine Ahrem, Peter Post, Klaus Wolf, Armin Beckert, Thomas Gerholt, Ralf Heinrich, Edmund Kügeler

In the AMANDA project a component-based framework for the integration of coupled technical applications, running distributed in a network, is developed. It is designed to deal with parallel and sequential programs and massive data exchange between the integrated programs. Two pilot applications will be implemented to show the feasibility of the chosen approach: a trimmed, freely flying, elastic airplane and an air-cooled turbine. Beside using the integration systems, the MpCCI library is used for the coupling of the codes, each simulating single physical processes.

Problem Solving Environments: Extending the Role of Visualization Systems

Helen Wright, Ken Brodlie, Jason Wood, Jim Procter

Visualization systems based on the dataflow paradigm are enjoying increasing popularity in the field of scientific computation. Not only do they permit rapid construction of a display application, but they also allow the simulation to be incorporated, giving the scientist the opportunity to interact with the calculation as well. However, if these systems are to realise their full potential for problem solving, additional support must be given for collaborative working, data management and visualization program construction. This paper will describe these systems, identify some of their shortcomings as problem solving environments and review current work which addresses these deficiencies.

Session 21-D.2
Topic 21: Problem Solving Environments

An Architecture for Web-Based Interaction and Steering of Adaptive Parallel/Distributed Applications

Rajeev Muralidhar, Samian Kaur, Manish Parashar

This paper presents an architecture for web-based interrogation, interaction and steering of adaptive, parallel/distributed scientific applications. The architecture is composed of detachable thin-clients at the front-end, a network of Java interaction servers in the middle, and a control network of sensors, actuators, interaction agents, and an application interaction proxy, superimposed on the application data-network, at the back-end. A key innovation of the architecture is the definition of interaction enabled Java proxies (using Java Native Interface) for distributed computational objects. These interaction objects along with the application interaction proxy provide a portal to the application, which can be accessed via the interaction web-server.

Computational Steering in Problem Solving Environments

David Lancaster, Jeff Reeve

A strong motive to build Problem Solving Environments (PSE's) is the ability to interactively steer computations. We analyse the requirements that steering puts on the architecture of such a PSE and propose a design that does not separate the development and execution parts of the PSE. We describe a prototype implementation of this design based on the standardized software infrastructure of Java Beans and CORBA that enables a high degree of steering.

Implementing Problem Solving Environments for Computational Science

Omer F. Rana, Maozhen Li, Matthew S. Shields, David W. Walker, David Golby

A Problem Solving Environment (PSE) should aim to hide implementation and systems details from application developers, to enable a scientist or engineer to concentrate on the science. A PSE is, by definition, problem domain specific, but the infrastructure for a PSE can be problem domain independent. A PSE must also enable the construction of new applications, or enable the integration of existing software or application codes (in various programming languages, or as executable binaries) in a uniform way. Most importantly, a PSE must be intuitive to use, and should support the sharing of good practice within a given application domain. After providing an overview of existing PSEs, common themes that must be present in PSEs are outlined. A domain independent infrastructure for a PSE is then described, followed by two application dependent PSEs for Molecular Dynamics and Boundary Element codes that make use of our generic PSE infrastructure.


Topic 20:
Parallel I/O and Storage Technology

Session 20-D.1: Parallel I/O Software
Topic 20: Parallel I/O and Storage Technology

Towards a High-Performance Implementation of MPI-IO on top of GPFS

Jean-Pierre Prost, Richard Treumann, Richard Hedges, Alice E. Koniges, Alison White

MPI-IO/GPFS is a prototype implementation of the I/O chapter of the Message Passing Interface (MPI) 2 standard. It uses the IBM General Parallel File System (GPFS), with prototyped extensions, as the underlying file system. This paper describes the features of this prototype which support its high performance and robustness. The use of hints at the file system level and at the MPI-IO level allows tailoring the use of the file system to the application needs. Error handling in collective operations provides robust error reporting and deadlock prevention in case of returning errors. . . .

Design and Evaluation of a Compiler-Directed Collective I/O Technique

Gokhan Memik, Mahmut T. Kandemir, Alok Choudhary

Current approaches to parallel I/O demand extensive user effort to obtain acceptable performance. This is in part due to difficulties in understanding the characteristics of a wide variety of I/O devices and in part due to inherent complexity of I/O software. While parallel I/O systems provide users with environments where large datasets can be shared between parallel processors, the ultimate performance of I/O-intensive codes depends largely on the relation between data access patterns and storage patterns of data in files and on disks. In cases where access patterns and storage patterns match, we can exploit parallel I/O hardware by allowing each processor to perform independent parallel I/O. To handle the cases in which data access patterns and storage patterns do not match, several I/O optimization techniques have been developed in recent years. Collective I/O is such an optimization technique that enables each processor to do I/O on behalf of other processors if doing so improves the overall performance. While it is generally accepted that collective I/O and its variants can bring impressive improvements as far as the I/O performance is concerned, it is difficult for the programmer to use collective I/O effectively. In this paper, we propose and evaluate a compiler-directed collective I/O approach which detects the opportunities for collective I/O and inserts the necessary I/O calls in the code automatically. An important characteristic of the approach is that instead of applying collective I/O indiscriminately, it uses collective I/O selectively, only in cases where independent parallel I/O would not be possible. We have implemented the necessary algorithms in a source-to-source translator and within a stand-alone tool. We have conducted several experiments using an IBM SP-2 distributed-memory message-passing machine with 128 nodes. Our experimental results demonstrate that our compiler-directed collective I/O scheme performs very well on different setups built using eight applications from several scientific benchmarks. In particular, our compiler directed collective I/O scheme was able to perform 18 % better in average than an indiscriminate collective I/O scheme in our base configuration.

Effective File-I/O Bandwidth Benchmark

Rolf Rabenseifner, Alice E. Koniges

The effective I/O bandwidth benchmark covers two goals: to achieve a characteristic average number for the I/O bandwidth achievable with parallel MPI-I/O applications, and to get detailed information about several access patterns and buffer lengths. On systems, meeting the rule that the total memory can be written to disk in 10 minutes, the benchmark should not need more than 15 minutes for a first pass of all patterns. First results of the b_eff_io benchmark are given for IBM SP and Cray T3E systems and compared with existing benchmarks based on parallel Posix-I/O.

Session 20-D.2: Storage Technology
Topic 20: Parallel I/O and Storage Technology

Instant Image: Transitive and Cyclical Snapshots in Distributed Storage Volumes

Prasenjit Sarkar

Snapshots are a useful mechanism to manage data, particularly for backups in high-availability storage systems. This paper presents the Instant Image algorithm for handling snapshots of storage volumes in a distributed storage system. The algorithm places no restrictions on the choice of storage volumes, allowing snapshot relationships between storage volumes that can be transitive and cyclical. In addition, in a distributed environment with snapshot relationships involving n storage subsystems, reads and writes to storage volumes involve only O(1) storage subsystems per read or write, thereby reducing messaging costs. Finally, the algorithm is not specific to storage systems and can be applied to other contexts requiring sna