Strategy and Simulation of Adaptive RID for Distributed Dynamic Load Balancing in Parallel Systems

Dynamic load balancing schemes are significant for efficiently executing nonuniform problems in highly parallel multicomputer systems.The objective is to minimize the total exectuion time of single applications.This paper has proposed an ARID strategy for distributed dynamic load balancing.Its principle and control protocol are described,and te communication overhead,the effect on system stability and the performance efficiency are analyzed.Finally,simulation experiments are carried out to compare the adaptive strategy with other dynamic load balancing schemes.     

A dynamic and adaptive load balancing strategy for parallel file system with large-scale I/O servers

Many solutions have been proposed to tackle the load imbalance issue of parallel file systems. However, all these solutions either adopt centralized algorithms, or lack considerations for both the network transmission and the tradeoff between benefits and side-effects of each dynamic file migration. Therefore, existing solutions will be prohibitively inefficient in large-scale parallel file systems. To address this problem, this paper presents SALB, a dynamic and adaptive load balancing algorithm which is totally based on a distributed architecture. To be also aware of the network transmission, SALB on the one hand adopts an adaptively adjusted load collection threshold in order to reduce the message exchanges for load collection, and on the other hand it employs an on-line load prediction model with a view to reducing the decision delay caused by the network transmission latency. Moreover, SALB employs an optimization model for selecting the migration candidates so as to balance the benefits and the side-effects of each dynamic file migration. Extensive experiments are conducted to prove the effectiveness of SALB. The results show that SALB achieves an optimal performance not only on the mean response time but also on the resource utilization among the schemes for comparison. The simulation results also indicate that SALB is able to deliver high scalability.     

A refinement-tree based partitioning method for dynamic load balancing with adaptively refined grids

The partitioning of an adaptive grid for distribution over parallel processors is considered in the context of adaptive multilevel methods for solving partial differential equations. A partitioning method based on the refinement-tree is presented. This method applies to most types of grids in two and three dimensions. For triangular and tetrahedral grids, it is guaranteed to produce connected partitions; no other partitioning method makes this guarantee. The method is related to the OCTREE method and space filling curves. Numerical results comparing it with several popular partitioning methods show that it computes partitions in an amount of time similar to fast load balancing methods like recursive coordinate bisection, and with mesh quality similar to slower, more optimal methods like the multilevel diffusive method in ParMETIS.     

A repartitioning hypergraph model for dynamic load balancing

In parallel adaptive applications, the computational structure of the applications changes over time, leading to load imbalances even though the initial load distributions were balanced. To restore balance and to keep communication volume low in further iterations of the applications, dynamic load balancing (repartitioning) of the changed computational structure is required. Repartitioning differs from static load balancing (partitioning) due to the additional requirement of minimizing migration cost to move data from an existing partition to a new partition. In this paper, we present a novel repartitioning hypergraph model for dynamic load balancing that accounts for both communication volume in the application and migration cost to move data, in order to minimize the overall cost. The use of a hypergraph-based model allows us to accurately model communication costs rather than approximate them with graph-based models. We show that the new model can be realized using hypergraph partitioning with fixed vertices and describe our parallel multilevel implementation within the Zoltan load balancing toolkit. To the best of our knowledge, this is the first implementation for dynamic load balancing based on hypergraph partitioning. To demonstrate the effectiveness of our approach, we conducted experiments on a Linux cluster with 1024 processors. The results show that, in terms of reducing total cost, our new model compares favorably to the graph-based dynamic load balancing approaches, and multilevel approaches improve the repartitioning quality significantly.     

Dynamic balancing of communication and computation load for HLA-based simulations on large-scale distributed systems

