基于G-EDF的DAG并行任务多核响应时间分析

doi:10.12068/j.issn.1005-3026.2019.03.003

东北大学学报:自然科学版 ›› 2019, Vol. 40 ›› Issue (3): 315-320.DOI: 10.12068/j.issn.1005-3026.2019.03.003

基于G-EDF的DAG并行任务多核响应时间分析

韩美灵，邓庆绪，张天宇，林宇晗

(东北大学计算机科学与工程学院，辽宁沈阳110169)

收稿日期:2018-01-22 修回日期:2018-01-22 出版日期:2019-03-15 发布日期:2019-03-08
通讯作者: 韩美灵
作者简介:韩美灵(1988-)，女，山东聊城人，东北大学博士研究生; 邓庆绪(1970-)，男，河南南阳人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(61472072，61528202); 辽宁重大装备制造协同创新中心资助项目.

Response Time Analysis of Multiprocessor Systems for DAG Parallel Tasks Based on G-EDF

HAN Mei-ling， DENG Qing-xu， ZHANG Tian-yu， LIN Yu-han

School of Computer Science & Engineering， Northeastern University， Shenyang 110169， China.

Received:2018-01-22 Revised:2018-01-22 Online:2019-03-15 Published:2019-03-08
Contact: DENG Qing-xu
About author:-
Supported by:
-

摘要/Abstract

摘要： 由于未考虑DAG(directed acyclic graph)任务的自身结构，基于G-EDF(global earliest deadline first)的DAG并行任务模型的可调度性分析存在很大的悲观性，因此本文针对DAG任务集在多处理器系统中采用G-EDF调度策略下的响应时间分析进行了研究.首先针对carry-in任务实例执行的情况提出更加精确的carry-in工作量估算方法.基于该carry-in工作量估算方法提出一种基于完成时间的问题窗口工作量估算方法.最后，结合上述两个改进策略提出了基于G-EDF的DAG任务响应时间分析方法.仿真实验表明，所提出的方法较目前已知的调度策略方法可调度性至少提高15%，最高可达25%.

关键词: 嵌入式实时系统, 多核处理器, 并行任务模型, 全局调度, 响应时间分析

Abstract: Since the self-structure of the DAG(directed acyclic graph)task is not considered， the schedulability analysis of the DAG parallel task model based on G-EDF(global earliest deadline first)is very pessimistic. The response time analysis of the DAG task set under the G-EDF scheduling strategy in multiprocessor systems was studied in this paper. First， a more accurate carry-in workload estimation method was proposed for the execution of the carry-in task instance. Then a method for estimating the problem window workload of completion time was put forward based on the carry-in workload estimation method. Based on the two proposed methods， this paper proposed a response time analyzing method to derive a response time upper bound of each task. The experiments show that the proposed method outperforms the state-of-the-art method by at least 15% and at most 25%.

Key words: embedded real-time systems, multiprocessors, parallel tasks model, global scheduling, response time analysis

中图分类号:

TP316.2

韩美灵，邓庆绪，张天宇，林宇晗. 基于G-EDF的DAG并行任务多核响应时间分析[J]. 东北大学学报:自然科学版, 2019, 40(3): 315-320.

HAN Mei-ling， DENG Qing-xu， ZHANG Tian-yu， LIN Yu-han. Response Time Analysis of Multiprocessor Systems for DAG Parallel Tasks Based on G-EDF[J]. Journal of Northeastern University Natural Science, 2019, 40(3): 315-320.

参考文献

[1]Intel.Intel Xeon Phi product family ［DB/OL］.(2013-07-03)［2017-06-20］.http://www.intel.com/content/www/us/en/processors/xeon/xeon-phi-detail.html，2018.
[2]Lakshmanan K，Kato S，Rajkumar R.Scheduling parallel real-time tasks on multi-core processors［C］// IEEE Real-Time Systems Symposium.San Diego:IEEE Computer Society，2010:259-268.
[3]Saifullah A，Agrawal K，Lu C，et al.Multi-core real-time scheduling for generalized parallel task models［C］// Real-Time Systems Symposium.San Juan:IEEE，2012:217-226.
[4]Chwa H S，Lee J，Phan K M，et al.Global EDF schedulability analysis for synchronous parallel tasks on multicore platforms［C］// Euromicro Conference on Real-Time Systems.Paris:IEEE Computer Society，2013:25-34.
[5]Cláudio M，Bertogna M，Pinho L M.Response-time analysis of synchronous parallel tasks in multiprocessor systems［C］// International Conference on Real-Time Networks and Systems.Versailles:ACM，2014:3-12.
[6]Nelissen G，Berten V，Milojevic D.Techniques optimizing the number of processors to schedule multi-threaded tasks［C］// Euromicro Conference on Real-Time Systems.Pisa:IEEE Computer Society，2012:321-330.
[7]Axer P，Quinton S，Neukirchner M，et al.Response-time analysis of parallel fork-join workloads with real-time constraints［C］// Euromicro Conference on Real-Time Systems.Paris:IEEE Computer Society，2013:215-224.
[8]Li J，Agrawal K，Lu C，et al.Analysis of global EDF for parallel tasks［C］// Euromicro Conference on Real-Time Systems.Paris:IEEE Computer Society，2013:3-13.
[9]Bonifaci V，Marchetti-Spaccamela A，Stiller S，et al.Feasibility analysis in the sporadic DAG task model［C］// Real-Time Systems.Vancouver:IEEE，2013:225-233.
[10]Baruah S，Bonifaci V，Marchettispaccamela A，et al.A for recurrent real-time processes［C］// Real-Time Systems Symposium.San Juan:IEEE Computer Society，2012:63-72.
[11]Li J，Chen J J，Agrawal K，et al.Analysis of federated and global scheduling for parallel real-time tasks［C］// Euromicro Conference on Real-Time Systems.Madrid:IEEE Computer Society，2014:85-96.
[12]Chwa H S，Lee J，Lee J，et al.Global EDF schedulability analysis for parallel tasks on multi-core platforms［J］.IEEE Transactions on Parallel & Distributed Systems，2017，28(5):1331-1345.
[13]Cordeiro D，Mounié G，Perarnau S，et al.Random graph generation for scheduling simulations［C］//Proceedings of the 3rd International ICST Conference on Simulation Tools and Techniques.Torremolinos:ICST(Institute for Computer Sciences，Social-Informatics and Telecommunications Engineering)，2010:60-71.

基于G-EDF的DAG并行任务多核响应时间分析

Response Time Analysis of Multiprocessor Systems for DAG Parallel Tasks Based on G-EDF

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	周本海;乔建忠;林树宽;. 多核平台的并行实时调度与内存分配算法[J]. 东北大学学报(自然科学版), 2012, 33(3): 357-360+376.
[2]	刘铮;赵海;李强;张骞;. 嵌入式实时系统中抢占控制策略及其优化[J]. 东北大学学报(自然科学版), 2009, 30(6): 813-816.