請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/59710
標題: | 考量資源擴增取捨之多核心即時系統排程 Many-Core Real-Time Task Scheduling with Resource Augmentation Trade-off Considerations |
作者: | Sheng-Wei Cheng 鄭聖威 |
指導教授: | 郭大維(Tei-Wei Kuo) |
關鍵字: | 即時系統,分群多核心平台,可程式化運算核心,同時考量記憶體分配與工作排程,資源擴充,近似演算法, Real-Time System,Many-Core Island-Based Platform,Reconfigurable Processor,Joint Memory Allocation and Task Scheduling,Resource Augmentation,Approximation Algorithm, |
出版年 : | 2017 |
學位: | 博士 |
摘要: | Following the success of multi-core architectures in power consumption reduction and thermal dissipation improvement, many-core architectures draw a lot of attention for the next development trend. On a multi-island platform, homogeneous cores are grouped into islands, each of which is equipped with a scratchpad memory module (referred to as local memory). In addition, a reconfigurable processor which consists of a reconfigurable fabric and general-purpose processors becomes popular due to the ability to accelerate a wide variety of applications. However, the demand to schedule real-time tasks on these emerging architectures poses a challenge. In this dissertation, we seek efficient solutions to schedule real-time tasks with memory preallocation, interference minimization, and
data prefetching concerns. We first show the NP-hardness and the inapproximability to schedule real-time tasks on a multi-island platform. Despite the inapproximability, positive results can still be found when different cases of the problem are investigated. We employ the idea of resource augmentation, and aim to capture the relation between the speedup factor and the resource augmentation factor. Being aware of such relation, we can help system developers to understand the trade-off between hardware costs and performance. For example, when the technique of resource augmentation is considered, this dissertation develops an algorithm with (2γ−1)/(γ−1) speedup factor and (γ + 1) memory augmentation factor for the memory preallocation problem on a multi-island platform, where γ represents the trade-off between CPU utilization and local memory space. In addition, resources, such as memory banks and buses, are shared among all cores within an island for power, performance, and cost reasons. The interference on the shared local memory also poses a challenge on real-time analysis, but can be alleviated if task data partition onto local memory is applied with care. We employ symmetric real-time analysis and rectify the analysis to adapt to the considered platform. We propose an algorithm with (5+ 3(2γ+1)/γ) speedup factor and (γ +1) memory augmentation factor for the interference minimization problem on a single-island platform, where γ > 0. Lastly, on a reconfigurable processor, tasks are required to configure their accelerators on a capacity-limited reconfigurable fabric before their execution. To improve system performance, task sequencing and task prefetching are important techniques to minimize the makespan of a task set. We aim at deriving a theoretical analysis that can help system developers quantify the performance of the resulted makespan with respect to the fabric capacity on a reconfigurable processor. We adopt Johnson’s rule and Post-Swapping algorithms to generate a task sequence, and identify capacity blocking and prefetching blocking when configuring accelerators on a reconfigurable processor. Our analysis yields an asymptotic approximation bound (4max{ω,0.5} − 1)OP T + ωrB for makespan minimization problem on a reconfigurable processor, where ωrB is the maximum accelerator configuration time among the tasks. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/59710 |
DOI: | 10.6342/NTU201700250 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-106-1.pdf 目前未授權公開取用 | 1.52 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。