MPICH作业提交方式的研究及改进

通过对MPICH作业提交方式的研究，进而优化作业的提交过程，提出了一种SBM方法，即一种新的作业提交方式，减少了通信的时间，得到更高的通信性能，实现了对MPICH作业提交方式的改进。设计并实现了基于SBM方法的MPICH系统，并与采用传统方法的系统进行了性能对比，证明了在大型并行计算中，基于SBM作业提交方式可以得到更好的通信性能。     

一种基于分组动态帧与二叉树递归识别的射频识别防冲突算法

首先分析和比较了传统射频识别防冲突算法的时间复杂度和通信复杂度,并在总结各自缺点的基础上提出了一种新颖的射频识别防冲突算法．该算法基于标签最优分组、最优帧长选择以及碰撞时隙内二叉树递归识别等策略．其次,建立了系统模型,并对该算法的时间复杂度和通信复杂度进行了数学推导．仿真数据表明,以上指标的理论值和模拟值有较好的一致性．与传统算法相比,该算法具有较佳的总体性能,系统吞吐率达到0.41左右,通信复杂度与EDFSA算法近似,但与树形算法相比减少了50%以上;此外,该算法受初始标签数量估计值及标签ID长度的影响均较小．     

最优二叉树的逆推调位启发式算法设计

针对构造有个带权叶子结点的最优二叉树提出一种新颖的启发式算法,该算法根据递推算法的逆推原理,利用结点位置的调动产生的权的变化值来决定节点在最优二叉树中的位置。该算法在使二叉树达到最优的运算过程中,完全区别于以往的哈夫曼算法。逆推调位算法步骤简明,速度迅捷,最后以举例的方式说明该算法的实效性。     

遍历二叉树的一种改进算法

在计算机科学与工程中,二叉树是一类十分重要的数据结构,有着广泛的应用。本文介绍二叉树的主要操作:遍历二叉树,和遍历算法;对于后序遍历,提出一种新的改进的非递归算法。传统的后序遍历非递归算法,需要为二叉树的结点建立标志位,用以判断该结点是否应进行访问。标志位随同结点的指针一起存入栈中。标志位的使用无疑增加了存贮空间。我们提出的改进算法,无须为二叉树的结点建立标志位,从而节省了存贮空间,但并不增加算法的时间复杂度。算法中所采用的思想与技巧亦可以推广应用到一般树(多叉树)的遍历算法中。     

线性时间复杂度的二叉树绘制算法

二叉树一种非常重要的数据结构,本文论述了绘制二叉树算法的基本思想,建立二叉树与満二叉树结点间的映射关系,并给出可行的对应算法,且其时间复杂度是线性的。     

线索二叉树的研究

线索二叉树是数据结构中的一项重要内容。本文提出了对二叉树加线索时的一种新方法。比较的结果表明，新算法所生成的线索二叉树比传统的先序和后序线索二叉树优越。     

基于Myrinet上MPICH-2的实现

在当前并行计算环境中的通信网络中,MPICH-1并行系统可以使用Internet和Myrinet千兆位包交换网络,而MPICH-2并行系统只能使用Internet,由于通信时间的限制而影响了整个系统性能.对MPICH-1和MPICH-2中的作业提交模式进行了研究,给出了一种在MPICH-2中使用Myrinet网络来提交作业的应用,从而达到减少了通信时间的目的.     

遍历二叉树的递归与非递归算法浅析

二叉树是数据结构中最常见的一种存储形式,而遍历二叉树又是二叉树中最重要的操作.该文分别以递归和非递归两种不同的算法来分析遍历二叉树的过程,旨在用简单明了的方法来实现二叉树的遍历,且先序、中序、后序三种遍历方式都可通过这两种算法实现.     

二叉树的遍历算法

二叉树是一种重要的非线性数据结构,在计算机领域有着广泛的应用。着重介绍二叉树的遍历问题,描述了递归、非递归、层次等二叉树遍历的多种算法。     

基于sDaCe-time的二叉树表示动态环境中的路径规划

研究具有空间和时间的space-time三维动态环境下的机器人路径规划,分析了四义树表示二维空间的搜索算法,在此基础上,提出采用二叉树表示二维空间的方法,时间信息中增加加速度,利用二叉树遍历方法和A*算法,设计一个在动态障碍物环境下进行路径规划的新算法,并在足球机器人系统中进行仿真,实现了较好的路径规划.     

KD60集群消息传递接口群集通信算法优化

