An Optimized Task Duplication Based Scheduling in Parallel System

Full Text (PDF, 602KB), PP.26-37

Views: 0 Downloads: 0

Author(s)

Rachhpal Singh 1,*

1. Department Of Computer Science, Guru Nanak Dev University, Amritsar-Punjab (India)

* Corresponding author.

DOI: https://doi.org/10.5815/ijisa.2016.08.04

Received: 22 Dec. 2015 / Revised: 7 Mar. 2016 / Accepted: 11 May 2016 / Published: 8 Aug. 2016

Index Terms

Task Duplication, Genetic Algorithm, load balance, Task Scheduling, optimization Task, Parallel Computing

Abstract

By the inherent nature of solving enormous number of problems with the concurrent execution, parallel process methods grow to be a popular technique. The challenges of parallel computing are dealing with the computing resources for the number of tasks and complexity, dependency, resource starvation, load balancing and efficiency. In this paper, the brief discussion about the parallel computation is carried out, and numerous performance issues are also discovered as an open issue. The risk encountered in parallel computing is the motivation to analyze different optimization techniques to accomplish the tasks without risky environment. Genetic Algorithm (GA) is another approach to make the concept of scheduling easy and fast. Here the paper presents a Task Duplication based Genetic Algorithm with Load Balance (TD-GA) approach on parallel processing for effective scheduling of multiple tasks with less schedule length and load balance. TD-GA algorithm truly handles the issues very well and the results show that complexity, load balance and resource utilization are finely managed when compared to the other optimization approaches.

Cite This Paper

Rachhpal Singh, "An Optimized Task Duplication Based Scheduling in Parallel System", International Journal of Intelligent Systems and Applications (IJISA), Vol.8, No.8, pp.26-37, 2016. DOI:10.5815/ijisa.2016.08.04

Reference