Dynamic balancing of computation and communication load is vital for the execution stability and performance of distributed, parallel simulations deployed on the shared, unreliable resources of large-scale environments. High Level Architecture (HLA) based simulations can experience a decrease in performance due to imbalances that are produced initially and/or during run time. These imbalances are generated by the dynamic load changes of distributed simulations or by unknown, non-managed background processes resulting from the non-dedication of shared resources. Due to the dynamic execution characteristics of elements that compose distributed applications, the computational load and interaction dependencies of each simulation entity change during run time. These dynamic changes lead to an irregular load and communication distribution, which increases overhead of resources and latencies. A static partitioning of load is limited to deterministic applications and is incapable of predicting the dynamic changes caused by distributed applications or by external background processes. Therefore, a scheme for balancing the communication and computational load during the execution of distributed simulations is devised in a scalable hierarchical architecture. The proposed balancing system employs local and cluster monitoring mechanisms in order to observe the distributed load changes and identify imbalances, repartitioning policies to determine a distribution of load and minimize imbalances. A migration technique is also employed by this proposed balancing system to perform reliable and low-latency load transfers. Such a system successfully improves the use of shared resources and increases distributed simulations’ performance by minimizing communication latencies and partitioning the load evenly. Experiments and comparative analyses were conducted in order to identify the gains that the proposed balancing scheme provides to large-scale distributed simulations.     

Dynamic load balancing with adaptive factoring methods in scientific applications

To improve the performance of scientific applications with parallel loops, dynamic loop scheduling methods have been proposed. Such methods address performance degradations due to load imbalance caused by predictable phenomena like nonuniform data distribution or algorithmic variance, and unpredictable phenomena such as data access latency or operating system interference. In particular, methods such as factoring, weighted factoring, adaptive weighted factoring, and adaptive factoring have been developed based on a probabilistic analysis of parallel loop iterates with variable running times. These methods have been successfully implemented in a number of applications such as: N-Body and Monte Carlo simulations, computational fluid dynamics, and radar signal processing. The focus of this paper is on adaptive weighted factoring (AWF), a method that was designed for scheduling parallel loops in time-stepping scientific applications. The main contribution of the paper is to relax the time-stepping requirement, a modification that allows the AWF to be used in any application with a parallel loop. The modification further allows the AWF to adapt to load imbalance that may occur during loop execution. Results of experiments to compare the performance of the modified AWF with the performance of the other loop scheduling methods in the context of three nontrivial applications reveal that the performance of the modified method is comparable to, and in some cases, superior to the performance of the most recently introduced adaptive factoring method.

A Dynamic Load Balancing Mechanism for Distributed Systems

It is desirable in a distributed system to have the system load balanced evenly among the nodes so that the mean job response time is minimized.In this paper,we present a dynamic load balancing mechanism(DLB).It adopts a cntralized approach and is network topology independent.The DLB mechanism employs a set of threscholds which are automatically adjusted as the system load changes.It also provides a simple mechanism for the system to switch between periodic and instantaneous load balancing policies with ease.The performance of the proposed algorithm is evaluated by intensive simulations for various parameters.Te simulation results show that the mean job response time in a system implementing DLB algorithm is significantly lower than the same system without load balancings.Furthermore,compared with a previously proposed algorithm,DLB algorithm demonstrates improved performance,especially when the system is heavily loaded and the load is unevenly distributed.     

并行燃烧数值模拟计算优化——面向自适应非结构网格的动态负载平衡方法

燃烧数值模拟计算通常采用非结构网格模拟计算区域。在非结构网格上进行并行模拟计算时,其自适应方式使得不同进程上的计算负载频繁变动,且差异巨大,导致并行计算效率低下。为了提高并行计算的效率,一个有效的方法是采用动态负载平衡技术。提出一种针对燃烧的化学反应状态的动态负载平衡方法,该方法采用不同策略对化学反应不同阶段各进程上的计算负载进行预测,根据预测结果平均进程间的计算任务,达到负载平衡。实验分析表明,该方法能有效地降低进程间的负载不平衡程度,使得模拟计算的总体运行时间降低了10％。     

Performance of parallel computations with dynamic processor allocation

