Parallelization of the TRIGRS model for rainfall-induced landslides using the message passing interface

We describe a parallel implementation of TRIGRS, the Transient Rainfall Infiltration and Grid-Based Regional Slope-Stability Model for the timing and distribution of rainfall-induced shallow landslides. We have parallelized the four time-demanding execution modes of TRIGRS, namely both the saturated and unsaturated model with finite and infinite soil depth options, within the Message Passing Interface framework. In addition to new features of the code, we outline details of the parallel implementation and show the performance gain with respect to the serial code. Results are obtained both on commercial hardware and on a high-performance multi-node machine, showing the different limits of applicability of the new code. We also discuss the implications for the application of the model on large-scale areas and as a tool for real-time landslide hazard monitoring.     

MPICH2-CMEX:可扩展消息传递接口实现技术

在大规模并行计算系统中,为了更有效地利用系统的并行性,实现一个高性能、可扩展的MPI系统是非常重要的。CMEX是无连接模式的用户级通讯软件接口,提供了高性能的报文传输和RDMA通讯操作,MPICH2-CMEX是基于CMEX的MPI实现,结合RDMA读和RDMA写通讯操作的特性,MPICH2-CMEX实现了多种数据传输通道,并利用并行应用的近邻通讯模式,实现了混合通道数据传输方法,实际的应用测试表明,MPICH2-CMEX系统具有良好的性能和可扩展性。     

基于网格的消息传递接口的实现:MPICH-G2

MPI(消息传递接口)作为一种著名的底层并行编程模型已被提出来作为网格编程的基础。描述了基于网格的消息传递接口的实现MPICH-G2,它基于MPICH和Gllobus工具包实现,在启动和管理中隐藏了异构性,具有良好的异构通讯性能。用一个例子说明如何在一个由Globus搭建的计算网格环境中通过MPICH-G2来创建和执行MPI计算。     

基于消息传递的数据交错重分布负载平衡技术

数据重分布是实现消息传递环境下负载平衡的重要手段,提出了数据交错分布的模型问题及模型问题的并行计算模型,分析了模型问题在消息传递环境下的实现,讨论了性能和适用条件,给出了分析结果,讨论了通信与计算的时间重叠问题,将数据交错重分布负载平衡技术应用到非平衡刚性动力学方程组的并行计算中,获得了很好的负载平衡效果。     

基于消息传递接口的大规模生物网络比对并行化算法

为有效降低生物网络比对算法的时间复杂度,提出一种基于可扩展的蛋白质相互作用网络比对(SPINAL)算法的消息传递接口(MPI)并行化实现方法。该方法将MPI并行化思想运用在SPINAL算法中,在多核环境中采用并行排序代替算法原本的排序方式,并结合负载均衡策略合理分配任务。实验结果表明,与未使用并行排序以及负载均衡策略相比,该方法在处理大规模生物网络比对时能有效地缩短计算时间,提高运算效率,对于不同组比对数据都有较为稳定的优化保障,具有良好的可扩展性。     

基于可视化库和信息传递接口云图显示的并行化处理

基于可视化库(VTK)可视化技术的特点,讨论可视化流水线机制和并行程序的基本结构.针对计算流体力学可视化后处理实现的问题,介绍和使用VTK颜色映射算法,并编写对计算流体力学结果数据彩色云图显示的程序.然后为了解决时间开销大的问题,提出了并行显示算法.该算法充分利用VTK任务间的并行性,减少程序运行时间,提高运行效率.最后在多核环境下,对大小不同的文件彩色云图显示的加速比进行了对比分析.实验结果显示了随压力变化的彩色云图,表明基于VTK可视化技术能满足可视化后处理方面的要求,与信息传递接口(MPI)结合能取得很好的并行效果.     

On the interconnection of message passing systems

