Parallel extremal optimization in processor load balancing for distributed applications

The paper concerns parallel methods for extremal optimization (EO) applied in processor load balancing in execution of distributed programs. In these methods EO algorithms detect an optimized strategy of tasks migration leading to reduction of program execution time. We use an improved EO algorithm with guided state changes (EO-GS) that provides parallel search for next solution state during solution improvement based on some knowledge of the problem. The search is based on two-step stochastic selection using two fitness functions which account for computation and communication assessment of migration targets. Based on the improved EO-GS approach we propose and evaluate several versions of the parallelization methods of EO algorithms in the context of processor load balancing. Some of them use the crossover operation known in genetic algorithms. The quality of the proposed algorithms is evaluated by experiments with simulated load balancing in execution of distributed programs represented as macro data flow graphs. Load balancing based on so parallelized improved EO provides better convergence of the algorithm, smaller number of task migrations to be done and reduced execution time of applications.     

Game-theoretic static load balancing for distributed systems

In this paper, we present a game theoretic approach to solve the static load balancing problem for single-class and multi-class (multi-user) jobs in a distributed system where the computers are connected by a communication network. The objective of our approach is to provide fairness to all the jobs (in a single-class system) and the users of the jobs (in a multi-user system). To provide fairness to all the jobs in the system, we use a cooperative game to model the load balancing problem. Our solution is based on the Nash Bargaining Solution (NBS) which provides a Pareto optimal solution for the distributed system and is also a fair solution. An algorithm for computing the NBS is derived for the proposed cooperative load balancing game. To provide fairness to all the users in the system, the load balancing problem is formulated as a non-cooperative game among the users who try to minimize the expected response time of their own jobs. We use the concept of Nash equilibrium as the solution of our non-cooperative game and derive a distributed algorithm for computing it. Our schemes are compared with other existing schemes using simulations with various system loads and configurations. We show that our schemes perform near the system optimal schemes and are superior to the other schemes in terms of fairness.     

Learning non-cooperative game for load balancing under self-interested distributed environment

Resources in large-scale distributed systems are distributed among several autonomous domains. These domains collaborate to produce significantly higher processing capacity through load balancing. However, resources in the same domain tend to be cooperative, whereas those in different domains are self-interested. Fairness is the key to collaboration under a self-interested environment. Accordingly, a fairness-aware load balancing algorithm is proposed. The load balancing problem is defined as a game. The Nash equilibrium solution for this problem minimizes the expected response time, while maintaining fairness. Furthermore, reinforcement learning is used to search for the Nash equilibrium. Compared with static approaches, this algorithm does not require a prior knowledge of job arrival and execution, and can adapt dynamically to these processes. The synthesized tests indicate that our algorithm is close to the optimal scheme in terms of overall expected response time under different system utilization, heterogeneity, and system size; it also ensures fairness similar to the proportional scheme. Trace simulation is conducted using the job workload log of the Scalable POWERpallel2 system in the San Diego Supercomputer Center. Our algorithm increases the expected response time by a maximum of 14%. But it improves fairness by 12–27% in contrast to Opportunistic Load Balancing, Minimum Execution Time, Minimum Completion Time, Switching Algorithm, and k-Percent Best.     

Task distribution using factoring load balancing in Master-Worker applications

Load imbalance among workers is one of the main causes of performance shortcomings in Master-Worker applications. We have observed that this problem is very similar to the one of scheduling distributed parallel loops, which has been widely in the literature. Thus, we have adapted one of the most successful algorithms, known as Factoring, to be used for Master-Worker applications. This has leads to a simple an elegant strategy that can be used to obtain an excellent automatic and dynamic load balancing strategy for the workers. Finally, we have assessed the resulting strategy through extensive experimentation and simulation.     

Numerical studies on a paradox for non-cooperative static load balancing in distributed computer systems

Numerical examples of a Braess-like paradox in which adding capacity to a distributed computer system may degrade the performance of all users in the system under non-cooperative optimization have been reported. Unlike the original Braess paradox, in the models examined, this behavior occurs only in the case of finitely many users and not in the case of infinite number of users and the degree of performance degradation can increase without bound. This study examines numerically some examples around the Braess-like paradox in a distributed computer system. In the numerical examples, it is observed that the worst-case degree of the paradox (WCDP) is largest in complete symmetry. The dependence of the WCDP on some system parameters is also examined.     

Dependency graph approach to load balancing distributed volume visualization

