基于MPI的动态负载平衡算法的研究

MPI是目前集群系统中最重要的并行编程工具,它采用消息传递的方式实现并行程序间通信.在MPI并行程序设计中实现负载平衡有着重要的意义,可以减少运行时间,提高MPI并行程序的性能.为了解决同构集群中动态负载均衡问题,提出了一种在MPI并行程序中实现的方法,可有效地根据节点的负载情况在节点间迁移任务.     

一种MPI并行程序设计中的动态负载平衡策略

介绍了MPI并行编程环境和MPI并行程序设计的特点,讨论了在MPI并行程序设计中实现动态负载平衡的方法,提出一种根据计算节点的计算能力和实时负载情况进行任务迁移的动态负载平衡策略。     

基于MPI并行程序的容错系统设计

为了确保并行程序能够在并行环境下准确地运行,须提高系统的可靠性,将容错技术应用到并行计算中。该文针对MPI并行程序提出一种容错系统的设计方法,采用检查点/卷回恢复技术、并添加故障检测功能,能够有效地处理节点失效故障和进程失效故障,在一定范围内实现容错,为MPI环境下进行大规模计算提供一个可使用的应用模型。     

二叉树动态负载平衡方法

文中提出了一种二叉树动态负载平衡方法，该方法使用二叉树动态负载平衡系统模型，解决了集中式负载平衡系统中主结点在分配任务、响应请求以及负载移动时的潜在瓶颈问题；提出了负载小于给定值时请求负载平衡以提高处理器的利用率。分析表明，该方法在可以有效地提高并行计算的性能，特别是对于任务密集的情况。     

一种基于MPI的并行体绘制算法

介绍了基于MPI并行程序开发平台实现的一种三维重建并行处理算法。算法采用了Master-Slave并行计算模型，针对射线投射方法的特点，为减少运算时间，选择对图像空间进行任务划分的策略，并用任务池方法实现了动态负载平衡。通过对虚拟中国人女性一号(VCH-FI)的头部和脚部数据集的重建，表明该算法在任务规模和节点规模上具有较好的可扩展性。     

并行计算中的负载均衡问题研究

在多处理机系统中,任务的静态分配和进程的动态调度都要求做到负载平衡。一个负载平衡的多处理机系统,将具有较高的系统性能,使并行程序总的执行时间最短。本文介绍了并行计算中的负载均衡问题,着重对动态负载平衡算法的组成以及几种典型的动态负载平衡算法进行了讨论与分析。     

一个用于工作站网络的动态负载平衡算法

数学和科学计算中的大部分问题都可以用数据并行程序来开发其并行性,但是在工作站网络环境中,负载波动很大,负载平衡是影响其效率的一个重要因素。本文提出了一种动态负载平衡的算法,它可以使数据并行程序在运行时动态地调整负载。并且文中给出了这种算法的实验结果。     

一种优化MPI程序性能的改进方法

在分布式存储系统上,MPI已被证实是理想的并行程序设计模型。MPI是基于消息传递的并行编程模型,进程间的通信是通过调用库函数来实现的,因此MPI并行程序中,通信部分代码的效率对该并行程序的性能有直接的影响。通过用集群通信函数替代点对点通信函数以及通过派生数据类型和建立新通信域这两种方式,两次改进DNS的MPI并行程序实现,并通过实验给出一个优化MPI并行程序的一般思路与方法。     

一种基于MPI和工作站群集的并行计算

本文主要分析了消息传递的模型及其实现的一种方式MPI,构造了一个四节点基于MPI的工作站群集并实现了求π的并行计算,最后给出性能分析和负载平衡分析.     

Petri网共享合成及其在并行系统中的应用

为了使Petri网技术能够应用于MPI并行程序的正确性和性能的验证,提出了Petri网共享合成运算构建MPI并行程序Petri网的算法。对分布式并行处理系统MPI并行程序的结构与消息传递过程进行分析,给出并行程序基本语句与传递函数的Petri网,将Petri网共享合成运算从两个Petri网的共享合成运算推广到并行程序的多个Petri网的共享合成运算,给出了推广定理和证明。提出了共享合成构建MPI并行程序Petri网的算法,并在消息传递并行系统中给出构建MPI并行程序Petri网的应用示例。实验结果表明,共享合成运算是构建MPI并行程序Petri网模型的一种有效方法。     

基于MPI高性能计算的方法研究

并行处理在计算能力方面与单处理器的串行处理相比有着无可比拟的优势。个人计算机和网络成本的下降使得使用分布式系统进行并行处理的现象越来越普遍,而分布式网络系统中多采用MPI作为并行编程标准。为了减少程序运行时间,改善MPI计算的性能,负载均衡方法尤为重要,本文提出一种在MPI并行处理中负载均衡的方法,可以按照节点的计算能力和负载情况,在节点之间分配和迁移任务。实验表明,本文提出的方法可有效提高MPI并行处理的性能。     

