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.     

An adaptive threshold based hybrid load balancing scheme with sender and receiver initiated approach using random information exchange

The primary objective of load balancing for distributed systems is to minimize the job execution time while maximizing the resource utilization. Load balancing on decentralized systems need effective information exchange policy so that with minimum amount of communication the nodes have up to date information about other nodes in the system. Periodic, event‐based and on‐demand information exchange are some important policies used for the same. All these approaches involve a lot of overhead and even sometime leading toward obsolete data with the nodes if there is a delay in the updation. This work presents an adaptive threshold‐based hybrid load balancing scheme with sender and receiver initiated approach (HLBWSR) using random information exchange (RIE). RIE ensures that the information is exchanged in such a way that each node in the system has up‐to‐date state of the other nodes with much reduced communication overhead. Further, the adaptive threshold ensures that almost an average numbers of jobs are executed by all the nodes in the system. The study of the effect of the use of RIE on sender initiated, receiver initiated and hybrid of sender and receiver initiated load balancing approach establishes the superior performance of HLBWSR among its RIE‐based peers. A comparative analysis of HLBWSR, with periodic information exchange strategy, modified estimated load information scheduling algorithm and load balancing on arrival reveals its effectiveness under various test conditions. Copyright © 2016 John Wiley & Sons, Ltd.     

Mapping rule-based systems onto multicomputers using simulated annealing

In this paper, we present a static load balancing method for mapping production rules in an expert system onto processors of a message-passing multicomputer. The method uses simulated annealing to achieve a nearly optimal allocation of production rules onto processor nodes. The approach balances the initial rule distribution to avoid higher communication demand among processor nodes at run time. A formal mapping model is developed and a new cost function is defined for the annealing process. New heuristic swap functions and cooling policies are provided to ensure the quality of the annealing process. A software load balancing package, SIMAL, was implemented on a SUN workstation to carry out the benchmark experiments. The overhead associated with this mapping method is O(m In m), where m is the number of rules in the production system. Two benchmark production systems, Toru-waltz and Tourney, are mapped onto a hypercube computer with 32 nodes. Experimental benchmark results verify the effectiveness of the rule mapping method. The method can be applied for distributed artificial intelligence processing or for the parallel execution of cooperating expert systems on a message-passing multicomputer.     

A Double Adaptive Algorithm for Multidimensional Integration on Multicore Based HPC Systems

In this work, a parallel double adaptive algorithm for the computation of a multidimensional integral on multicore based multicomputer systems is described. This new algorithm is the revision of a procedure developed by one of the present authors for multicomputer systems, with the aim to introduce features for an efficient implementation in multicore based hierarchical environments. Two different adaptive strategies have been combined together in the algorithm: a first procedure is responsible for load balancing among the system nodes and a second one is responsible for coordinating the cores within a single node. The performance is analyzed and experimental results on a Blade Server with 8 nodes and 2 quad-core CPUs per node have been achieved.     

Strategies for dynamic load balancing on highly parallel computers

Dynamic load balancing strategies for minimizing the execution time of single applications running in parallel on multicomputer systems are discussed. Dynamic load balancing (DLB) is essential for the efficient use of highly parallel systems when solving non-uniform problems with unpredictable load estimates. With the evolution of more highly parallel systems, centralized DLB approaches which make use of a high degree of knowledge become less feasible due to the load balancing communication overhead. Five DLB strategies are presented which illustrate the tradeoff between 1) knowledge - the accuracy of each balancing decision, and 2) overhead - the amount of added processing and communication incurred by the balancing process. All five strategies have been implemented on an Inter iPSC/2 hypercube     

Distributed load balancing for parallel main memory hash join

Parallel joins have been widely studied during the past decade and a number of efficient algorithms were presented. While it is known that the performance of these algorithms may suffer greatly in the presence of skewed input data, the work on load balancing schemes for parallel join has been limited. The main contribution of this paper is the development and analysis of a new distributed data structure and an effective load balancing scheme for parallel main memory hash join on NUMA architecture. Multiprocessors based on this architecture are scalable in both size of main memory and number of processors, and provide very high memory bandwidth. The load balancing scheme is based on random probing to avoid the hot spot problems caused by probing sequentially. We have modeled this load balancing scheme both analytically and experimentally. The experiments were run on a BBN TC2000 multiprocessor system     

