Title: Dynamic task allocation in distributed computing systems by heuristic algorithms

Authors: Deepak Garg; Paramjeet Singh

Addresses: National Institute of Geophysics and Volcanology, Section of Pisa, 56126 Pisa, Italy ' Department of Mathematics and Applied Mathematics, University of Cape Town, Cape Town, South Africa

Abstract: Efficient task scheduling is a crucial step to achieve high performance for multiprocessor platform. In a distributed computing system (DCS) the tasks of a program must be assigned dynamically to the heterogeneous processors to utilise the computational capabilities and resources of the system efficiently. In this article, the problem of finding an optimal dynamic assignment of a modular program for multiprocessor system is analysed. This paper deals with dynamic task assignment problem for allocating m tasks of a distributed program to n heterogeneous processors (m >>> n) with effect to minimise the total cost of the program. This allocation permits each task to be migrated from one processor to another during the execution of the program. The dynamic task allocation model is developed by considering three different categories including the effect of processor relative speed. This development implies the coupling of logical modelling and statistical notions. We design the mathematical model and study the phase wise execution cost (EC), inter-task communication cost (ITCC), migration cost (MC) and residence cost (RC) of each task with respect to each processor in the form of matrices.

Keywords: dynamic task assignment; distributed computing systems; DCS; execution cost; communication cost; migration cost; residence cost; dynamic task allocation; heuristics; task scheduling; multiprocessor systems; modular programs; mathematical modelling.

DOI: 10.1504/IJOR.2014.065610

International Journal of Operational Research, 2014 Vol.21 No.4, pp.391 - 408

Received: 25 Jan 2013
Accepted: 03 Mar 2013
Published online: 25 Nov 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article