An optimal algorithm for Gaussian elimination of band matrices on an MIMD computer

This paper describes a parallel algorithm for the LU decomposition of band matrices using Gaussian elimination. The matrix dimension is n × n with 2r−1 diagonals. In the case when 1 r 2 p an optimal number of the processors, , is determined according to the equation . When 2 p r n a number of processors, p, statged by Veldhorst is adopted (see [7]). For band matrix with 2r-1 diagonals (1 r 2p) the task scheduling procedure with the aim to obtain maximal parallelism in system operation, i.e. good load balancing, is defined. The architecture of the system is of MIMD type. The connection between the processors is realised via a common bus. Communication and synchronization is performed by message passing technique.     

Computational science in high schools: defining curricula and environments

The paper presents a new approach for the introduction of computational science into high level school curricula. It also discusses a set of real life problems that are appropriate for these curricula because they can be described through simple models. The computer based simulation of these systems require an ad hoc environment, including a programming language, suitable for this target age. The paper proposes a new environment, the ORESPICS environment, including a new programming language. The sequential part of the language integrates the classical imperative constructs with a simple set of graphical primitives, mostly taken from the LOGO language. The concurrent part of the language is based on the message passing paradigm. The solutions of some classical problems through ORESPICS are shown.     

Algorithms for scheduling with applications to parallel computing

Scheduling of message passing for synchronous communication is found to be equivalent to colouring the edges of a graph without conflict. The graph edge-colouring problem, which has other applications, is studied. An algorithm which colours the graph with no more than deg + 1 colours, where deg is the degree of the graph, is implemented. The problem of minimising the sum of the largest weight for each colour is also investigated and an algorithm suggested. These algorithms are used to organise the communication as part of a finite element Euler solver. Different communication schemes and their effect on the performance of the flow solver are compared.     

A robustness measure for hypercube networks

Hypercube networks offer a feasible cost-effective solution to parallel computing. Here, a large number of low-cost processors with their own local memories are connected to form an n-cube (B_n) or one of its variants; and the inter-processor communication takes place by message passing instead of shared variables. This paper addresses a constrained two-terminal reliability measure referred to as distance reliability (DR) as it considers the probability that a message can be delivered in optimal time from a given node s to a node t. The problem is equivalent to that of having an operational optimal path (not just any path) between the two nodes. In B_n, the Hamming distance between labels of s and t or H(s, t) determines the length of the optimal path between the two nodes. The shortest distance restriction guarantees optimal communication delay between processors and high link/node utilization across the network. Moreover, it provides a measure for the robustness of symmetric networks. In particular, when H(s, t) = n in B_n, DR will yield the probability of degradation in the diameter, a concept which directly relates to fault-diameter. The paper proposes two schemes to evaluate DR in B_n. The first scheme uses a combinatorial approach by limiting the number of faulty components to (2H(s, t) − 2), while the second outlines paths of length H(s, t) and, then generates a recursive closed-form solution to compute DR. The theoretical results have been verified by simulation. The discrepancy between the theoretical and simulation results is in most cases below 1% and in the worst case 4.6%.     

Fast barrier synchronization in wormhole k-ary n-cube networks with multidestination worms

This paper presents a new approach to implement fast barrier synchronization in wormhole k-ary n-cubes. The novelty lies in using multidestination messages instead of the traditional single destination messages. Two different multidestination worm types, gather and broadcasting, are introduced to implement the report and wake-up phases of barrier synchronization, respectively. Algorithms for complete and arbitrary set barrier synchronization are presented using these new worms. It is shown that complete barrier synchronization in a k-ary n-cube system with e-cube routing can be implemented with 2n communication start-ups as compared to 2nlog₂k start-ups needed with unicast-based message passing. This leads to an asymptotic improvement by a factor of log₂k. Simulation results for different system and architectural parameters indicate that the new framework can reduce barrier synchronization cost considerably compared to the unicast-based scheme. For arbitrary set barrier, an interesting trend is observed where the synchronization cost keeps on reducing beyond a certain number of participating nodes. The framework demonstrates potential for supporting fast barrier synchronization in large wormhole-routed systems.     

分布式实时操作系统消息机制的设计与实现

