分布式并行计算环境下混合遗传算法的研究

为提高混合遗传算法的计算效率和求解质量,提出一个并行混合遗传算法框架。该框架主要由遗传算法、小生境操作和单纯形3部分组成,遗传算法和小生境操作采用串行执行方式,单纯形采用分布式并行执行方式。分布式并行计算环境由4台计算机通过交换机连接构成,并设计了一个动态任务调度方案。一个典型工程算例验证了新算法的有效性,并且在分布式并行环境下取得了较好的加速比和并行效率。     

道路网中的移动对象连续K近邻查询

已有道路网中的连续k近邻查询处理算法采用增量式的查询处理机制,当数据频繁更新时性能急剧下降.结合多核多线程技术,提出了一种基于多线程的连续查询处理框架.该框架周期性重计算所有查询结果,将查询处理分为顺序执行的数据更新阶段和查询执行阶段,分别使用任务并行和数据并行的方法执行各阶段的操作.设计了数据更新阶段使用的数据结构,提出了查询处理阶段的k近邻查询处理策略,包含离线预计算和在线k近邻查询处理算法两个部分.对k近邻算法复杂性及多线程处理框架的加速比进行了理论分析.实验结果表明,提出的算法在数据频繁更新下,串行执行时性能优于已有算法,而基于多线程处理框架的并行执行在任何参数配置下性能均优于已有算法;且基于多线程处理框架的并行执行具有较好的性能扩展性,加速比可以达到1.51～1.7.     

蚁群算法解决TSP问题的并行化研究与实现

蚁群算法在处理大规模TSP(Traveling Salesman Problem)问题时耗时较长,为了解决这一不足,给出一种基于多核环境下的并行优化算法.采用OpenMp并行优化技术对蚁群算法中最为耗时的循环迭代和循环赋值部分进行改进,减少其运算时间,同时利用粗粒度并行策略和PC机多核的优势将具有一定规模的小蚁群分配到对应的处理器上,使其并行执行,并且在适当时机让各处理器上的蚁群进行相互间的通信.通过实验证明,改进后的并行蚁群算法程序执行时间明显缩短,执行效率显著提高.由此可见,改进后的并行蚁群算法是可行有效的.     

区块链智能合约交易并行执行模型综述

以太坊等区块链采用串行方式执行区块中的智能合约交易,虽能严格保障执行后节点间区块链状态的一致性,但这已成为目前制约区块链吞吐率的一个重要瓶颈.因此,采用并行方法优化智能合约交易的执行逐渐成为工业界和学术界关注的重点.总结了区块链智能合约并行执行方法的研究进展,提出了一个研究框架,该框架以智能合约并行执行的阶段为视角,凝练出4种智能合约并行执行模型,即基于静态分析的并行执行模型、基于动态分析的并行执行模型、节点间并行执行模型和分治并行执行模型,然后描述了每种模型下典型的并行执行方法.最后,对交易依赖图和并发控制策略等影响并行执行的因素进行了讨论,并提出了未来可研究的方向.     

MapReduce下连续泊位分配系统

针对传统串行环境下码头连续泊位分配算法在船数大于七条时,算法的执行效率明显降低、资源占用量显著增加.首次设计了基于分布式环境下连续泊位分配系统总体架构和软件架构;提出了基于Hadoop平台下连续泊位分配系统开发环境的搭建,分布式环境下码头泊位分配系统组件设计与部署以及分布式环境下基于MapReduce改进连续泊位分配算法的关键技术;最后实现了分布式环境下连续泊位分配系统.实验结果表明,该系统可以有效的提高连续泊位分配问题的执行效率.     

一种基于粗粒度-主从式的混合并行遗传算法

为了解决串行遗传算法的收敛速度和早熟问题．人们开始研究遗传算法的并行执行，并取得了很好的结果。本文提出了一种基于分布式集群环境的层次结构(粗粒度一主从式)的并行遗传算法一混合并行遗传算法。仿真表明，采用混合并行遗传算法可以有效的提高优化的速度和解的精度。     

基于多核CPU的表约束并行传播模式研究

