基於多核心及異質記憶體模組之即時程序排程

多核心及異質記憶體之設計已廣泛的使用於伺服器、個人電腦甚至嵌入式系統，隨著硬體技術之成長，軟體的開發益趨於多樣化且複雜，這也加重了系統軟體之需求與挑戰，甚者，由於多核心排程技術須更進一步考量異質記憶體之使用，傳統即時多核心排程技術將使得系統使用效率低落。基於以上之觀察，本論文利用非揮發性記憶體開發出一快速開機機制，減少開機時載入及初始化之冗長時間，同時並權衡考量系統執行時期之效能，以有限的執行時期之效能損失為前提，最小化系統開機之時間。進一步在系統之執行時期本論文提出處理器與記憶體共管理之演算法，此演算法包含異質記憶體管理機制以及對應之多核心工作排程技術，以期達成系統即時效能之需求。然而當系統核心數量不斷上升時，記憶體架構勢必益趨複雜，本於此一考量，本論文延伸探討多核心及異質記憶體之共同資源管理機制，於可重新結構配置之多核心硬體環境之下，所提出之機制將可最小化系統資源之消耗並達成軟體之即時效能需求。最後，透過一連串的實驗以及模擬來評估演算法之性能，並展示所提出設計之可行性。

關鍵字

多核心；異質記憶體；即時系統；快速開機；即時排程

並列摘要

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.