Spark环境下基于子图的异步迭代更新方法

全局同步计算模型简单易用,但是路障同步导致收敛速度变慢。以顶点为中心的异步迭代虽然提高了收敛速度,但在计算节点之间需要频繁发送信息。在Spark环境下提出一种基于子图的异步迭代更新方法。在子图之间建立异步消息通信连接后,子图能以异步方式发送数据块;通过多线程同步避免数据读写冲突,保证异步更新时顶点状态的一致性。在大规模样本数据集上分别从收敛结果、收敛速度和通信代价验证方法有效性。实验结果表明,与全局同步迭代相比,该方法有效提高了计算收敛速度。与顶点为中心的异步更新方式相比,该方法在收敛时间上略有增长,但是显著降低了通信开销。     

Asyn-SimRank：一种可异步执行的大规模 SimRank 算法

SimRank 算法利用网络结构来评估网络中任意2点的相似性,它被广泛应用于社交网络和链接预测等诸多领域中．近年来,随着大数据技术的发展,SimRank 算法处理的数据不断增大,人们利用MapReduce 等分布式计算模型设计实现分布式的大规模 SimRank 算法来适应大数据处理的需求．但是,由于 SimRank 算法包含开销较大的迭代过程,每次迭代之后都需要一个全局同步,且每次迭代的计算复杂度高、通信量大,SimRank 算法不能在分布式环境下高效地实现．1）提出 Asyn‐SimRank 算法,该算法采用迭代‐累积的方式完成迭代计算,异步执行 SimRank 的核心迭代过程,避免了大规模分布式计算中的大量同步开销,同时有效降低计算量并减少通信开销;2）提出关键点优先调度计算,提升了 Asyn‐SimRank 算法的全局收敛速度;3）证明了 Asyn‐SimRank 算法的正确性和收敛性以及关键点优先调度计算的有效性;4）支持异步迭代的分布式框架 Maiter 上实现了 Asyn‐SimRank 算法．实验结果显示,相比较于 Hadoop ,Spark 上实现的 SimRank 算法和 Delta‐SimRank 算法,Asyn‐SimRank 算法大大提升了算法的计算效率,加速了算法收敛．     

图数据库中基于GPU的图分析计算方法

现有的图数据库对于在线分析操作大多采用基于CPU的分布式图计算引擎（如GraphX）,但CPU核心数量有限的不足会导致计算效率低下,同时集群间的同步也会产生额外的通信开销。通过使用图形处理单元（GPU）对图计算进行加速,设计并实现图处理系统RockGraph。该系统能够根据用户需求从图数据库中提取出包含核心信息的子图,经过数据格式转换后,利用JNI工具调用动态链接库,采用超显存GPU图计算框架进行在线分析,并将计算结果写回图数据库。实验结果表明,与基于CPU的分布式图计算系统相比,RockGraph的图分析效率可提高3倍~5倍。     

大数据下基于异步累积更新的高效P-Rank计算方法

P-Rank是SimRank的扩展形式,也是一种相似度度量方法,被用来计算网络中任意两个结点的相似性.不同于SimRank只考虑结点的入度信息,P-Rank还加入了结点的出度信息,从而更加客观准确地评价结点间的相似程度.随着大数据时代的到来,P-Rank需要处理的数据日益增大.使用MapReduce等分布式模型实现大规模P-Rank迭代计算的方法,本质上是一种同步迭代方法,不可避免地具有同步迭代方法的缺点:迭代时间(尤其是迭代过程中处理器等待的时间)长,计算速度慢,因此效率低下.为了解决这一问题,采用了一种迭代计算方法——异步累积更新算法.这个算法实现了异步计算,减少了计算过程处理器结点的等待时间,提高了计算速度,节省了时间开销.从异步的角度实现了P-Rank算法,将异步累积更新算法应用在了P-Rank上,并进行了对比实验.实验结果表明该算法有效地提高了计算收敛速度.     

并行分布计算中的任务调度问题（二）