随着数字信号处理技术的迅猛发展,针对并行数字信号处理(DSP)应用自主开发了一个满足用户需要的高性能分布式实时操作系统--腾飞分布式实时操作系统(TF-RTOS).消息机制用于线程间的通信,是操作系统中的重要部分.在开发TF-RTOS过程中,从消息命令包、消息队列、消息传递过程和消息原语这4个方面设计并实现了一种直接消息传递的消息机制,该消息机制具有简化线程间通信、增强系统功能、提高系统性能的特点.     

位置透明的MA可靠消息传递机制

移动Agent系统中的通信机制多由RMI加上消息发送机制实现，在现有的三种主流消息发送机制上进行改进，提出了新的消息转发策略——资源分散模型(Resource Distributed Model)。RDM提供了一种类似于结合了Homeagent和按路径转发方式的寻址策略，达到消息可达的目的，基于RDM的移动服务(Mobile Service)是一种在快速寻址后将消息快速转发的方式，MS减少了消息缓存部件的消息缓存量，并可用多个MS同时寻址从而提高消息发送速度。     

Device level communication libraries for high‐performance computing in Java

Since its release, the Java programming language has attracted considerable attention from the high‐performance computing (HPC) community because of its portability, high programming productivity, and built‐in multithreading and networking support. As a consequence, several initiatives have been taken to develop a high‐performance Java message‐passing library to program distributed memory architectures, such as clusters. The performance of Java message‐passing applications relies heavily on the communications performance. Thus, the design and implementation of low‐level communication devices that support message‐passing libraries is an important research issue in Java for HPC. MPJ Express is our Java message‐passing implementation for developing high‐performance parallel Java applications. Its public release currently contains three communication devices: the first one is built using the Java New Input/Output (NIO) package for the TCP/IP; the second one is specifically designed for the Myrinet Express library on Myrinet; and the third one supports thread‐based shared memory communications. Although these devices have been successfully deployed in many production environments, previous performance evaluations of MPJ Express suggest that the buffering layer, tightly coupled with these devices, incurs a certain degree of copying overhead, which represents one of the main performance penalties. This paper presents a more efficient Java message‐passing communications device, based on Java Input/Output sockets, that avoids this buffering overhead. Moreover, this device implements several strategies, both in the communication protocol and in the HPC hardware support, which optimizes Java message‐passing communications. In order to evaluate its benefits, this paper analyzes the performance of this device comparatively with other Java and native message‐passing libraries on various high‐speed networks, such as Gigabit Ethernet, Scalable Coherent Interface, Myrinet, and InfiniBand, as well as on a shared memory multicore scenario. The reported communication overhead reduction encourages the upcoming incorporation of this device in MPJ Express ( http://mpj‐express.org ). Copyright © 2011 John Wiley & Sons, Ltd.     

嵌入式环境下RPC的设计与实现

远程过程调用(RPC)是分布式系统中常见的进程间通信手段，与显式的消息传递方法相比，RPC能为多节点进程间通信提供更好的透明性。该文在分析了RPC系统结构的基础上，结合嵌入式环境设计了一个通用的RPC系统，并在ARM7、μC/OS-II、以太网和TCP/IP的基础上实现了该RPC设计。通过测试，比较了RPC方式与显式消息传递的时间损耗。     

一种进程间异步通信模型的研究

该文给出了在分布式系统下一种基于消息传递与排队技术的进程间异步通信模型,并给出了消息队列的管理方法和消息传递模式,最后提出了用局部按名手址方式来解决进程寻址问题。     

Scalable parallel FFT for spectral simulations on a Beowulf cluster

The implementation and performance of the multidimensional Fast Fourier Transform (FFT) on a distributed memory Beowulf cluster is examined. We focus on the three-dimensional (3D) real transform, an essential computational component of Galerkin and pseudo-spectral codes. The approach studied is a 1D domain decomposition algorithm that relies on communication-intensive transpose operation involving P processors. Communication is based upon the standard portable message passing interface (MPI). We show that 1/P scaling for execution time at fixed problem size N³ (i.e., linear speedup) can be obtained provided that (1) the transpose algorithm is optimized for simultaneous block communication by all processors; and (2) communication is arranged for non-overlapping pairwise communication between processors, thus eliminating blocking when standard fast ethernet interconnects are employed. This method provides the basis for implementation of scalable and efficient spectral method computations of hydrodynamic and magneto-hydrodynamic turbulence on Beowulf clusters assembled from standard commodity components. An example is presented using a 3D passive scalar code.     

利用Oracle PL/SQL Package实现Dispatcher设计模式

Dispatcher设计模式可以使用各种技术来实现。以社会保险业务处理为基础，有效地利用ORACLEPL／SQL Package语言及支撑环境对面向对象技术的支持，通过定义消息ID、传递消息ID、撰写处理函数、连接消息ID和处理函数来实现Dispatcher设计模式，并且构造出能处理各项社会保险管理业务的Package组件。     

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.     

The Argonne/GMD macros in FORTRAN for portable parallel programming and their implementation on the Intel iPSC/2

A macro package for expressing message passing functions within parallel FORTRAN program is presented. It makes the user program fully portable among all parallel computers where the macros are implemented. The implementation on the Intel iPSC/2 hypercube is discussed in more detail. New message passing primitives have been added to the iPSC/2 operating system, offering the user a broader functionality at no efficiency loss. The full macro set, using these primitives, works with the same performance as the original Intel primitives.     

基于一般逻辑拓扑结构的广播通信研究和实现

在分布存储并行计算消息传递系统中,许多广播通信中的消息传递路径是对程序员透明的,程序员不能改变消息传递路径,但应用程序运行时的情况很复杂。程序员根据计算环境及应用程序特征选择消息传递路径,有助于提高广播通信的效能。在通信过程中,消息标志是用来区分消息的,以便接受进程能正确接受消息。然后,消息标志易导致应用程序出错,而且消息标志增加编制程序的复杂性。文中首先给出了逻辑拓扑结构的形式定义及基本性质,提     

Neighborhood-consensus message passing as a framework for generalized iterated conditional expectations

In this paper we propose a novel inference method for maximum a posteriori estimation with Markov random field prior. The central idea is to integrate a kind of joint “voting” of neighboring labels into a message passing scheme similar to loopy belief propagation (LBP). While the LBP operates with many pairwise interactions, we formulate “messages” sent from a neighborhood as a whole. Hence the name neighborhood-consensus message passing (NCMP). The practical algorithm is much simpler than LBP and combines the flexibility of iterated conditional modes (ICM) with some ideas of more general message passing. The proposed method is also a generalization of the iterated conditional expectations algorithm (ICE): we revisit ICE and redefine it in a message passing framework in a more general form. We also develop a simplified version of NCMP, called weighted iterated conditional modes (WICM), that is suitable for large neighborhoods. We verify the potentials of our methods on four different benchmarks, showing the improvement in quality and/or speed over related inference techniques.     

基于请求应答方式消息传递机制有色Petri网模型

分布式系统的对等模型中,各个节点从功能上看是对等关系,相互之间进行消息的请求和响应。讨论了一种将广播请求和点到点应答两种通信方式相结合的消息传递机制FMPRR(Fast Message Passing based on Request Response mode)的实现,这种机制采用wormhole寻径流控策略。用有色Petri网来形式化描述和分析FMPRR,通过模型状态空间分析结果,对FMPRR消息传递机制进行验证。     

消息传递方法及其在信息融合中的应用

作为针对复杂问题的确定性推断方法,近年来消息传递方法及其在信息融合领域中的应用备受关注.消息传递为大规模问题提供了基于贝叶斯的、统一的、可扩展的、效率高的推断框架,消息传递方法在概率图模型的节点之间传递消息.首先,对概率图模型进行简要介绍,总结消息传递基础理论方法和近似拓展方法的基本原理、特点以及研究进展;然后,针对信息融合领域中的3类重难点问题:状态估计与平滑、目标跟踪和多源异构数据融合,分别综述消息传递在信息融合中的最新研究进展,并总结不同消息传递方法的适用场景;最后,讨论消息传递方法在信息融合领域未来可能的研究方向.     

机群系统中基于MPI的多维稀疏数组传递方法

机群系统是一种分布存储系统，它主要利用消息传递方式来实现各结点之间的通信。而MPI（Message Passing Interface）作为一种基于消息传递的并行程序设计环境，已广泛应用于多种并行系统，尤其是像机群系统那样的分布存储并行机。该文主要探讨了MPI中的消息传递调用接口，提出了几种有效的在结点间传递多维稀疏数组的方法，并通过实践加以比较。     

XNETi网络接口的差错控制与分包／重组问题的研究

ＸＮＥＴｉ是为ＸＮＥＴ网络互连系统设计的基于ＰＣＩ总线的网络接口,可以有效地支持用户层的消息传递。本文着重介绍了ＸＮＥＴｉ中差错控制与分包／重组等功能的具体实现。