网格计算环境下资源联合分配的映射策略与机制

提出用于网格环境的资源协同调度框架及网格环境下多任务的资源映射策略,用图论中有向无环图解决资源调度过程中任务的优先级限制问题,并在有向无环图上构造兼容图,通过寻找图中最大独立任务集的方法,解决多任务对多资源请求的资源共享问题。给出了网格计算环境下动态资源联合分配的资源管理机制。     

有向无环图的高效归约算法

将一个应用程序部署到给定的片上网络上执行时,需要将应用程序中的每一个子任务都指派给片上网络中的一个节点执行。该问题一般被建模成一组子任务作为顶点的有向无环图,任务在片上网络上的部署过程就等同于一个有向无环图的顶点向一个片上网络拓扑映射的过程。而随着应用程序和片上网络规模的增大,计算一个最优的映射方案是典型的难解问题。为了加速有向无环图到片上网络拓扑的映射过程,提出了有向无环图的归约算法,使归约后的图中的顶点数量尽可能地与给定片上网络中的节点数量相同。提出的图归约算法可以有效地识别出所有可归约子图,这些可归约子图可被归约为单一顶点。新算法的适用范围从嵌套图扩展到了任意图,并且拥有与原算法相同的复杂度量级。还提出了一种并行化的算法思想来加速可归约子图的搜索过程。     

信任委托证书图搜索研究

分析了分布式信任管理的证书结构反证书授权模型,包括线性链式授权、门限授权、条件授权和复合证书授权等,探讨了不同模型下的证书表达与证书链处理机制．提出了基于有向无环图DAG的证书图结构,并对利用DAG表达证书图作出证明。在证书链的搜索算法中。通过对多重边的有向无环图用深度优先和广度优先算法结合实现对证书链的搜索,避免证书图中产生的环形链而导致低搜索效率问题。     

VLCC中的DAG并行算法

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

基于DAG的拓扑排序改进算法及在BOM中的运用

文章讨论了传统的BOM防止嵌套错误算法和低层码计算的算法的实现过程。在分析算法的实现过程后对其原理进行评价的基础上,将BOM树结构和DAG图性质进行比较后对这两种算法进行改进,提出了一种蕴涵了拓扑排序思想的算法。最后编程实现了此算法的伪代码,该算法在实际运用中取得了明显的效果,减少了数据库系统资源的占用,大大提高了数据库的性能和响应能力。     

基于依赖结构的功能测试集排序方法

为解决依赖结构优先级在测试用例权值相等时存在的问题,针对流行的深度优先搜索算法进行改进。通过结合测试用例之间的功能依赖和测试用例的代码覆盖率,推导出有向无环图和算法流程图;利用推导出的有向无环图和流程图,使用权值和代码覆盖率算出最长路径作为测试集,以达到缩减测试集,同时保证代码覆盖率的目的。结合实例,将依赖结构优先级和现存的技术进行对比,验证了依赖结构优先级技术在提高错误检测率方面的可行性和实用性。     

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

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

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

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

基于Petri网的网格数据库查询计划模型的映射转换

网格数据库中主要采用基于有向无环图（DAG）的查询计划建模方式,该方法由于不考虑子查询与节点的数据关系,因而对子查询在节点的优化调度方面支持不足。对查询计划提出了基于Petri网的形式化描述模型NSN,通过扩展子查询与节点以及子查询之间的数据关联关系的描述,对子查询的优化调度提供更大的支持;进一步给出了从DAG模型到NSN模型的转换规则和转换算法,实现了查询计划从DAG到NSN模型的转换,最后通过实验验证了NSN模型对子查询在节点中的分派调度的优越性。     

面向对象的流程工业系统有向无环图建模

提出流程工业系统中有向无环图的面向对象的建模方法。介绍使用面向对象的技术对流程工业系统模进行建模的关键要素的技巧,定义描述流程工业系统中有向无环图模型的建模机制,扩展流程工业系统模型所具有的特性。以流程工业系统出现异常时的诊断实例说明系统模型解决问题的有效性。     

面向高通量计算机的图算法优化技术

随着互联网技术的蓬勃发展,图数据的规模呈爆炸式增长.如何高效地处理大规模图数据逐渐成为工业界和学术界关注的焦点.宽度优先搜索算法是解决图遍历问题的经典算法,也是Graph500基准的核心测试程序之一.高通量计算机采用ARM架构的众核体系结构,具有高并发、强实时、低功耗等适于大数据计算的特点.在单节点上,BFS算法的优化已取得一系列进展,首先对现有的优化技术进行系统的介绍,并在此基础上提出2种面向高通量计算机的优化手段,通过减少冗余访存和提高缓存局部性,有效提高了算法的访存效率.通过这些优化手段,在高通量计算机上对BFS算法的性能进行了系统的评估.对于顶点规模为2³⁰的Kronecker图(顶点数为2³⁰,边数为2³⁴),优化后的BFS算法在高通量计算机上的平均性能为24.26 GTEPS.与两路x86架构服务器相比,单节点具有1.18倍的性能优势.在性能功耗比方面,高通量计算机的结果为181.04 MTEPS/W.在2019年6月份的Green Graph500面向大数据集的排行榜上取得第2名的成绩.综上,高通量计算机的高并发和低功耗等特点非常适合处理大规模图计算等数据密集型应用.     

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

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