在并行程序设计中,SPMD是最为常用的一种编程模式,该模式下的任务调度有其自身的一些特点,本文首先讨论了如何用闭式表达式来决定该执行模式下的最佳处理器数。然后,针对任务图存在的不确定性,介绍了采用动态技术进行任务调度的一般方法。由于动态调度会带来额外开销,因此有效的动态调度方案必须结合实际具体的并行程序和硬件系统。为了减少动态调度开销,对于一些含有不确定性的任务图,也可通过任务图归约技术,先把不确定性转换为确定性,然后再利用静态调度方法,本文我们主要讨论了条件分支语句的静态调度问题。另外,并行循环的调度分配是影响并行程序执行性能的一个重要因素,在本文的最后我们结合独立循环、相关循环、均匀循环和非均匀循环的调度分配问题,着重讨论了基于循环分配的自适应混合调度方法,以及变循环传递相关为循环独立相关的循环展开(un-rolling)技术。     

分布式序列模式发现算法的研究

提出算法FDMSP(fast distributed mining of sequential patterns),以解决分布式环境下的序列模式挖掘问题.首先对分布式环境下序列模式的性质进行了分析.算法采用前缀投影技术划分模式搜索空间,利用序列模式前缀指定选举站点统计序列的全局支持计数,利用局部约减、选举约减、计数约减等方法减少候选序列数,同时将算法分为3个子过程异步运行,使得算法具有较低的I/O开销、内存开销和通信开销,从而高效地生成全局序列模式.实验结果显示,在具有海量数据的局域网环境中,FDMSP算法的性能优于将数据集中后采用GSP算法68.5%～99.5%,并且FDMSP算法具有良好的可伸缩性.     

遗传优化的混合网格计算调度模型SCE部署研究

网格计算涉及的资源通常存在区域和组织差异,涉及的作业(Job)则存在数据和计算两种密集类,针对具有混合特征的网格计算,提出了基于SCE中间件的遗传优化网格作业调度算法.首先分析了具有不同密集类型Job的混合网格计算模型,得到作业与资源的属性表示,以及作业调度与资源之间的约束关系.然后根据混合网格计算模型分析,将其转化成约束条件下的最优解问题,引入改进遗传算法进行求解.在种群初始化时根据适应性筛选出一部分样本作为初始种群,利用高质量样本启发寻优,降低进化代数;同时针对每个染色体的作业执行速度和染色体内每个作业的执行速度依次设计适应性,从而加速收敛;通过适应性修正、交叉和变异处理,防止种群出现过早或者局部收敛,并且增加种群多样性.最后基于SCE部署作业调度,从中间件进一步提升作业调度效率,减少出错.实验结果表明,基于SCE中间件的遗传优化网格作业调度算法能够有效抑制执行错误的发生,提升作业调度与资源配置的效率,降低作业调度响应时间.     

基于分布式数据集的并行计算框架内存优化方法

随着科学计算和人工智能技术的快速发展，分布式环境下的并行计算已成为解决大规模理论计算和数据处理问题的重要手段。内存容量的提高以及迭代算法的广泛应用，使得以Spark为代表的内存计算技术愈发成熟。但是，当前主流的分布式内存模型和计算框架难以兼顾易用性和计算性能，并且在数据格式定义、内存分配、内存使用效率等方面存在不足。提出一种基于分布式数据集的并行计算方法，分别从模型理论和系统开销两个角度对内存计算进行优化。在理论上，通过对计算过程进行建模分析，以解决Spark在科学计算环境下表达能力不足的问题，同时给出计算框架的开销模型，为后续性能优化提供支持。在系统上，提出一种框架级的内存优化方法，该方法主要包括对跨语言分布式内存数据集的重构、分布式共享内存的管理、消息传递过程的优化等模块。实验结果表明，基于该优化方法实现的并行计算框架可以显著提升数据集的内存分配效率，减少序列化/反序列化开销，缓解内存占用压力，应用测试的执行时间相比Spark减少了69%～92%。     

异构计算环境下基于优先队列划分的调度算法

