考量資源擴增取捨之多核心即時系統排程

Abstract

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.