一维高效动态负载平衡方法：多层均权法

提出了一个适合同构和异构并行计算环境的高效一维动态负载平衡方法;多层均权法,并成功地解决了多物质非定常流体力学Lagrange法并行数值模拟过程中的动态负载不平衡问题。文中给出了详细的理论分析以及两台并行机上结合某实际物理问题组织的并行数值实验。     

有向图并行计算中的多目标剖分算法

在以离散网格为基础的某些数值模拟中,网格间的数据依赖关系可以抽象为有向图．如何剖分这些有向图成多个子图,将各子图对应的数值模拟任务映射到不同的处理机,是该类数值模拟并行计算的基础．剖分算法中,需要综合考虑连通性、并行度、负载平衡、通信开销四个目标．文章在传统有向图剖分算法的基础上,提出了一个权衡这四个目标的有向图多目标剖分区域分解算法．应用于二维非结构网格上的柱对称中子输运并行计算中,通量扫描并行算法在该区域剖分算法上获得的并行效率比原来的无向图区域剖分算法高50％以上．     

一种基于实测的自动负载建模算法

负载平衡是影响大规模并行计算效率的一个关键因素,准确的负载建模是负载平衡的基础.提出了一种基于实测的自动负载建模算法.该算法无需用户提供信息,具有良好的理论保证以及近似线性的计算复杂度和完全的并行性.2400个进程上的分子动力学模拟表明,该算法执行速度快,同时能够保证60％以上的负载平衡效率.     

大规模并行 CFD 软件的负载平衡设计

基于多区结构网格的计算流体力学方法,在并行处理的难点是多个网格数据块在计算资源上的高效合理分配,以实现大规模并行环境下的负载平衡。本文围绕负载平衡问题,介绍了 CCFD 软件开展的一些工作,包括：1. 面向结构网格的双层图剖分策略,通过细层图剖分环节考虑计算量和通信量的负载平衡;2. 建立可细分的重叠网格体系,并基于该体系建立了重叠网格系统的双级负载平衡模型。算例验证表明,所采用的负载平衡策略在大规模并行环境下能获得较高并行效率。     

基于计算量拟合的并行数据剖分算法

提出了一种基于计算量拟合的并行数据剖分算法,算法针对并行计算中静态负载不平衡问题,由各处理器实测计算时间,拟合出各基本数据剖分单元的计算量,在此基础上按各处理器计算时间相等的原则确定数据剖分。模拟试验表明,该算法能快速有效地实现各处理器的负载平衡。     

基于Mobile Agent技术的负载平衡模型研究

为更好地实现分布式系统中的负载平衡，结合自主设计的分布式数据库服务器系统DDSS（distributed database server system），抽象出分布式冗余系统的3层管理框架，从对负载索引的客观描述与定义着眼，引入服务请求消化率、阈值负载贴近度等概念及主动负载平衡的思想，提出并实现了基于移动代理技术的负载平衡模型MMA，并对其性能进行了分析．通过分析表明，基于移动代理技术的负载平衡模型MMA具有代价小、智能性好、效率高及具有对负载索引的刻画客观准确等优点．     

基于边权约束法实现接触问题多约束图剖分

为提高接触问题并行计算的效率,分析内力计算和接触计算过程的并行性,提出基于边权约束法构造接触多约束图的方法,对比和分析多约束图剖分算法和双重区域剖分算法的负载平衡和通信性能.数值实验表明,在典型二维模型中多约束图剖分算法的负载平衡性能略低于双重区域剖分算法,但仍可将负载不平衡度控制在较好的范围内,简化并行计算的通信过程,减少总通信量并降低动态通信量比例.     

基于多块结构网格大规模并行计算的负载均衡设计及实现

