异构机群系统上并行计算双序列的最长公共子序列*

针对处理机节点具有不同计算速度、不同通信能力的情况,考虑计算和通信启动开销,给定处理机分配顺序,基于可分负载理论,提出一种存储受限异构机群系统的序列串最优分配线性规划模型,给出相应的序列串最优分配方法。实验结果表明,基于最优序列串分配方法的双序列最长公共子序列并行算法优于平均分配序列串算法,获得了较好的加速,并具有良好的可扩展性。     

异构机群系统中的最优处理机分配算法

在异构机群系统的并行计算中，处理机结点的划分及并行子任务在处理机上的映射将直接影响到应用程序并行计算的性能。本论文将通过对影响并行计算性能的主要参数的分析，提出一个基于人工智能Ａ算法的最优处理机分配算法，为高性能的异构机群系统并行计算提供理论支持。     

异构机群系统上近似串匹配并行算法

基于可分负载理论的最优原则,在假定正文串分配顺序固定的前提下,考虑处理机节点具有不同计算速度、不同通信能力的情况,提出一种异构机群计算环境下的最优正文串分配策略,给出最优正文串分配的闭合解。对于节点具有不同计算速度、通信能力、存储容量的异构机群系统,建立正文串最优分配的线性规划模型。针对几种特殊情况讨论正文串的最优分配顺序。实验结果表明,与平均分配正文串策略以及按照从处理机能力分配正文串策略相比,利用该策略进行近似串匹配并行处理所需时间分别缩短了10%~40%和5%~20%。     

存储受限异构机群系统的多目标串近似匹配并行算法

针对处理机节点具有不同的计算能力、通信延迟和存储容量的情形,考虑计算和通信启动开销,给定处理机分配顺序,基于可分负载理论,分别建立单层和两层树结构模型的存储受限异构机群系统的目标串最优分配线性规划模型,给出相应的目标串最优分配方法,并讨论了处理机最优分配顺序.实验结果表明,本文提出的基于最优分配方法的多目标串近似匹配并行算法优于平均分配算法,获得了较好的加速并具有良好的可扩展性.     

基于大规模序列比对软件的并行优化方案

基于基因电脑克隆软件SiClone和可变剪接分析软件AltSplice的并行优化工作，提出一种基于大规模序列比对软件的并行优化方案。该方案对所要进行比对分析的大规模序列库按某种策略进行分割部署，使机群中每个节点处理整个序列库的一部分，可有效减少磁盘I／O和节点间通信开销，适合低价高效的Linux机群系统。     

Mesh网均等分区策略

在大规模并行计算机系统中，处理机资源可能被多个用户作业竞争，操作系统必须采用一种处理机分配策略确定多少和哪些处理机分配给一个作业。文中针对大规模、消息通信并行计算机提出了矩形和非矩形两种处理机分配策略，这两种策略均满足对每个用户所分配处理机数的公平性以及处理机分配的邻近性。     

异构机群上高效可扩展的Motif发现并行算法

在节点具有不同计算速度、不同通信能力的异构机群系统上,分别建立求解l≤16和l>16的Motif发现问题的最优序列分配模型,在此基础上设计实现融合投票和统一投影-邻居阈值思想的Motif发现并行算法。实验结果表明,给出的基于最优序列分配策略的Motif发现并行算法具有良好的加速和可扩展性,优于采用平均分配策略的Motif发现并行算法。     

一种基于蚁群算法的生物序列并行比对方法

生物序列比对是生物信息领域的重要课题,比对结果的合理性和正确性关系到基于比对结果研究的正确性。在保证正确性的前提下利用并行计算充分挖掘计算潜力对提高比对效率有重要意义。针对双序列的全局比对问题,提出了基于蚁群算法的双序列比对并行化方案。对耗时最多的搜索比对路径和信息素更新两个步骤给出了基于共享内存模型的并行化方法。"天河二号"上OpenMP实验结果表明,8线程并行情况下,加速比可达5.03,且序列越长性能越高。     

基于机群环境的并行多连接存储分布技术

基于机群系统的数据存储分布是并行数据库领域的一个重要问题。已有的研究工作多集中在基于单个关系的存储分布,不能有效支持复杂多连接查询处理。文章提出了多个关系整体分布方法,给出分布属性选择和处理机分配算法。实验结果表明,算法具有良好的性能,有助于提高并行多连接查询效率。     

二进制文件结构化比较的并行算法实现

为了提高二进制文件结构化比较的效率，提出了一种基于全局地址空间编程模型实现的并行结构化比较算法，将整个结构化比较过程分为并发获取比对信息和并行结构化比较两个子模块。该算法充分利用UPC语言的亲缘性特征，将共享访问私有化，减少通信开销。并通过有效的负载平衡方法，在机群系统上实现了该并行程序。实际数据的测试结果表明，此并行算法是高效的而且可扩展性较好。     

异构机群系统上基于多轮分配方式的近似串匹配并行算法