Performance modeling of load-balancing algorithms using neural networks

The paper presents a new approach that uses neural networks to predict the performance of a number of dynamic decentralized load-balancing strategies. A distributed multicomputer system using distributed load-balancing strategies is represented by a unified analytical queuing model. A large simulation data set is used to train a neural network using the back-propagation learning algorithm based on gradient descent The performance model using the predicted data from the neural network produces the average response time of various load balancing algorithms under various system parameters. The validation and comparison with simulation data show that the neural network is very effective in predicting the performance of dynamic load-balancing algorithms. Our work leads to interesting techniques for designing load balancing schemes (for large distributed systems) that are computationally very expensive to simulate. One of the important findings is that performance is affected least by the number of nodes, and most by the number of links at each node in a large distributed system.     

支持动态负载平衡的分层消息队列模型

中间件技术为解决异构分布式环境下的负载平衡问题提供了有力的工具,但传统的消息中间件负载平衡的实现较为复杂,其动态参数繁多且容易带来额外开销。提出了一种分层消息队列模型,该模型中利用队列组管理器对分布式队列进行组管理,并提供了丰富的任务分配策略。在该模型的基础上提出动态负载平衡实现方案:通过基于队列的阈值阈长模型实时监控成员队列的负载情况,采用集中式调度进行负载信息搜集和负载平衡决策,结合负载迁移和队列组管理进行过载处理。     

Optimal Clustering of Hierarchical Hyper-Ring Multicomputers

The Hyper-Ring (HR) is presented as a hierarchical and scalable ring-based topology for small-scale to massively parallel systems which eliminates the major disadvantages of large-scale rings. With a fixed node degree, a low cost, symmetric properties, and a simple routing scheme, the HR topology is very suitable for small-scale to large-scale multicomputer systems. Assuming pipelined communication, the performance of 4- and 5-dimensional HR multicomputers is modeled, the performance model is evaluated, and the results of the performance model evaluation are analyzed. Moreover, the impact of the traffic load and message length on the system performance is analyzed. The major objective of this work is to shed light on how to cluster HRs in order to optimize the system efficiency. Assuming a uniform message arrival rate into the nodes of the HR, the results show that the efficiency of HR topologies with an equal number of nodes is best when the topologies are perfectly balanced. The next best-performing HRs are those with larger rings at the lower (outer) levels and smaller rings at the higher levels (near the root ring). The results confirm that the HR topology is suitable for massively parallel and scalable multicomputer systems as well as for networks of workstations.     

Hybrid work stealing of locality-flexible and cancelable tasks for the APGAS library

Since large parallel machines are typically clusters of multicore nodes, parallel programs should be able to deal with both shared memory and distributed memory. This paper proposes a hybrid work stealing scheme, which combines the lifeline-based variant of distributed task pools with the node-internal load balancing of Java’s Fork/Join framework. We implemented our scheme by extending the APGAS library for Java, which is a branch of the X10 project. APGAS programmers can now spawn locality-flexible tasks with a new asyncAny construct. These tasks are transparently mapped to any resource in the overall system, so that the load is balanced over both nodes and cores. Unprocessed asyncAny-tasks can also be cancelled. In performance measurements with up to 144 workers on up to 12 nodes, we observed near linear speedups for four benchmarks and a low overhead for cancellation-related bookkeeping.     

Parallel CBIR implementations with load balancing algorithms

