基于通信开销的多类型DAG任务调度方法

随着异构多核处理器的性能不断增强,具有关联关系任务的调度问题和调度算法成为研究者们关注的焦点。针对异构多核平台上的有向无环图(Directed Acyclic Graph,DAG)任务模型进行了调度分析。由于异构环境中计算资源类型丰富数量多,实际调度过程中处在不同核上的任务之间的通信开销是存在的。而当前大多数调度算法要么忽略不同核上的任务之间的通信开销,要么优先级判定和选择处理器核执行时不能全面考虑核间任务的通信开销,造成资源浪费,增加了系统调度任务的整体长度。因此,针对具有通信开销的DAG任务模型,讨论了任务间的通信开销对任务调度算法的影响,提出了复合节点生成算法(Composite Node Generation Algorithm,CNGA)任务调度算法。该算法根据任务间通信开销大小进行预处理分配生成复合节点,重构DAG图将任务节点的上行秩和通信占比作为参数决定任务节点的优先级。实验结果与HEFT和CPOP算法比较,在任务通信开销和任务执行开销之比(Communication to Computation Ratio,CCR)一定的情况下响应时间比原有的HEFT和CPOP提升10.19%,稳定性以松弛度和接受率为参数平均提升3.96%。

DAG区块链中连通度极限值CLV研究

DAG(Directed Acyclic Graph)区块链技术在性能、确定性等方面较中本聪最长链显露出更多优势。DAG区块链技术中的核心问题就是交易排序,其中引入了连通度极限值(Connectivity Limit Value,CLV)。可推定中本聪最长链的CLV取值为零,保证网络的安全达到极高的水平,但是交易验证的并行度差。为此对DAG区块链扩容方案进行泛化分析,DAG区块链网络具有高并发性,但CLV取值非零,相应安全性受到影响。继而探索连通度极限值与网络的安全阈值、网络延迟等存在的关系,并针对在DAG区块链网络中要保障CLV取值在安全阈值与网络延迟之间的平衡问题,引用进化计算中的方法给出了平衡关系式,在安全性与延迟度之间提出合理优化。此外针对DAG区块链中沙漏区块的CLV取值进行分析并给出合理建议。

基于DAG认证的网络切片场景切换算法

针对网络切片场景切换时重复身份认证导致的切换延迟问题,提出了一种基于有向无环图(DAG)认证的网络切片场景切换算法。该算法首先从DAG认证方面实现了用户场景切换的持续身份认证,确保了用户能够快速实现网络切片场景切换;然后针对多用户场景切换问题,使用了Wassertein优化下的条件生成对抗网络算法进行了场景切换优先级判定,保证了用户场景切换的低掉落率。仿真结果表明,本文算法通过避免额外的身份认证实现了更低的切换延迟,同时改善了低延迟下的掉落率性能。

阿扎胞苷联合DAG方案治疗急性髓系白血病的临床研究

目的探讨阿扎胞苷联合DAG方案(柔红霉素+阿糖胞苷+重组人粒细胞集落刺激因子)治疗急性髓系白血病(AML)患者的临床效果。方法回顾性分析2020年9月至2021年12月收治的200例AML患者临床资料。根据治疗方案不同分为对照组(DAG方案,100例)与观察组(阿扎胞苷联合DAG方案,100例)。以21 d为1个疗程,需治疗2个疗程。对比2组患者临床疗效、细胞免疫功能及治疗期间药物毒副反应。结果观察组临床总有效率高于对照组(P<0.05);治疗后,2组CD_(3)^(+),CD_(4)^(+),CD_(4)^(+)/CD_(8)^(+) 值均低于治疗前(P<0.05),但治疗后,组间细胞免疫细胞指标比较,差异无统计学意义(P>0.05)。治疗期间,对比2组药物毒副反应率,差异无统计学意义(P>0.05)。结论阿扎胞苷联合DAG方案治疗可提高AML患者临床疗效,且不加重患者免疫抑制状态及药物毒副作用。

