在群集式異質性計算環境中，對於有向非循環圖來表示的平行化應用程式，提供一個有效的工作排程方法來獲取高效能的結果。然而，找尋一個有效的排程需要考慮不同計算能力的處理器及不同頻寬的連接；近年來，提出複製演算法和前看演算法在排程這個議題上，但它們有著不同的優缺點。此篇論文題出了一個複製和前看的混合式演算法(DuLo)來依照工作的特性來選擇複製或者前看演算法所決定的處理器。在隨機產生圖中的實驗研究比較，DuLo演算法在排程長度、平均排程長度比例和加速數值皆顯著地優於複製演算法和前看演算法。

Effective task scheduling of parallel applications represented by direct acyclic graph (DAG) is critical for obtaining high performance in heterogeneous cluster computing environment (HCCE). However, finding an effective schedule in HCCE requires the consideration of processors with varying processing capabilities and network links with varying bandwidths. There are two algorithms, which are Duplication and Lookahead, for scheduling DAG have been proposed recently. They are different disadvantage and advantage in task scheduling. Thus, this paper presents a hybrid scheduling algorithm, called Adaptive Task Scheduling with Task Duplication and Lookahead (DuLo). DuLo considers the characteristic of task to assigned task on the processor which is decided from Duplication and Lookahaed. In comparison study, based on randomly generated graphs, show that DuLo algorithm significantly surpasses Duplication and Lookahead algorithm in terms of quality, which are mainly presented with makespan, schedule length ratio and speedup.

[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness: WH Freeman & Co., 1979.
[2] E. G. Coffman and J. L. Bruno, Computer and job-shop scheduling theory: Wiley New York, 1976.
[3] H. El-Rewini, T. G. Lewis, and H. H. Ali, Task scheduling in parallel and distributed systems: Prentice-Hall, Inc., 1994.
[4] R. Graham, E. Lawler, J. Lenstra, and A. H. G. R. Kan, "Optimization and approximation in deterministic sequencing and scheduling: a survey," Discrete optimization: proceedings, vol. 1, p. 287, 1979.
[5] H. Topcuoglu, S. Hariri, and M. Wu, "Performance-effective and low-complexity task scheduling for heterogeneous computing," IEEE transactions on parallel and distributed systems, pp. 260-274, 2002.
[6] L. Wang, H. J. Siegel, V. P. Roychowdhury, and A. A. Maciejewski, "Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based Approach, " Journal of Parallel and Distributed Computing, vol. 47, pp. 8-22, 1997.
[7] X. Tang, K. Li, G. Liao, and R. Li, "List scheduling with duplication for heterogeneous computing systems," Journal of Parallel and Distributed Computing, vol. 70, pp. 323-329, 2010.
[8] L. F. Bittencourt, R. Sakellariou, and E. R. M. Madeira, "Dag scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm," 2010, pp. 27-34.
[9] Z. Shi and J. J. Dongarra, "Scheduling workflow applications on processors with different capabilities," Future generation computer systems, vol. 22, pp. 665-675, 2006.
[10] G. Liu, K. Poh, and M. Xie, "Iterative list scheduling for heterogeneous computing," Journal of Parallel and Distributed Computing, vol. 65, pp. 654-665, 2005.
[11] S. C. Kim and S. Lee, "Push-pull: Guided search dag scheduling for heterogeneous clusters," pp. 603-610.
[12] A. Giersch, Y. Robert, and F. Vivien, "Scheduling tasks sharing files on heterogeneous clusters," Recent Advances in Parallel Virtual Machine and Message Passing Interface, pp. 657-660, 2003.
[13] T. Yang and A. Gerasoulis, "DSC: Scheduling parallel tasks on an unbounded number of processors," Parallel and Distributed Systems, IEEE Transactions on, vol. 5, pp. 33
951-967, 1994.
[14] M. Y. Wu and D. D. Gajski, "Hypertool: A programming aid for message-passing systems," Parallel and Distributed Systems, IEEE Transactions on, vol. 1, pp. 330-343, 1990.
[15] J. C. Liou and M. A. Palis, "An efficient task clustering heuristic for scheduling DAGs on multiprocessors," 1996.
[16] G. C. Sih and E. A. Lee, "A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures," Parallel and Distributed Systems, IEEE Transactions on, vol. 4, pp. 175-187, 1993.
[17] J. J. Hwang, Y. C. Chow, F. D. Anger, and C. Y. Lee, "Scheduling precedence graphs in systems with interprocessor communication times," SIAM Journal on Computing, vol. 18, p. 244, 1989.
[18] H. El-Rewini and T. G. Lewis, "Scheduling parallel program tasks onto arbitrary target machines," Journal of Parallel and Distributed Computing, vol. 9, pp. 138-153, 1990.
[19] B. Kruatrachue and T. Lewis, "Grain size determination for parallel processing," Software, IEEE, vol. 5, pp. 23-32, 1988.
[20] Z. H. Chen, T. C. Chen, J. Y. Chien, A. Su, and C. K. Shieh, "Exploiting Parallelism of MPEG-4 Decoder with Dataflow Programming on Multicore Processor," 2010, pp. 367-373.
[21] I. Ahmad and Y. K. Kwok, "A new approach to scheduling parallel programs using task duplication," 1994, pp. 47-51.
[22] G. L. Park, B. Shirazi, and J. Marquis, "DFRN: A new approach for duplication based scheduling for distributed memory multiprocessor systems," 1997, p. 157.
[23] Y. C. Chung and S. Ranka, "Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors," 1992, pp. 512-521.
[24] R. Sakellariou and H. Zhao, "A hybrid heuristic for DAG scheduling on heterogeneous systems," 2004.