The purpose of content-based information retrieval (CBIR) systems is to retrieve, from real data stored in a database, information that is relevant to a query. When large volumes of data are considered, as it is very often the case with databases dealing with multimedia data, it may become necessary to look for parallel solutions in order to store and gain access to the available items in an efficient way.Among the range of parallel options available nowadays, clusters stand out as flexible and cost effective solutions, although the fact that they are composed of a number of independent machines makes it easy for them to become heterogeneous. This paper describes a heterogeneous cluster-oriented CBIR implementation. First, the cluster solution is analyzed without load balancing, and then, a new load balancing algorithm for this version of the CBIR system is presented.The load balancing algorithm described here is dynamic, distributed, global and highly scalable. Nodes are monitored through a load index which allows the estimation of their total amount of workload, as well as the global system state. Load balancing operations between pairs of nodes take place whenever a node finishes its job, resulting in a receptor-triggered scheme which minimizes the system's communication overhead. Globally, the CBIR cluster implementation together with the load balancing algorithm can cope effectively with varying degrees of heterogeneity within the cluster; the experiments presented within the paper show the validity of the overall strategy.Together, the CBIR implementation and the load balancing algorithm described in this paper span a new path for performant, cost effective CBIR systems which has not been explored before in the technical literature.     

A Robust Distributed Adaptive Finite Element Program for Coupled Fluid-Structure Problems

This paper describes an implementation of an adaptive finite element program for coupled fluid-structure problems using a network of workstations. A pool of task programming paradigm suitable for a heterogeneous distributed workstation environment is presented. The issues of load balancing and fault recovery are explored. Numerical results for this distributed programming paradigm are presented and compared with sequential and parallel programming models.     

A load balancing framework for adaptive and asynchronous applications

We describe the design of a flexible load balancing framework and runtime software system for supporting the development of adaptive applications on distributed-memory parallel computers. The runtime system supports a global namespace, transparent object migration, automatic message forwarding and routing, and automatic load balancing. These features can be used at the discretion of the application developer in order to simplify program development and to eliminate complex bookkeeping associated with mobile data objects. An evaluation of this system in the context of a three-dimensional tetrahedral advancing front parallel mesh generator shows that overall runtime improvements of 15 percent compared to common stop-and-repartition load balancing methods, 30 percent compared to explicit intrusive load balancing methods, and 42 percent compared to no load balancing are possible on large processor configurations. At the same time, the overheads attributable to the runtime system are a fraction of 1 percent of the total runtime. The parallel advancing front method is a coarse-grained and highly adaptive application and therefore exercises all of the features of the runtime system.     

Optimizer-Assisted Load Balancing Techniques for Multicomputer Database Management Systems

Although load balancing incurs processing costs, and therefore can have a profound influence on the optimized execution plan of a query, none of the existing parallelizing query optimizers consider this factor. In this paper, we address this issue by introducing the cost of load balancing as a new factor for query optimization. Specifically, we implemented three new optimizers for multiway join queries that take the load balancing issue into consideration. To evaluate the efficiency of these schemes, we also implemented a simulator for the parallel execution of multiway joins. To provide more faith, our simulation model was validated by comparing the simulation results to those produced by the actual implementation of the same algorithms running on a multicomputer system. This simulator was used in our study to compare the new techniques to a more conventional system in which load balancing is performed at runtime, but it is not a factor for query optimization. Our extensive simulation results confirm that the new methods, indeed, provide very significant savings. Most interestingly, the best scheme displays a performance which is essentially immune from the skew effect. Furthermore, we observed that these new optimizers can consistently achieve the same level of performance gain regardless of the CPU power, I/O, and communication capabilities of the computing system. This indicates that our approaches are generally useful for all hardware platforms.     

分布式文件系统元数据服务的负载均衡框架

请求负载均衡,是分布式文件系统元数据管理需要面对的核心问题.以最大化元数据服务器集群吞吐量为目标,在已有元数据管理层之上设计实现了一种分布式缓存框架,专门管理热点元数据,均衡不断变化的负载.与已有的元数据负载均衡架构相比,这种两层的负载均衡架构灵活度更高,对负载的感知能力更强,并且避免了热点元数据重新分布、迁移引起的元数据命名空间结构被破坏的情况.经观察分析,元数据尺寸小、数量大,预取错误元数据带来的代价远远小于预取错误数据带来的代价.针对元数据的以上鲜明特点,提出一种元数据预取策略和基于预取机制的元数据缓存替换算法,加强了上述分布式缓存层的性能,这种两层的元数据负载均衡框架同时考虑了缓存一致性的问题.最后,在一个真实的分布式文件系统中验证了框架及方法的有效性.     

