曙光1000A上消息传递与共享存储的比较

分布式共享存储虽然有易于编程的优点,但往往被认为效率不高、完全由软件实现的分布式共享存储系统（又称为虚拟共享存储系统）更是如此,文中以典型的消息传递系统ＰＶＭ与分布式共享存储系统ＪＩＡＪＩＡ粉列,报这两种并行程序设计环境的特点,并用７个应用程序在曙光１０００Ａ上分别比较了这两个系统的性能,实验３结果表明,ＪＩＡＪＩＡ的与ＰＶ玎当,但基于ＪＩＡＪＩＡ的并行程序设计却比ＰＶＮ简单得多。     

收缩背包问题的并行分枝界限算法

收缩背包问题（collapsing knapsack problem,CKP)是0－1背包问题的变体,其中背包的容量为所装物品数量的非增函数,针对并行计算的需求,在对CKP问题分解的基础上,给出了求解每个子问题的权分枝界限算法,提出了基于MIMD－DM的收缩背包问题的并行分枝界限算法;并在曙光1000上设计和实现了该算法,以消息传递方式来解决子算法最优解的播送问题,同时给出了子问题的求解顺序,讨论了问题求解过程中的递归深度和系统的通信开销对加速比曲线的影响。     

Robust gossiping with an application to consensus

We study deterministic gossiping in synchronous systems with dynamic crash failures. Each processor is initialized with an input value called rumor. In the standard gossip problem, the goal of every processor is to learn all the rumors. When processors may crash, then this goal needs to be revised, since it is possible, at a point in an execution, that certain rumors are known only to processors that have already crashed. We define gossiping to be completed, for a system with crashes, when every processor knows either the rumor of processor v or that v has already crashed, for any processor v. We design gossiping algorithms that are efficient with respect to both time and communication. Let t<n be the number of failures, where n is the number of processors. If , then one of our algorithms completes gossiping in O(log²t) time and with O(npolylogn) messages. We develop an algorithm that performs gossiping with O(n^1.77) messages and in O(log²n) time, in any execution in which at least one processor remains non-faulty. We show a trade-off between time and communication in gossiping algorithms: if the number of messages is at most O(npolylogn), then the time has to be at least . By way of application, we show that if n−t=Ω(n), then consensus can be solved in O(t) time and with O(nlog²t) messages.     

不确定性MPI／PVM程序的完全调试

讨论如何完全地调试不确定性MPI／PVM并行程序．在循环调试过程中,不确定性导致前次遇到的错误在以后的执行中很可能无法再现．基于MPI／PVM的FIFO通信模型,给出一种记录－重放技术的实现．通过可控制的重放,用户可以覆盖所有可能的程序执行路径,从而达到完全调试的目的．和其它方法相比,所提供的方法所需时空开销要小得多．此技术已在两种消息传递体系结构上得到实现：一种是曙光－2000超级服务器（由国家智能计算机研究中心开发）,它由单处理器（PowerPC）结点经MESH网互联而成;另一种是国家高性能计算中心（     

SIFT特征分布式并行提取算法

SIFT(scale invariant feature transform)特征在物体检测和识别、图像配准与融合、纹理识别、场景分类、人脸检测、图像检索、三维重建、数字水印、影像追踪等领域具有广泛应用,但存在计算量大、消耗时间长的缺点.基于消息传递机制,采用数据并行策略,提出了在PC机群或COW(cluster ofworkstation)上提取图像SIFT特征的分布式并行算法(DP-SIFT算法):根据特征空间-高斯尺度金字塔的特点提出了高度宽度受限的数据块划分算法,设计了数据分配和特征调整方法;研究了数据块划分和数据发送方法对通信时间的影响,提出了基于消息传递机制的并行图像处理中数据块划分与数据发送方式协同对通信优化的策略;实验结果表明DP-SIFT算法具有良好的加速性能和较高的处理器利用效率,千兆以太网连接32核的PC机群系统图像规模为1024×768时,加速比和处理器效率分别可以达到20和0.6;图像规模为2048×1536时可达18和0.56.     

基于消息传递的移动EJB对象强迁移构件模型的研究

移动计算环境下的Agent对象迁移包括强迁移和弱迁移技术。在特定的多环境中，一个重要的问题是合理地为移动Agent对象实现异地迁移计算提供有效的管理和支持，目前使用的支持系统有基于传统解释语言的、基于CORBA平台的和基于Java语言的。在移动Agent对象强迁移技术的理论基础上，提出了一种基于消息传递的移动EJB对象强迁移构件模型，分析与改进了适合强迁移对象进程消息发送的同步消息传递算法，使得该构件模型的消息传递具有很好的同步机制，从而提供了一种良好的移动Agent对象迁移构件化管理支持方式。     

MPICH在Windows操作系统中的实现与应用

该文给出了对应于MPI标准的MPICH软件包在Windows操作系统中的配置和在MSVC＋＋中的实现方法，并对MPI与C／C＋＋绑定的基本编程进行了简要介绍。然后将其与一种电磁场数值算法——时域有限差分法相结合，以一维情况为例，讨论了网络并行时域有限差分法的实现方法。通过在由两台PC机构成的最简单的PC机群上的编程实现，验证了这种方法的可行性和高效性，实验结果表明通过MPICH软件包实现时域有限差分法的网络并行运算，可以使这种算法的加速比达到1．8。     

一种高效可靠的移动Agent间通信机制

作为未来分布式系统的一种主流计算模式,移动Agent技术具有广阔的研究前景.协作与通信是移动Agent系统必不可少的组成部分.然而由于Agent的移动性和自主性,现有研究工作所提出的移动Agent间通信机制在可靠性尤其是有效性上存在着一定的不足,如不能够在底层理想地解决通信失效等问题.针对上述问题,设计了一种具有高度自适应性的消息传递机制--EMFS(efficiently message forwarding scheme).该协议在Agent寻址上采取指针寻址和集中式寻址相结合的方式;而对于通信失效的解决则采用了以检测法为主,辅以同步的方法,从而能够在彻底解决通信失效的基础上,较大地提高整个通信系统的性能.此外还对协议的主要参数进行了讨论,从理论上分析比较了EMFS的性能,并给出了模拟实验数据,说明了协议的正确性和高效性.     

基于机群系统的C＋＋语言并行化实现

在计算机机群系统环境下，将面向对象程序设计技术与并行技术相结合能够有效地降低并行程序设计的难度，提高并行程序的可维护性、可移植性和可重用性．本文探讨了机群系统下的Ｃ＋＋语言并行化实现的几种方法，分别介绍了基于消息传递的ＭＰＣ＋＋、基于共享对象的ＳＯＣ＋＋和基于对象级并行的ＣＣＰＰ语言模型、编程接口及其实现，并给出了几种语言系统评测的结果及分析．     

多计算机互连网通信中关于死锁问题的一种理论

如何获得死锁而且通信性能良好的选路算法始终是人们十分关心的问题。本文提出了纯分流点的概念并证明了选路算法无死锁的充要条件，从理论上解决了死锁关系问题，为死锁的判定，消除和设计无死锁的算法提供了有力的依据。