并行传播是并行约束程序领域中的一个研究方向,其研究内容是如何并行执行在约束上的过滤算法.根据维持表约束网络广义弧相容（generalized arc consistency,简称GAC）的串行传播模式,提出了维持表约束网络临时广义弧相容（temporary generalized arc consistency,简称TGAC）的并行传播模式,该模式基于多核CPU,由并行传播算法和并行过滤算法两部分组成;之后,给出了并行传播模式的可靠性证明,而且通过对并行传播模式的最坏时间复杂度分析,可以认为并行传播模式在平均过滤时间较长的实例上要快于串行传播模式;最终的实验结果也验证了上述结论,并行传播模式在多数实例集上取得了从1.4~3.4不等的加速比.     

基于分布式协调系统的并行频繁模式增长算法的优化

频繁模式挖掘可以发现数据中频繁出现的模式,是关联规则挖掘的重要步骤。并行频繁模式算法将其应用到并行环境中,以对海量数据进行挖掘。在Apachc软件基金会的Mahout项目实现的基础上,对计数和排序阶段以及算法的执行顺序提出了新的优化策略。优化后的设计将计数信息存储在分布式协调系统上,充分地利用了分布式协调系统的高可用性、适宜存储元数据信息的特点。该设计减小了小文件在分布式文件系统(HDFS)上的开销,同时保留了其优点,还能使计数过程和排序过程并行执行,减小了计算节点的内存开销。对比了文件系统I/O的开销,并分析了实现设计中的难点,为未来的工作打下了基础。     

基于层次空间聚类的表语义汇总算法

频繁模式挖掘可以发现数据中频繁出现的模式,是关联规则挖掘的重要步骤。并行频繁模式算法将其应用到并行环境中,以对海量数据进行挖掘。在Apache软件基金会的Mahout项目实现的基础上,对计数和排序阶段以及算法的执行顺序提出了新的优化策略。优化后的设计将计数信息存储在分布式协调系统上,充分地利用了分布式协调系统的高可用性、适宜存储元数据信息的特点。该设计减小了小文件在分布式文件系统(HDFS)上的开销,同时保留了其优点,还能使计数过程和排序过程并行执行,减小了计算节点的内存开销。对比了文件系统I/O的开销,并分析了实现设计中的难点,为未来的工作打下了基础。     

基于CUDA的直升机旋翼桨叶挥舞角快速测量方法

针对基于立体视觉的直升机旋翼桨叶挥舞角测量CPU串行算法耗时多、效率不高的问题,利用图像处理单元(GPU)并行计算的优势,提出一种基于CUDA统一计算设备构架的并行处理快速算法.首先,对算法中最耗时的图像去噪、阈值分割、连通域标记三部分进行并行化设计;然后,采用多层次并行策略将大量密集运算分配到不同的图像处理单元上并行执行,利用共享内存和共享寄存器加速数据访问;最后,进行多次测量实验,结果表明该方法执行效率明显高于CPU串行方法,可满足旋翼桨叶挥舞角快速测量的要求.     

一个有效的并行分析算法

并行分析在并行编译系统中有着很重要的作用,它的优劣直接影响到编译系统的成败,随着机群系统及其并行开发环境的发展,多数的并行系统可支持多重并行循环的运行。而对只支持一重并行循环的编程系统,选择并行运行效率最高的循环,也是很重要的。为此,本文提出了一个有效的循环并行分析方案,它不但能给出多层循环的并行性,而且能够处理绝大部分实际应用中的并行性问题,本文对传统的并行分析算法进行修改,并给出了一个有效的并     

基于双向并行灾变粒子群优化算法的城市环路交通协调控制系统

根据我国部分城市道路网包含多条环路的特点，设计了一种双向并行灾变粒子群优化算法的城市环路交通协调控制系统。该系统以路网中的闭合环路作为控制子区，采用三层递阶分布式结构和双向并行灾变粒子群优化，分阶段优化控制周期、相位差和绿信比，并对不同闭合环路进行协调控制形成预选方案。通过系统设定的面控率进行判断、选择，最终确定信号控制方案。示例验证结果表明该控制系统能有效减少区域车辆总延误，减少停车次数。     

A consistent generation of pipeline parallelism and distribution of operations and data among processors

The problem of mapping affine loop nests onto parallel computers with distributed memory is considered. A technique for algorithm scheduling and distributing operations and data over processors is proposed. This technique makes it possible to generate pipeline parallelism and minimize the amount of data exchanges between the processors. The method is adapted for automation and explicitly allows for dependence on outer variables of loops.     

分布存储系统中优化通信的冗余计算分割