In parallel adaptive mesh refinement (AMR) computations the problem size can vary significantly during a simulation. The goal here is to explore the performance implications of dynamically varying the number of processors proportional to the problem size during simulation. An emulator has been developed to assess the effects of this approach on parallel communication, parallel runtime and resource consumption. The computation and communication models used in the emulator are described in detail. Results using the emulator with different AMR strategies are described for a test case. Results show for the test case, varying the number of processors, on average, reduces the total parallel communications overhead from 16 to 19% and improves parallel runtime time from 4 to 8%. These results also show that on average resource utilization improves more than 37%.     

Achieve load balancing with a dynamic re-routing CICQ switching scheme

Multi-path based routing and switching can achieve network-wide load balancing and reduce the port conflicts of switching devices.Motivated by this novel idea,in this paper,through analyzing the feasibility of implementing multi-next-hops in core switching networks comprehensively,we advance a switching scheme called MHRS(multi-next-hop re-routing switch)and a forwarding table management scheme called HMFT(hierarchical multi-stage forwarding table)to support multi-next-hop dynamical re-routing.MHRS implements dynamical re-routing in the switches according its congestion status to achieve real-time load balancing,while HMFT can provide traffic with different forwarding paths based on their QoS requirements.Theoretical analysis and simulation results show that switches equipped with HMFT and MHRS can provide good delay and throughput performance.Besides,they can reduce port conflicts significantly.     

一种基于CICQ的动态重路由交换机制

多径路由交换机制能够通过改变到达网络交换节点的流量分布缓解交换系统的端口争用.本文深入探讨了多下一跳交换机制在核心交换网实施的可能性,提出了一种支持动态重路由的交换结构MHRS和支持多下一跳流量均衡的转发表管理结构HMFT.MHRS算法根据交换系统当前拥塞度实施交换系统内部的动态重路由,实现网络流量的实时动态均衡.HMFT对多下一跳交换节点进行QoS度量和区分,从而为不同业务需求提供不同转发路径.理论分析和仿真结果表明:以MHRS和HMFT算法为构件的网络交换系统能够获得良好的时延和吞吐量保障.     

Static load balancing for a parallel ray tracing on a MIMD hypercube