One of the most important abstractions for designing distributed programs is the broadcast facility. In this paper, we study the interconnection of distributed message passing systems. We have shown that totally ordered systems cannot be properly interconnected in any form. However, we have provided a simple protocol to properly interconnect FIFO ordered systems.     

Adaptive checkpointing in message passing distributed systems

Determining consistent global checkpoints is common to many distributed problems such as fault-tolerance, distributed debugging, properties detection, etc. Uncoordinated and coordinated checkpointing algorithms have been traditionally used for such determinations. This paper addresses a third technique, namely adaptive checkpointing, that has recently emerged. This technique assumes processes take local checkpoints independently and requires them to take additional local checkpoints in order that all local checkpoints be members of some consistent global checkpoint. We first study the characteristics of such adaptive algorithms. Then, a general adaptive checkpointing algorithm is designed from a condition, first stated by Netzer and Xu, that answers the following question: ‘does a given local checkpoint belong to a consistent global checkpoint’' (such a local checkpoint is not useless). The resulting algorithm has the nice property to reduce the number of additional local checkpoints taken to ensure the property ‘no local checkpoint is useless’. Futhermore, it provides each local checkpoint with a consistent global checkpoint to which it belongs. Compared to uncoordinated and coordinated checkpointing algorithms, this algorithm combines the advantages of both without inheriting their drawbacks.     

Hiding message delivery latency using Direct-to-Cache-Transfer techniques in message passing environments

Communication overhead is the key obstacle to reaching hardware performance limits. The majority is associated with software overhead, a significant portion of which is attributed to message copying. To reduce this copying overhead, we have devised techniques that do not require to copy a received message in order for it to be bound to its final destination. Rather, a late-binding mechanism, which involves address translation and a dedicated cache, facilitates fast access to received messages by the consuming process/thread.We have introduced two policies namely Direct to Cache Transfer (DTCT) and lazy DTCT that determine whether a message after it is bound needs to be transferred into the data cache. We have studied the proposed methods in simulation and have shown their effectiveness in reducing access times to message payloads by the consuming process.     

Connecting tools using message passing in the Field environment

An overview is given of the Field environment, which was developed to show that highly integrated, interactive environments like those on PCs can be implemented on workstations and can be used for classical-language and large-scale programming. Field connects tools with selective broadcasting, which follows the Unix philosophy of letting independent tools cooperate through simple conventions, demonstrating that this simple approach is feasible and desirable. Field achieves its goals by providing a consistent graphical front end and a simple integration framework that lets existing and new Unix tools cooperate. The front end is based on a tool set called the Brown workstation environment. The framework combines selective broadcasting with an annotation editor that provides consistent access to the source code in multiple contexts and with a set of specialized interactive analysis tools. Field's integration framework and message facility are described     

A fast multiprocessor message passing implementation

We present the design and implementation of a loosely coupled multiprocessor built from off-the-shelf parts. Message passing is used as the communication paradigm. Several novel techniques are used to reduce the demands on the kernel from the message passing subsystem. We achieve message passing times of the same order for messages within processors and interprocessor messages, allowing transparent interprocess communication. Because it is possible to achieve these performance results, we conclude that process allocation need not be a critical problem in efficient multiprocessor design, at least for small scale multiprocessors.     

Hpcfolder: a simple tool used to parallelize algorithms using the message passing interface (MPI)

The Journal of Supercomputing - Hpcfolder is a user-friendly high-performance computing tool that can be used to analyze the performance of algorithms parallelized using MPI. It is possible to view...     

Predicting the execution time of message passing models

