一种基于DAG图划分的网格关联任务调度算法

网格计算中的大型应用程序往往被分解为多个关联任务.对于这类应用,任务间的依赖是一个不可忽略的因素.传统算法只能将其视为元任务来考虑,限制了对任务粒度的进一步划分,从而大大降低了任务调度的性能.本文提出一种基于DAG图划分的关联任务调度算法.它优先调度关键路径上的任务,同时利用任务复制的方法充分利用资源上的时间碎片,保证依赖关系及时得到满足.仿真结果表明,对于网格环境下的大规模关联任务,该算法有效地提高了作业执行速度和资源使用效率.     

基于模糊聚类思想的网格独立任务调度算法

任务调度是网格研究的核心问题之一,在研究网格任务调度问题的基础上,利用模糊聚类思想提出将网格任务与资源进行混合模糊聚类的网格独立任务调度算法,该算法将最适合的资源分配给与之相适应的任务,即尽量将任务调度到恰好满足其需求的资源上执行,从而把综合能力大大超过当前任务的资源“预留”给将来的任务使用,算法具有良好的性能和负载均衡效果,为网格任务调度提供一种新的思路。     

一种协同的FCPM模糊聚类算法

比重隶属度模糊聚类(FCPM)算法可从不同角度解决聚类问题,取得较好效果。协同聚类算法利用不同特征子集之间的协同关系,并与其它聚类算法相结合,可提高原有的聚类性能。文中在FCPM聚类算法的基础上进行改进,将其与协同聚类算法相结合,提出一种协同的FCPM聚类算法。该算法在原有FCPM聚类算法的基础上,提高对数据集的聚类效果。在对数据集Wine和Iris进行测试的结果表明,该方法优于FCPM算法,说明该方法的有效性。     

一种区域型模糊聚类算法

使用支撑集和模糊待分集的概念来描述数据集的分布,在此基础上提出了一种区域型模糊聚类算法———re-gionalfuzzyclusteringalgorithm。仿真结果表明该算法有比常用的模糊C均值更好的聚类性能。     

DAG任务图的一种调度算法

并行程序的调度技术是开发并行计算机系统的计算潜能的关键问题。本文讨论了4种典型的调度算法的缺陷，提出了一种新的调度算法CPFMBF，它采用的策略是：优先调度关键路径节点，其次调度b-level值大的节点，再次调度节点的关键路径影响度大的节点。对照分析及在几种具代表性的工程应用任务图上的实验结果证明CPFMBF算法的调度性能普遍好于其它算法。     

一种基于网格的引力聚类算法

将万有引力和牛顿第二运动定律的思想引入到聚类分析中,提出了一种基于网格的引力聚类算法GCABG.该算法可以自动决定目标数据集中的簇的个数,并且能发现任意形状的簇且可以过滤"噪声"数据.实验结果表明GCABG可以产生高质量的聚类结果.     

一种新的基于网格的聚类算法

新的基于网格的聚类算法(CABG)利用网格处理技术对数据进行了预处理,能根据数据分布情况动态计算每个单元格的半径,并成功地将网格预处理后所得单元格数据运用于其后的聚类分析中,从而简化了算法所需的初始参数。实验表明,CABG算法不仅具有DBSCAN算法准确挖掘各种形状的聚类和很好的噪声处理能力的优点,而且具有较高聚类速度以及对初始参数较低的敏感度。     

基于遗传模拟退火算法的模糊聚类方法

首先对模糊C-均值聚类算法做了简要分析和评论,根据其特点,提出了一种基于遗传模拟退火算法的聚类分析方法,从而提高了遗传算法的全局搜索能力。算法中采用了适合于模糊聚类的树型编码方案,实验表明,该算法可克服系统对数据集及初始聚类中心的敏感性,避免陷入局部极小,具有良好的准确性与可靠性,在模式识别、数据挖掘等领域有着广泛的应用前景。     

一种基于网格的改进的K-Means聚类算法

K-Means算法对数据集中的每个数据点进行多次处理,因此对于大数据集时间效率不高.为提高K-Means算法的时间性能并使聚类结果更优,利用网格方法定义了单元密度聚合度概念,提出了一种基于网格的改进的K-Means聚类算法(IKMG).IKMG利用网格连通性原理并借助树形结构,将多个密集网格单元作为初始根节点,周围网格作为它的子节点,以此类推,广度优先扩展树最终得到K个聚类树.实验结果表明,IKMG不但大大缩短了K-Means算法对大数据集的处理时间,而且能有效消除聚类结果对初始聚类中心的敏感性,无需人为指定K值,能找出不同大小、不同形状的聚类.     

一种基于任务复制方法的网格调度算法

根据Intemet上存在大量空闲主机的情况，结合流行的P2P的思想给出了一种基于资源代理的网格系统模型，该模型能提供超级计算能力给一般的用户。针对在像网格这样的大规模系统中部署大量监控组件的困难性，设计了一种基于任务复制的调度算法。该算法无需任何有关环境的预测信息，仅需知道任务的相对长度，就可在执行过程中自动地适应网格的动态性，并且具有容错功能。     

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

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

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

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

基于选择性复制前驱任务的DAG调度算法

针对异构环境下相关任务的静态调度问题,以最小化调度长度为主要目标,结合表调度与基于复制的调度思想提出了选择性任务复制调度算法.在任务调度过程中,利用处理器的空闲时间,通过有选择地复制能提前当前任务开始执行时间的父任务来减少任务之间信息传递的通信延迟,有利于后续任务的及时调度,从而缩短整个任务图的并行完成时间.实验结果表明,文中算法在通信量比较大的情况下在时间上优于复杂度相同的HEFT,HNDP及DDS算法,且随着任务图中通信时间/计算时间比值的增加,其优越性也越来越明显.     

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

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

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

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

硬件加速功能验证问题的DAG划分算法

功能验证是超大规模集成电路(very large scale integration, VLSI)设计的一个基本环节. 随着超大规模电路的普及与发展, 在单处理器上对整个电路进行功能验证在可行性和效率上都存在较大的缺陷. 基于硬件加速器的功能验证是将整个电路划分成若干个规模更小的子电路; 然后在多个硬件处理器上并行的执行功能验证. 当电路划分结果的并行性较优时可提高功能验证的效率, 缩短时间周期. 类似电路设计中的其他划分问题, 用于硬件加速功能验证的电路划分问题可以被抽象成图划分问题. 相较于传统图划分问题, 硬件加速功能验证的划分问题还需要保证较小的模拟深度和较高的调度并行性. 为了满足硬件加速功能验证的划分需求, 提出了一种基于传统多级图划分策略的有效算法. 该算法结合调度思想, 利用电路的关键路径信息和时序信息, 将硬件加速功能验证问题转化为有向无环图的多级划分问题. 随机电路网表数据的实验结果表明, 所构造的算法可以有效的减少关键路径长度并且不会引起切边数的增长恶化.     

基于任务复制的分簇与调度算法

针对并行与分布式系统中相关任务的静态调度问题,以最小化调度长度为主要目标,以减少资源数为次要目标,对待复制的重要祖先集定义了新的选择策略,提出了基于任务复制的动态关键前驱调度算法.改进了粒度的定义,证明了对任意DAG,算法有优于前人的性能下界.实验结果优于典型任务复制算法,特别是对经典EZ算例的解(调度长度为8)好于前人认为的理论最优解(调度长度为8.5),并证明了新的解为最优解.定义了DAG的补图,讨论了不允许任务复制时树型DAG的2-优度算法.