Performance Evaluation of Task Scheduling Algorithm on LCQ Network

Authors: Zaki Ahmad Khan, Jamshed Siddiqui, Abdus Samad

Abstract:

The Scheduling and mapping of tasks on a set of processors is considered as a critical problem in parallel and distributed computing system. This paper deals with the problem of dynamic scheduling on a special type of multiprocessor architecture known as Linear Crossed Cube (LCQ) network. This proposed multiprocessor is a hybrid network which combines the features of both linear types of architectures as well as cube based architectures. Two standard dynamic scheduling schemes namely Minimum Distance Scheduling (MDS) and Two Round Scheduling (TRS) schemes are implemented on the LCQ network. Parallel tasks are mapped and the imbalance of load is evaluated on different set of processors in LCQ network. The simulations results are evaluated and effort is made by means of through analysis of the results to obtain the best solution for the given network in term of load imbalance left and execution time. The other performance matrices like speedup and efficiency are also evaluated with the given dynamic algorithms.

Keywords: Dynamic algorithm, Load imbalance, Mapping, Task scheduling.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1105377

References:

[1] I. Ahmad and A. Ghafoor, “Semi-Distributed Load Balancing for Massively Parallel Multicomputer Systems,” IEEE Transactions on Software Engineering, vol. 17, no. 10, pp. 987-1004, 1991.
[2] M. H. W. LeMair and A. P. Reeves, “Strategies for dynamic load balancing on highly parallel computers,” IEEE Transactions on Parallel and Distributed Systems, vol. 4, no. 9, pp. 979-993, 1993.
[3] M. J. Zaki, W. Li and S. Parthasarathy, “Customized Dynamic Load Balancing for a Network of Workstations,” Journal of Parallel and Distributed Computing, no. 43, pp. 156-162, 1997.
[4] S. Sharma, S. Singh and M. Sharma, “Performance Analysis of Load Balancing Algorithms,” in proceeding of World Academy of Science, Engineering and Technology, vol. 2 , pp. 02-21, 2008.
[5] Z. Zeng and B. Veeravalli, “Design and Performance Evaluation of Queue-and-Rate-Adjustment Dynamic Load Balancing Policies for Distributed Networks,” IEEE Transactions on Computers, vol. 55, no. 11, pp. 1410-1422, 2006.
[6] K. Lakshmanan, D. D. Niz and R. Rajkumar, “Coordinated Task Scheduling, Allocation and Synchronization on Multiprocessors,” in proceeding of 30th IEEE Real-Time Systems Symposium, pp. 469-478, 2009.
[7] A. Chandra and P. Shenoy, “Hierarchical Scheduling for Symmetric Multiprocessors,” IEEE Transactions On Parallel And Distributed Systems, vol. 19, no. 3, pp. 418-431, 2008.
[8] J. Jia, B. Veeravalli and J. Weissman, “Scheduling Multiprocessor Divisible Loads on Arbitrary Networks,” IEEE Transactions On Parallel And Distributed Systems, vol. 21, no. 4, pp. 520-531, 2010.
[9] M. Guzek, J. E. Pecero, B. Dorronsoro and P. Bouvry, “Multi-objective evolutionary algorithms for energy-aware scheduling on distributed computing systems,” Applied Soft Computing, vol. 24, pp. 432–446, 2014.
[10] F. A. Omara and M. M. Arafa, “Genetic algorithms for task scheduling problem,” Journal Parallel Distributed Computing, vol. 70, pp. 13–22, 2010.
[11] A. Samad, M. Q. Rafiq and O. Farooq, “A Novel Algorithm For Fast Retrival Of Information From A Multiprocessor Server,” in proceeding of 7th WSEAS International Conference on software engineering, parallel and distributed systems (SEPADS '08), University of Cambridge, UK, pp. 68-73, 2008.
[12] A. Samad, M. Q. Rafiq and O. Farooq, “Two Round Scheduling (TRS) Scheme for Linearly Extensible Multiprocessor Systems,” International Journal of Computer Applications, vol. 38, no. 10, pp. 34-40, 2012.
[13] A. Samad, M. Q. Rafiq and O. Farooq, “Multi-stage scheduling scheme for massively parallel systems,” in proceeding of International Conference on Software Engineering and Mobile Application Modelling and Development (ICSEMA), pp. 168-176, 2012.
[14] E. Dodonov and R. F. d. Mello, “A novel approach for distributed application scheduling based on prediction of communication events,” Future Generation Computer Systems, vol. 26, pp. 740–752, 2010.
[15] Q. Kang, H. He and H. Song, “Task assignment in heterogeneous computing systems using an effective iterated greedy algorithm,” The Journal of Systems and Software, vol. 84, pp. 985–992, 2011.
[16] N. Rajak, A. Dixit and R. Rajak, “Classification of list task scheduling algorithms: A short review paper,” Journal of Industrial and Intelligent Information, vol. 2, no. 4, pp. 320-323, 2014.
[17] R. Kaur and R. Kaur, “Multiprocessor scheduling using task duplication based scheduling algorithms: A review paper,” International Journal of Application or Innovation in Engineering and Management, vol. 2, no. 4, pp. 311-317, 2013.
[18] R. Hwang, M. Gen and H. Katayama, “A comparison of multiprocessor task scheduling algorithms with communication costs,” Computers and Operations Research, vol. 35, pp. 976-993, 2008.
[19] S. Bansal, B. Kothari and C. Hota, “Dynamic Task-Scheduling in Grid Computing using Prioritized Round Robin Algorithm,” International Journal of Computer Science Issues, vol. 8, no. 2, pp. 472–477, 2011.
[20] Z. A. Khan, J. Siddiqui and A. Samad, “Linear Crossed Cube (LCQ): A New Interconnection Network Topology for Massively Parallel System,” International Journal of Computer Network and Information Security, vol. 7, no. 3, pp. 18-25, 2015.