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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:69906", author = "Zaki Ahmad Khan and Jamshed Siddiqui and Abdus Samad", title = "Performance Evaluation of Task Scheduling Algorithm on LCQ Network", 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.", volume = "9", number = "3", pages = "789-6", }