[1]Frank Willmore, “Introduction to Parallel Computing”, 2012.
[2]HalukTopcuoglu, Salim Hariri and Min-You Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing”, IEEE Transactions on Parallel And Distributed Systems, Vol. 1, No. 3, March 2002.
[3]Koichi Asakura, Bing Shao and Toyohide Watanabe, “A Task Duplication Based Scheduling Algorithm for Avoiding Useless Duplication”, July 18, 2010.
[4]D. Asir Antony Gnana Singh, E. Jebamalar Leavline, R. Priyanka, P. Padma Priya, "Dimensionality Reduction using Genetic Algorithm for Improving Accuracy in Medical Diagnosis", International Journal of Intelligent Systems and Applications(IJISA), IJISA, Vol. 8, No. 1, January 2016, ISSN: 2074-904X (Print), ISSN: 2074-9058 (Online), DOI: 10.5815/ijisa, Published By: MECS Publisher
[5]Sekhri Larbi, Slimane Mohamed, "Modeling the Scheduling Problem of Identical Parallel Machines with Load Balancing by Time Petri Nets”, International Journal of Intelligent Systems and Applications (IJISA), ISSN: 2074-904X (Print), ISSN: 2074-9058 (Online), Vol. 7, No. 1, December 2014, DOI: 10.5815/ijisa, Published By: MECS Publisher.
[6]Zhiwei Ye, MingWei Wang, Huazhong Jin, Wei Liu, XuDong Lai, " An Image Thresholding Approach Based on Ant Colony Optimization Algorithm Combined with Genetic Algorithm” , International Journal of Intelligent Systems and Applications (IJISA), ISSN: 2074-904X (Print), ISSN:2074-9058(Online), DOI: 10.5815, Vol. 7, No. 5, April 2015, Published By: MECS Publisher.
[7]Reza Ebrahimzadeh, Mahdi Jampour, " Chaotic Genetic Algorithm based on Lorenz Chaotic System for Optimization Problems", International Journal of Intelligent Systems and Applications (IJISA), ISSN: 2074-904X (Print), ISSN: 2074-9058 (Online), Vol. 5, No. 5, April 2013, PP.19-24, DOI: 10.5815/ijisa.2013.05.03, Publisher: MECS.
[8]Raksha Sharma, Vishnu Kant Soni, Manoj Kumar Mishra and Prachet Bhuyan, "A Survey of Job Scheduling and Resource Management in Grid Computing", World Academy of Science, Engineering and Technology, Vol.4, 2010
[9]Pinky Rosemarry, Payal Singhal, and Ravinder Singh, "A Study of Various Job & Resource Scheduling Algorithms in Grid Computing", International Journal of Computer Science and Information Technologies, Vol. 3, pp. 5504-5507, 2012.
[10]Osama I. Hassanein,Ayman A. Aly,Ahmed A. Abo-Ismail, “Parameter Tuning via Genetic Algorithm of Fuzzy Controller for Fire Tube Boiler”, International Journal of Intelligent Systems and Applications, ISSN: 2074-904X (Print), ISSN: 2074-9058 (Online), Vol.4, No.4, April 2012, PP.9-18.
[11]A. Ebaid, R. Ammar, S. Rajasekaran and R. ElKharboutly, "An enhanced scheduling algorithm using a recursive critical path approach with task duplication," 2012 IEEE International Symposium on Signal Processing and Information Technology (ISSPIT), Ho Chi Minh City, 2012, pp. 000107-000113, doi: 10.1109/ISSPIT.2012.6621269.
[12]J. Zhao and H. Qiu, "Genetic algorithm and ant colony algorithm based Energy-Efficient Task Scheduling," 2013 IEEE Third International Conference on Information Science and Technology (ICIST), Yangzhou, 2013, pp. 946-950. doi: 10.1109/ICIST.2013.6747695
[13]H. A. Bazoobandi, M. Khorashadizadeh and M. Eftekhari, "Solving task scheduling problem in multi-processors with genetic algorithm and task duplication," Intelligent Systems (ICIS), 2014 Iranian Conference on, Bam, 2014, pp. 1-4. doi: 10.1109/IranianCIS.2014.6802528.
[14]S. Shakya and U. Prajapati, "Task scheduling in Grid computing using Genetic Algorithm," Green Computing and Internet of Things (ICGCIoT), 2015 International Conference on, Noida, 2015, pp. 1245-1248. doi: 10.1109/ICGCIoT.2015.7380654
[15]Oliver Sinnen, Andrea To, Manpreet Kaur, “Contention-Aware Scheduling with Task Duplication”, Journal of Parallel and Distributed Computing, Volume 71, Issue 1, January 2011, Pages 77–86.
[16]Ian Karlin et al, “Exploring Traditional and Emerging Parallel Programming Models using a Proxy Application”, IEEE 27th International Symposium on Parallel & Distributed Processing (IPDPS), 2013.
[17]He,Y. Hongyang Sun and Wen-Jing Hsu, “Adaptive Scheduling of Parallel Jobs on Functionally Heterogeneous Resources”, International Conference on Parallel Processing, 2007.
[18]“Introduction to Parallel Computing”, George Karypis, Parallel Programming Platforms.
[19]Satoshi Ohshima, Kenji Kise, Takahiro Katagiri and Toshitsugu Yuba “Parallel Processing of Matrix Multiplication in a CPU and GPU Heterogeneous Environment”, 2006.
[20]Henry Kasim, Verdi March, Rita Zhang1, and Simon See, “Survey on Parallel Programming Model”, 2008.
[21]Wei-Ming Lin and QiuyanGu, “An Efficient Clustering-Based Task Scheduling Algorithm for Parallel Programs with Task Duplication”, Journal Of Information Science And Engineering, Vol. 23, 589-604, 2007.
[22]Mohammad I. Daoud and NawwafKharma, “An Efficient Genetic Algorithm for Task Scheduling in Heterogeneous Distributed Computing Systems”, 2006 IEEE Congress on Evolutionary Computation, 2006.
[23]Heejo Lee, Jong Kim, Sung Je Hong,Sunggu Lee, “Task scheduling using a block dependency DAG for block-oriented sparse Choleskyfactorization”, Parallel Computing (ELSEVIER), Vol. 29, pp. 135–159, 2003.
[24]HeikkiOrsila, TeroKangas, and Timo D. Hamalainen, “Hybrid Algorithm for Mapping Static Task Graphs on Multiprocessor SoCs”, 2012.
[25]Amir Masoud Rahmaniand Mojtaba Rezvani, “A Novel Genetic Algorithm for Static Task Scheduling in Distributed Systems”, International Journal of Computer Theory and Engineering, Vol. 1, No. 1, April 2009.
[26]Singh, Jasbir, Singh Gurvinder, “Improved Task Scheduling on Parallel System using Genetic Algorithm”, International Journal of Computer Applications, Feb2012, Vol. 39, p17-22, 2012.
[27]Dahal, K. Hossain, A., Varghese, B, “Scheduling in Multiprocessor System Using Genetic Algorithm, Computer Information Systems and Industrial Management Applications, 2008.
[28]Jaspal Singh, Harsharanpal Singh, “Efficient Tasks scheduling for heterogeneous multiprocessor using Genetic algorithm with Node duplication”, Indian Journal of Computer Science and Engineering (IJCSE), 2011.
[29]RituVerma, SunitaDhingra, “Genetic Algorithm for Multiprocessor Task Scheduling”, CiteSeer, 2011.
[30]Yu-Kwong Kwok, Ishfaq Ahmad, “Efficient Scheduling of Arbitrary Task Graphs to Multiprocessors Using a Parallel Genetic Algorithm”, Journal of Parallel and Distributed Computing, Vol. 47, Issue 1, 25 November 1997, Pages 58–77.