Performance Evaluation of Task Scheduling Algorithm on LCQ Network

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.

Authors:

• Zaki Ahmad Khan
• Jamshed Siddiqui
• Abdus Samad

Keywords:

• Dynamic algorithm
• Load imbalance
• Mapping
• Task scheduling.

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.