Parallel Processing Letters

Program transformations are one of the most valuable compiler techniques to improve parallelism or data locality. However, restructuring compilers have a hard time coping with data dependences. A typical solution is to focus on program parts where the dependences are simple enough to enable any transformation. For more complex problems is only addressed the question of checking whether a transformation is legal or not. In this paper we propose to go further. Starting from a transformation with no guarantee on legality, we show how we can correct it for dependence satisfaction. Two directions are explored: first when transformation properties can be explicitly expressed and second when they are implicit as in the data locality transformation case. Generating code having the best properties is a direct application of this result.

Measurement-based profiling introduces intrusion in program execution. Intrusion effects can be mitigated by compensating for measurement overhead. Techniques for compensation analysis in performance profiling are presented and their implementation in the TAU performance system described. Experimental results on the NAS parallel benchmarks demonstrate that overhead compensation can be effective in improving the accuracy of performance profiling. However, parallel time profiling requires the execution delay introduced by measurement on individual processes to be communicated between processes when they interact. Parallel execution scenarios are given to model the effects and to determine the analysis procedures to be applied online.

We compare experimentally different parallelization models using MPI and OpenMP for structured adaptive mesh refinement on a shared-memory parallel computer, a SunFire 15K. Due to the dynamic properties of the mesh no static parallelization model with fixed number of processes and threads performs best in all stages. Different combinations of MPI and OpenMP are preferable in different settings of the application and grid hierarchy. We suggest a new dynamic approach using a mixed MPI-OpenMP model that adapts the number of threads during run time and gives good performance in all stages throughout the whole run as the solution state changes, i.e. the resolution in the computational grid changes.

Of the many factors that contribute to communication performance, perhaps one of the least investigated is that of message-buffer alignment. Although the generally accepted practice is to page-align buffer memory for best performance, our studies show that the actual relationship of buffer alignment to communication performance cannot be expressed with such a simple formula. This paper presents a case study in which porting a simple network performance test from one language to another resulted in a large performance discrepancy even though both versions of the code consist primarily of calls to messaging-layer functions. Careful analysis of the two code versions revealed that the discrepancy relates to the alignment in memory of the message buffers. Further investigation revealed some surprising results about the impact of message-buffer alignment on communication performance: (1) different networks and node architectures prefer different buffer alignments; (2) page-aligned memory does not always give the best possible performance, and, in some cases, actually yields the worst possible performance; and, (3) on some systems, the most significant factor affecting network performance is the relative alignment of send and receive buffers with respect to each other.

Several aspects of today's Grids are based on centralized or hierarchical services. However, as Grids increase their size from tens to thousands of hosts, functionalities should be decentralized to avoid bottlenecks and guarantee scalability. A way to ensure Grid scalability is to adopt Peer-to-Peer (P2P) models and techniques to implement non-hierarchical decentralized Grid services and systems. Pure decentralized P2P protocols based on a pervasive exchange of messages, such as Gnutella, appear to be inadequate for OGSA Grids, where peers communicate among them through Grid Services mechanisms. On the other hand, this class of protocols offers useful properties in dealing with Grid resources heterogeneity and dynamicity. This paper proposes a modified Gnutella discovery protocol, named Gridnut, which makes it suitable for OGSA Grids. In particular, Gridnut uses appropriate message buffering and merging techniques to make Grid Services effective as a way to exchange messages in a P2P fashion. We present the design of Gridnut and compare Gnutella and Gridnut performances under different network and load conditions.

We present Quantify, a programming framework for exposing high-performance parallel MPI applications using Grid Services. The two distinctive programming styles of Grid Services and MPI are bridged using a data-centric virtualization approach through the notion of Uses and Provides Quantities. Quantities are used to describe an abstract application interface, permit data exchange between applications and facilitate the composition of two or more applications in a service workflow. Uses and Provides Quantities are modelled using Service Data Elements (SDEs). Finally we demonstrate the applicability of the framework using a Flood Crisis application scenario.

The deteriorating effect of old history in asynchronous implementations of Jacobi-type iterative methods applied to linear least squares problem is well documented. A partially asynchronous algorithm is developed which employs a combination of synchronization, a relaxation parameter and an aggregation of variables. It is shown by numerical experiments that this combined effort to decrease the effect of old history is effective.