结构网格具有网格生成速度快、质量高、数据结构相对简单、较适用于流体表面应力集中的运算等优点。在大规模 CFD（Computational Fluid Dynamics）并行计算中,需要将网格区域划分为多块网格,而多块网格之间的数据通信会制约并行计算能力的提高,因此对结构网格的负载平衡优化是提高并行计算能力的重点。本文提出了一个采用多层次 k-way 多约束条件图剖分算法来改进负载平衡的方案,并对 M6 翼型和 CRM 模型的多种规模进行了实际计算,结果证明多层次 k-way图剖分算法能够有效地优化负载平衡,在此基础上得到了最优节点间的计算负载平衡和通信负载平衡,最终达到了理想的并行效率。     

数据不规则问题并行计算的负载平衡策略的研究

讨论以边缘通信为特征的数据不规则问题并行计算的静态负载平衡策略。从图论的角度讨论了静态负载平衡问题，给出三个优化目标，即点集等分，最短通路和通信量最小。对于以边缘通信为特征的一般数值计算问题，论述了二维问题正方形划分总通信量最小、并行效率最高，三维问题立方体划分总通信量最小、并行效率最高的结论。基于以上结论和实际课题特点，提出一种一维优先的规则分块算法和基于自动重分块的不规则分块算法相结合的方法。实验证明，该方法实现简单，能够处理不同规模的数据不规则问题，达到较优的负载平衡和较高的通信效率，提高并行程序的整体效率．     

基于多蚁群算法的无线传感器网络路由的跨层设计

针对事件驱动型无线传感器网络对数据传输的强实时性和高可靠性的要求,将统计获得的节点接入效率和负载队列长度等MAC层状态信息作为路由度量参数。考虑到蚂蚁网络算法在重负荷网络中存在传输延迟大、聚合速度慢等缺陷,提出了一种基于多蚁群算法的负载感知和高效接入的跨层路由协议,该协议把节点的单跳延迟、负载及带宽接入效率等参数作为路径的启发值进行路由优化。仿真结果表明,基于多蚁群算法的路由协议能够保证数据传输的实时性,能够实现无线传感器网络的拥塞控制及负载平衡。     

A novel dynamic load balancing scheme for parallel systems

Adaptive mesh refinement (AMR) is a type of multiscale algorithm that achieves high resolution in localized regions of dynamic, multidimensional numerical simulations. One of the key issues related to AMR is dynamic load balancing (DLB), which allows large-scale adaptive applications to run efficiently on parallel systems. In this paper, we present an efficient DLB scheme for structured AMR (SAMR) applications. This scheme interleaves a grid-splitting technique with direct grid movements (e.g., direct movement from an overloaded processor to an underloaded processor), for which the objective is to efficiently redistribute workload among all the processors so as to reduce the parallel execution time. The potential benefits of our DLB scheme are examined by incorporating our techniques into a SAMR cosmology application, the ENZO code. Experiments show that by using our scheme, the parallel execution time can be reduced by up to 57% and the quality of load balancing can be improved by a factor of six, as compared to the original DLB scheme used in ENZO.     

并行分治计算中的一种Work-stealing策略

在机群尤其是共享式多用户机群环境中提高非规则问题的并行计算效率是一项具有挑战性的工作.给出了一种适于多核处理器节点构成的机群的层次Work-stealing负载均衡策略(简称HWS),它能够有效利用节点的动态变化的可用计算资源.分析了分治计算问题中的动态性与非规则性,并使用HWS策略对分治计算问题进行了动态负载均衡(DLB)实验.实验表明,HWS在加速比、CPU利用率和负载分布等性能指标上均优于Work-sharing和Satin-CRS策略.     

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

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

Dynamic Load Balancing for Short-range Parallel Molecular Dynamics Simulations