ROS2多线程执行器上DAG任务的优先级分配方法

随着机器人操作系统(robot operating system, ROS)的日益普及,系统也变得更加复杂,这类系统的计算平台正逐渐转变为多核心平台.在ROS中,任务执行的顺序取决于底层任务调度策略和分配给任务的优先级,而最大限度地缩短所有任务的执行时间是并行系统任务调度的一个重要目标.受强化学习在解决各种组合优化问题的最新研究成果的启发,在考虑ROS2多线程执行器的调度机制和执行约束的前提下,提出了一种基于强化学习的任务优先级分配方法,该方法提取了基于有向无环图形式表示的任务集的时间和结构特征,通过策略梯度和蒙特卡洛树搜索(Monte Carlo tree search, MCTS)方法有效地学习ROS2调度策略并给出合理的优先级设置方案,最终达到最小化并行任务的最大完工时间的目的.通过模拟平台环境下随机生成的任务图以评估所提方法,结果表明所提方法明显优于基准方法.作为一种离线分析方法,所提方法可以很容易地扩展到复杂的ROS中,在可接受的时间内找到接近最优的解决方案.

基于超体积法的云计算DAG任务调度方法研究

针对云计算复杂工作流的调度均衡问题,提出了结合hypervolume的DAG任务调度算法。根据对复杂工作流的分析,确定时间和成本双目标求解模型,设定调度优化前提。在DAG图设计过程中,针对耦合任务设计了优先级机制和后驱任务的执行时机。针对若干DAG图的情况,引入平衡系数对DAG工作流进行分层处理,从而避免不同DAG图间任务出现竞争。将DAG调度部署于MapReduce框架进行并发处理,采用构建最小树的方式来消除DAG图存在较多的冗余耦合。考虑到网络攻击带来的故障情况,采用时隙与资源的映射关系来规避。最后,为了增强双目标的搜索性能,引入hypervolume计算以获得更好的收敛性。基于WorkflowSim仿真平台,从时间开销、成本开销、以及抗网络攻击三方面对所提算法进行验证,结果表明,上述算法能够很好的确保时间和成本最小且均衡,同时有效抵抗网络攻击对任务成功率的影响。

DAG任务同步中无锁机制实现方法研究

随着多核嵌入式实时系统的发展,DAG任务同步问题得到了广泛的关注.目前的任务同步方法大都采用锁机制,但锁机制存在许多问题,如自旋锁存在任务忙等状态,浪费CPU资源;使用互斥锁的任务若获取不到共享资源会被阻塞,产生上下文切换开销;顺序锁允许写任务有更高的优先级,但写任务不能频繁更新数据,否则读任务会产生饿死现象.上述锁机制如果应用于多核平台下的DAG任务同步,不仅会影响系统整体执行效率,导致后继任务无法执行,严重时会引发死锁现象导致系统崩溃.因此,提出了在DAG任务同步过程中使用DCAS无锁机制,有效避免了锁机制存在的问题.在LITMUSRT多核平台下,以多任务同时申请、填充和释放Vxworks网络缓冲区为例,对缓冲池中的三元组mBlk,clBlk,cluster分别使用DCAS无锁机制.实验结果表明,相比传统锁机制,DCAS无锁机制在DAG任务同步方面有较好的效果,响应时间减少了10.4%,系统的整体执行效率提高了4.2%.

公开选举代表投票的DAG共识机制