We present a framework that uses data dependency information to automate load balanced volume distribution and ray-task scheduling for parallel visualization of massive volumes. This dependency graph approach improves load balancing for both ray casting and ray tracing. The main bottlenecks in distributed volume rendering involve moving data across the network and loading memory into rendering hardware. Our load balancing solution combines static network distribution with dynamic ray-task scheduling. At the core of the dependency graph approach are the flex-block tree, introduced in this paper, and the cell-tree. The flex-block tree is similar to a kd-tree except that leaf nodes are cells containing a combination of empty space and tightly cropped subvolumes, or flex-blocks. A main contribution of this paper is the moving walls algorithm, which uses dynamic programming to create a flex-block partition. We show results for optimizing distributed ray cast rendering using a time cost function. We compare data distribution using the moving walls algorithm, with distribution using a recursive solution, and with a grid combined with a local kd-tree partition on each render-node.

基于目标约束的分层动态负载均衡算法*

针对网格环境下的负载不均问题,提出了一种分层动态负载均衡机制,该机制采用随机服务模型描述网格任务流特性及其资源上的动态负载状态,将站点内负载平衡问题归结为目标约束规划问题。理论分析了分层负载均衡机制的有效性证明并设计了优化方案的求解算法,仿真实验结果显示,该分层负载均衡算法在平均响应时间、系统吞吐量方面优于以往的RBA算法和DBA算法。     

Resource scheduling and load balancing in distributed robotic control systems

This paper describes the latest advances made to a software architecture designed to control multiple miniature robots. As the robots themselves have very limited computational capabilities, a distributed control system is needed to coordinate tasks among a large number of robots. Two of the major challenges facing such a system are the scheduling of access to system resources and the distribution of work across multiple workstations. This paper discusses solutions to these problems in the context of a distributed surveillance task.     

Hash-based proximity clustering for efficient load balancing in heterogeneous DHT networks

Distributed hash table (DHT) networks based on consistent hashing functions have an inherent load uneven distribution problem. The objective of DHT load balancing is to balance the workload of the network nodes in proportion to their capacity so as to eliminate traffic bottleneck. It is challenging because of the dynamism, proximity and heterogeneity natures of DHT networks and time-varying load characteristics.     

Towards a hybrid load balancing policy in grid computing system

Grid computing has become conventional in distributed systems due to technological advancements and network popularity. Grid computing facilitates distributed applications by integrating available idle network computing resources into formidable computing power. As a result, by using efficient integration and sharing of resources, this enables abundant computing resources to solve complicated problems that a single machine cannot manage. However, grid computing mines resources from accessible idle nodes and node accessibility varies with time. A node that is currently idle, may become occupied within a second of time and then be unavailable to provide resources. Accordingly, node selection must provide effective and sufficient resources over a long period to allow load assignment. This study proposes a hybrid load balancing policy to integrate static and dynamic load balancing technologies. Essentially, a static load balancing policy is applied to select effective and suitable node sets. This will lower the unbalanced load probability caused by assigning tasks to ineffective nodes. When a node reveals the possible inability to continue providing resources, the dynamic load balancing policy will determine whether the node in question is ineffective to provide load assignment. The system will then obtain a new replacement node within a short time, to maintain system execution performance.     

Application of load balancing based on symmetric balanced incomplete block design to random networks

In a load balancing algorithm [O. Lee, M. Anshel, I. Chung, Design of an efficient load balancing algorithm on distributed networks by employing symmetric balanced incomplete block design, IEE Proceedings - Communications 151 (6) (2004) 535-538] based on the SBIBD (Symmetric Balanced Incomplete Block Design), each node receives global workload information by only two round message exchange with traffic overhead, where v is the number of nodes. It is very efficient and works well only when v=p²+p+1 is used for a prime number p. In this paper, we generated a special incidence structure using the SBIBD and then propose a new load balancing algorithm, which executes well for an arbitrary number of nodes. To accomplish this, we add a number of links to nodes in order for each node to receive more than 80% of the workload information by two round message exchange. For performance of our algorithm, we carried out an experiment for the number of nodes, w, which was up to 5000. Traffic overhead is less than in a round and standard deviation of traffic overhead shows that each node has a mostly well-balanced amount of traffic.     

Distributed strategic interleaving with load balancing

In a previous paper, we developed an algebraic theory of threads, interleaving of threads, and interaction of threads with services. In the current paper, we assume that the threads and services are distributed over the nodes of a network. We extend the theory developed so far to the distributed case by introducing distributed interleaving strategies that support explicit thread migration and see to load balancing or capability searching by implicit thread migration. The extension to the distributed case provides insight into details of multi-threading that come up in a networked environment.     

