請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/66003
標題: | 基於多核心及異質記憶體模組之即時程序排程 Real-Time Task Scheduling over Multiple Cores with Heterogeneous Memory Modules |
作者: | Che-Wei Chang 張哲維 |
指導教授: | 郭大維 |
關鍵字: | 多核心,異質記憶體,即時系統,快速開機,即時排程, multi-core,heterogeneous memory,real-time system,fast booting,real-time scheduling, |
出版年 : | 2012 |
學位: | 博士 |
摘要: | 多核心及異質記憶體之設計已廣泛的使用於伺服器、個人電腦甚至嵌入式系統,隨著硬體技術之成長,軟體的開發益趨於多樣化且複雜,這也加重了系統軟體之需求與挑戰,甚者,由於多核心排程技術須更進一步考量異質記憶體之使用,傳統即時多核心排程技術將使得系統使用效率低落。基於以上之觀察,本論文利用非揮發性記憶體開發出一快速開機機制,減少開機時載入及初始化之冗長時間,同時並權衡考量系統執行時期之效能,以有限的執行時期之效能損失為前提,最小化系統開機之時間。進一步在系統之執行時期本論文提出處理器與記憶體共管理之演算法,此演算法包含異質記憶體管理機制以及對應之多核心工作排程技術,以期達成系統即時效能之需求。然而當系統核心數量不斷上升時,記憶體架構勢必益趨複雜,本於此一考量,本論文延伸探討多核心及異質記憶體之共同資源管理機制,於可重新結構配置之多核心硬體環境之下,所提出之機制將可最小化系統資源之消耗並達成軟體之即時效能需求。最後,透過一連串的實驗以及模擬來評估演算法之性能,並展示所提出設計之可行性。 Multiple cores and heterogeneous memory components are widely adopted in the designs of servers, personal computers, and even embedded systems. Such trends have imposed great pressure on better and more support from the operating systems and even imply more demands in the system efficiency enhancement, including booting time, for many systems. The success of the system efficiency enhancement relies on not only task scheduling over cores but also allocation strategies of other resources. Such an observation motivates the joint consideration of task scheduling and the memory allocation of task images. This dissertation first shows that the booting time minimization problem for real-time systems with nonvolatile memory is NP-hard. An optimal but pseudo-polynomial-time algorithm, a 0.25-approximation algorithm, and a polynomial-time approximation scheme are proposed for the tradeoff between the solution quality and the time complexity. In the second part of this dissertation, the run-time performance optimization problem for multi-core systems equipped with heterogeneous shared memory modules is considered. A two-phase algorithm is proposed to minimize the maximum required utilization among cores, where memory modules have different access latencies: The first phase determines the memory allocation, and the second phase assigns tasks onto cores with a tight (2− 2M+1)-approximation bound, where M is the number of cores. In the third part of this dissertation, the results are extended for island-based multi-core platforms with an observation that the number of cores in a system keeps increasing. This dissertation explores real-time task scheduling over homogeneous cores with local memory shared by the cores in an island and global memory shared by the entire system. Approximation algorithms are provided to efficiently derive the task partition and the memory allocation. Case studies and simulations were conducted to evaluate the proposed algorithms, and the results further revealed the insights into the joint-consideration designs of memory allocation and task scheduling. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/66003 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-101-1.pdf 目前未授權公開取用 | 1.04 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。