Two level preemptive global fixed priority DAG recursive scheduling for multi-core platforms

LUO Liang

Chinese

您当前的位置：

首页 >

文章列表页 >

Two level preemptive global fixed priority DAG recursive scheduling for multi-core platforms

更新时间：2026-09-04

- Two level preemptive global fixed priority DAG recursive scheduling for multi-core platforms
- Vol. 37, Issue 4, Pages: 70-75(2020)
- 作者机构：
  
  广西大学计算机与电子信息学院,广西,南宁,530004
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2020
- 稿件说明：
移动端阅览
骆亮. 多核平台两级抢占式固定优先级DAG递归调度[J]. 微电子学与计算机, 2020, 37(4): 70-75.

LUO Liang. Two level preemptive global fixed priority DAG recursive scheduling for multi-core platforms[J]. 2020, 37(4): 70-75.
骆亮. 多核平台两级抢占式固定优先级DAG递归调度[J]. 微电子学与计算机, 2020, 37(4): 70-75. DOI：

LUO Liang. Two level preemptive global fixed priority DAG recursive scheduling for multi-core platforms[J]. 2020, 37(4): 70-75. DOI：

摘要

为提高应用程序调度实时性，提高程序调度应用价值，采用有向无环图(DAG)建立多核平台上的并行和递归任务的集合，获得具有优先级约束(即有向边)的子任务(即节点)，并保证在某个指定的截止日期之前完成其所有子任务的执行.每个任务都可能生成无限数量的实例，其中连续实例的发布被一些最小到达时间隔开.同时，DAG任务的每个子任务被分配一个固定优先级，提出一种两级抢占式全局固定优先级调度(GFP)策略：任务级调度器首先确定最高优先级就绪任务，然后，子任务级调度器选择其最高优先级子任务来执行.然后，为所提两级GFP调度器推导出一个可调度性测试，如果满足该测试则保证所有任务在GFP下满足其最后期限.最后，通过实验分析，验证了所提算法在接受率指标上的性能优势.

Abstract

For real-time application scheduling

directed acyclic graph (DAG) is used to set up a set of parallel and recursive tasks on multi-core platforms to obtain sub-tasks (i.e. nodes) with priority constraints (i.e. directed edges) and to ensure that all the sub-tasks are executed before a specified deadline. Each task may generate an unlimited number of instances

in which the publication of successive instances is separated by some minimum arrival time. At the same time

each sub-task of the DAG task is assigned a fixed priority. A two-level preemptive global fixed priority scheduling (GFP) strategy is proposed. The task-level scheduler first determines the highest priority ready task

and then the sub-task-level scheduler selects its highest priority sub-task to execute. The sub task level scheduler then selects its highest priority sub task to perform. Then

a schedulability test is derived for the proposed two-level GFP scheduler

which guarantees that all tasks meet their deadlines under GFP. Finally

through experimental analysis

the performance advantage of the proposed algorithm on acceptance rate index is verified.

关键词

Keywords

references

WANG Y, LI K L, LI K Q. Partition Scheduling on Heterogeneous Multicore Processors for Multi-dimensional Loops Applications[J]. International Journal of Parallel Programming, 2017, 45(4): 827-852. DOI: 827

ZHOU Z, WILLIAM P, SHUVRA S B, et al. Scheduling of Parallelized Synchronous Dataflow Actors for Multicore Signal Processing[J]. Journal of Signal Processing Systems, 2016, 83(3): 309-328. DOI: 309

SANDRA C, FRANCISCO D I, RAFAEL M, et al. Architecture-aware configuration and scheduling of matrix multiplication on asymmetric multicore processors[J]. Cluster Computing, 2016, 19(3): 1037-1051. DOI: 1037

UMARANI S G, GEETHA R. Task scheduling using Ant Colony Optimization in multicore architectures: a survey[J]. Soft Computing, 2018, 22(15): 5179-5196. DOI: 5179

NAMHOON K, BRYAN C W, MICAIAH C, et al. Attacking the one-out-of-m multicore problem by combining hardware management with mixed-criticality provisioning[J]. Real-Time Systems, 2017, 53(5): 709-759. DOI: 709

ARASH D, MAHMOUD N, SAEID A. CCA: a deadline-constrained workflow scheduling algorithm for multicore resources on the cloud[J]. The Journal of Supercomputing, 2017, 73(2): 756-781. DOI: 756

RYAN J, IPPOKRATIS P, RADU S, et al. Scalability of write-ahead logging on multicore and multisocket hardware[J]. The VLDB Journal, 2012, 21(2): 239-263. DOI: 239

GEORGE F Z, WILLIAM PLISHKER, SHUVRA S BHATTACHARYYA, et al. Implementation, Scheduling, and Adaptation of Partial Expansion Graphs on Multicore Platforms[J]. Journal of Signal Processing Systems, 2017, 87(1): 107-125. DOI: 107

RISAT M P. Real-time scheduling algorithm for safety-critical systems on faulty multicore environments[J]. Real-Time Systems, 2017, 53(1): 45-81. DOI: 45

刘德儿, 熊证, 沈敬伟, 等.完全拓扑关系结构D-TIN多核并行构建[J].计算机辅助设计与图形学学报, 2016, 28(6): 950-959. DOI: 950

亢良伊, 王建飞, 刘杰, 等.可扩展机器学习的并行与分布式优化算法综述[J].软件学报, 2018, 29(1): 109-130. DOI: 109

RAFAEL R S, ENRIQUE S Q. Architecture-aware optimization of an HEVC decoder on asymmetric multicore processors[J]. Journal of Real-Time Image Processing, 2017, 13(1): 25-38. DOI: 25

于俊清, 张维维, 陈文斌, 等.面向多核集群的数据流程序层次流水线并行优化方法[J].计算机学报, 2014, 37(10): 2071-2083. DOI: 2071

刘松, 伍卫国, 赵博, 等.面向局部性和并行优化的循环分块技术[J].计算机研究与发展, 2015, 52(5): 1160-1176. DOI: 1160

ANURADHA P, HEMALATHA R, NARSIMHA G. Energy efficient scheduling algorithm for the multicore heterogeneous embedded architectures[J]. Design Automation for Embedded Systems, 2018, 22(2): 1-12. DOI: 1

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

High gain stability high temperature operational amplifier based on reverse body bias

Research on assembly action recognition based on MSS-YOLO-MPHands fusion architecture

Simulation on the DC characteristics of double heterojunction p-GaN HEMT with AlN/GaN hybrid buffer layer

Aerial small object detection algorithm based on improved RT-DETR

Steganography model guided by attention mechanism and improved dense convolution

Related Author

No data

Related Institution

No data

AI问答

Postal code：100079
Tel：（010）53879206 Email：tmw@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09082226号-64 京公网安备11010602201714号
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