近年來，在多核心系統的廣泛使用下，如何把執行的工作平均分配到各個計算單元上去處理是現代計算機科學的重要議題。然而，在大部份探討排程演算法的論文中，多是在已知的假設條件下對一般性的工作做排程。在本論文裡，我們透過修改自異質性多核心平台的Heterogeneous Earliest Finish Time (HEFT)演算法，提出一個更有效率且適用於同質性平台系統上的排程演算法。此演算法繼承了HEFT原有的優良特性，例如：實作簡單、低複雜度以及高效能等，在一般情況下若與目前的HEFT修改版本做比較，它只要更簡單的計算即可達到相同或更優秀的效果，最佳的實驗結果顯示可節省7%以上的處理器時間。我們也特別針對了處理二維向量圖形的同質性多核心平台做排程上的探討，我們將會隨之介紹該如何去估計各個向量圖形的處理時間、分析各子向量圖之間的相依性、把它們對應到一般的樹狀圖上予以計算，最後才使用我們的演算法去作排程。

In recent years, the number of processor cores on one platform has largely increased, while evenly distributing jobs to every processor becomes an important issue. Most previously discussed scheduling situations were well defined general cases. In this thesis, we propose an algorithm, which is modified from Heterogeneous Earliest Finished Time (HEFT), to increase the performance of a homogeneous system. Our proposed algorithm inherits all the advantages of HEFT such as easy implementation, low complexity and high performance etc. In general condition, it generates less overhead for scheduling but the output performance still approaches to or even better than the recent modified version of HEFT up to 7%. The multiprocessor scheduling problems are focused on two dimensional vector graphics, and we will discuss how to estimate the processing time, determine the dependency of each sub-graph, map it onto a directed acyclic graph, and then use our proposed algorithm for vector graphics processing.

[1] H. Topcuoglu, S. Hariri, and M. Y. Wu, "Performance-effective and low-complexity task scheduling for heterogeneous computing," IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 3, pp. 260-274, 2002.
[2] H. Topcuoglu, S. Hariri, and M.-Y. Wu, "Task scheduling algorithms for heterogeneous processors," in Heterogeneous Computing Workshop. (HCW '99) Proceedings. Eighth, pp. 3-14, 1999.
[3] O. Sinnen, Task Scheduling For Parallel Systems, Wiley, p. 315, 2007.
[4] T. Yang and A. Gerasoulis, "DSC - Scheduling parallel tasks on an unbounded number of processors," IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 9, pp. 951-967, 1994.
[5] I. Ahmad and Y. K. Kwok, "On exploiting task duplication in parallel program scheduling," IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 9, pp. 872-892, 1998.
[6] S. Ranaweera and D. P. Agrawal, "A task duplication based scheduling algorithm for heterogeneous systems," in Parallel and Distributed Processing Symposium. IPDPS 2000. Proceedings. 14th International, pp. 445-450, 2000.
[7] X. Y. Tang, K. L. Li, G. P. Liao, et al., "List scheduling with duplication for heterogeneous computing systems," Journal of Parallel and Distributed Computing, vol. 70, no. 4, pp. 323-329, Apr 2010.
[8] G. Q. Liu, K. L. Poh, and M. Xie, "Iterative list scheduling for heterogeneous computing," Journal of Parallel and Distributed Computing, vol. 65, no. 5, pp. 654-665, 2005.
[9] T. L. Adam, K. M. Chandy, and J. R. Dickson, "Comparison of list schedules for parallel processing systems," Communications of the ACM, vol. 17, no. 12, pp. 685-690, 1974.
[10] Y. K. Kwok and I. Ahmad, "Benchmarking and comparison of the task graph scheduling algorithms," Journal of Parallel and Distributed Computing, vol. 59, no. 3, pp. 381-422, 1999.
[11] M. A. Palis, J. C. Liou, and D. S. L. Wei, "Task clustering and scheduling for distributed memory parallel architectures," IEEE Transactions on Parallel and Distributed Systems, vol. 7, no. 1, pp. 46-55, Jan 1996.
[12] R. C. Correa, A. Ferreira, and P. Rebreyend, "Scheduling multiprocessor tasks with genetic algorithms," IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 8, pp. 825-837, 1999.
[13] A. S. Wu, H. Yu, S. Jin, et al., "An incremental genetic algorithm approach to multiprocessor scheduling," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 9, pp. 824-834, 2004.
[14] L. Wang, H. J. Siegel, V. P. Roychowdhury, et al., "Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach," Journal of Parallel and Distributed Computing, vol. 47, no. 1, pp. 8-22, 1997.
[15] O. Sinnen and L. Sousa, "List scheduling: extension for contention awareness and evaluation of node priorities for heterogeneous cluster architectures," Parallel Computing, vol. 30, no. 1, pp. 81-101, 2004.
[16] D. Rice, Google, R. J. Simpson, et al., OpenVG Specification Version 1.1, The Khronos Group Inc., p. 251, 2008.
[17] T. Hagras and J. Janecek, "A high performance, low complexity algorithm for compile-time task scheduling in heterogeneous systems," Parallel Computing, vol. 31, no. 7, pp. 653-670, 2005.
[18] J. Corbet, A. Rubini, and K.-H. Greg, Linux Device Driver third edition, O'Reilly, p. 616, 2005.
[19] L. F. Bittencourt, R. Sakellariou, and E. R. M. Madeira, "DAG Scheduling Using a Lookahead Variant of the Heterogeneous Earliest Finish Time Algorithm," in Parallel, Distributed and Network-Based Processing (PDP), 2010 18th Euromicro International Conference on, pp. 27-34, 2010.