Duplication with Task Assignment in Mesh Distributed System
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Load balancing is the major benefit of any distributed system. To facilitate thisadvantage, task duplication and migration methodologies are employed. As this paperdeals with dependent tasks (DAG), we used duplication. Task duplication reduces theoverall schedule length of DAG along-with load balancing. This paper proposes a newtask duplication algorithm at the time of tasks assignment on various processors. With theintention of conducting proposed algorithm performance computation; simulation hasbeen done on the Netbeans IDE. The mesh topology of a distributed system is simulatedat this juncture. For task duplication, overall schedule length of DAG is the mainparameter that decides the performance of a proposed duplication algorithm. Afterobtaining the results we compared our performance with arbitrary task assignment,CAWF and HEFT-TD algorithms. Additionally, we also compared the complexity of theproposed algorithm with the Duplication Based Bottom Up scheduling (DBUS) andHeterogeneous Earliest Finish Time with Task Duplication (HEFT-TD).
Abstract
Load balancing is the major benefit of any distributed system. To facilitate thisadvantage, task duplication and migration methodologies are employed. As this paperdeals with dependent tasks (DAG), we used duplication. Task duplication reduces theoverall schedule length of DAG along-with load balancing. This paper proposes a newtask duplication algorithm at the time of tasks assignment on various processors. With theintention of conducting proposed algorithm performance computation; simulation hasbeen done on the Netbeans IDE. The mesh topology of a distributed system is simulatedat this juncture. For task duplication, overall schedule length of DAG is the mainparameter that decides the performance of a proposed duplication algorithm. Afterobtaining the results we compared our performance with arbitrary task assignment,CAWF and HEFT-TD algorithms. Additionally, we also compared the complexity of theproposed algorithm with the Duplication Based Bottom Up scheduling (DBUS) andHeterogeneous Earliest Finish Time with Task Duplication (HEFT-TD).
참고문헌 (17)
- L. N. Bhuyan, "Generalized hypercube and hyperbus structures for a computer network", IEEE Transactions on Computers, 33(4), pp.323~333 (1984)
- D. Bozdağ, "A task duplication based bottom-up scheduling algorithm for heterogeneous environments", Proceedings of the 20th International Parallel and Distributed Processing Symposium (2006)
- Y. Jégou, "Runtime support for task migration on distributed memory architectures", Proceedings of the 11th International Conference on Parallel Processing Symposium (1997)
- J. M. Lopez, "Worst-case utilization bound for EDF scheduling on real-time multiprocessor systems", Proceedings of the 12th Euromicro Conference on Real-Time Systems, pp.25~33 (2000)
- A. Burchard, "New strategies for assigning real-time tasks to multiprocessor systems", IEEE Transactions on Computers, 44(12), pp.1429~1442 (1995)
- C. Wang, "Dynamic voltage scaling for priority-driven scheduled distributed real-time systems", 박사, pp.2007
- E. G. Coffman, Jr., "Approximation Algorithms for NP-Hard Problems", pp.46~93 (1997), PWS Pub. Co.
- A. Bashiry, "Task partitioning and load balancing strategy for matrix applications on distributed system", Journal of Computers, 8(3), pp.576~584 (2013)
- J. Baxter, "The LAST algorithm: a heuristic-based static task allocation algorithm", Proceedings of the 1989 International Conference on Parallel Processing, pp.217~222 (1989)
- B. Kruatrachue, "Grain size determination for parallel processing", IEEE Software, 5(1), pp.23~32 (1988)
- P. Chaudhuri, "Process scheduling in heterogeneous multiprocessor systems using task duplication", International Journal of Business Data Communications and Networking, 6(1), pp.58~69 (2010)
- S. Ranaweera, "A task duplication based scheduling algorithm for heterogeneous systems", Proceedings of the 14th International Parallel and Distributed Processing Symposium, pp.445~450 (2000)
- S. Ranaweera, "A scalable task duplication based scheduling algorithm for heterogeneous systems", Proceedings of the International Conference on Parallel Processing, pp.383~390 (2000)
- J. Singh, "Efficient tasks scheduling for heterogeneous multiprocessor using genetic algorithm with node duplication", Indian Journal of Computer Science and Engineering, 2(3), pp.402~410 (2011)
- R. Sharma, "Duplication with task assignment in mesh distributed system", World Congress on Information and Communication Technologies, pp.672~676 (2011)
- E. G. Coffman, Jr., "Handbook of Combinatorial Optimization", pp.151~207 (1998), Kluwer Academic Publishers
- V. M. Lo, "Heuristic algorithms for task assignment in distributed systems", IEEE Transactions on Computers, 37(11), pp.1384~1397 (1988)