多核平台两级抢占式固定优先级DAG递归调度

骆亮

Chinese

您当前的位置：

首页 >

文章列表页 >

多核平台两级抢占式固定优先级DAG递归调度

更新时间：2026-09-04

- 多核平台两级抢占式固定优先级DAG递归调度
- Two level preemptive global fixed priority DAG recursive scheduling for multi-core platforms
- 微电子学与计算机 2020年37卷第4期页码：70-75
- 作者机构：
  
  广西大学计算机与电子信息学院,广西,南宁,530004
- 作者简介：
- 基金信息：
  
  国家自然科学基金项目 61363025广西省自然科学基金项目 2015B036
- DOI：
  中图分类号：
- 纸质出版：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

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

V型沟槽SiC中子探测器的蒙特卡洛分析

面向处理器分支预测单元的Spectre攻击轻量化防御方法

一种基于特征上下文理解与切片分析的肺结核检测算法

基于改进RT-DETR的航拍小目标检测算法

基于区块链的AI生成内容溯源框架设计研究