In this paper we study the Station Placement problem on directed graphs, a problem that has applications to efficient multicasting in circuit-switched networks. We first argue that the problem on general directed graphs can be efficiently reduced to computing bounded depth Steiner tree on complete weighted directed graphs. Then, we concentrate on the case in which the graph is a directed tree and we give polynomial time algorithms to solve the problem and a natural variant of the problem.

In this paper, we propose different approaches for the parallel loop scheduling problem on distributed as well as shared memory systems. Specifically, we propose adaptive loop scheduling models in order to achieve load balancing, low runtime scheduling, low synchronization overhead and low communication overhead. Our models are based on an adaptive determination of the chunk size and an exploitation of the processor affinity property, and consider different situations (central or local queues, and dynamic or static loop partition).

Recent studies have revealed that deadlocks are generally infrequent in the network. Thus the hardware resources, e.g. virtual channels, dedicated for deadlock avoidance are not utilised most of the time. This consideration has motivated the development of novel adaptive routing algorithms with deadlock recovery. This paper describes a new analytical model to predict message latency in hypercubes with a true fully adaptive routing algorithm with progressive deadlock recovery. One of the main features of the proposed model is the use of results from queueing systems with impatient customers to capture the effects of the timeout mechanism used in this routing algorithm for deadlock detection. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.

This paper presents a consensus protocol for asynchronous distributed systems made up of n processes, where up to f<n/4 processes can behave arbitrarily (Byzantine processes). The protocol assumes that the underlying system is equipped with an unreliable failure detector of the class . The failure detectors of the class ensure that (1) all mute processes are detected (a mute process is a process that, after some time, stops sending protocol messages), and (2) after some unknown but finite time, no correct process is suspected (mute processes are a subset of the Byzantine processes). The proposed protocol enjoys the following properties. It is based on the round coordinator paradigm and its design principle is particularly simple. Its message complexity is O(n²) per round. In addition to a round number, the message size is O(1), except for one message per round (sent by the round coordinator) whose size is O(n). The protocol does not use message "proofs", certificates, or application level signatures. When no process is faulty, all processes propose the same value, and the failure detector makes no mistake, the processes decide in one round (4 communication steps). Finally, when a process decides, it only needs a simple unreliable broadcast mechanism to prevent the other processes from deadlocking. All these features make the protocol attractive to cope with the net effect of Byzantine failures and asynchrony.

In this paper, we present a self-stabilizing algorithm for finding cut-nodes and bridges in arbitrary rooted networks with a low memory requirement (O(log(n)) bits per processor where n is the number of processors). Our algorithm is silent and must be composed with a silent self-stabilizing algorithm computing a Depth-First Search (DFS) Spanning Tree of the network. So, in the paper, we will prove that the composition of our algorithm with any silent self-stabilizing DFS algorithm is self-stabilizing. Finally, we will show that our algorithm needs O(n²) moves to reach a terminal configuration once the DFS spanning tree is computed. Note that this time complexity is equivalent to the best proposed solutions.

Applications of the cellular Potts model to investigate cellular structures are becoming widely spread in the scientific literature. Despite its realism and generality, the standard Monte Carlo algorithm used to evolve this model in the scientific literature lacks computational efficiency. As an alternative we introduce the Random Walker algorithm that is a modified Monte Carlo procedure of simpler parallelization. We test it in cell sorting and foam coarsening simulations obtaining velocity increase factors of 10 and 3 times, respectively, in relation to the standard algorithm. The results obtained with these simulations are equivalent to those obtained with the standard algorithm.

A multipoint request is a group of collaborating nodes that wish to establish a communication for a certain duration of time. This need arises in parallel applications executed on processing elements connected either by specialized interconnection networks or over wide area networks (collective communication operations). Each individual request is satisfied by a given subtree connecting the participating nodes. We aim to maximize the number of requests that can be simultaneously satisfied. In this paper, we show that this problem is NP-complete and we propose for it an approximation algorithm provided that the number of requests using the same edge is bounded by a constant.

Collective communication performance is critical in a number of MPI applications. In this paper we focus on two widely used primitives, broadcast and reduce, and present experimental results obtained on a cluster of PC connected by InfiniBand. We integrated our algorithms in the MPICH library and we used MPICH implementation of broadcast and reduce primitives to compare the performance of our algorithms based on α-trees. Our tests show that the MPICH implementation can be improved.