人工智能的飞速发展对高性能计算提出了更高的要求,异构计算环境下任务调度问题一直是高性能计算中的关键问题.本文提出一种基于优先队列划分的调度算法(PQDSA),该算法根据DAG(有向无循环图)任务集的入口节点数量确定优先队列数,通过任务的通信开销和计算开销划分任务队列,进而将关键节点任务分配给合适的队列,以产生效果较佳的任务调度队列,从而提高任务间的并行性,降低任务集的完工时间.与此同时,进一步基于插入策略将任务调度到处理器上,使任务调度更加高效地执行.PQDSA算法可以减少任务间的时间消耗,提高处理器的调度效率.通过与两个经典算法的性能对比,实验结果表明本文提出的PQDSA算法在任务完工时间和调度效率方面都要明显优于对比的算法.     

基于框架的虚拟计算环境关键技术研究

通过分析目前几种虚拟计算环境的现状、特点及适用范围,针对中小规模、异构零散的的计算需求,提出一种基于框架技术的虚拟计算环境的实现方法,并结合框架技术设计了分层服务模型.基于复杂多样的、性能差距明显的计算资源的调度问题,提出了一种基于对等模式的随机自适应调度算法.该算法提供对关联任务的调度,适合异构的、资源规模较大的环境,尤其是计算资源差异明显的异构计算环境.实现了基于框架技术的虚拟计算原型系统,并通过实验测试对比算法的调度性能,最后将计算环境应用于实际的地震资料处理中.     

一种新的Web集群请求调度模式与体系结构

分析了网络及Web应用的发展对Web集群请求调度提出的新要求,在此基础上提出了一种基于文档组织分布的新请求调度模式.针对该请求调度模式的特点,提出了一种分布调度、分布路由的Web集群体系结构,该结构结合了多分配器集群和分布式集群的优点,能保证系统的可扩展性,并能有效减少集群内的通信开销和消除单点故障.     

面向空天地一体化信息网络的边缘计算资源融合管理方法

随着空天地一体化信息网络的建设与发展，无线网络的全球无缝覆盖与泛在的人工智能成为了可能.卫星与无人机作为天基边缘计算节点，辅助地面设备完成各项任务，成为6G网络中的重要应用场景.当前针对卫星、无人机边缘计算的研究处于起步阶段，这些研究在边缘计算服务模式及实际应用方面仍有待进一步深入.单个卫星或无人机的计算能力薄弱，通常难于独立提供较复杂的数据处理服务.现有资源管理算法通常需要多轮博弈才能收敛，难于满足空天地一体化场景中资源管理方法快速收敛的需求.针对以上挑战，本文在天算星座边缘计算服务场景基础上，对空天地一体化网络中天基资源的服务模式进行了分析，提出了组合及聚合两种计算服务融合方式.本文将天基边缘计算资源的管理建模为两阶段的斯坦科尔伯格博弈模型，提出了分布式混合动态迭代算法与分布式分组动态迭代算法，加快了博弈过程的收敛速度.本文基于分布式场景构建了仿真实验，并在典型参数设置下对算法性能进行了分析.仿真实验结果表明：在两种不同服务模式下，本文提出的方法能够使空中边缘计算节点与用户设备获得最大收益;相比近年相关研究，本文所提方法的收敛时间能够缩短60%以上.     

RoCE协议下基于在网计算的MPI通信优化

高性能计算中,通信上的巨大开销已成为其算力提升的主要瓶颈之一,通信性能的优化一直是一个重要挑战.针对通信优化任务,提出一种基于在网计算技术降低通信开销的方法.该方法在基于以太网的超算环境下,利用RoCEv2协议、可编程交换机以及OpenMPI,实现将归约计算卸载到可编程交换机,支持Node和Socket两种通信模式.在真实超算环境下开展了集合通信基准测试和OpenFOAM应用测试实验,结果表明,当服务器节点数达到一定规模时,该方法在Node和Socket两种模式下相较于传统的主机通信,均呈现出较好的性能提升,其中集合通信基准测试有10%–30%左右性能提升,在应用级测试中应用整体性能有1%–5%左右提升.     

