有向无环图(DAG)架构在影视特效与后期制作中的应用研究 被引量：1

1

作者 王璇 周辉 《现代电影技术》 2025年第4期13-19,共7页

针对影视特效与后期制作中传统工作流因依赖关系复杂化导致的效率低下问题,本研究探讨了有向无环图(DAG)架构的核心特性及其在任务调度与计算优化中的应用价值,并提出一种跨软件的全流程统一任务调度框架,以解决行业协作与资源管理的关... 针对影视特效与后期制作中传统工作流因依赖关系复杂化导致的效率低下问题,本研究探讨了有向无环图(DAG)架构的核心特性及其在任务调度与计算优化中的应用价值,并提出一种跨软件的全流程统一任务调度框架,以解决行业协作与资源管理的关键瓶颈。通过分析Houdini、Maya、Nuke等主流数字内容创作(DCC)软件的DAG架构,研究其在任务调度、并行计算与动态扩展方面的实现方式,并结合影视制作全流程需求,设计基于DAG的统一框架,涉及通用数据标准、全局任务调度引擎与资源库等,同时采用Kahn算法实现拓扑排序与动态依赖管理。总体而言,DAG架构凭借其无环依赖、拓扑排序与动态扩展能力,为影视制作提供了高效的任务调度与计算优化方案,未来仍需进一步解决跨软件兼容性与标准化问题,并结合AI与云原生技术,最终实现全流程自动化,为影视工业化发展提供技术支撑。 展开更多

关键词 有向无环图(dag) 影视特效 后期制作 全局任务调度 动态依赖管理

在线阅读 下载PDF 职称材料

一种基于模糊聚类的网格DAG任务图调度算法 被引量：49

2

作者 杜晓丽 蒋昌俊 +1 位作者 徐国荣 丁志军 《软件学报》 EI CSCD 北大核心 2006年第11期2277-2288,共12页

针对网格环境中,任务调度的目标系统具有规模庞大、分布异构和动态性等特点,提出一种基于模糊聚类的网格异构任务调度算法.以往的很多调度算法需要在调度的每一步遍历整个目标系统,虽然能够获得较小的makespan,但是无疑增加了整个调度的... 针对网格环境中,任务调度的目标系统具有规模庞大、分布异构和动态性等特点,提出一种基于模糊聚类的网格异构任务调度算法.以往的很多调度算法需要在调度的每一步遍历整个目标系统,虽然能够获得较小的makespan,但是无疑增加了整个调度的Runtime.定义了一组刻画处理单元综合性能的特征,利用模糊聚类方法对目标系统(处理单元网络)进行预处理,实现了对处理单元网络的合理划分,使得在任务调度时能够较准确地优先选择综合性能较好的处理单元聚类,从而缩小搜索空间,大量减少任务调度时选择处理单元的时间耗费.此外,就绪任务优先级的构造既隐含考虑了关键路径上节点的执行情况对整个程序执行的影响,又考虑了异构资源对任务执行的影响.实验及性能分析比较的结果表明,定义的处理器特征能够实现对处理器网络的合理划分,而且随着目标系统规模的增大,所提出的算法优越性越来越明显. 展开更多

关键词 网格 dag(direct ACYCLIC grapb) 任务调度 模糊聚类 异构计算环境

在线阅读 下载PDF 职称材料

一种基于DAG图的异构可重构任务划分方法 被引量：4

3

作者 郝水侠 曾国荪 谭一鸣 《同济大学学报（自然科学版）》 EI CAS CSCD 北大核心 2011年第11期1693-1698,共6页

为了实现高性能低功耗的计算,以任务划分为研究对象,提出了异构可重构计算的基本概念和形式化描述方法,给出了基于异构计算任务和异构可重构体系结构相结合的异构可重构两种任务划分方法:节点内部可重组及网络可重建的任务划分及算法,... 为了实现高性能低功耗的计算,以任务划分为研究对象,提出了异构可重构计算的基本概念和形式化描述方法,给出了基于异构计算任务和异构可重构体系结构相结合的异构可重构两种任务划分方法:节点内部可重组及网络可重建的任务划分及算法,最后验证了其任务划分方法的有效性. 展开更多

