CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Classification of Task Partitioning and Load Balancing Strategies in Distributed Parallel Computing Systems

by Rafiqul Zaman Khan, Javed Ali
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 60 - Number 17
Year of Publication: 2012
Authors: Rafiqul Zaman Khan, Javed Ali
10.5120/9788-4419

Rafiqul Zaman Khan, Javed Ali . Classification of Task Partitioning and Load Balancing Strategies in Distributed Parallel Computing Systems. International Journal of Computer Applications. 60, 17 ( December 2012), 48-53. DOI=10.5120/9788-4419

@article{ 10.5120/9788-4419,
author = { Rafiqul Zaman Khan, Javed Ali },
title = { Classification of Task Partitioning and Load Balancing Strategies in Distributed Parallel Computing Systems },
journal = { International Journal of Computer Applications },
issue_date = { December 2012 },
volume = { 60 },
number = { 17 },
month = { December },
year = { 2012 },
issn = { 0975-8887 },
pages = { 48-53 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume60/number17/9788-4419/ },
doi = { 10.5120/9788-4419 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:07:17.409811+05:30
%A Rafiqul Zaman Khan
%A Javed Ali
%T Classification of Task Partitioning and Load Balancing Strategies in Distributed Parallel Computing Systems
%J International Journal of Computer Applications
%@ 0975-8887
%V 60
%N 17
%P 48-53
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Distribution of the tasks amongst the various computing nodes is itself an intellectually challenging problem in the high performance distributed computing systems. To choose the appropriate strategy for the required system is difficult without the meaningful comparison of the existing task partitioning and load balancing strategies. The effectiveness of the strategy depend on the number of factors-efficiency, interconnection topology, communication mode, program structure, throughput and computing capabilities of the structure. A number of task partitioning and load balancing strategies have been proposed, each of which perform remarkable results under different circumstances. The main goal of the paper is to unravel the mystery of strategies and to classify when and where each strategy is appropriate. In this paper, taxonomy of task partitioning and load balancing is presented in an attempt to provide a common terminology and classification mechanism.

References
  1. Gary. E. Christensen, MIMD vs. SIMD parallel processing: A case study in 3D medical image registration, Parallel Computing 24 (9/10) (1998) ,pp. 1369–1383.
  2. Feitelson D. G. , "A Survey of Scheduling in Multiprogrammed Parallel Systems", Research Report RC 19790 (87657), IBM T. J. Watson Research Center, August 1997.
  3. Jia-X. Z. ; Wei-M. Z. ; , "A DAG-based partitioning-reconfiguring scheduling algorithm in network of workstations,"High Performance Computing in the Asia-Pacific Region, 2000. Proceedings. The Fourth International Conference/Exhibition on , vol. 1. , 2000, pp. 323-324
  4. Andrews J. B. and Polychronopoulos C. D. . "An analytical approach to performance/cost modeling of parallel computers". Journal of Parallel and Distributed Computing, 12(4):Aug. 1991, pp. 343–356.
  5. Menasce, D. A. , Saha, D. , Porto, S. C. D. S. ,Almeida, V. A. F. , and Tripathhi, S. K. "Static and dynamic processor scheduling disciplines in heterogeneous parallel architectures". J. Parallel Distrib. Comput. 28, 1 (July 1995), pp . 3-6.
  6. [Gajski,D. , and Peir, J. , "Essential Issue in Multiprocessor", IEEE Computer Vol 18, No. 6 ,1985,PP. 1-5.
  7. Menasce, D. A. , Porto, S. C. ,and Tripathi, S. K. . Static heuristic processor assignment in heterogeneous message passing architectures. Int. J. High Speed Computing. 1994, PP. 114–135.
  8. Shmoys D. B. , Wein J. , and Williamson D. P. , "Scheduling parallel machines on-line". SIAM Journal on Computing,, December 1995.
  9. Nelson R. and Towsley D. , "Comparison of threshold scheduling policies for multiple server systems," IBM, Research. Report,1985.
  10. Feitelson D. G. and Rudolph L. . Parallel job scheduling: Issues and approaches. In IPPS'95 Workshop: Job Scheduling Strategies for Parallel Processing,Springer–Verlag, Lecture Notes in Computer Science LNCS 949, 1995,pp. 1-3.
  11. Kwok Y. and Ahmad I. , "Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors", ACM Computing Surveys 31(4) (December 1999) 406–471
  12. Yu-Kwong K. and Ishfaq A. , "Efficient Scheduling of Arbitrary Task Graphs to Multiprocessors Using a Parallel Genetic Algorithm",Journal of Parallel and Distributed Computing, 1997, pp. 1-3.
  13. Grewe D. and M. F. O'Boyle. A static task partitioning approach for heterogeneous systems using OpenCL. In CC'11, Mar. -Apr. 2011.
  14. Savvas K and Tahar Kechadi, M. "Dynamic Task Scheduling in Computing Cluster Environments," Proceedings of the ISPDC/Heterogeneous Parallel Computing, IEEE conference, 2004, pp. 121–154.
  15. S. Ali, H. J. Siegel, M. Maheswaran, D. Hensgen and S. Ali. "Task Execution Time Modeling for Heterogeneous Computing System. Proceedings of Heterogeneous Computing Workshop", 2000, pp. 184-199 .
  16. Chen H. . "On the Design of Task Scheduling in the Heterogeneous Computing Environments". IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, 2005.
  17. Ahmed M. , S. M. H. Chowdhury, M. Hasan, Fast preemptive task scheduling algorithm for homogeneous and heterogeneous distributed memory systems, in: Ninth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2008, pp. 721– 726.
  18. Radulescu A. and A. J. C. van Gemund. "On the complexity of list scheduling algorithms for distributed memory systems". ACM Int'l Conf. on Supercomputing,Rhodes Greece, 1999.
  19. Andersson B. , Jonsson J. , "Preemptive multiprocessor scheduling anomalies," Proceedings of IPDPS 2002, pages: 12-19, 2002
  20. Pandelis] D. G. , "Optimal Preemptive Scheduling on Uniform Machines with Discounted Flow Time Objectives," European Journal of Operational Research, Vol. 177, No. 1, 2007, pp. 630-637.
  21. Gonzalez T. , "Optimal Mean Finish Time Preemptive Schedules, Technical Report 220, Computer Science Department, Pennsylvania State University 1977.
  22. Renan A. S. , Romulo S. de O. , "A Heterogeneous Preemptive and Non-preemptive Scheduling Approach for Real-Rime Systems on Multiprocessors,", 2012 Second Brazilian Conference on Critical Embedded Systems, 2012, pp. 70-75.
  23. Desrochers M. , Lenstra J. K. , and Savelsbergh M. W. P. , "A Classification Scheme for Vehicle Routing and Scheduling Problems", European Journal of Operational Research ,1990, pp. 320–331.
  24. Burns A. . "Preemptive Priority Based Scheduling: An Appropriate Engineering Approach". Technical Report YCS 214, University of York, 1993,pp. 12-18.
  25. Jeffay, K. ; Stanat, D. F. ; Martel, C. U. ; "On Non-Preemptive Scheduling of Period and Sporadic Tasks," Real-Time Systems Symposium, Proceedings. , Twelfth , vol. , no. , 1991, pp. 129-139.
  26. Zamfirache, F. ;,Zaharie, D. , Craciun, C. ,"Evolutionary Task Scheduling in Static and Dynamic Environments" Computational Cybernetics and Technical Informatics , International Joint Conference on , vol. , no. , 2010,pp. 619-625.
  27. Ahmad, I. ; Dhodhi, M. K. ; Ul-Mustafa, R. ; , "DPS: Dynamic Priority Scheduling Heuristic for Heterogeneous Computing Systems," Computers and Digital Techniques, IEE Proceedings - , vol. 145, no. 6, , Nov 1998,pp. 411-418.
  28. Norman M. G. and Thanisch P. . "Models of Machines and Computation for Mapping in Multicomputers". ACM Comput. Surv. ,1993. pp. 263–302.
  29. Sih, G. C. ; Lee, E. A. ; , "A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures," Parallel and Distributed Systems, IEEE Transactions on , vol. 4, no. 2, , Feb 1993, pp. 175-187.
  30. Iverson M. , F. Ozgumer, and Follen G. . "Parallelizing Existing Applications in a Distributed Heterogeneous Environment" In Proceedings of the 4th Heterogeneous Computing Workshop (HCW'95), , 1995, pp. 91–99.
  31. Wu, M. Y. and Gajski, D. D. , "Hypertool: A Programming Aid for Message-Passing Systems". IEEE Transaction Parallel Distributed. Systems. 1990 pp. 331–344.
  32. Hwang, J. -J. , Chow, Y. -C. , Anger, F. D. , and Lee, C. Y. " Scheduling Precedence Graphs in Systems with Inter-processor Communication Times. SIAM J. Computer, 1989, pp. 245–256.
  33. Sarkar, V. "Partitioning and Scheduling Parallel Programs for Multiprocessors". MIT Press, Cambridge, MA. 1989.
  34. Papadimitriou, C. H. and Yannakakis, M. ,"Towards an Architecture-Independent Analysis of Parallel Algorithms". SIAM J. Computer, 1990,pp. 324–327.
  35. Chen, H. , Shirazi, B. , and Marquis, J. "Performance Evaluation of a Novel Scheduling Method: Linear Clustering with Task Duplication". In Proceedings of the 2nd International Conference on Parallel and Distributed Systems, 1993,pp. 271–276.
Index Terms

Computer Science
Information Sciences

Keywords

Task Scheduling Dynamic Preemptive Non-Preemptive Parallel Computing

Powered by PhDFocusTM