Adaptive and scalable load balancing for metadata server cluster in cloud-scale file systems

Big data is an emerging term in the storage industry, and it is data analytics on big storage, i.e., Cloud-scale storage. In Cloud-scale (or EB-scale) file systems, load balancing in request workloads across a metadata server cluster is critical for avoiding performance bottlenecks and improving quality of services.Many good approaches have been proposed for load balancing in distributed file systems. Some of them pay attention to global namespace balancing, making metadata distribution across metadata servers as uniform as possible. However, they do not work well in skew request distributions, which impair load balancing but simultaneously increase the effectiveness of caching and replication. In this paper, we propose Cloud Cache (C²), an adaptive and scalable load balancing scheme for metadata server cluster in EB-scale file systems. It combines adaptive cache diffusion and replication scheme to cope with the request load balancing problem, and it can be integrated into existing distributed metadata management approaches to efficiently improve their load balancing performance. C² runs as follows: 1) to run adaptive cache diffusion first, if a node is overloaded, loadshedding will be used; otherwise, load-stealing will be used; and 2) to run adaptive replication scheme second, if there is a very popular metadata item (or at least two items) causing a node be overloaded, adaptive replication scheme will be used, in which the very popular item is not split into several nodes using adaptive cache diffusion because of its knapsack property. By conducting performance evaluation in trace-driven simulations, experimental results demonstrate the efficiency and scalability of C².     

基于序列划分策略的Hmmsearch程序两级并行实现

Hmmsearch程序是生物序列分析软件包HMMER中最主要程序之一,采用集中式动态负载平衡方案。为了提高其可扩展性,提出一种基于序列划分策略的两级并行算法,采用分布式动态负载平衡方案。通过增加中间层形成“Master-subMaster’Slave”结构,来改善原“Master-Slave”结构的不足。实验数据表明改进算法比原算法具有更好的可扩展并行性能。     

Web应用服务器自适应负载平衡服务

Web应用服务器是为事务性Web应用提供一系列运行时服务的分布式系统.基于中间件的自适应负载平衡服务是为Web应用服务器提供高可信赖性和高伸缩性的一种有效方法,但目前还存在许多不足,如缺乏服务端透明性、负载策略不可替换等,不能满足Web应用服务器特有的需求.分析了Web应用服务器负载平衡服务的关键需要,设计了一种自适应负载平衡服务,阐述了在J2EE应用服务器WebFrame2.0上实现该服务的若干关键技术及其解决办法,包括可热插拔、负载策略可替换、负载反馈与自适应控制、状态迁移以及容错技术等,最后是相关工作介绍及其比较.该负载平衡服务已在Web应用服务器WebFrame2.0中得以实现.     

Dynamic storage and access load balancing for answering range queries in peer-to-peer networks

Recently, many applications have used Peer-to-Peer (P2P) systems to overcome the current problems with client/server systems such as non-scalability, high bandwidth requirement and single point of failure. In this paper, we propose an efficient scheme to support efficient range query processing over structured P2P systems, while balancing both the storage load and access load. The paper proposes a rotating token scheme to balance the storage load by placing joining nodes in appropriate locations in the identifier space to share loads with already overloaded nodes. Then, to support range queries, we utilize an order-preserving mapping function to map keys to nodes in order preserving way and without hashing. This may result in an access load imbalance due to non-uniform distribution of keys in the identifier space. Thus, we propose an adaptive replication scheme to relieve overloaded nodes by shedding some load on other nodes to balance the access load. We derive a formula for estimating the overhead of the proposed adaptive replication scheme. In this study, we carry simulation experiments with synthetic data to measure the performance of the proposed schemes. Our simulation experiments show significant gains in both storage load balancing and access load balancing.