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

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).