CFP last date
20 December 2024
Reseach Article

An Effective Load Balancing Task Allocation Algorithm using Task Clustering

by Poornima Bhardwaj, Vinod Kumar
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 77 - Number 7
Year of Publication: 2013
Authors: Poornima Bhardwaj, Vinod Kumar
10.5120/13410-1064

Poornima Bhardwaj, Vinod Kumar . An Effective Load Balancing Task Allocation Algorithm using Task Clustering. International Journal of Computer Applications. 77, 7 ( September 2013), 32-39. DOI=10.5120/13410-1064

@article{ 10.5120/13410-1064,
author = { Poornima Bhardwaj, Vinod Kumar },
title = { An Effective Load Balancing Task Allocation Algorithm using Task Clustering },
journal = { International Journal of Computer Applications },
issue_date = { September 2013 },
volume = { 77 },
number = { 7 },
month = { September },
year = { 2013 },
issn = { 0975-8887 },
pages = { 32-39 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume77/number7/13410-1064/ },
doi = { 10.5120/13410-1064 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:49:41.131182+05:30
%A Poornima Bhardwaj
%A Vinod Kumar
%T An Effective Load Balancing Task Allocation Algorithm using Task Clustering
%J International Journal of Computer Applications
%@ 0975-8887
%V 77
%N 7
%P 32-39
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In Distributed Computing Systems (DCSs), a program is split into small tasks and distributed among several computing elements to minimize the overall system cost. Several challenges have been posed by this mode of processing which can be classified mainly into two broad categories. One class belongs to the hardware oriented issues of building such systems more and more effective while the other aims at designing efficient algorithms to make the best use of the technology in hand. The task allocation problem in a DCS belongs to the later class. Intrinsically, task allocation problem is NP- hard. To overcome this issue, it is necessary to introduce heuristics for generating near optimal solution to the given problem. This paper deals with the problem of task allocation in DCSs in such a way that the load on each processing node is almost balanced. Further, the development of an effective algorithm for allocating 'm' tasks to 'n' processors of a given distributed system using task clustering by taking both Inter Task Communication Cost (ITCC) and the Execution Cost (EC) is taken into consideration.

References
  1. Alakeel Ali M. 2010. A guide to dynamic load balancing in distributed computer systems. International Journal of Computer Science and Network Security, 10 (6), 153 -160.
  2. Bokhari, S. H. 1987. Assignment problems in parallel and distributed computing.
  3. Chu, W. W. , Holloway, L. J. , Lan, M. T. , and Efe, K. 1980. Task allocation in distributed data processing. IEEE Computer, 13(11) (Nov. 1980), 57-69.
  4. Gerasoulis, A. and Yang, T. A. 1992. A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessors. Journal of Parallel and Distributed Computing, (1992), 276 – 291.
  5. Govil, Kapil 2011. A smart algorithm for dynamic task allocation for distributed processing environment. International Journal of Computer Applications, 28(2), (2011), 13-19.
  6. Gillett, Billy E. 1979. Introduction to operations research: a computer-oriented algorithmic approach.
  7. Kafil, M. , and Ahmad, I. 1998. Optimal Task Assignment in Heterogeneous Computing Systems. IEEE Concurrency, (1998), 42- 51.
  8. Kim, S. J. , and Browne, J. C. 1988. A general approach to mapping of parallel computations upon multiprocessor architectures. In Proceedings of the International Conference on Parallel Processing.
  9. Kumar, Avanish, Sharma, Abhilasha and Dhagat, Vanita Ben 2010. Maximal link mode algorithm for task allocation in distributed computing systems. Proceedings of the 4th National Conference: INDIACom-2010.
  10. Liou, J. -C. and Palis, M. A. 1996. An efficient clustering heuristic for scheduling dags on multiprocessor. In Proceedings of the 8th Symposium on Parallel and Distributed Processing.
  11. Palis M. A. , Liou, J. -C. and Wei, D. S. 1996. Task clustering and scheduling for distributed memory parallel architectures. IEEE Transactions on Parallel and Distributed Systems (1996), 46 – 55.
  12. Raii, Anurag and Kapoor, Vikram 2012. Efficient clustering model for utilization of processor's capacity in distributed computing system. International Journal of Computer Applications, 44(23), 21- 25.
  13. Richard, R. Y. , Lee, E. Y. S. and Tsuchiya, M. 1982. A task allocation modal for distributed computer system. IEEE Transaction on Computers 31, 41- 47.
  14. Sagar, G. and Sarje, A. K. 1991. Task allocation modal for distributed system. International Journal of System Science, 22(9), 1671 – 1678.
  15. Sarje, A. K. and Sagar, G. 1991. Heuristic modal for task allocation in distributed computer systems. IEEE Proceedings on Computers and Digital Techniques, 138(5), 313 – 318.
  16. Saxena Pankaj, Govil Kapil, Saxena Gaurav, Kumar Saurabh and Agrawal Neha. 2012. An algorithmic approach and comparative analysis of task assignment to processor for achieving time efficiency in process completion. International Journal of Applied Engineering and Technology, 2(1), 114-119.
  17. Sharma, Manisha, Kumar, Harendra, Garg, Deepak. 2012. An Optimal Task Allocation Model through Clustering with Inter-Processor Distances in Heterogeneous Distributed Computing Systems. International Journal of Soft Computing and Engineering, 2(1), 50- 55.
  18. Srinivasan, S. , and Jha, N. K. 1999. Safety and reliability driven task allocation in distributed systems. IEEE Transactions on Parallel and Distributed Systems. 10(3), 238 – 251.
  19. Vidyarthi, Deo Prakash, Tripathi, Anil Kumar, Sarker, Biplab Kumer, Dhawan, Abhishek and Yang, Laurence Tianruo. 2004. Cluster - based multiple task allocation in distributed computing system. In Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS'04).
  20. Yang, T. and Gerasoulis, A. 1994. DSC: scheduling parallel tasks on an unbounded number of processors. IEEE Transactions on Parallel and Distributed Systems. 5(9), 951- 967.
Index Terms

Computer Science
Information Sciences

Keywords

Distributed Computing Systems Task Allocation Static Load Balancing Execution Cost Communication Cost.