区块链作为一种创新型的分布式账本技术,以其去中心化、可追溯、防篡改等特性,在未来许多行业中具有广泛的应用前景.但现有单链式结构的区块链存在并发低、高延迟等问题.一种基于有向无环图(directed acyclic graph,DAG)结构的新型账本技术的出现有望突破传统区块链的性能瓶颈,但目前基于DAG型区块链系统的共识机制并不成熟.本文针对典型DAG型区块链系统Nano网络的ORV共识机制存在的安全性问题进行改进,提出了一种基于代表选举模型的公开选举代表投票共识机制,即OERV(open election representative voting).使主要代表节点的权益得到了分散,增强了去中心化程度,提高了网络安全性.实验结果表明,OERV算法性能高效,能够在不牺牲系统效率的同时增强系统的稳定性和安全性,对于推动DAG型区块链共识机制的研究有着重要的现实意义.

DAG植入机后插钢管柱在逆作法施工中的应用

结合北京某邻地铁织补项目逆作法施工中一桩一柱后插法施工技术,从植入机的选型、设备原理及优点等方面进行阐述。根据施工监测数据,对钢管柱的垂直度、标高、轴线位置等参数的控制措施进行优化,总结了DAG植入机后插法施工钢管柱的施工工艺及控制要点,保证了后插法钢管柱施工的安全、高效、精准,可为相似工程提供借鉴。

大数据DAG任务流调度平台技术研究与应用

文章提出了一种大数据DAG任务流调度平台技术,其能够基于DAG任务流进行调度,以及对大数据处理流程进行调度。为了实现这一目的,文章从几个方面进行详细设计,即架构设计、协议设计、引擎设计、引擎热加载机制、DAG结构、资源介质机制、调度算法、回调机制、信号机制。使用基于拖拽的方式进行流程配置,降低用户的使用难度,最终实现在企业实时/离线大数据处理流程中承担所有任务调度工作。

车联网中基于有向无环图区块链的个性化联邦互蒸馏学习方法

联邦学习(FL)作为一种分布式训练方法,在车联网(IoV)中得到了广泛应用。区别于传统机器学习,FL允许智能网联车辆(CAVs)通过共享模型而非原始数据来协同训练全局模型,从而保护CAV隐私和数据安全。为了提升联邦学习模型精度,降低通信开销,该文首先提出一种基于有向无环图(DAG)区块链和CAVs的IoV架构,分别负责全局模型共享和本地模型训练。其次,设计了一种基于DAG区块链的异步联邦互蒸馏学习(DAFML)算法在本地同时训练教师和学生模型,教师模型的专业级网络结构可取得更高精度,学生模型的轻量级网络结构可降低通信开销,并采用互蒸馏学习使教师模型和学生模型从互相转移的软标签中学习知识以更新模型。此外,为了进一步提高模型精度,基于全局训练轮次和模型精度设定个性化权值来调节互蒸馏占比。仿真结果表明,DAFML算法在模型精度和蒸馏比率方面优于其他比较算法。

面向异构处理平台任务调度的麻雀优化算法

针对当前异构信号处理平台中各处理器任务数量分配不均衡、处理器性能发挥不完全以及系统运行效率低的问题,文中提出一种面向异构处理平台的麻雀优化算法。该算法利用了麻雀算法较强的全局寻优能力和麻雀种群内部的高效工作机制。在经典麻雀算法基础上,文中提出了符合任务调度的二进制异或编解码规则,将离散的任务分配方案映射为连续的麻雀位置信息。将处理器负载均衡指数作为适应度函数,选取每次迭代中的最优解;在麻雀遍历任务时,采用任务优先级分流排序策略。对通信密集型任务和计算密集型任务采取不同的计算式得到更符合任务特点的遍历顺序,生成随机任务图,并将所提算法同ICPA(Improved Critical Path Algortthm)算法进行对比。仿真结果表明,相比于ICPA算法,所提算法的负载均衡指数平均优化率为60%,各处理器负载情况更加均衡,能更好地发挥异构处理平台的整体效能。

月桂酸甘油二酯和豆蔻酸甘油二酯的固定化脂肪酶R IM-03催化合成及纯化

