基于DAG图的自适应代码划分优化算法

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

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

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

基于簇的层次敏感的可重构系统任务划分算法

对于可重构计算中面积约束条件下的任务划分问题,提出一种基于簇的、层次敏感的划分LSCBP算法.该算法按照依赖优先、最早最先和碎片利用三原则构造了新的启发函数AS_Level,能够跟踪节点分配过程并进行动态调整;它克服了CBP算法机械选取节点进行划分的缺点,同时算法复杂度也增大到O{｜ V｜^2＋｜ E｜}.对随机生成的任务图（节点数小于250）的划分实验表明：对于相同的DAG,LSCBP算法能够比CBP算法获得更少的任务簇（可重构资源需求量）和簇间有向边（通信代价）.     

低功耗驱动的电路网表多级划分算法

在划分阶段因得不到实际线长值而无法精确计算功耗值.通过组合使用互连线的通路级数、通路级差和基本线长,提出一种新的独立线长预测方法.使用预测线长和开关活动性的乘积度量划分阶段的动态功耗,并将这一乘积作为权重赋给每条互连线;在聚类和细化处理阶段,尽量避免权重较大的互连线被分割,以实现低功耗驱动的多级划分.实验结果表明,该算法可有效地减小电路的功耗,并且对其他技术指标影响不大.     

基于量子粒子群优化的DAG并行任务调度研究*

任务调度是网络并行计算系统的核心问题之一。在有向无环图(DAG)描述问题的基础上,提出了一种进行并行任务调度的量子粒子群优化算法。首先对DAG并行任务调度问题作出定义,并给出了优化问题的目标;然后分别讨论了问题的编码表示、解码方案、位置向量的计算方法、离散问题连续化、算法的总体流程等;最后给出算法的仿真实验情况及分析,实验结果表明,该算法有良好的全局寻优性能和快捷的收敛速度,调度效果优于遗传算法和粒子群优化算法。     

VLCC中的DAG并行算法

基于组件的密码学虚拟实验室（VLCC）采用有向无环图（DAG）的拓扑排序机制管理组件。在分析VLCC各组件之间的数据依赖和运行次序关系的基础上,提出一种新的基于Java多线程机制和“唤醒”机制的DAG并行算法。与拓扑排序算法相比,具有低算法时间复杂度的特点。实验结果表明,系统在新算法下较大地缩短了系统运行时间,提高资源使用效率和用户满意度,能更好地完善VLCC。     

故障场景下的边缘计算DAG任务重调度方法

边缘计算将计算和存储资源部署在靠近数据源的网络边缘,并高效调度用户卸载的任务,从而极大地提升了用户的服务体验(Quality of Experience,QoE).但是,边缘计算缺乏可靠的基础设施保护,服务器节点或通信链路的突发故障可能会导致服务失败.为此,建立了边缘计算中的计算节点和通信链路故障模型,并针对依赖型用户...     

基于DAG的分布式账本共识机制研究

自2008年比特币出现以来,研究学者相继提出了多种分布式账本技术,其中,区块链是当前分布式账本最主要的实现形式之一.但当前区块链中存在一个核心问题:可扩展性瓶颈.具体而言,区块链的吞吐量严重不足,且其交易确认也较为缓慢,这些因素极大地限制了它的实际应用.在此背景下,基于DAG(有向无环图)的分布式账本因其具有高并发特性,有望突破传统区块链中的性能瓶颈,从而受到了学术界和产业界越来越多的关注和研究.在基于DAG的分布式账本中,最为核心和关键的技术是其共识机制,为此,对该关键技术进行了系统深入的研究.首次从共识形态出发将现有基于DAG的分布式账本分为以下3类:基于主干链的DAG账本;基于平行链的DAG账本;基于朴素DAG的账本.在此基础上,对不同类型的共识机制本质原理及特性进行了深入阐述,并从不同层面对它们进行了详细的对比分析.最后,指出基于DAG的共识机制研究中存在的问题与挑战,并给出进一步的研究方向.     

一种基于DAG动态重构的认知网络服务迁移方法

针对认知网络高度动态性带来的服务随机失效问题,提出了一种服务迁移方法以保障认知网络的 QoS.首先,采用先迁移、后优化的思想,重新生成关联服务有向无环图(directed acyclic graph,简称DAG),并在此基础上提出 DAG 动态重构算法,将关联服务转化为层次化 DAG 服务;其次,计算关键服务迁移路径,并给出可迁移服务死锁避免理论分析,将迁移服务提前迁移到当前网络空闲资源运行,以缩短服务的执行时间.仿真实验测试了3种故障注入类型下网络服务迁移方案的服务性能.实验结果显示,该方法在弹性网络负载与未知故障情况下具有较好的 QoS保障效果.     

Analysis of a Heuristic for Code Partitioning

In this paper, we analyze the time complexity and performance of a heuristic for code partitioning for Distributed Memory Multiprocessors (DMMs). The partitioning method is data-flow based where all levels of parallelism are exploited. Given a weighted Directed Acyclic Graph (DAG) representation of the program, our algorithm automatically determines the granularity of parallelism by partitioning the graph into tasks to be scheduled on the DMM. The granularity of parallelism depends only on the program to be executed and on the target machine parameters. The output of our algorithm is passed on as input to the scheduling phase. Finding an optimal solution to this problem is NP-complete. Due to the high cost of graph algorithms, it is nearly impossible to come up with close to optimal solutions that do not have very high cost (higher order polynomial). Our proposed heuristic gives good performance and has relatively low cost.     

基于DAG图解-重构的机群系统静态调度算法

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

无回路网络中最短路问题的高效算法

无回路网络是一类重要的网络,给出在无回路网络中求解最短路树形图和任意顶点对间最短路的高效算法。该算法将顶点进行重新编号,结合广度优先探索法,从源顶点出发依次搜索每个顶点的所有出弧,并在弧的头部进行权值变换操作,可以得到最短路树形图和任意顶点对间最短路,算法复杂度分别为O(m)和O(m(n-m1/2))。该算法思想简便、复杂度低、易于操作。 关键词：     

面向VLSI的门级单粒子效应评估技术

由于空间辐射环境充满了各类射线和高能粒子，非常容易诱发集成电路发生单粒子效应，因此有必要开发对应的评估技术，分析单粒子效应对超大规模集成电路（VLSI）的影响。以ISCAS89测试基准电路为主要研究对象，提出了一种适用于VLSI的单粒子效应评估技术，可以通过脚本自动生成仿真和测试文件，实现任意节点的故障注入，并可以在任何一种支持硬件描述语言的EDA仿真工具上进行评估。分别对使用三模冗余技术、自刷新寄存器技术加固后的电路和原始电路进行了对比评估。评估结果符合逻辑，验证了门级单粒子效应评估测试技术的有效性。通过提出的评估技术，可以快速评估电路的抗辐射能力，提高查找设计缺陷、对电路进行针对性加固的效率，对于提高集成电路的安全性和稳定性有着重要的应用价值。     

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

针对异构环境并行计算的静态任务调度问题,以最小化有向无环图 (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算法更有效,而且时间复杂度较低.     

云计算环境下基于路径优先级的任务调度算法

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

An efficient list-based task scheduling algorithm for heterogeneous distributed computing environment

The task scheduling in heterogeneous distributed computing systems plays a crucial role in reducing the makespan and maximizing resource utilization. The diverse nature of the devices in heterogeneous distributed computing systems intensifies the complexity of scheduling the tasks. To overcome this problem, a new list-based static task scheduling algorithm namely Deadline-Aware-Longest-Path-of-all-Predecessors (DA-LPP) is being proposed in this article. In the prioritization phase of the DA-LPP algorithm, the path length of the current task from all its predecessors at each level is computed and among them, the longest path length value is assigned as the rank of the task. This strategy emphasizes the tasks in the critical path. This well-optimized prioritization phase leads to an observable minimization in the makespan of the applications. In the processor selection phase, the DA-LPP algorithm implements the improved insertion-based policy which effectively utilizes the unoccupied leftover free time slots of the processors which improve resource utilization, further least computation cost allocation approach is followed to minimize the overall computation cost of the processors and parental prioritization policy is incorporated to further reduce the scheduling length. To demonstrate the robustness of the proposed algorithm, a synthetic graph generator is used in this experiment to generate a huge variety of graphs. Apart from the synthetic graphs, real-world application graphs like Montage, LIGO, Cybershake, and Epigenomic are also considered to grade the performance of the DA-LPP algorithm. Experimental results of the DA-LPP algorithm show improvement in performance in terms of scheduling length ratio, makespan reduction rate , and resource reduction rate when compared with other algorithms like DQWS, DUCO, DCO and EPRD. The results reveal that for 1000 task set with deadline equals to two times of the critical path, the scheduling length ratio of the DA-LPP algorithm is better than DQWS by 35%, DUCO by 23%, DCO by 26 %, and EPRD by 17%.