A parallel ray tracing algorithm is presented. It subdivides the seene into 3D regions, the adjacency of which is modelled by a connectivity graph of regions. Since with each region is associated a ray tracing process, this graph becomes a graph of processes, the edges of which represent the communications between processes. This graph of processes is suitably mapped onto a hypercube topology so as to minimize the communication cost. Static load balancing is performed and solutions are brought to the problems of network congestion and termination.This work has been supported byC ³ and by the CCETT (Centre Commun d'Etudes de Télédiffusion et Télécommunications) under contract 86ME46     

WSN中一种负载均衡的动态非均匀分簇方案

无线传感器网络(WSN)是由资源受限的传感器节点构成,节点能耗对网络的性能有着重要影响,对网络进行分簇可以有效地控制节点整体能耗。针对网络实际运行时节点状态和事件位置动态变化等特点,提出了一种负载均衡的动态非均匀分簇方案。方案主体思路是:首先网络利用O-LEACH算法自组织地进行非均匀分簇,接着动态地从簇头中选举出一定数量的决策节点用于网络的数据汇聚,并根据事件发生位置和节点状态变换而动态更改决策节点角色。仿真结果表明,与CAPNet方案相比,该方案均衡了网络能耗,提高了传输效率,延长了网络生命周期。     

Cooperative load balancing in distributed systems

A serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. In this paper, we formulate the static load‐balancing problem in single class job distributed systems as a cooperative game among computers. The computers comprising the distributed system are modeled as M/M/1 queueing systems. It is shown that the Nash bargaining solution (NBS) provides an optimal solution (operation point) for the distributed system and it is also a fair solution. We propose a cooperative load‐balancing game and present the structure of NBS. For this game an algorithm for computing NBS is derived. We show that the fairness index is always equal to 1 using NBS, which means that the solution is fair to all jobs. Finally, the performance of our cooperative load‐balancing scheme is compared with that of other existing schemes. Copyright © 2008 John Wiley & Sons, Ltd.     

An adaptive load balancing management technique for RFID middleware systems

In recent years, Radio Frequency Identification (RFID) industries have taken a great interest in utilizing the benefits of RFID for supply chain management, inventory control and various other applications. This paper proposed an adaptive load balancing technique for RFID middleware systems to meet the demands of scalability and heterogeneity. First, we explored five basic load balancing policies, namely, information policy, job selection policy, transfer policy, initiation policy and location policy. Eighteen load balancing schemes were then proposed for RFID middleware systems that were combinations of various types of the five basic load balancing policies. Our empirical study suggested that these load balancing strategies performed differently under different workload statuses. Finally, an adaptive load balancing strategy was proposed. The load balancing schemes and the proposed adaptive load balancing strategy have been implemented in the RFID Middleware Load Management System (RM‐LMS). Copyright © 2010 John Wiley & Sons, Ltd.     

Data partitioning and load balancing in parallel disk systems

Parallel disk systems provide opportunities for exploiting I/O parallelism in two possible ways, namely via inter-request and intra-request parallelism. In this paper, we discuss the main issues in performance tuning of such systems, namely striping and load balancing, and show their relationship to response time and throughput. We outline the main components of an intelligent, self-reliant file system that aims to optimize striping by taking into account the requirements of the applications, and performs load balancing by judicious file allocation and dynamic redistributions of the data when access patterns change. Our system uses simple but effective heuristics that incur only little overhead. We present performance experiments based on synthetic workloads and real-life traces. Received May 17, 1994 / Accepted June 9, 1997     

面向同构型多处理机系统的动态负载平衡算法

为了解决同构型多处理机系统中的负载不平衡问题,提出一种分布式控制、发送者驱动的动态平衡算法,该算法利用CPU队列长度衡量处理机负载状态、利用进程执行时间选取适合被迁移的负载、利用较完备的消息机制传播处理机负载状态和负载平衡要求,适用于计算密集型任务.实验结果验证了该算法的有效性.     

Managing complex data and geometry in parallel structured AMR applications

Adaptive mesh refinement (AMR) is an increasingly important simulation methodology for many science and engineering problems. AMR has the potential to generate highly resolved simulations efficiently by dynamically refining the computational mesh near key numerical solution features. AMR requires more complex numerical algorithms and programming than uniform fixed mesh approaches. Software libraries that provide general AMR functionality can ease these burdens significantly. A major challenge for library developers is to achieve adequate flexibility to meet diverse and evolving application requirements. In this paper, we describe the design of software abstractions for general AMR data management and parallel communication operations in SAMRAI, an object-oriented C++ structured AMR (SAMR) library developed at Lawrence Livermore National Laboratory (LLNL). The SAMRAI infrastructure provides the foundation for a variety of diverse application codes at LLNL and elsewhere. We illustrate SAMRAI functionality by describing how its unique features are used in these codes which employ complex data structures and geometry. We highlight capabilities for moving and deforming meshes, coupling multiple SAMR mesh hierarchies, and immersed and embedded boundary methods for modeling complex geometrical features. We also describe how irregular data structures, such as particles and internal mesh boundaries, may be implemented using SAMRAI tools without excessive application programmer effort. This work was performed under the auspices of the US Department of Energy by University of California Lawrence Livermore National Laboratory under contract number W-7405-Eng-48 and is released under UCRL-JRNL-214559.     

A novel dynamic modelling approach for parallel mechanisms analysis

A novel approach (recursive matrix method), which is used for kinematic and dynamic analysis of a 3-DOF parallel mechanism with revolute actuators, is established in this paper. The active links of the mechanism are actuated by three electric motors and have three independent motions. Knowing the evolution of movable platform, first we develop the positions, velocities and accelerations of all elements of the mechanism. An inverse dynamic problem is solved using the principle of virtual work. Finally, recursive relations and graphs for the torques of three actuators are determined. It showed the efficiency of the proposed method by the example.