Heuristic Resource Allocation Algorithms for Dynamic Load Balancing in Heterogeneous Distributed Computing System

Heuristic Resource Allocation Algorithms for Dynamic Load Balancing in Heterogeneous Distributed Computing System

Bibhudatta Sahoo (NIT Rourkela, India), Sanjay Kumar Jena (NIT Rourkela, India) and Sudipta Mahapatra (IIT Karagpur, India)
Copyright: © 2014 |Pages: 29
DOI: 10.4018/978-1-4666-4940-8.ch010
OnDemand PDF Download:
List Price: $37.50


Distributed heterogeneous computing is being widely applied to a variety of large-size computational problems. These computational environments consist of multiple heterogeneous computing modules; these modules interact with each other to solve the problem. The load balancing problem in the Heterogeneous Distributed Computing System (HDCS) deals with allocation of tasks to computing nodes, so that computing nodes are evenly loaded. The complexity of dynamic load balancing increases with the size of HDCS and becomes difficult to solve effectively. Due to the complexity of the dynamic load balancing problem, the majority of researchers use a heuristic algorithm to obtain near optimal solutions. The authors use three different type of resource allocation heuristic techniques, namely greedy heuristic, simulated annealing, and genetic algorithm, for dynamic load balancing on HDCS. A new codification suitable to simulated annealing and the genetic algorithm has been introduced for dynamic load balancing on HDCS. This chapter demonstrates the use of the common coding scheme and iterative structure by simulated annealing and genetic algorithms for allocating the tasks among the computing nodes to minimize the makespan. The resource allocation algorithm uses sliding window techniques to select the tasks to be allocated to computing nodes in each iteration. A suitable codification for simulated annealing and genetic algorithm for dynamic load balancing strategy are explained along with implementation details. Consistent Expected Time to Compute (ETC) matrix is used to simulate the effect of the genetic algorithm-based dynamic load balancing scheme compared with first-fit, randomized heuristic, and simulated annealing.
Chapter Preview

1. Introduction

Distributed heterogeneous computing is being widely applied to a variety of large size computational problems. The large scale computing problems requires more computing time, which can be meat by utilizing the ideal computing time of the vast computing resources distributed over the globe. These computational environments are consists of multiple heterogeneous computing modules, these modules interact with each other to solve the problem. In a Heterogeneous distributed computing system (HDCS), processing loads arrive from many users at random time instants. A proper scheduling policy attempts to assign these loads to available computing nodes so as to complete the processing of all loads in the shortest possible time. Modern distributed computing technology includes clusters, the grid, service-oriented architecture, massively parallel processors, pear-to-peer networking, and cloud computing (Hwang 2012). The central or serial scheduler schedules the processes in a distributed system to make use of the system resources in such a manner that resource usage, response time, network congestion, and scheduling overhead are optimized. There are number of techniques and methodologies for scheduling processes of a distributed system. These are task assignment, load-balancing, load-sharing approaches (Wu 1999, Watts 1998). Due to heterogeneity of computing nodes, jobs encounter different execution times on different processors. Therefore, research should address scheduling in heterogeneous environment. Genetic algorithm have been proposed over the years for solving static and dynamic load balancing problems on distributed system.

In task assignment approach, each process submitted by a user for processing is viewed as a collection of related tasks and these tasks are scheduled to suitable nodes so as to improve performance. In load sharing approach simply attempts to conserve the ability of the system to perform work by assuring that no node is idle while processes wait for being processed. In load balancing approach, processes submitted by the users are distributed among the nodes of the system so as to equalize the workload among the nodes at any point of time. Processes might have to be migrated from one machine to another even in the middle of execution to ensure equal workload. Load balancing strategies may be static or dynamic (Grosu 2002, Ucar 2006, Wu 1999, Zomaya 20011). To improve the utilization of the processors, parallel computations require that processes be distributed to processors in such a way that the computational load is spread among the processors. Dynamic load distribution (also called load balancing, load sharing, or load migration) can be applied to restore balance (Spies 1996). In general, load-balancing algorithms can be broadly categorized as centralized or decentralized, dynamic or static, periodic or non-periodic, and those with thresholds or without thresholds (Casavant 1988, Dandamudi 1998, Wu 1999). Central scheduler or serial scheduler or load balancing service should be able to effectively control the computing resource for dynamic allocation to the tasks (Ghosh 2010). We have used a centralized load-balancing algorithm framework as it imposes fewer overheads on the system than the decentralized algorithm (Zomaya 2001).

Complete Chapter List

Search this Book: