A Performance Study of Task Allocation Algorithms in a Distributed Computing System (DCS)

Biplab KUMER SARKER; Anil KUMAR TRIPATHI; Deo PRAKASH VIDYARTHI; Kuniaki UEHARA

A Performance Study of Task Allocation Algorithms in a Distributed Computing System (DCS)

Biplab KUMER SARKER, Anil KUMAR TRIPATHI, Deo PRAKASH VIDYARTHI, Kuniaki UEHARA

Full Text Views

0

Cite this

Summary :

A Distributed Computing System (DCS) contributes in proper partitioning of the tasks into modules and allocating them to various nodes so as to enable parallel execution of their modules by individual different processing nodes of the system. The scheduling of various modules on particular processing nodes may be preceded by appropriate allocation of modules of the different tasks to various processing nodes and then only the appropriate execution characteristic can be obtained. A number of algorithms have been proposed for allocation of tasks in a DCS. Most of the solutions proposed had simplifying assumptions. The very first assumption has been: consideration of a single task with their corresponding modules only; second, no consideration of the status of processing nodes in terms of the previously allocated modules of various tasks and third, the capacity and capability of the processing nodes. This work proposes algorithms for a realistic situation wherein multiple tasks with their modules compete for execution on a DCS dynamically considering their architectural capability. In this work, we propose two algorithms based on the two well-known A^* and GA for the task allocation models. The paper explains the algorithms elaborately by illustrated examples and presents a comparative performance study among our algorithms and the algorithms for task allocation proposed in the various literatures. The results demonstrate that our GA based task allocation algorithm achieves better performance compared with the other algorithms.

Publication: IEICE TRANSACTIONS on Information Vol.E86-D No.9 pp.1611-1619

Publication Date: 2003/09/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Parallel and Distributed Computing, Applications and Technologies)

Category: Algorithms and Applications

Cite this

Copy

Biplab KUMER SARKER, Anil KUMAR TRIPATHI, Deo PRAKASH VIDYARTHI, Kuniaki UEHARA, "A Performance Study of Task Allocation Algorithms in a Distributed Computing System (DCS)" in IEICE TRANSACTIONS on Information, vol. E86-D, no. 9, pp. 1611-1619, September 2003, doi: .
Abstract: A Distributed Computing System (DCS) contributes in proper partitioning of the tasks into modules and allocating them to various nodes so as to enable parallel execution of their modules by individual different processing nodes of the system. The scheduling of various modules on particular processing nodes may be preceded by appropriate allocation of modules of the different tasks to various processing nodes and then only the appropriate execution characteristic can be obtained. A number of algorithms have been proposed for allocation of tasks in a DCS. Most of the solutions proposed had simplifying assumptions. The very first assumption has been: consideration of a single task with their corresponding modules only; second, no consideration of the status of processing nodes in terms of the previously allocated modules of various tasks and third, the capacity and capability of the processing nodes. This work proposes algorithms for a realistic situation wherein multiple tasks with their modules compete for execution on a DCS dynamically considering their architectural capability. In this work, we propose two algorithms based on the two well-known A^* and GA for the task allocation models. The paper explains the algorithms elaborately by illustrated examples and presents a comparative performance study among our algorithms and the algorithms for task allocation proposed in the various literatures. The results demonstrate that our GA based task allocation algorithm achieves better performance compared with the other algorithms.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_9_1611/_p

Copy

@ARTICLE{e86-d_9_1611,
author={Biplab KUMER SARKER, Anil KUMAR TRIPATHI, Deo PRAKASH VIDYARTHI, Kuniaki UEHARA, },
journal={IEICE TRANSACTIONS on Information},
title={A Performance Study of Task Allocation Algorithms in a Distributed Computing System (DCS)},
year={2003},
volume={E86-D},
number={9},
pages={1611-1619},
abstract={A Distributed Computing System (DCS) contributes in proper partitioning of the tasks into modules and allocating them to various nodes so as to enable parallel execution of their modules by individual different processing nodes of the system. The scheduling of various modules on particular processing nodes may be preceded by appropriate allocation of modules of the different tasks to various processing nodes and then only the appropriate execution characteristic can be obtained. A number of algorithms have been proposed for allocation of tasks in a DCS. Most of the solutions proposed had simplifying assumptions. The very first assumption has been: consideration of a single task with their corresponding modules only; second, no consideration of the status of processing nodes in terms of the previously allocated modules of various tasks and third, the capacity and capability of the processing nodes. This work proposes algorithms for a realistic situation wherein multiple tasks with their modules compete for execution on a DCS dynamically considering their architectural capability. In this work, we propose two algorithms based on the two well-known A^* and GA for the task allocation models. The paper explains the algorithms elaborately by illustrated examples and presents a comparative performance study among our algorithms and the algorithms for task allocation proposed in the various literatures. The results demonstrate that our GA based task allocation algorithm achieves better performance compared with the other algorithms.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - A Performance Study of Task Allocation Algorithms in a Distributed Computing System (DCS)
T2 - IEICE TRANSACTIONS on Information
SP - 1611
EP - 1619
AU - Biplab KUMER SARKER
AU - Anil KUMAR TRIPATHI
AU - Deo PRAKASH VIDYARTHI
AU - Kuniaki UEHARA
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2003
AB - A Distributed Computing System (DCS) contributes in proper partitioning of the tasks into modules and allocating them to various nodes so as to enable parallel execution of their modules by individual different processing nodes of the system. The scheduling of various modules on particular processing nodes may be preceded by appropriate allocation of modules of the different tasks to various processing nodes and then only the appropriate execution characteristic can be obtained. A number of algorithms have been proposed for allocation of tasks in a DCS. Most of the solutions proposed had simplifying assumptions. The very first assumption has been: consideration of a single task with their corresponding modules only; second, no consideration of the status of processing nodes in terms of the previously allocated modules of various tasks and third, the capacity and capability of the processing nodes. This work proposes algorithms for a realistic situation wherein multiple tasks with their modules compete for execution on a DCS dynamically considering their architectural capability. In this work, we propose two algorithms based on the two well-known A^* and GA for the task allocation models. The paper explains the algorithms elaborately by illustrated examples and presents a comparative performance study among our algorithms and the algorithms for task allocation proposed in the various literatures. The results demonstrate that our GA based task allocation algorithm achieves better performance compared with the other algorithms.
ER -