Recent publications prove that runtime systems oriented to the Bulk Synchronous Parallel Model usually achieve remarkable accuracy in their predictions. That accuracy can be seen in the capacity of the software for packing the messages generated during the superstep and their capability to find a rearrangement of the messages sent at the end of the superstep. Unfortunately, barrier synchronisation imposes some limits both in the range of available algorithms and in their performance. The asynchronous nature of many MPI/PVM programs makes their expression difficult or infeasible using a BSP oriented library. Through the generalisation of the concept of superstep we propose two extensions of the BSP model: the BSP Without Barriers (BSPWB) and the Message Passing Machine (MPM) models. These new models are oriented to MPI/PVM parallel programming. The parameters of the models and their quality are evaluated on four standard parallel platforms. The use of these BSP extensions is illustrated using the Fast Fourier Transform and the Parallel Sorting by Regular Sampling algorithms. Copyright © 1999 John Wiley & Sons, Ltd.     

Predicate transfer and timeout in message passing systems

Timeout in a message passing system is studied with emphasis on the notion of predicate transfer. Under certain conditions, a predicate describing the state of the sender can be transferred to the receiver when a timeout occurs. These conditions relate to the way the message passing system is implemented. This relationship is discussed and a technique for formally describing the semantics of message passing with timeout is presented.     

On the complexity of buffer allocation in message passing systems

Message passing programs commonly use message buffers to avoid unnecessary synchronizations and to improve performance by overlapping communication with computation. Unfortunately, using buffers can introduce portability problems and can lead to deadlock problems on systems without a sufficient number of message buffers.We explore a variety of problems related to buffer allocation for safe and efficient execution of message passing programs. We show that determining the minimum number of message buffers or verifying that each process has a sufficient number of message buffers are intractable problems. However, we give a polynomial time algorithm to determine the minimum number of message buffers needed to ensure that no send operation is unnecessarily delayed due to lack of message buffers. We extend these results to several different buffering schemes, which in some cases make the problems tractable.     

Convergent tree-reweighted message passing for energy minimization

Algorithms for discrete energy minimization are of fundamental importance in computer vision. In this paper, we focus on the recent technique proposed by Wainwright et al. [33]—tree-reweighted max-product message passing (TRW). It was inspired by the problem of maximizing a lower bound on the energy. However, the algorithm is not guaranteed to increase this bound—it may actually go down. In addition, TRW does not always converge. We develop a modification of this algorithm which we call sequential tree-reweighted message passing. Its main property is that the bound is guaranteed not to decrease. We also give a weak tree agreement condition which characterizes local maxima of the bound with respect to TRW algorithms. We prove that our algorithm has a limit point that achieves weak tree agreement. Finally, we show that, our algorithm requires half as much memory as traditional message passing approaches. Experimental results demonstrate that on certain synthetic and real problems, our algorithm outperforms both the ordinary belief propagation and tree-reweighted algorithm in [33]. In addition, on stereo problems with Potts interactions, we obtain a lower energy than graph cuts.     

Toward formally-based design of message passing programs

Presents a systematic approach to the development of message passing programs. Our programming model is SPMD, with communications restricted to collective operations: scan, reduction, gather, etc. The design process in such an architecture-independent language is based on correctness-preserving transformation rules that are provable in a formal functional framework. We develop a set of design rules for composition and decomposition. For example, scan followed by reduction is replaced by a single reduction, and global reduction is decomposed into two faster operations. The impact of the design rules on the target performance is estimated analytically and tested in machine experiments. As a case study, we design two provably correct, efficient programs using the Message Passing Interface (MPI) for the famous maximum segment sum problem, starting from an intuitive, but inefficient, algorithm specification     

A modal logic for message passing processes

A first-order modal logic is given for describing properties of processes which may send and receive values or messages along communication ports. We give two methods for proving that a process enjoys such a property. The first is the construction, for each processP and formulaF, of acharacteristic formula P satF such thatP enjoys the propertyF if and only if the formulaP satF is logically equivalent to tt. The second is a sound and complete proof system whose judgements take the formB P: F, meaning: under the assumptionB the processP enjoys the propertyF.The notion ofsymbolic operational semantics plays a crucial role in the design of both the characteristic formulae and the proof system.This work was been supported by the SERC grant GR/H16537 and the ESPRIT BRA CONCUR II