大规模集群已经发展到多核的时代,多核架构对并行计算提出了新的要求。消息传递接口(MPI)是最常用的并行编程模型,而群集通信又是MPI中的重要组成部分。研究高效的群集通信算法对并行计算效率的提升有着重要的作用。KD60平台是采用首款国产多核芯片——龙芯3号搭建的国产万亿次多核集群。首先分析了KD60平台多核集群的体系特征以及多核架构下通信具有的层次性特征;然后分析原有群集通信算法实现原理及其不足;最后以广播为例,在原有算法基础上,采用一种基于片上多核(CMP)架构改进算法,改变原有算法通信模式,同时结合实验平台KD60体系特征,对算法做了体系相关优化。实验结果表明,改进算法能够很好地利用多核结构的特点,提高了群集通信广播算法的性能。     

MPI + MPI: a new hybrid approach to parallel programming with MPI plus shared memory

Hybrid parallel programming with the message passing interface (MPI) for internode communication in conjunction with a shared-memory programming model to manage intranode parallelism has become a dominant approach to scalable parallel programming. While this model provides a great deal of flexibility and performance potential, it saddles programmers with the complexity of utilizing two parallel programming systems in the same application. We introduce an MPI-integrated shared-memory programming model that is incorporated into MPI through a small extension to the one-sided communication interface. We discuss the integration of this interface with the MPI 3.0 one-sided semantics and describe solutions for providing portable and efficient data sharing, atomic operations, and memory consistency. We describe an implementation of the new interface in the MPICH2 and Open MPI implementations and demonstrate an average performance improvement of 40 % to the communication component of a five-point stencil solver.     

并行程序设计环境的研究

MPI(MessagePassingInterface)是目前一种比较著名的应用于并行环境的消息传递标准。MPICH是MPI1.2标准的一个完全实现,也是应用范围最广的一种并行及分布式环境。MPICH除包含MPI函数库之外,还包含了一套程序设计以及运行环境。本文将简要介绍如何应用MPICH的Windows版本,建立一个基于Windows的并行程序设计及运行环境。     

几何定理并行验证算法研究

几何定理证明的数值验证法以数值计算代替符号计算来提高效率，但是在实际应用中对复杂命题的解题效率还存在问题。该文尝试用并行计算方法来提高算法效率，分析了MPI编程模型下的任务划分、通信组织、任务调度等问题，并在MPICH2下实现了数值并行验证算法，对算法的并行性能指标进行了测试，得到了较好的结果。     

An integrated fine-grain runtime system for MPI

Fine-grain MPI (FG-MPI) extends the execution model of MPI to allow for interleaved execution of multiple concurrent MPI processes inside an OS-process. It provides a runtime that is integrated into the MPICH2 middleware and uses light-weight coroutines to implement an MPI-aware scheduler. In this paper we describe the FG-MPI runtime system and discuss the main design issues in its implementation. FG-MPI enables expression of function-level parallelism, which along with a runtime scheduler, can be used to simplify MPI programming and achieve performance without adding complexity to the program. As an example, we use FG-MPI to re-structure a typical use of non-blocking communication and show that the integrated scheduler relieves the programmer from scheduling computation and communication inside the application and brings the performance part outside of the program specification into the runtime.     

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

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

MPI容错机制的研究

MPI是广泛应用于集群系统的并行程序开发环境，MPI的容错是集群系统可靠性的关键问题。该文讨论了MPI标准中的容错，结合协调设置检查点和同步卷回等机制设计了基于检查点的卷回恢复系统MPIChaRR、该系统应用于Linux集群机，MPICH应用程序运行中的节点故障恢复是对用户透明的。     

A Speculative and Adaptive MPI Rendezvous Protocol Over RDMA-enabled Interconnects

Overlapping computation with communication is a key technique to conceal the effect of communication latency on the performance of parallel applications. Message Passing Interface (MPI) is a widely used message passing standard for high performance computing. One of the most important factors in achieving a good level of overlap is the MPI ability to make progress on outstanding communication operations. In this paper, we propose a novel speculative MPI Rendezvous protocol that uses RDMA Read and RDMA Write to effectively improve communication progress and consequently the overlap ability. Performance results based on a modified MPICH2 implementation over 10-Gigabit iWARP Ethernet reveal a significant (80–100%) improvement in receiver side overlap and progress ability. We have also observed up to 30% improvement in application wait time for some NPB applications as well as the RADIX application. For applications that do not benefit from this protocol, an adaptation mechanism is used to stop the speculation to effectively reduce the protocol overhead.     

基于MPI的并行程序设计

在介绍消息传递接口标准(MPI)和分析并行程序设计方法的基础上,提出了在并行程序设计中需要进行算法级分析和程序级测试,以此来对影响具体的并行程序执行效率的因素进行分析,并用实例验证了分析结果。最后对MPI的实现之一———MPICH1.2.5版本的不足,提出了改进的方法。     

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

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