云计算环境下多有向无环图工作流的节能调度算法

针对多有向无环图(DAG)工作流节能调度算法中存在的节能效果不佳、适用范围较窄和无法兼顾性能优化等问题,提出了一种新的多DAG工作流节能调度方法--MREO。MREO在对计算密集型和通信密集型任务特点进行分析的基础上,通过整合独立任务,减少了处理器的数量,并利用回溯和分支限界算法对任务整合路径进行动态的优化选择,有效降低了整合算法的复杂度。实验结果证明,MREO在保证多DAG工作流性能的前提下,能够有效降低系统的计算和通信能量开销,获得了良好的节能效果。     

Reducing conflict resolution time for solving graph problems in broadcast communications

In this paper, we propose some algorithms to solve the topological ordering problem, the breadth-first search problem and the connected component problem under the broadcast communication model. The basic idea of our algorithms is to divide a graph into several layers. Only after all vertices in one layer are processed, we begin to process the vertices in another layer. Thus, the number of broadcast conflicts is reduced. We also propose a randomized conflict resolution scheme to resolve conflicts. We show that the average time complexity of our algorithms is Θ(n), where n is the number of available processors and also the number of vertices in the graph.     

有向无环图上k步可达查询优化算法

k步可达查询用于在给定的有向无环图（DAG）中回答两点之间是否存在长度不超过k的路径。针对现有方法的索引规模大、查询处理效率低的问题,提出一种基于部分点的双向最短路径索引来提升索引的可达信息覆盖率,并提出一组优化规则来减小索引规模;然后提出基于简化图的正反互逆拓扑索引来加速回答不可达查询;最后提出远距离优先的双向遍历策略来提高查询处理的效率。基于21个真实数据集（如引用网络、社交网络等）的实验结果表明,相比已有的高效方法PLL及BFSI-B,所提出的算法具有更小的索引规模和更快的查询响应速度。     

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

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

基于进化自适应蝙蝠算法的异构多核处理器任务调度

异构多核处理器的任务调度问题已经被证明是一个NP完全问题。为满足复杂应用的计算需求, 提高异构多核处理器的任务调度效率, 提出一种基于进化自适应蝙蝠算法(EABA)的异构多核处理器任务调度算法。首先, 对任务调度问题进行描述, 并建立相应的数学模型; 接着, 设计任务分配编码方案和适应度函数, 将所提算法映射到离散空间, 使其能够适用于离散的异构多核处理器任务调度问题的研究; 然后, 为避免算法过早陷入局部最优, 引入衰减脉冲策略和进化自适应变换策略; 最后, 设计仿真实验, 将所提算法与蝙蝠算法(BA)、改进粒子群算法(IPSO)、人工鱼群算法(AFSA)、改进鲸鱼优化算法(IWOA)进行比较。实验结果表明, 在中等规模任务(40~70个)和大规模任务(80~100个)下, EABA算法的最优调度长度与次优算法相比分别缩短了12.86%和13.67%, 算法平均执行时间分别减少了14.51%和13.50%。     

Efficient coding of labeled directed acyclic graphs

 We use an adaptation of the Prüfer code for trees to encode labeled directed acyclic graphs, which are often abbreviated to DAGs (or ADGs). In this paper, each DAG is assigned a unique DAG code, which allows an easy handling for several purposes. The set of all possible DAG codes (and therefore the set of all DAGs) for a fixed number of n vertices can be generated efficiently. Furthermore, we are able to rank DAGs, i.e., we provide an algorithm that assigns every DAG a unique number in the set {0,…,a _n −1}, where a _n is the cardinality of the set of labeled DAGs with n≥1 vertices, and we are able to unrank DAGs, which is the inverse operation. We also gain recurrence relations, which can be used to calculate a _n and a _n,q , i.e., the number of DAGs with n vertices and q edges. Finally, it is possible to generate, enumerate, rank and unrank DAGs with given number of edges and also DAGs with bounded indegree. RID="*" ID="*" This research was supported by the Austrian Science Fund (FWF), P13261-INF. I want to thank the reviewers, specially the one who suggested to add the algorithm for unranking DAG codes, for reading the paper very carefully and for the helpful comments.     

基于DAGs模型的RAID系统的设计与实现

研究了一种基于DAGs模型的自动执行的冗余磁盘阵列技术,描述了这种模型的优点以及DAG的执行机制和Roll away错误恢复策略。在此基础上讨论了RAID系统实现,并结合实际课题讨论了在实际中运用这种模型开发RAID系统的好处与优势。