为促进固定化脂肪酶R IM-03在合成甘油二酯(DAG)中的应用,采用固定化脂肪酶RIM-03催化月桂酸/豆蔻酸和甘油酯化合成甘油二酯,并采用分子蒸馏对其进行纯化。对酯化反应和分子蒸馏的工艺条件进行了优化,并考察了纯化产物的理化性质。结果表明:固定化脂肪酶R IM-03催化甘油和月桂酸/豆蔻酸合成甘油二酯的最优条件为底物(脂肪酸与甘油)物质的量比2∶1、反应温度60℃、反应时间6h、酶添加量6%(以底物质量计),在此条件下月桂酸甘油二酯和豆蔻酸甘油二酯粗产物中甘油二酯含量分别为43.87%和30.00%,甘油三酯(TAG)含量分别为8.71%和6.87%,催化剂可重复利用至少10次;月桂酸甘油二酯粗产物纯化的最优条件为一级分子蒸馏温度170℃、二级分子蒸馏温度180℃,豆蔻酸甘油二酯粗产物纯化的最优条件为一级分子蒸馏温度170℃、二级分子蒸馏温度190℃,在最优条件下纯化月桂酸甘油二酯和豆蔻酸甘油二酯中甘油二酯含量分别达81.29%和80.08%,1,3-甘油二酯含量分别为53.16%和54.27%,DAG/(DAG+TAG)约为80%;纯化月桂酸甘油二酯和豆蔻酸甘油二酯的滑动熔点分别为48.9℃和57.0℃,在30~40℃区间的固体脂肪含量呈陡然下降趋势,在两者复配的体系中,当豆蔻酸甘油二酯占60%以上时,相容性理想。综上,固定化脂肪酶RIM-03具有在甘油二酯合成中应用的潜力,DAG/(DAG+TAG)可作为关键控制指标,异酸甘油二酯复配可改变产物的熔化性质。

一种基于模糊聚类的网格DAG任务图调度算法

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

异构分布式环境下多DAG工作流的混合调度策略

关于多个DAG工作流在异构分布式环境下调度的研究近来有了新的进展,也解决了一些问题,但现阶段还没有考虑和解决根据不同类型DAG的需求按优先级进行分类,以及对不同时间到达的多个不同优先级DAG进行调度的问题.为解决这些问题,针对各用户对DAG工作流的QoS需求的不同,在对不同用户的DAG工作流进行优先级划分的基础上,首先提出了一种新的调度模型,并改进了已有的公平调度算法,解决在不同时间上被提交的具有相同优先级的多个DAG工作流之间调度的公平性问题.为了提高资源利用率和高优先级DAG尽可能小地受低优先级DAG的影响,又提出了一种适用于多个不同优先级DAG之间调度的Backfill算法.在新的系统模型和这两种算法的基础上,提出了一种混合调度策略.实验结果表明,这种混合调策略能够兼顾不同时间到达的多个不同类型DAG调度需求和资源利用率的改善.另外,通过实验发现了关于两个DAG调度所特有的'拖尾'规律,具有进一步研究和应用的价值.

多DAG工作流在云计算环境下的可靠性调度方法

针对云计算环境中多个DAG科学工作流的可靠性调度问题,提出一种考虑虚拟机之间链路通信竞争的动态多DAG分层调度算法.首先使用通信竞争模型描述虚拟机之间的通信,然后分别计算主版本及副版本任务的最早完成时间,并限定任务所调度的虚拟机单元.再对多个同时到达的DAG工作流任务使用动态分层方法,计算每个DAG任务的不公平程度因子.该算法有效解决了当多个DAG中任务的权值相差较大时,之前到达的DAG不会因为剩余任务迟迟得不到调度而导致执行时间跨度增大的问题.仿真实验表明,在保证可靠调度的前提下,该算法不仅能提高多个DAG调度的公平程度,而且能有效地缩短多个DAG调度的平均最早完成时间.

云计算环境下多DAG调度的资源分配进化算法