在给定正文串分配轮数的前提下,考虑处理机节点具有不同计算速度、不同通信能力的情形,根据从处理机是否允许重叠执行计算和通信操作,提出异构机群计算环境下的最优正文串多轮分配策略;同时提出一种周期性的正文串多轮分配策略并给出了相应的正文串多轮分配的闭合解,此策略可以求出最优的分配轮数.实验结果表明,正文串多轮分配策略比正文串单轮分配策略大大缩短了近似串匹配并行处理的时间,并且在正文串多轮分配策略中,当近似串匹配应用的规模较小时,分配轮数比参与近似串匹配并行处理的从处理机数更能影响近似串匹配并行处理的完成时间,反之,从处理机数对近似串匹配并行处理的完成时间影响更大.     

异构机群系统上带返回信息的可分负载多轮调度算法

针对处理机具有不同的计算速度、通信能力的异构机群计算环境,以及实际应用中许多问题的求解在处理完任务后向中心处理机节点返回处理结果信息的情形,通过允许计算和通信操作重叠执行,采取FIFO调度策略和多次并行分配计算任务的方法,提出一种带返回结果信息的调度轮数可变的可分负载多轮调度算法.实验结果表明,该算法对于处理具有返回结果信息的应用的调度性能优于UMR可分负载多轮调度算法,并且可以获得近似最优的调度轮数.     

多核机群上通信高效的整数序列并行排序方法

建立一个适用于整数序列排序的数据分配模型,在多核计算节点组成的异构机群上设计通信高效的整数序列并行算法。所提出的数据分配模型依据机群中各节点不同的计算能力、通信速率和存储容量,动态计算出调度分配给各节点的数据块的大小以平衡各个节点的负载。所设计的并行排序算法利用整数序列的特性,主节点采取两轮分发数据与接收结果的方法,从节点运用分桶打包方式返回有序的整数子序列给主节点,主节点采用桶映射方法将各个有序子序列直接整合成最终有序序列,以减少需要耗费较多通信时间的数据归并操作。分析与实验测试结果表明,给出的多核机群上的整数序列并行排序算法高效,具有良好的可扩展性。     

基于异构Flink集群的节点优先级调度策略

Flink流处理系统默认的任务调度策略在一定程度上忽略了集群异构和节点可用资源,导致集群整体负载不均衡。研究分布式节点的实时性能和集群作业环境,根据实际作业环境的异构分布情况,设计结合异构Flink集群的节点优先级调整方法,以基于Ganglia可扩展分布式集群资源监控系统的集群信息为依据,动态调整适应当前作业环境的节点优先级指数。基于此提出Flink节点动态自适应调度策略,通过实时监测节点的异构状况,并在任务执行过程中根据实时作业环境更新节点优先级指数,为系统任务找到最佳的执行节点完成任务分配。实验结果表明,相比于Flink默认的任务调度策略,基于节点优先级调整方法的自适应调度策略在WorldCount基准测试中的运行时间约平均减少6%,可使异构Flink集群在保持集群低延迟的同时,节点资源利用率和任务执行效率更高。     

异构集群系统的可分负载多轮调度算法*

针对更实际的异构集群计算环境,充分考虑处理机具有不同的计算速度、通信能力和存储容量的特性,通过允许计算和通信操作重叠执行,采取多次并行分配计算任务的方法,设计一种可分负载多轮调度算法。实验结果表明,该算法不但能获得与均匀多轮调度(UMR)算法相当的渐近最优调度时间长度,并且能够处理更大规模的应用负载,实用性更强。     

基于DDS的异构网络数据分发方法研究

在异构网络环境中,数据实现高效、可靠与安全的分发,面临着不同的应用环境对操作系统、通信方式、网络协议以及服务质量（ QoS）的多种要求。文中设计了一种基于DDS的,在异构网络通信中使用的数据分发系统。针对异构网络与DDS的特性,提出了异构网络数据分发系统的三层组织结构,并对每一层的具体内容,要实现的功能进行了研究。经过对异构网络中所传递的数据进行分析,结合OpenDDS本身的QoS策略推出该系统本身的QoS策略。最后,通过实验对该数据分发系统的网络延迟以及时延抖动进行了测试,表明了该系统能够有效满足异构网络之间的数据分发需求。     

异构传感器网络中一种基于局部簇的分簇算法

为了降低异构传感器网络中节点间的通信代价及网络能耗,首先基于分解和组合数学原理提出了局部簇的概念,使节点的工作仅局限于一个簇内而非整个网络。然后,在局部簇内又提出了一种新的分簇算法:根据节点能量异构特征选择簇首,簇首除首轮由基站选出外,其他轮数均由前一轮中的簇首节点来确定;数据传输采用混合拓扑的网络结构,簇内同构节点可直接相互通信;引入了簇维护策略,维持簇的工作状态。仿真结果表明,基于局部簇的分簇算法明显减少了簇首的能耗,降低了整个簇的能耗。鉴于簇的局部性和独立性,显而易见新算法可以有效降低整个异构传感网络的能耗。