The iterative Multilevel Averaging Weight (MAW) algorithm presented in paper [1] is modified to solve the dynamic load imbalance problems arising from the two-dimensional short-range parallel molecular dynamics simulations in this paper. Firstly, five types of load balancing models are given which allows detailed studies of the algorithm. In particular, it shows that for strip decomposition, the number of iteration needs for the system to converge from an initially unbalanced state to a well balanced state is bounded by 2 log P , where P is the number of processors. This result can permit the algorithm to efficiently track fluctuations in the molecular density as the simulation progresses, and is much better than that of the Cellular Automaton Diffusion (CAD) scheme presented in paper [2] . Secondly, we apply MAW algorithm to solve the load imbalance problem in the parallel molecular dynamics simulation for higher speed wall collisions. At last, the numerical experimental results and parallel computing performance with MPI-1.2 under a PC-Cluster consists of 64 Pentium-III 500 MHz nodes connected by 100 Mbps Switches are given in this paper.     

Heterogeneous pipelined square-root Kalman Filter algorithm for the MMSE-OSIC problem

This paper describes a pipelined parallel algorithm for the MMSE-OSIC decoding procedure proposed in V-BLAST wireless MIMO systems, for heterogeneous networks of processors. It is based on a block version of the square-root Kalman Filter algorithm that was initially devised to solve the RLS problem. It has been parallelized in a pipelined way obtaining a good efficiency and scalability. The optimum load balancing for this parallel algorithm is dynamic, but we derive a static load balancing scheme with good performance.     

一种基于主负载信息表的动态负载平衡模型及其均衡算法研究

1.引言对于静态和动态负载平衡算法的研究,国际上已经有了30多年的历史。特别是近年来随着一些高速网络的兴起(如ATM),对于它的研究仍然方兴未艾。但是因为一些并行任务之间的互相依赖关系和通讯量的大小很难在编译时就进行确定,所以人们更加倾向于研究动态负载平衡。虽然目前国内外在这方面产生了不少各有特色的算法,譬如Hui等人就在理     

Optimal Load Balancing in a Multiple Processor System with Many Job Classes

A loosely coupled multiprocessor system contains multiple processors which have their own local memories. To balance the load among multiple processors is of fundamental importance in enhancing the performance of such a multiple processor system. Probabilistic load balancing in a heterogeneous multiple processor system with many job classes is considered in this study. The load balancing scheme is formulated as a nonlinear programming problem with linear constraints. An optimal probabilistic load balancing algorithm is proposed to solve this nonlinear programming problem. The proposed load balancing method is proven globally optimum in the sense that it results in a minimum overall average job response time on a probabilistic basis.     

Corollaries to two-limit cycle theorems†

A load processor is a system that has a buffer which can receive load and store it while it is waiting to be processed and has a local decision-making policy for determining if portions of its load should be sent to other load processors. A load balancing system is a set of such load processors that are connected in a network so that (i) they can sense the amount of load in the buffers of neighbouring processors and pass load to them, and (ii) so that, via local information and decisions by the individual load processors, the overall load in the entire network can be balanced. Such balancing is important to ensure that certain processors are not overloaded while others are left idle (i.e. load balancing helps avoid underutilization of processing resources). The topology of the network, delays in transporting and sensing load, types of load, and types of local load passing policies all affect the performance of the load balancing system. In this paper, we show how a variety of load balancing systems can be modelled in a discrete event system (DES) theoretic framework, and how balancing properties and performance can be characterized and analysed in a general Lyapunov stability theoretic framework.     

Load balancing strategies for a parallel ray-tracing system based on constant subdivision

Static and dynamic load balancing strategies for a multiprocessor system for a ray tracing algorithm based on constant subdivision are presented. An object space is divided into regular cubes (subspaces), whose boundary planes are perpendicular to the coordinate axes, and these are allocated to the processors in the system. Here, load balancing among the processors is the most important problem. Firstly, in a category of static load balancing, strategies for mapping the subspaces into the processors are evaluated by simulation. Moreover, we propose a hierarchical multiprocessor system in order to realize dynamic load balancing with the static one. Its architecture can overcome the limitation of the static load balancing in a large scale multiprocessor system.