Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20]

¡@

Journal of Information Science and Engineering, Vol. 23 No. 2, pp. 589-604 (March 2007)

An Efficient Clustering-Based Task Scheduling Algorithm for Parallel Programs with Task Duplication*

Wei-Ming Lin and Qiuyan Gu+
 Department of Electrical and Computer Engineering
The University of Texas at San Antonio
San Antonio, TX 78249-0669, U.S.A.
+Net2phone Global Services, LLC
Newark, NJ 07102, U.S.A.

This paper presents an efficient task scheduling algorithm for multiprocessor systems based on clustering with task duplication. This algorithm has a relatively small time complexity of O(|E| log |V|) for a task graph of |V| nodes and |E| edges. Results from an extensive simulation run on randomly generated graphs as well as several application graphs demonstrate a significant improvement in using the proposed technique over several well-known fast techniques. Schedule lengths produced by the proposed algorithm are in general comparable to the ones generated by techniques with a much larger computation time requirement. Actual processing time required by this technique is among the smallest in all advanced techniques, while the number of processors needed is also among the least in all techniques.

Keywords: task scheduling, multiprocessor system, task graph, parallel processing, task duplication

Full Text (¥þ¤åÀÉ) Retrieve PDF document (200703_14.pdf)

Received September 2, 2005; revised December 8, 2005; accepted December 15, 2005.
Communicated by Tsan-sheng Hsu.
* This research was supported in part by the 2004-2005 UTSA Faculty Research Award and in part by the Department of Defense/Air Force Office of Scientific Research under grant F49620-1-0472.