基于蚁群遗传算法的网格资源调度研究

传统的资源调度算法在网格环境下存在一定缺陷,如不能很好地平衡资源节点的负载,不能很好满足用户服务质量需求等.为了提高网络质量,应用遗传算法全局快速收敛的优点,将遗传算法融入到蚁群算法的每一次迭代中,使之具有很强的全局搜索能力,以加快算法的收敛速度,提出了在价格机制驱动下,应用蚁群遗传算法进行网格资源调度的算法.仿真实验结果表明,在价格机制驱动下,应用蚁群遗传算法进行网格资源调度可以减少系统总执行时间和任务完成时间,系统负载均衡度好,提高了资源调度效率,在网格环境下,算法具有稳定性和高效性.     

计算网格中动态负载平衡的分布调度模式

网格计算下对资源进行有效的管理和调度可以提高系统的利用率.在对现有若干调度方法的研究和分析基础上,针对计算网格中的负载平衡问题,提出了一种分布式网格作业调度模型,并给出相关算法.算法通过建立主从模式的负载信息收集机制,提供给节点全局负载信息,加速重负载节点的负载转移速度.通过有效的负载平衡模式,解决资源调度中负载平衡及其可靠性问题.     

基于EDA的并行基因表达式程序设计方法

将分布评估算法(EDA)引入基因表达式程序设计方法中,以提高其收敛速度。为减少计算时间,提高解质量,在加入EDA的基因表达式程序设计方法的基础上设计了同步和异步分布式并行算法,同时比较了同步和异步并行算法。实验结果表明,并行算法提高了运行速度和解质量。最后通过实验分析了迁移代频对并行算法的影响。     

基于树型Petri网的网格资源调度模型

讨论树型网格环境下独立任务的调度问题,把网格资源计算能力和网络通信速度的异构资源调度问题转化为线性规划问题。提出网格资源调度的树型Petri网模型,基于速度优先的启发式资源调度算法对树型Petri网模型进行性能分析,验证了树型Petri网的单口模式传输特点。     

动态划分序列模式挖掘算法

在对海量数据进行序列模式挖掘时,由于产生的候选序列数量大并且需要反复遍历数据库,会带来存储受限及时效性问题.为此,基于无共享分布式环境,提出一种动态划分序列模式挖掘算法DPSPM.通过分布数据降低数据库扫描的规模,降低I、O开销,使用分派函数指定选举节点,降低通信开销,设计动态列表存储候选序列,降低内存开销,多个子过程异步运行,提高算法的执行效能.实验结果表明,DPSPM算法在较小支持度情况下对中大型数据库有较好的搜索效率.     

分布式电网经济调度及其多目标优化模型研究

为克服传统经济调度的目标单一,计算量大,优化不力等诸多不足导致模型适用的困难,从电网分区和协调计算的角度建立了基于多目标优化的分布式电网经济调度模型.该模型同时考虑了由售购电价差引起的经济效益最大,机组运行能耗最少和污染气体排放最小等三个目标函数.重点阐述了一种基于近似牛顿方向的多区域分布式计算方法,并利用改进的距离差分进化算法用于各个分区内的独立优化计算,然后采取异步迭代的信息同步机制实现了全局的等值修正计算.最终算例表明了该方法能够在分布式电网经济调度的优化计算过程中取得良好的应用效果.     

GPU加速分子动力学模拟中的电荷分布计算

在集群与GPU组成的异构并行计算平台上,使用MPI+CUDA混合编程模型,实现基于ABEEMσπ模型的分子动力学模拟中电荷分布的计算.通过对电荷分布分布求解中的计算部分移植到GPU上进行,并针对算法中通信开销大和资源未充分利用的问题,通过异构平台的异步并发方法进行优化,提高了求解效率.性能测试结果表明,相比于单纯MPI并行算法,优化后GPU加速的异构并行算法,在化学大分子模型电荷分布计算上,有着明显的性能优势.