针对并行循环套序列，提出一种冗余计算分割的通信优化方法，根据数据流分析，文中给出用以确定每个循环套的冗余计算量的一般方法，并在此基础上提出冗余计算分割的实现和判定，针对规则依赖的程序，该文还提出了一个高效的冗余计算分割的实现方法，该技术已经在一个并行编译器中实现，试验结果表明，它比传统的通信优化技术有明显的优越性。     

测试任一嵌套DO循环置换合法性的阻碍矩阵算法

对程序进行并行变换是提高程序并行性的有效手段，许多并行变换都要寻找一种最优的循不置换，在寻找过程中，如果对每一个被考察的置换都重新进行相关性测试，那么整个寻找过程将极费时间，本文给出了一个测试嵌套循环任一置换的阻碍矩阵测试算法，它将测试一循环置换的合成法性转化为测试一组向前置换的合法性，并且仅需要嵌套循循环做一遍相关性测试，利用该算法可以简便迅速检查任一循环置换的合法性，从而使许多并行变换变得实际可     

A Loop Transformation Algorithm for Communication Overlapping

Overlapping communication with computation is a well-known approach to improving performance. Previous research has focused on optimizations performed by the programmer. This paper presents a compiler algorithm that automatically determines the appropriate loop indices of a given nested loop and applies loop interchange and tiling in order to overlap communication with computation. The algorithm avoids generating redundant communication by providing a framework for combining information on data dependence, communication, and reuse. It also describes a method of generating messages to exchange data between processors for tiled loops on distributed memory machines. The algorithm has been implemented in our High Performance Fortran (HPF) compiler, and experimental results have shown its effectiveness on distributed memory machines, such as the RISC System/6000 Scalable POWERparallel System. This paper also discusses the architectural problems of efficient optimization.     

Quantum loop programs

Loop is a powerful program construct in classical computation, but its power is still not exploited fully in quantum computation. The exploitation of such power definitely requires a deep understanding of the mechanism of quantum loop programs. In this paper, we introduce a general scheme of quantum loops and describe its computational process. The function computed by a quantum loop is defined, and a denotational semantics and a weakest precondition semantics of a quantum loop are given. The notions of termination and almost termination are proposed for quantum loops. This paper only consider the case of finite-dimensional state spaces. Necessary and sufficient conditions for termination and almost termination of a general quantum loop on any mixed input state are presented. A quantum loop is said to be (almost) terminating if it (almost) terminates on any input state. We show that a quantum loop is almost terminating if and only if it is uniformly almost terminating. It is observed that a small disturbance either on the unitary transformation in the loop body or on the measurement in the loop guard can make any quantum loop (almost) terminating, provided that some dimension restriction is satisfied. Moreover, a representation of the function computed by a quantum loop is given in terms of finite summations of matrices. To illustrate the notions and results obtained in this paper, two simple classes of quantum loop programs, one qubit quantum loops, and two qubit quantum loops defined by controlled gates, are carefully examined, and to show their expressive power, quantum loops are applied in describing quantum walks.     

选择性循环的并行方法

针对含有大量循环的串行程序存在的问题,提出一种基于线程级前瞻技术的循环选择方案。该方案对循环进行最优选择后建立一个可并行运行的循环集。对于该集合中的循环,选择并行效率高的代码段作并行处理,以加快串行程序运行速度。实验表明,相对于一般的简单内部循环或外部循环并行方法,该方案使9种基准代码的加速比平均上升23.8%,从而提高串行程序并行运行的效率。     

网络环境下不敏感系统的分布式区域预测控制方法

针对二分图网络结构下的不敏感系统的可控性比较差的问题,本文提出了带有区域控制的分布式模型预测控制方法.该方法首先利用分支定界法对分布式控制系统结构进行最优设计;然后,结合区域控制提高控制系统的动态性能指标;最后,依据回路之间的关联性的强弱选择每个回路的控制方式(精确控制或区域控制).仿真结果显示带有区域控制的分布式预测控制系统的调节时间比没有带区域控制的分布式控制系统明显缩短;同时,通过对回路控制方式的选择增加了精确控制的智能体数量.仿真结果证明了利用分布式区域预测控制方法可以提高系统的容错性,通过对系统的可控性和关联性进行分析,可以在精确控制和区域控制之间寻找到最优组合,从而达到快速精确的控制效果.