We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

An Optimal Task Allocation Model for System Cost Analysis in Heterogeneous Distributed Computing Systems: A Heuristic Approach

by P. K. Yadav, M. P. Singh, Kuldeep Sharma
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 28 - Number 4
Year of Publication: 2011
Authors: P. K. Yadav, M. P. Singh, Kuldeep Sharma
10.5120/3374-4664

P. K. Yadav, M. P. Singh, Kuldeep Sharma . An Optimal Task Allocation Model for System Cost Analysis in Heterogeneous Distributed Computing Systems: A Heuristic Approach. International Journal of Computer Applications. 28, 4 ( August 2011), 30-37. DOI=10.5120/3374-4664

@article{ 10.5120/3374-4664,
author = { P. K. Yadav, M. P. Singh, Kuldeep Sharma },
title = { An Optimal Task Allocation Model for System Cost Analysis in Heterogeneous Distributed Computing Systems: A Heuristic Approach },
journal = { International Journal of Computer Applications },
issue_date = { August 2011 },
volume = { 28 },
number = { 4 },
month = { August },
year = { 2011 },
issn = { 0975-8887 },
pages = { 30-37 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume28/number4/3374-4664/ },
doi = { 10.5120/3374-4664 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:13:53.715891+05:30
%A P. K. Yadav
%A M. P. Singh
%A Kuldeep Sharma
%T An Optimal Task Allocation Model for System Cost Analysis in Heterogeneous Distributed Computing Systems: A Heuristic Approach
%J International Journal of Computer Applications
%@ 0975-8887
%V 28
%N 4
%P 30-37
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In Distributed computing systems (DCSs), task allocation strategy is an essential phase to minimize the system cost (i.e. the sum of execution and communication costs). To utilize the capabilities of distributed computing system (DCS) for an effective parallelism, the tasks of a parallel program must be properly allocated to the available processors in the system. Inherently, task allocation problem is NP-hard in complexity. To overcome this problem, 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 DCS such that the system cost is minimized. This can be done by minimizing the inter-processor communication cost (IPCC). Therefore, in this paper we have proposed an algorithm that tries to allocate the tasks to the processors, one by one on the basis of communication link sum (CLS). This type of allocation policy will reduce the inter-processor communication (IPC) and thus minimize the system cost. For an allocation purposes, execution cost of the tasks on each processor and communication cost between the tasks has been taken in the form of matrices.

References
  1. G. Sagar and A.K. Sarje, “Task Allocation Model for Distributed System,” Int. J. Systems Sci. Vol. 22, 9(1991). pp. 1671- 1678.
  2. A.K.Sarje and G.Sagar, “Heuristic Model for Task Allocation in Distributed Computer Systems,” IEE Proceedings-E, Vol.138, 5(1991).
  3. Ajith Tom P. and C. Siva Ram Murthy, “An Improved Algorithm For Module Allocation in Distributed Computing Systems,” Journal of Parallel and Distributed Computing Systems,” 42 (1997),pp. 82-90.
  4. M. Kafil and I. Ahmad, “Optimal Task Assignment in Heterogeneous Computing Systems,” 0-8186- 7879-8/97$ 10.00  1997 IEEE.
  5. Peng, Dar- Tezen, Shin, K.G. and Abdel, Zoher,T.F., “Assignment Scheduling Communication periodic Tasks in Distributed Real Time System,” IEEE Transactions on Software Engineering, SE-13, (1997), pp. 745- 757.
  6. W.W.Chu, Leslie J.Holloway, Min-Tsung Lan, and Kemal Kfe, “Task Allocation in Distributed Data Processing,” IEEE Concurrency, November 1980.pp.57-69.
  7. P-Y. Richard MA, Edward Y.S. Lee and Masahiro Tsuchiya, “A Task Allocation Model for Distributed Computing Systems,’’ IEEE Transactions on Computers, Vol.C-31,1(1982), pp.41- 46.
  8. C. C. Shen and W.H. Tasi, “A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minimax Criterion,” IEEE Transactions on Computers, Vol. C- 34, 3(1985).
  9. Stone, H.S., “Critical Load Factors in Two- Processor Distributed System,” IEEE Transactions on Software Engrg. 4(May 1978),pp. 254- 258.
  10. Imtiaz Ahmad Muhammad K.Dhodhi and Arif Ghafoor, “Task Assignment in Distributed Computing Systems,” IEEE Concurrency (1995), pp.49-53.
  11. Cheol-Hoon Lee, Dongmyun Lee and Myunghwan Kim, “Optimal Task Assignment in Linear Array Networks,’’ IEEE Transactions on Computers, Vol.41, 7(1997).
  12. Sol M.Shatz, Jia-Ping Wang, and Masanori Goto, “Task Allocation For Maximizing Reliability of Distributed Computer Systems,” IEEE Transactions on Computers, vol.41.9(1992).
  13. S.Kartik and C.Siva Ram Murthy, “Task Allocation Algorithms for Maximizing Reliability of Distributed Computing System,” IEEE Transactions on computers, Vol.46,6 (1997).
  14. D.J. Chen et al., “A Heuristic Algorithm for the Reliability- Oriented File Assignment in a Distributed Computing System,” Computers Math. Applic. Vol. 29.10(1995), pp. 85- 104,
  15. Peng-Yeng Yin, Shiuh-Sheng Yu, Pei-Pei Wang, Yi-Te Wang, “Task Allocation for Maximizing Reliability of a Distributed System using Hybrid Particle Swarm Optimization,” The Journal of Systems and Software, 80(2007).pp. 724-735.
  16. Santhanam Srinivasan and Niraj K.Jha, “Safety and Reliability Drivan Task Allocation in Distributed Systems,” IEEE transactions on Parallel and Distributed Systems, Vol.10. 3(1999).
  17. D.P.Vidayarthi and A.K.Tripathi, “Maximizing reliability of Distributed Computing System with Task allocation using Simple Genetic Algorithm,” Journal of System Architecture, 47(2001), pp.549-559.
  18. Pradeep Kumar Yadav, M.P. Singh and Kuldeep Sharma, “Task Allocation Model for Reliability and Cost optimization in Distributed Computing System,” International Journal of modeling, simulation and scientific computations, vol-2, 2(2011), pp. 1-19.
  19. Qin-Ma Kng, Hong He, Hui- Min Song, Rong Deng, “ Task allocation for maximizing Reliability of distributed Computing System using Honeybee mating Optimization,” The Journal of Systems and software, Vol.83, 2(2010).
  20. Sung- Ho Woo, Sung- Bang Yang, Shen- Dug Kim and Tack- Don Han, “Task scheduling in Distributed computing systems with a genetic algorithm,” 0- 8186- 7901- 8/97 $ 10.000© 1997 IEEE p.p. 301-305.
  21. Hongjun Lu, “load Balanced Task Allocation in locally Distributed Computer Sciences,” Technical report# 633, feb- 1996.
  22. A.A. Elsadek & B. E. Wells, “A heuristic model for task allocation in heterogeneous distributed computing systems,” International journal of computers and there applications, Vol.6, No.1, March 1999. Pp. 0-35.
  23. V.M. Lo, “Heuristic Algorithms for Task assignment in distributed systems,” IEEE Transactions on computers, Vol.37. No. 11, pp. 1384- 1397, November 1988.
  24. K. Kfe, “Heuristic Models of Task Assignment Scheduling in Distributed Systems,” Computer, Vol. 15, pp. 50- 56, June 1982.
  25. H. Ellis, Sahni S and S. Rajsekaram, “Fundamentals of computers algorithm,” Galgotiya publication Pvt Ltd., (2005).
  26. H. Kumar et al., “A Task Allocation Model for Distributed Data Network,” Journal of Mathematical Sciences, Vol.1, 4(2006),pp.379-392.
Index Terms

Computer Science
Information Sciences

Keywords

Distributed computing system task allocation execution cost communication cost communication link sum

Powered by PhDFocusTM