Artificial life techniques for load balancing in computational grids

Load balancing is a very important and complex problem in computational grids. A computational grid differs from traditional high performance computing systems in the heterogeneity of the computing nodes and communication links, as well as background workloads that may be present in the computing nodes. There is a need to develop algorithms that could capture this complexity yet can be easily implemented and used to solve a wide range of load balancing scenarios. Artificial life techniques have been used to solve a wide range of complex problems in recent times. The power of these techniques stems from their capability in searching large search spaces, which arise in many combinatorial optimization problems, very efficiently. This paper studies several well-known artificial life techniques to gauge their suitability for solving grid load balancing problems. Due to their popularity and robustness, a genetic algorithm (GA) and tabu search (TS) are used to solve the grid load balancing problem. The effectiveness of each algorithm is shown for a number of test problems, especially when prediction information is not fully accurate. Performance comparisons with Min-min, Max-min, and Sufferage are also discussed.     

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.     

Integrating load balancing and locality in the parallelization of irregular problems

An irregular problem models the evolution of a system where several elements are irregularly distributed in a domain. The evolution modifies this distribution in a way that cannot be foreseen and the behavior of each element depends upon the elements close to it according to a problem dependent relation. Starting from a hierarchical representation of the domain, we define a parallelization methodology that includes a load balancing strategy that preserves this locality property and a strategy to collect information distributed onto the processing nodes.     

动态负载均衡算法在校园网格中的应用

校园网格能有效消除信息孤岛,实现我国高校的计算资源和信息资源的有效共享。一个亟待解决的问题是在校园网格环境下,服务器节点响应能力低下。目前已提出多种技术与方案以解决并提高校园网格的服务器节点的响应能力,负载均衡技术就是一种全新的技术。本文根据校园网格的特点和影响负载均衡的因素,对基于校园网格的负载均衡技术进行了分析和探讨,并提出一种动态负载均衡算法。     

Competitive distributed decision-making

We study several natural problems in distributed decision-making from the standpoint of competitive analysis; in these problems incomplete information is a result of the distributed nature of the problem, as opposed to the on-line mode of decision making that was heretofore prevalent in this area. In several simple situations of distributed scheduling, the competitive ratio can be computed exactly, and the different ratios can be used as a measure of the value of information and communication between decision-makers. In a more general distributed scheduling situation, we give tight upper and lower bounds on the competitive ratio achievable in the deterministic case, and give an optimal randomized algorithm with a much better competitive ratio.The research of Xiaotie Deng was supported by an NSERC grant and that of C. H. Papadimitriou was supported by an NSF grant.     

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.     

DUCF: Distributed load balancing Unequal Clustering in wireless sensor networks using Fuzzy approach

Data gathering in wireless sensor networks (WSN) consumes more energy due to large amount of data transmitted. In direct transmission (DT) method, each node has to transmit its generated data to the base station (BS) which leads to higher energy consumption and affects the lifetime of the network. Clustering is one of the efficient ways of data gathering in WSN. There are various kinds of clustering techniques, which reduce the overall energy consumption in sensor networks. Cluster head (CH) plays a vital role in data gathering in clustered WSN. Energy consumption in CH node is comparatively higher than other non CH nodes because of its activities like data aggregation and transmission to BS node. The present day clustering algorithms in WSN use multi-hopping mechanism which cost higher energy for the CH nodes near to BS since it routes the data from other CHs to BS. Some CH nodes may die earlier than its intended lifetime due to its overloaded work which affects the performance of the WSN. This paper contributes a new clustering algorithm, Distributed Unequal Clustering using Fuzzy logic (DUCF) which elects CHs using fuzzy approach. DUCF forms unequal clusters to balance the energy consumption among the CHs. Fuzzy inference system (FIS) in DUCF uses the residual energy, node degree and distance to BS as input variables for CH election. Chance and size are the output fuzzy parameters in DUCF. DUCF assigns the maximum limit (size) of a number of member nodes for a CH by considering its input fuzzy parameters. The smaller cluster size is assigned for CHs which are nearer to BS since it acts as a router for other distant CHs. DUCF ensures load balancing among the clusters by varying the cluster size of its CH nodes. DUCF uses Mamdani method for fuzzy inference and Centroid method for defuzzification. DUCF performance was compared with well known algorithms such as LEACH, CHEF and EAUCF in various network scenarios. The experimental results indicated that DUCF forms unequal clusters which ensure load balancing among clusters, which again improves the network lifetime compared with its counterparts.