基于反馈机制的动态负载平衡算法研究*

动态负载平衡是提高多处理器系统资源利用率和并行计算性能的重要途径。为了解决变化负载系统中子任务可并行计算的双重循环(PTM-NL)问题,提出一种基于反馈机制的动态负载平衡算法。该算法以处理器作业速度为负载指标,在循环计算中根据反馈的负载指标分配计算任务,动态适应负载变化。实验结果表明,该算法在变化负载的系统中能有效提高PTM-NL问题并行效率。     

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

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

基于MPI_Ruby的自平衡容错型声场并行计算

基于MPI消息传递范型的并行计算是高性能计算热点中的一个主要方向。然而，大规模并行计算应用源码的编制具有相当程度的复杂性，而且静态特征的MPI标准并不提供任何的容错机制和动态任务平衡管理机制。对此，本文以声场并行计算过程为例，介绍了2002年新出现的具有高度易用性的MPI_Ruby语言，给出了一个应用层任务自平衡高度算法和基于组间通信体的容错算法。场场并行计算用MPI_Ruby编写较之用MPI编写能大幅节省源码行数。     

MapReduce框架下一种负载均衡的Top-k连接查询算法

针对传统Top-k连接查询算法在处理海量数据时的时效问题,提出一种基于MapReduce框架的负载均衡的并行Top-k连接查询算法(P-TKJ)。使用直方图形式来存储数据,有助于提高CPU的利用率。同时融入了提前终止策略和磁盘数据的选择性访问,以便提高对HDFS数据访问的性能。另外,提出了一种基于最长处理时间优先(LPT)算法的负载均衡策略来均衡Reduce任务,以此设计出高效的并行Top-k连接算法。一个集群实验结果表明,该方法能够有效缩短算法的执行时间。     

SMP集群系统上矩阵特征问题并行求解器的有效算法

对称矩阵三对角化和三对角对称矩阵的特征值求解是稠密对称矩阵特征问题并行求解器的关键步 .针对SMP集群系统的多级体系结构,基于Householder变换的矩阵三对角化和三对角矩阵特征值问题的分而治之算法,给出了它们的MPI OpenMP混合并行算法 .算法研究集中在SMP集群系统环境下的负载平衡、通信开销和性能评价 .混合并行算法的设计结合了粗粒度线程并行模式和任务共享的动态调用方法,改善了MPI算法中的负载平衡问题、降低了通信开销 .在深腾6800上的实验表明,基于混合并行算法的求解器比纯MPI版本的求解器具有更好的性能和可扩展性 .     

基于分治法求解对称三对角矩阵特征问题的混合并行实现

基于对称三对角矩阵特征求解的分而治之方法,提出了一种改进的使用MPI/Cilk模型求解的混合并行实现,结合节点间数据并行和节点内多任务并行,实现了对分治算法中分治阶段和合并阶段的多任务划分和动态调度.节点内利用Cilk任务并行模型解决了线程级并行的数据依赖和饥饿等待等问题,提高了并行性;节点间通过改进合并过程中的通信流程,使组内进程间只进行互补的数据交换,降低了通信开销.数值实验体现了该混合并行算法在计算效率和扩展性方面的优势.     

异构集群环境下负载平衡调度算法研究与实现

围绕平衡负载这一目标，针对进程级并行任务的动态调度问题进行了研究，提出了一个异构集群环境下动态负载平衡算法，它结合了自适应数据采集与交换算法，有效的解决了服务器之间负载不平衡的问题，提高了系统的吞吐率。     

Cacheminer: A runtime approach to exploit cache locality on SMP

Exploiting cache locality of parallel programs at runtime is a complementary approach to a compiler optimization. This is particularly important for those applications with dynamic memory access patterns. We propose a memory-layout oriented technique to exploit cache locality of parallel loops at runtime on Symmetric Multiprocessor (SMP) systems. Guided by application-dependent and targeted architecture-dependent hints, our system, called Cacheminer, reorganizes and partitions a parallel loop using the memory-access space of its execution. Through effective runtime transformations, our system maximizes the data reuse in each partitioned data region assigned in a cache, and minimizes the data sharing among the partitioned data regions assigned to all caches. The executions of tasks in the partitions are scheduled in an adaptive and locality-presented way to minimize the execution time of programs by trading off load balance and locality. We have implemented the Cacheminer runtime library on two commercial SMP servers and an SimCS simulated SMP. Our simulation and measurement results show that our runtime approach can achieve comparable performance with the compiler optimizations for programs with regular computation and memory-access patterns, whose load balance and cache locality can be well optimized by the tiling and other program transformations. However, our experimental results show that our approach is able to significantly improve the memory performance for the applications with irregular computation and dynamic memory access patterns. These types of programs are usually hard to optimize by static compiler optimizations