关键词 有向无环图(dag) 异构计算任务 可重构体系结构 任务划分

在线阅读 下载PDF 职称材料

基于DAG图的自适应代码划分优化算法 被引量：1

4

作者 周静 曾国荪 《计算机工程》 CAS CSCD 北大核心 2007年第20期15-17,共3页

并行编译的两大工作是程序代码划分和调度。对于调度问题,目前已有大量的解决方案,但是针对代码划分提取并行性的研究工作却非常少。该文提出了通过合并结点来划分DAG图的新的划分算法。实例分析证明,该算法是一种有效的、低复杂度的自... 并行编译的两大工作是程序代码划分和调度。对于调度问题,目前已有大量的解决方案,但是针对代码划分提取并行性的研究工作却非常少。该文提出了通过合并结点来划分DAG图的新的划分算法。实例分析证明,该算法是一种有效的、低复杂度的自适应代码划分解决方案,并且适用于异构计算的任务图划分。 展开更多

关键词 并行编译 有向无环图 代码划分 任务合并 关键路径

在线阅读 下载PDF 职称材料

基于DAG图解-重构的机群系统静态调度算法 被引量：7

5

作者 周佳祥 郑纬民 《软件学报》 EI CSCD 北大核心 2000年第8期1097-1104,共8页

机群系统静态任务调度是 NP-完全问题 ,通常的算法是通过一些启发式算法得到多项式次优解 .该文提出的图解 -子图重构算法实现了对分布在有向无环图 (directed acyclic graph,简称 DAG)上的并行任务的快速有效调度 .该算法的复杂性为 O(... 机群系统静态任务调度是 NP-完全问题 ,通常的算法是通过一些启发式算法得到多项式次优解 .该文提出的图解 -子图重构算法实现了对分布在有向无环图 (directed acyclic graph,简称 DAG)上的并行任务的快速有效调度 .该算法的复杂性为 O(log| V| × (|V|+|E|) ) ,采用递归方法实现了对任务图的有效分解和子图重构 ,生成任务群 ,完成任务调度 ,并且初步实现了对处理机的优化 .通过实例分析以及与其他启发式调度算法的性能比较 ,证明该算法是一种快速、有效、可行的任务调度算法 . 展开更多

关键词 机群系统 图解-子图重构算法 静态调度算法 dag

在线阅读 下载PDF 职称材料

基于ILS-PSO算法的移动云计算DAG图的任务调度研究与应用 被引量：3

6

作者 董韵 张毅 孙晋 《计算机与数字工程》 2020年第3期575-580,595,共7页

移动云计算已经深入到人们工作和生活的各个方面,同时也对移动设备的续航时间、计算能力,存储容量和安全性提出了更高的要求。移动云计算网络中的移动设备由于资源有限、通信受限,无法满足复杂应用的要求。为了解决移动云计算环境下复... 移动云计算已经深入到人们工作和生活的各个方面,同时也对移动设备的续航时间、计算能力,存储容量和安全性提出了更高的要求。移动云计算网络中的移动设备由于资源有限、通信受限,无法满足复杂应用的要求。为了解决移动云计算环境下复杂应用的有效使用问题,对移动设备网络和DAG任务图进行深入研究,将复杂应用分解成多个不相交的集合分配给移动设备并行执行,满足移动设备电池容量的约束下,提出了粒子群优化(PSO)算法求解最优调度方案的方法,并且应用迭代局部搜索(ILS)策略,保证了全局和局部搜索的平衡。 展开更多

关键词 移动云计算 移动设备 dag任务图 粒子群优化 迭代局部搜索 搜索平衡

在线阅读 下载PDF 职称材料

分布式系统下的启发式任务调度算法 被引量：12

7

作者 贾丽云 张向利 张红梅 《计算机工程与应用》 CSCD 北大核心 2017年第12期63-69,共7页

为了提升异构分布式环境下处理具有依赖关系的任务的性能,提出一种基于关键任务和处理器选择参数的启发式任务调度算法(HCNPSV)。该算法结合表调度和任务复制调度的思想,改进了关键任务的计算方法,并按照是否为关键任务、上行权重值递... 为了提升异构分布式环境下处理具有依赖关系的任务的性能,提出一种基于关键任务和处理器选择参数的启发式任务调度算法(HCNPSV)。该算法结合表调度和任务复制调度的思想,改进了关键任务的计算方法,并按照是否为关键任务、上行权重值递减、关联任务数递增的顺序获得调度序列,资源选择阶段综合考虑了任务的最早完成时间和到出口节点的最短距离,最后将任务调度到处理器选择参数最小的资源上执行。实验结果表明,HCNPSV有效地提高了系统的调度性能。 展开更多

关键词 分布式系统 静态任务调度 有向无环图 关键任务 任务复制

在线阅读 下载PDF 职称材料

处理顺序约束的信息物理融合系统静态任务表调度算法 被引量：7

8

作者 王小乐 黄宏斌 邓苏 《自动化学报》 EI CSCD 北大核心 2012年第11期1870-1879,共10页

针对异构环境并行计算的静态任务调度问题,以最小化有向无环图(Directed acyclic graph,DAG)的执行跨度为目标,改变HEFT(Heterogeneous earliest finish time)算法中任务上行权重的计算方法,获得更加合理的任务顺序排列,提出了一种最早... 针对异构环境并行计算的静态任务调度问题,以最小化有向无环图(Directed acyclic graph,DAG)的执行跨度为目标,改变HEFT(Heterogeneous earliest finish time)算法中任务上行权重的计算方法,获得更加合理的任务顺序排列,提出了一种最早完成时间优先的表调度算法IHEFT(Improvement heterogeneous earliest finish time).该算法在计算任务的上行权重时,分别计算该任务分配给不同资源的上行权重,取其最小值,比使用所有资源对该任务的平均处理时间进行计算的HEFT算法更为准确.确定任务的处理顺序后采用最早完成时间越小越优先的策略将任务分配给最优资源,并使得任务的开始执行时间和结束时间满足DAG中有向边的通讯时间约束.通过使用部分文献中的算例数据以及随机生成满足一定结构要求的DAG进行算法测试,将IHEFT与HEFT,CPOP(Critical-path-on-a-processor)和LDCP(Longest dynamic critical path)进行了比较,结果显示IHEFT算法更有效,而且时间复杂度较低. 展开更多

关键词 异构计算环境 信息物理融合系统 有向无环图 任务调度 表调度 静态任务

在线阅读 下载PDF 职称材料

基于超立方体的静态任务调度 被引量：1

9

作者 章军 冯秀山 韩承德 《软件学报》 EI CSCD 北大核心 1999年第12期1275-1278,共4页

该文给出一个基于超立方体的静态任务调度算法 .在算法的设计中 ,首先建立了任务优先级表和处理机优先级表 ,任务在调度时总是顺次调度高优先级任务 ,然后再从处理机优先级表中选择能使该任务最早开始执行的处理机 .最后 ,分别给出了基... 该文给出一个基于超立方体的静态任务调度算法 .在算法的设计中 ,首先建立了任务优先级表和处理机优先级表 ,任务在调度时总是顺次调度高优先级任务 ,然后再从处理机优先级表中选择能使该任务最早开始执行的处理机 .最后 ,分别给出了基于 LU分解的任务图与随机生成的任务图的调度结果 . 展开更多

关键词 静态任务调度 超立方体 多处理机 算法

在线阅读 下载PDF 职称材料

网格任务调度方法研究 被引量：3

10

作者 贺敏伟 李贵海 +2 位作者 扶卿妮 李绍华 林健 《计算机工程与应用》 CSCD 北大核心 2009年第10期123-126,共4页

网格计算中的关键问题之一是计算任务在各个资源之间的调度。提出了基于量子遗传算法(QGA)的网格任务调度算法,以减少调度时间为主要目标,增加资源利用率为次要目标。该算法采用量子比特间接编码的方式,通过有向无环图(DAG)来描述子任... 网格计算中的关键问题之一是计算任务在各个资源之间的调度。提出了基于量子遗传算法(QGA)的网格任务调度算法,以减少调度时间为主要目标,增加资源利用率为次要目标。该算法采用量子比特间接编码的方式,通过有向无环图(DAG)来描述子任务间的依赖关系,根据深度值来给子任务的执行顺序进行排序。仿真结果显示,无论是任务完成时间还是资源利用率,此方法都明显优于基于遗传算法(GA)的网格调度算法。 展开更多

关键词 网格计算 任务调度 量子遗传算法 有向无环图

在线阅读 下载PDF 职称材料

云计算环境下基于路径优先级的任务调度算法 被引量：9

11

作者 祝家钰 肖丹 《计算机工程与设计》 CSCD 北大核心 2013年第10期3511-3515,共5页

为了最小化云计算系统的任务调度长度,结合表启发式调度技术和任务复制的思想提出基于路径优先权的任务调度算法。采用一种新方法计算DAG图中任务节点及边的权值,从最高优先权的路径开始依次选择任务进行调度,并通过有选择性地复制任务... 为了最小化云计算系统的任务调度长度,结合表启发式调度技术和任务复制的思想提出基于路径优先权的任务调度算法。采用一种新方法计算DAG图中任务节点及边的权值,从最高优先权的路径开始依次选择任务进行调度,并通过有选择性地复制任务节点的父任务来减少任务间信息传送的时间花费,最后将任务安排到使其执行完成时间最早的虚拟机上。通过随机产生的DAG图与HEFT算法进行对比分析,实验结果表明了该算法能获得较短的调度长度。 展开更多

关键词 云计算 异构系统 表启发式调度 有向无环图 路径优先级 任务复制

在线阅读 下载PDF 职称材料

移动网格关联任务调度研究

12

作者 鞠宏军 杜丽娟 《计算机工程与科学》 CSCD 北大核心 2013年第6期57-64,共8页

以移动网格为背景,研究关联任务在动态资源环境下的调度问题,既考虑任务之间的依赖关系,还考虑资源动态加入、离开、性能变化等行为。提出子集调度加重调度的动态调度策略。动态子集划分考虑了任务之间的依赖关系,并有利于减少重调度次... 以移动网格为背景,研究关联任务在动态资源环境下的调度问题,既考虑任务之间的依赖关系,还考虑资源动态加入、离开、性能变化等行为。提出子集调度加重调度的动态调度策略。动态子集划分考虑了任务之间的依赖关系,并有利于减少重调度次数。阐述了子集调度目标和约束条件,提出了融合模拟退火思想的粒子群调度算法。重调度进一步提高调度策略对资源动态行为的适应性,阐述了重调度触发条件。给出了移动网格关联任务调度策略的完整流程,并对提出的算法进行了复杂性分析和实验分析。实验结果表明了调度策略和算法的有效性。 展开更多

关键词 移动网格 任务调度 动态资源 dag图 重调度

在线阅读 下载PDF 职称材料

移动网格中依赖性任务调度

13

作者 鞠宏军 杜丽娟 《微电子学与计算机》 CSCD 北大核心 2013年第4期1-4,9,共5页

本文研究移动网格环境下的依赖性任务调度问题,提出预调度加重调度的动态调度策略.预调度利用改进的HEFT算法将所有任务映射到当前可用资源,目标是总完成时间最短,同时考虑了资源的能量约束条件.任务运行过程中监测资源的各种异常行为,... 本文研究移动网格环境下的依赖性任务调度问题,提出预调度加重调度的动态调度策略.预调度利用改进的HEFT算法将所有任务映射到当前可用资源,目标是总完成时间最短,同时考虑了资源的能量约束条件.任务运行过程中监测资源的各种异常行为,当满足重调度触发条件时进行重调度,从而实现对动态环境的自适应性.通过实例分析表明了调度策略的有效性. 展开更多

关键词 移动网格 任务调度 动态资源 dag图 重调度

在线阅读 下载PDF 职称材料

一种基于异构系统的实时调度算法研究

14

作者 郑小长 杨红和 《邵阳学院学报（自然科学版）》 2016年第2期36-40,共5页

高效调度是异构系统中实现高性能计算的关键.调度问题已经被证明是NP完全问题,由于其关键性,调度问题已经被国内外研究机构广泛研究,并提出了多种算法.尽管在一些文献中提出了异构多处理器的调度算法,但是这些算法的调度成本较高,并且... 高效调度是异构系统中实现高性能计算的关键.调度问题已经被证明是NP完全问题,由于其关键性,调度问题已经被国内外研究机构广泛研究,并提出了多种算法.尽管在一些文献中提出了异构多处理器的调度算法,但是这些算法的调度成本较高,并且在较低的调度成本下无法提供高质量的调度.本文提出一种最小评分优先算法(HMSF),该算法是一种适用于异构系统的高性能、快速调度算法,通过和传统的HEFT算法和DLS算法进行试验对比发现,HMSF算法可以使调度长度更短. 展开更多

关键词 异构系统 实时调度 dag调度 任务图 调度长度

在线阅读 下载PDF 职称材料

基于并行优先级任务树的多核调度方法研究 被引量：3

15

作者 黄姝娟 朱怡安 《西北工业大学学报》 EI CAS CSCD 北大核心 2012年第5期652-656,共5页

文章针对具有复杂依赖关系的实时周期任务难以调度的问题,提出了一种模型转化方法,该方法将具有复杂关系的实时结点任务图转化为并行优先级任务树,然后根据模型中定义的优先关系并结合EDF(Earliest Deadline First)算法,将任务调度到相... 文章针对具有复杂依赖关系的实时周期任务难以调度的问题,提出了一种模型转化方法,该方法将具有复杂关系的实时结点任务图转化为并行优先级任务树,然后根据模型中定义的优先关系并结合EDF(Earliest Deadline First)算法,将任务调度到相应的核上去执行。仿真试验表明,该方法比核与任务相对应的分配方法不仅可以提高CPU利用率而且大大减少了核间通信的开销。 展开更多

关键词 并行优先级任务树 有向无环图 多核 实时任务

在线阅读 下载PDF 职称材料

云计算环境下任务调度的趋势分析

16

作者 梁桂才 《计算机应用》 CSCD 北大核心 2014年第A02期70-72,77,共4页

云计算应用大规模和虚拟化的资源,通过计算机网络随时随地向用户提供基于不同需求的服务。作为影响云服务的关键因素,任务调度被许多专家学者所研究。研究了云计算中的任务调度算法的新特性,如何降低用户成本和云计算中心的能耗,以及实... 云计算应用大规模和虚拟化的资源,通过计算机网络随时随地向用户提供基于不同需求的服务。作为影响云服务的关键因素,任务调度被许多专家学者所研究。研究了云计算中的任务调度算法的新特性,如何降低用户成本和云计算中心的能耗,以及实现效率与公平最大化和安全等目标。 展开更多

关键词 云计算 任务调度 虚拟机 有向无环图

在线阅读 下载PDF 职称材料

基于可重构处理器的并行优化算法 被引量：2

17

作者 刘石柱 尹首一 +2 位作者 殷崇勇 刘雷波 魏少军 《计算机工程》 CAS CSCD 2012年第21期286-289,共4页

为挖掘可重构处理器的内在并行性,需要编译器通过分析程序的并行性来决定可重构处理器硬件最好的执行模式。为此,提出一种基于可重构处理器的并行优化算法。将有向无环图的并行计算部分映射到可重构处理器上,对任务实现3个不同层次的并... 为挖掘可重构处理器的内在并行性,需要编译器通过分析程序的并行性来决定可重构处理器硬件最好的执行模式。为此,提出一种基于可重构处理器的并行优化算法。将有向无环图的并行计算部分映射到可重构处理器上,对任务实现3个不同层次的并行性(指令级并行、循环级并行、线程级并行)。测试结果表明,该算法使得可重构处理器在处理任务时比未用并行优化算法的性能提升1.2倍左右。 展开更多

关键词 可重构处理器 并行优化 并行处理 任务编译器 有向无环图

在线阅读 下载PDF 职称材料

异构信号处理平台中层次性流水线调度算法 被引量：5

18

作者 杨平平 岳春生 胡泽明 《计算机工程》 CAS CSCD 北大核心 2018年第11期83-89,共7页

现有实时任务调度算法在系统异构性方面没有考虑处理节点计算能力的差异,导致任务划分不均衡。为此,根据异构信号处理平台实时任务的特点,提出一种面向异构信号处理平台的层次性流水线调度算法。基于数据流图的多层次任务划分算法并借... 现有实时任务调度算法在系统异构性方面没有考虑处理节点计算能力的差异,导致任务划分不均衡。为此,根据异构信号处理平台实时任务的特点,提出一种面向异构信号处理平台的层次性流水线调度算法。基于数据流图的多层次任务划分算法并借鉴多层图划分思想,实现任务调度负载均衡和低通信同步开销。采用同步流水线调度方法达到低延迟实时数据处理的目的。实验结果表明,与事件触发数据流调度算法相比,该算法能有效提高异构信号处理平台的实时处理能力。 展开更多

关键词 异构信号处理平台 有向无环图 负载均衡 任务调度 同步流水线

在线阅读 下载PDF 职称材料

异构分布式系统中一种新型主副版本调度算法 被引量：1

19

作者 朱永超 周川 +2 位作者 郭健 吴益飞 崔玉伟 《计算机工程与应用》 CSCD 北大核心 2019年第21期93-98,共6页

针对异构分布式系统中处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题,提出一种新型高可靠性主副版本调度算法(HRPB)。任务模型以有向无环图(DAG)表示,该算法共计调度主、副两个版本的任务。在任务优先级排序阶段,根据... 针对异构分布式系统中处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题,提出一种新型高可靠性主副版本调度算法(HRPB)。任务模型以有向无环图(DAG)表示,该算法共计调度主、副两个版本的任务。在任务优先级排序阶段,根据任务执行时间及截止时限来制定新指标平均最晚开始时间(ALST)进行排序;在任务处理器分配阶段,采取多一重备份策略以解决处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题,并且改进了副版本调度时的可靠性指标计算方法。通过随机生成DAG图进行算法仿真测试,实验结果表明,HRPB比eFRD具有更优的副版本调度成功率、更高的系统可靠性。 展开更多

关键词 异构分布式系统 优先级约束任务 有向无环图 主副版本 任务调度

在线阅读 下载PDF 职称材料

基于直接后继节点完成时间的异构调度算法 被引量：1

20

作者 王冠 王宇新 +2 位作者 陈鑫 王飞 郭禾 《计算机应用》 CSCD 北大核心 2017年第1期12-17,133,共7页

分布式环境下的异构计算系统(HCS)是大数据时代进行数据密集型计算不可或缺的,一个有效的任务调度算法可以提高整个异构计算系统的效率。在对异构环境下的任务调度进行有向无环图(DAG)建模的基础上,提出基于直接后继节点完成时间的异构... 分布式环境下的异构计算系统(HCS)是大数据时代进行数据密集型计算不可或缺的,一个有效的任务调度算法可以提高整个异构计算系统的效率。在对异构环境下的任务调度进行有向无环图(DAG)建模的基础上,提出基于直接后继节点完成时间的异构调度算法(HSFT)。在计算开销和通信开销差异度较大的异构环境中,考虑两者之间的平衡,采用更为合理的以计算均值与标准方差的乘积和通信权值与任务节点出度的比值作为优先权值计算方法,并在考虑最快完成时间(EFT)的基础上,将直接后继节点完成时间(SFT)用于处理器分配策略。实验结果表明,HSFT在不增加算法时间复杂度的情况下,比HEFT、SDBATS、PEFT等算法有更短的调度长度(makespan)、更优的调度长度比和效率。 展开更多

关键词 有向无环图调度 异构计算 任务优先级 直接后继节点 静态任务调度

在线阅读 下载PDF 职称材料