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

鄭聖威

doi:10.6342/NTU201700250

山西大学，您好！

感谢采购，人社期刊库｜人社论文库，期间：2025/01/01~2025/12/31

感谢试用，科学期刊库｜科学论文库，期间：2024/10/20~2025/01/20

浏览高级检索

关闭
检索检索高级检索出版物检索
浏览期刊主题浏览核心期刊浏览期刊拼音浏览

关闭

查询符号(半角)	查询符号意义说明
空格	表示为「AND」两个查询词之交集
双引号 ( " " )	片语以双引号标示开始及结束，而且只寻找出现顺序相同的字词，例： " image process "
?	表示一个字母切截，输入两个?表两个字母，依此类推，例：输入「Appl?」，查得结果应为appl e , appl y … ( 常用于英文字查询 )
*	表示不限字母切截，由0~n. 例：输入「appl*」，查得结果应为appl e , appl es , appl y , appl ied , appl ication … ( 常用于英文字查询 )
AND、OR、NOT	布尔逻辑组合关键字，用来扩大或缩小查询范围的技巧。 (1) AND ：缩小查询范围 (2) OR ：扩大查询范围(3) NOT：排除不相关的范围

DOI 是数位物件识别码（ D igital O bject I dentifier ）的简称，
为物件在网路上的唯一识别码，可用于永久连结并引用目标物件。

使用DOI作为永久连结

每个DOI号前面加上「 http://dx.doi.org/ 」便成为永久网址。
如以DOI号为 10.5297/ser.1201.002 的文献为例，此文献的永久连结便是： http://dx.doi.org/ 10.5297/ser.1201.002 。
日后不论出版单位如何更动此文献位置，永久连结所指向的位置皆会即时更新，不再错失重要的研究。

引用含有DOI的文献

有DOI的文献在引用时皆应同时引用DOI。若使用APA、Chicago以外未规范DOI的引用格式，可引用DOI永久连结。

DOI可强化引用精确性、增强学术圈连结，并给予使用者跨平台的良好使用经验，目前在全世界已有超过五千万个对象申请DOI。如想对DOI的使用与概念有进一步了解，请参考（）。

书目管理工具

相关连结

问题回报

全文下载

考量资源扩增取舍之多核心即时系统排程

Many-Core Real-Time Task Scheduling with Resource Augmentation Trade-off Considerations

郑圣威 , 博士　　导师：郭大维　　共同指导教授：陈建佳

英文 DOI： 10.6342/NTU201700250

即时系统；分群多核心平台；可程式化运算核心；同时考量记忆体分配与工作排程；资源扩充；近似演算法； Real-Time System ； Many-Core Island-Based Platform ； Reconfigurable Processor ； Joint Memory Allocation and Task Scheduling ； Resource Augmentation ； Approximation Algorithm

0 个人觉得这篇文章赞

摘要 │ 参考文献 (66) │ 国际计量

并列摘要〈TOP〉

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.

参考文献 ( 66 ) 〈TOP〉

[2] T. P. Baker. Stack-based Scheduling for Real time Processes. Real-Time System,pages 67–99, 1991.
连结：
[3] F. Barat and R. Lauwereins. Reconfigurable instruction set processors: a survey. In RSP, 2000.
连结：
[4] S. Baruah and N. Fisher. A Dynamic Programming Approach to Task Partitioning upon Memory-constrained Multiprocessors. In Proc. of IEEE RTCSA, 2004.
连结：
[5] S. Baruah and N. Fisher. The Partitioned Multiprocessor Scheduling of Sporadic Task Systems. In Proc. of IEEE RTSS, pages 321–329, 2005.
连结：
[6] Sanjoy K Baruah, Aloysius K Mok, and Louis E Rosier. Preemptively scheduling hard-real-time sporadic tasks on one processor. In Real-Time Systems Symposium, 1990. Proceedings., 11th, pages 182–190. IEEE, 1990.
连结：

国际计量

〈TOP〉

E-mail ：

文章公开取用时，将寄通知信至您填写的信箱地址

E-mail ：

使用DOI作为永久连结

引用含有DOI的文献

DOI可强化引用精确性、增强学术圈连结，并给予使用者跨平台的良好使用经验，目前在全世界已有超过五千万个对象申请DOI。 如想对DOI的使用与概念有进一步了解，请参考 （ ） 。

DOI可强化引用精确性、增强学术圈连结，并给予使用者跨平台的良好使用经验，目前在全世界已有超过五千万个对象申请DOI。如想对DOI的使用与概念有进一步了解，请参考（）。