现有多DAG调度研究主要在多个DAG共享资源调度的时间最小化、公平性最大化、吞吐量最大化等问题方面提出了相关的解决方案,然而,现有的方法还不能很好地解决云计算环境下多DAG共享资源调度的资源分配优化问题。为此,首先分析讨论了一组多DAG共享云计算资源调度中的多DAG数量、属性结构分布特点与资源需求量之间的关系,并在此基础上提出了基于资源需求强度预测变异方法的进化算法EFRD,有效地解决了云计算环境下多DAG共享资源调度的资源分配优化问题,既保证了多DAG的调度执行时间最小化,也避免了资源的浪费。实验表明,EFRD算法能够有效地收敛到最优解。

带通信开销的DAG工作流费用优化模型与算法

通信开销在云环境中无法忽略,但现有DAG(directed acyclic graph)工作流费用优化模型大都未考虑任务之间的通信开销,难以在实际云环境中应用.为此,提出带通信开销的工作流费用优化模型CA-DAG(communication aware-DAG),并在分层算法的基础上提出针对CA-DAG模型的调度算法CACO(communication aware cost optimization).CACO使用前向一致规则(forward consistent,FC)求解工作流的最小完工时间;根据逆向分层策略将任务分层,使费用优化问题从全局转化到局部;采用动态规划方法收集任务在选择服务时产生的零散"时间碎片",增加任务的费用优化空间,改善费用优化效果.仿真实验结果表明,在考虑通信开销时,CACO费用优化效果较DTL(deadline top level),DBL(deadline bottom level),TCDBL(temporal consistency deadline bottom level)都有显著提高.

异构分布式系统DAG可靠性模型与容错算法

异构分布式系统性能得到大幅度提升的同时,却造成故障率大增,以有向无环图(Directed Acyclic Graph,DAG)任务模型研究异构分布式系统的容错调度成为当前的研究热点.广泛采用的基于任务复制的容错算法存在以下问题:(1)DAG任务可靠性需求与DAG可靠性需求的约束存在缺陷且缺乏严谨的理论证明;(2)每个任务仅有一个副版任务,不足以应对任务潜在的多次发生的故障;(3)盲目地使每个任务拥有ε+1个副版来容忍可能的ε个故障,虽然提高了系统的可靠性但易造成系统冗余度过高,并付出昂贵的计算资源.文中首先分析DAG图中任务依赖关系,确定DAG任务的可靠性概率模型,并建立DAG可靠性模型;接着提出满足可靠性目标的任务复制下限值算法、经济的任务复制策略算法和贪婪的任务复制策略算法,精确量化各个任务需要复制的次数,最后在上述算法的基础上提出可选策略的DAG容错算法OPDFT(Optional Policy on DAG Fault-Tolerant).实验表明,OPDFT算法的经济复制策略和贪婪复制策略的可靠性代价分别是盲目策略算法可靠性代价的60%和70%左右.

异构系统中DAG任务调度的双螺旋结构遗传算法

任务调度问题是一个NP完全问题,基于启发式的方法通常被用来求解次优解,其性能在很大程度上依赖启发的成效,在复杂问题时可能会产生不理想的结果.鉴于此,根据染色体双螺旋结构模型,提出了一种异构计算系统中依赖任务调度的双螺旋结构遗传算法.算法将遗传算法和启发式方法有机地结合,首先针对任务图的数据依赖关系,采用启发式方法,控制遗传算法的交叉与变异操作合理改变一个染色体主链结构,以产生较佳的任务调度优先队列;然后模仿碱基互补配对方法,利用启发式异构环境下最早完成时间算法,实现从一个染色体主链(任务集)到另一个染色体主链(异构处理机集)的映射,以提高算法的有效性和收敛速度.随机任务图和真实问题任务图的仿真实验表明,所提出的算法在调度性能上明显优于启发式算法,最大完成时间平均减少10.1%.