The week's pick
Reseach Article
Two Round Scheduling (TRS) Scheme for Linearly Extensible Multiprocessor Systems
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 38 - Number 10 |
| Year of Publication: 2012 |
| Authors: Abdus Samad, M. Qasim Rafiq, Omar Farooq |
10.5120/4726-6910
|
Abdus Samad, M. Qasim Rafiq, Omar Farooq . Two Round Scheduling (TRS) Scheme for Linearly Extensible Multiprocessor Systems. International Journal of Computer Applications. 38, 10 ( January 2012), 34-40. DOI=10.5120/4726-6910
Abstract
Balancing the computational load over multiprocessor networks is an important problem in massively parallel systems. The key advantage of such systems is to allow concurrent execution of workload characterized by computation units known as processes or tasks. The scheduling problem is to maintain a balanced execution of all the tasks among the various available processors (nodes) in a multiprocessor network. This paper studies the scheduling of tasks on a pool of identical nodes which are connected through some interconnection network. A novel dynamic scheduling scheme named as Two Round Scheduling (TRS) scheme has been proposed and implemented for scheduling the load on various multiprocessor interconnection networks. In particular, the performance of the proposed scheme is evaluated for linearly extensible multiprocessor systems, however, a comparison is also made with other standard existing multiprocessor systems. The TRS operates in two steps to make the network fully balanced. The performance of this scheme is evaluated in terms of the performance index called Load Imbalance Factor (LIF), which represents the deviation of load among processors and the balancing time for different types of loads. The comparative simulation study shows that the proposed TRS scheme gives better performance in terms of task scheduling on various linearly extensible multiprocessor networks for both uniform and non-uniform types of loads.
References
- M. J. Zaki, Wei Li, and S. Parthasarathy, “Customized Dynamic Load Balancing for a Network of Workstations”, Journal of Parallel and distributed Computing, no. 43, 1997, 156-162.
- Z. Zeng, B. Veeravalli, “Design and Performance Evaluation of Queue-and-Rate-Adjustment Dynamic Load Balancing Policies for Distributed Networks”, IEEE Trans. on Computers, vol. 55, no. 11, 2006, 1410-1422.
- S. Salleh, N. A. B. Aziz, N. A Azmee and N. H. Mohammed, “Dynamic Multiprocessor Scheduling for the Reconfigurable mesh Computing Network”, Journal of Technology, University of Technology, Malaysia, vol. 37, 2002, 55-66.
- B. Parhami., “Challenges in interconnection network design in the era of multiprocessor and massively parallel Microchips” In Proceedings of International Conference on communication in Computing, 241-246.
- S. Kim and A. V Veidenbaum, “Interconnection network organization and its impact on performance and cost in shared memory multiprocessors” Journals of parallel computing, vol. 25, 1999, 283-309.
- A. Patel, A. Kasalik, and C. McCrosky, “Area Efficient VLSI Layout for binary Hypercube”, IEEE Transaction on Computers, vol. 49, no. 2, 2006, 160-169.
- M. Q. Rafiq, P. Kumar and J. P. Gupta., “A Novel Tree-Structured Multiprocessor Network”, In Proceedings of International Conference of on Robotics Vision and Parallel Processing for Automation, Malaysia, vol. 2, 1995, 576-585.
- A. Samad, M. Q. Rafiq and O. Farooq, “A Novel Algorithm for Fast Retrieval of Information from A Multiprocessor Server”, In Proceedings of 7th WSEAS International Conference on Software Engineering, Parallel and Distributed Systems (SEPADS '08), University of Cambridge, UK, 2008, 68-73.
- A. Samad and M. Q. Rafiq, “A Novel Server Architecture for Networking”, In Proceedings of Int’l Conference on Robotics, Vision Information and Signal Processing, Malaysia, 2005, 1029-1032.
- B. Towles and W. Dally. Principles and Practices of Interconnection Network. Morgan Kaufmann Press, san Francisco.
- A. Ishfaq and A. Ghafoor, “Semi-Dostributed Load Balancing For Massively Parallel Multicomputer Systems”, IEEE Transaction on Software Engineering, vol. 17, no. 10, 1991, 987-1004.
- W. M. H. LeMair and A. P. Reeves, “Strategies for dynamic load balancing on highly parallel computers”, IEEE Transaction on Parallel and Distributed Systems, vol. 4, no. 9, 1993, 979-92.
- H. Attiya, “Two phase Algorithm for Load Balancing in Heterogeneous Distributed Systems”, In Proceedings of 12th Euromicro Conference on Parallel, Distributed and Network-Based Processing (Euro-PDP’04), 2004, 434-439.
- M. Bertogna., M. Cirinei, and G. Lipari, “Schedulability analysis of Global scheduling algorithm on multiprocessor platforms”, IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 4, 2009, 553-566.
- M. Dobber, R. V. D. Mei and G.Koole, “Dynamic Load Balancing and Job Replication in a Global-Scale Grid Environment: A Comparison” IEEE Transaction on Parallel and Distributed Systems, vol. 20, no. 2, 2009, 207-218.
- Yiqiu Fang, Fei Wang, Junwei Ge, “A Task Scheduling Algorithm Based on Load Balancing in Cloud Computing” Lecture Notes in Computer Science, Issue: 6318, Publisher: Springer-Verlag, 2010, 271-277.
- Bertogna, M., Cirinei, M., and Lipari, G., “Schedulability analysis of Global scheduling algorithm on multiprocessor platforms”, IEEE Transaction on Parallel and Distributed Systems, volume 20, number 4, 2009, 553-566.
- D.I. George Amalarethinam and G.J. Joyce Mary, “A new DAG based Dynamic Task Scheduling Algorithm (DYTAS) for Multiprocessor Systems”. International Journal of Computer Applications (0975 – 8887) Vol. 19, No. 8, 2011, 24-28.
Index Terms
Keywords