A High Performance Model for Task Allocation in Distributed Computing System Using K-Means Clustering Technique

A High Performance Model for Task Allocation in Distributed Computing System Using K-Means Clustering Technique

Harendra Kumar (Department of Mathematics and Statistics, Gurukula Kangri University, Haridwar, India), Nutan Kumari Chauhan (Department of Mathematics and Statistics, Gurukula Kangri University, Haridwar, India) and Pradeep Kumar Yadav (Department of Research Planning and Business Development, Central Building Research Institute, Roorkee, India)
Copyright: © 2018 |Pages: 23
DOI: 10.4018/IJDST.2018070101

Abstract

Tasks allocation is an important step for obtaining high performance in distributed computing system (DCS). This article attempts to develop a mathematical model for allocating the tasks to the processors in order to achieve optimal cost and optimal reliability of the system. The proposed model has been divided into two stages. Stage-I, makes the ‘n' clusters of set of ‘m' tasks by using k-means clustering technique. To use the k-means clustering techniques, the inter-task communication costs have been modified in such a way that highly communicated tasks are clustered together to minimize the communication costs between tasks. Stage-II, allocates the ‘n' clusters of tasks onto ‘n' processors to minimize the system cost. To design the mathematical model, executions costs and inter tasks communication costs have been taken in the form of matrices. To test the performance of the proposed model, many examples are considered from different research papers and results of examples have compared with some existing models.
Article Preview
Top

1. Introduction

Distributed computing system (DCS) consists of multiple processors, which are distributed at different sites and interconnected by a communication network. Task allocation is very important step in DCS. The purpose of task allocation is to maintain maximum utilization of computing resources. Task allocation approaches can be classified into two categories: statistical and dynamical. Statistical approaches allow a stochastic relaxation that reduces the cost function in search of a global minimum to take the task allocation decision. The statistical approaches get near to optimal solutions. In statistical approaches, when a task is assigned to the processor, it remains there until the execution of program. Due to this reason, it required more convergence times. While dynamical approaches are employed more frequently because they offer a better efficiency, having the flexibility of tasks migration.

The performance of the system depends upon several components such as load distribution, system reliability and system cost. Load distribution improves the performance of the system by transferring tasks from heavily loaded processors to lightly loaded processors. If workloads at some processors are typically heavier than at others, or if some processors execute tasks more slowly than others, the situation of lightly loaded or heavily loaded processors are likely to occur often. It is shown that even in such D; at least one processor is likely to be idle while other processors are heavily loaded due to the statistical fluctuations in the arrival of tasks computing system to the system and task service time requirements. Therefore, even in a homogeneous distributed, system performance can be potentially improved by the appropriate transfer of the workload from heavily loaded processors to lightly loaded processors. System reliability also plays an important role to improve the performance of the system. The system reliability can be defined as that all involved processors and communication links are operational during the execution of program.

In this manuscript, we have used the clustering technique to reduce the inter-task communication costs. Clustering is the act of grouping a set of objects in such a way that objects in the same groups (clusters) are more similar (in some senses) to each other to those in other group (cluster). The result of a cluster analysis can contribute directly to development of classification schemes. Indeed, clustering is used to reduce a very large data to a relatively compact analysis. Clustering was originated by Driver and Kroeber in 1932 and introduced to psychology by Zubin in 1938. Clustering is used in many fields such as machine learning, pattern recognition, image analysis, information retrieval, bioinformatics, data compression and computer graphics.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 11: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing