|
|
论文:2012,Vol:30,Issue(5):652-656 |
|
|
引用本文： |
|
|
黄姝娟, 朱怡安. 基于并行优先级任务树的多核调度方法研究[J]. 西北工业大学 |
|
|
Huang Shujuan, Zhu Yi'an. Improving Multi-Core Scheduling Method through Using PPTT (Parallel Priority Task Tree) Model[J]. Northwestern polytechnical university |
|
|
|
|
|
|
|
| 基于并行优先级任务树的多核调度方法研究 |
|
| 黄姝娟1,2, 朱怡安1,2 |
|
1. 西北工业大学 计算机学院, 陕西 西安 710072;
2. 西北工业大学 软件与微电子学院, 陕西 西安 710072 |
| 摘要: |
| 文章针对具有复杂依赖关系的实时周期任务难以调度的问题,提出了一种模型转化方法,该方法将具有复杂关系的实时结点任务图转化为并行优先级任务树,然后根据模型中定义的优先关系并结合EDF(Earliest Deadline First)算法,将任务调度到相应的核上去执行。仿真试验表明,该方法比核与任务相对应的分配方法不仅可以提高CPU利用率而且大大减少了核间通信的开销。 |
| 关键词:
并行优先级任务树
有向无环图
多核
实时任务
|
|
| Improving Multi-Core Scheduling Method through Using PPTT (Parallel Priority Task Tree) Model |
|
| Huang Shujuan1,2, Zhu Yi'an1,2 |
|
1. Department of Computer Science and Engineering, Northwestern Polytechnical University, Xi'an 710072 China;
2. Department of Software Engineering, Northwestern Polytechnical University, Xi'an 710072 China |
| Abstract: |
| Sections 1 through 4 of the full paper explain and evaluate the improvement mentioned in the title.Thecore of our thinking and that of sections 1 through 4 consists of: (1)past research papers on the multi-core schedu-ling model only focus on the independent tasks or the dependent tasks that are not real-time tasks; we propose anew scheduling model PPTT which can study the mutually dependent real-time tasks; it can ensure the satisfactionof the dependence relationship between any two tasks and can work together with the EDF(Earliest Deadline First)algorithm to schedule these real-time tasks running on the corresponding cores; (2) section 1 is entitled"Schedu-ling Algorithm Based on PPTT Mathematical Model" ; (3) section 2 is entitled "Establishing Priority Relation-ship" ; (4) section 3 in entitled"Allocating Algorithm of Multiprocessor" ; (5) simulation results, presented in Fig.4, and their analysis show preliminarily that the model and algorithm presented in this paper are indeed effec-tive and the core has indeed a higher utilization. |
| Key words:
algorithms
computer simulation
control
design
efficiency
embedded systems
flowcharting
math-ematical models
multiprocessing systems
multitasking
real time systems
resource allocation
scheduling
synchronization;directed acyclic graph (DAG)
multi-core
parallel priority task tree(PPTT)
|
|
| 收稿日期: 2011-10-20
修回日期:
|
| DOI: |
| 基金项目: 航空科学基金(20100753022);航天科技创新基金(2011XR160001);西北工业大学基础研究基金(JC201102837)资助 |
| 通讯作者:
Email： |
| 作者简介: 黄姝娟(1975-)，女，西北工业大学讲师，主要从事嵌入式与普适计算研究。
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] Cong L,Anderson J H.Supporting Pipelines in Soft Real-Time Multiprocessor Systems.ECRTS'09.21st Euromicro Conferenceon,Real-Time Systems,2009,269-278
[2] 李仁发等.多处理器片上系统任务调度研究进展评述.计算机研究与发展,2008,45(9): 1620-1629Li Renfa,et al.A Survey of Task Scheduling Research Progress on Multiprocessor System-on-Chip.Journal of Computer Re-search and Development,2008,45(9): 1620-1629 (in Chinese)
[3] Mills A F,Anderson J H.A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling.Real-Time and EmbeddedTechnology and Applications Symposium (RTAS),2010,10: 311-320
[4] Liu C L,Layland J W.Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment.Journal of the Associa-tion for Computing Machinery,1973,20: 46-61
[5] Bozdag D,et al.Compaction of Schedules and a Two-Stage Approach for Duplication-Based DAG Scheduling.IEEE Trans onParallel and Distributed Systems,2009,20: 857-871 |
|
|
|
|
|
|
|
