Resource Contention-Aware Task Scheduling for MPSoC Designs

多核心系統晶片資源競爭考量工作排程演算法

莊震宇(Chen-Yu Chuang)

指導教授 ： 蔡仁松

國立清華大學/電機資訊學院/資訊工程學系/碩士(2010年)

https://doi.org/10.6843/NTHU.2010.00450

摘要

這篇論文提出一個多核心系統晶片(MPSoC)設計用的資源競爭考量的排程演算法。伴隨這系統設計複雜度的提高，越來越多的工作(軟體)共同分享著有限的系統資源(硬體資源)。也因此，資源競爭所造成的工作執行延遲在現今複雜的系統晶片下已成為了造成系統效能的瓶頸之一。然而，在過去探究工作排程問題的研究中，關於競爭延遲的部分卻沒有被詳盡的探討。因此，為了達到系統效能的最佳化，我們根據舊有的清單排程(list-scheduling)方法進行有效的改善，將資源競爭延遲加入到工作排程的考量中，而提出一個資源競爭考量排程演算法來解決資源競爭的問題。在實驗中，我們採用本篇所提出的排程方法與過去各排程方法做了比較。在複雜的系統設計中，相較於求得最佳化排程結果的方法(ILP)在排程時間上快了125倍，卻只有23%的排程結果的增加。相較於最快的清單排程方法在排程結果上我們的方法有將近15%改進，卻只有些微的排程時間差距。這證明了我們所提出的方法是有效且實用的排程方法。

關鍵字

工作排程 ； 多核心系統晶片 ； 資源競爭

並列摘要

無資料

並列關鍵字

task scheduling ； MPSoC ； resource contention

參考文獻

[1] J. D. Ullman, “NP-complete scheduling problems,” J. Comput. Syst. Sci., vol. 10, pp. 384–393, 1975.

[5] C. Lee, M. Potkonjak, and W. Wolf, “Synthesis of hard real-time application specific systems,” IEEE Transactions on Design Automation Embedded Systems, vol. 4, no.4, pp. 215–241, 1999.

[6] Haluk Topcuoglu, Salim Hariri, and Min-You 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.

[7] Y. K. Kwok and I. Ahmad, “Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors,” IEEE Transactions on Parallel and Distributed System, vol. 7, no. 5, pp. 506–521, 1996

[8] Oliver Sinnen and Leonel A.. Sousa, “Communication Contention in Task Scheduling,” IEEE Transactions on Parallel and Distributed Systems, vol 16, no 6, pp. 503-515, 2005