ZH算法的性质及一种新视角分析

文献［1］提出的MSP问题是一个NP完全问题。为了求解MSP问题,文献［1］给出了ZH算法。本文以ZH算法为研究对象,剖析ZH算法主要过程,从新的角度解读其作用,给出并证明ZH算法的两条重要性质——顶点边集守恒性质和顶点边集存在性质。对算法过程和作用的新视角分析为MSP问题的研究提供重要参考,ZH算法的重要性质也为算法的正确性证明提供帮助。     

DEM生成算法并行化研究

数字高程模型DEM（Digital Dlevation Model），是一种表示三维空间连续起伏状态的数学模型，如今在各行业应用十分广泛。针对DEM生成过程中计算复杂、数据量大的特点，在分析几种常用的DEM生成算法的基础上，以线性内插算法为样本，对DEM生成算法的并行化处理问题进行了深入研究。研究中，分别从数据并行和算法并行的角度，对DEM生成算法并行化进行了分析，并在网络分布式机群下进行了数据处理实验，取得了较好的并行处理效果。最后，进一步根据实验结果，讨论了责任发解方法的并行效率，提出了DEM生成算法并行化的有效途径。     

MPI通信代码自动生成算法

对于高性能并行计算机而言，如何由给出的计算、数据划分信息及精确数组数据流分析信息自动生成并行化代码是实现串行程序并行化的一个重要问题。根据Saman P.Amarasinghe和Lam的定理，实现了一种并行化识别工具中MPI（Message Passing Interface）并行化代码自动生成技术的算法，并对该算法的性能进行分析。     

遥感图像K-Means并行算法研究

K-Means算法是对遥感图像在没有先验知识情况下进行无监督分类的重要算法之一,在遥感影像的分析中得到了广泛的应用.针对K-Means算法复杂,处理过程中计算时间长的缺点,人们试图寻求快速的并行处理方式.在这种并行化的探索过程中,由于K-Means算法独特的流程结构,使其并行化处理方式难以顺利进行.本文在分析K-Means算法特点的基础上,对其并行化方式进行了深入的研究.针对K-Means算法并行化在处理速度和分类精度方面存在的问题,提出了一种基于分块逼近的算法并行模型,可兼顾并行效率和分类精度之间的综合要求,实现某种精度可控的并行处理.最后,根据实验结果讨论并提出了迭代算法并行化的有效途径.     

基于CUDA的SVM算法并行化研究

SVM算法在统计分类以及回归分析中得到了广泛的应用。而随着物联网的迅速发展,SVM算法在各种应用中往往需要解决大量数据的快速处理问题。在SVM算法并行化研究中,首先对SVM算法进行分析研究,提出了基于CUDA的SVM算法并行化方案;其次,进一步研究海量数据的处理,提出海量数据处理的并行化方案;最后,通过实验分析对比了并行化算法的性能。     

具有量子行为粒子群优化算法的并行化研究

在研究了具有量子行为粒子群算法的基础上,受遗传算法并行化的启发,对具有量子行为的粒子群算法提出并实现了新的并行化策略。针对通信时间过长的问题,提出了改进方法。最后通过benchmark测试函数,将并行化量子粒子优化算法和二进制遗传算法、十进制遗传算法、粒子群优化算法的并行化方法进行了仿真比较,并对结果进行了分析。     

矢量多边形栅格化算法快速并行化方法研究

本文在分析典型多边形栅格化算法的基础上,研究了串行算法并行化思路,提出一种多边形栅格化算法并行框架。该并行框架包括MPI与OpenMP的双层并行模式、顾及负载均衡的矢量多边形数据划分方法、多边形栅格化基本算子调用接口。利用本文形成的并行框架对扫描线算法、边界代数法进行了并行化,并利用大规模土地现状数据验证本文所提出的并行化方法的有效性。试验结果表明,该方法能够解决矢量多边形栅格化串行算法快速并行化的问题,并行化后的算法大大减少了矢量多边形转换时间,具有良好的并行效率。     

面向公有云的支持快速解密的CP-ABE方案

现有的密文策略基于属性加密CP-ABE（ciphertext-policy attribute-based encryption）算法普遍在解密时存在计算量过大、计算时间过长的问题，该问题造成CP-ABE难以应用和实施.针对该问题，将计算外包引入到方案的设计之中，提出一种面向公有云的基于Spark大数据平台的CP-ABE快速解密方案.在该方案中，专门根据CP-ABE的解密特点设计了解密并行化算法；利用并行化算法，将计算量较大的叶子节点解密和根节点解密并行化；之后，将并行化任务交给Spark集群进行处理.计算外包使得绝大多数解密工作由云服务器完成，用户客户端只需进行一次指数运算；而并行化处理则提高了解密速度.安全性分析表明，所提出的方案在一般群模型和随机预言模型下能对抗选择明文攻击.     

并行LLL算法研究综述

Lenstra-Lenstra-Lovasz（LLL）格基约化算法自1982年被提出以来，已被成功应用于计算机代数、编码理论、密码分析、算法数论、整数规划等众多领域。经过三十多年的发展，串行LLL算法的理论分析和实际效率都已得到显著改进，但仍不能满足密码分析等领域处理较大规模问题的需要。因此，并行LLL算法研究被寄予厚望。对并行LLL算法的研究现状进行了综述，总结了当前并行LLL算法设计与分析中存在的问题和难点，并对其未来发展趋势进行了展望。     

多重循环的软件流水：比较和提高

循环并行化是并行编译的核心问题之一。许多科学计算程序的大部分执行时间花费在循环上，有效开发循环中的并行性将提高整个程序的执行效率。多重循环最为常见，因此并行化多重循环具有重要的理论和现实意义。现代处理器中硬件资源迅速增长，也使得在整个多维循环空间中开发并行性成为必要。目前大多数软件流水算法只对最内层循环，仅有少数的算法对多重循环进行软件流水，本文介绍几种多重循环的软件流水算法，比较它们之间的相似与不同之处，为编译器实现中算法的选择提供了指导。     

Time‐Domain Parallelization for Accelerating Cloth Simulation

Cloth simulations, widely used in computer animation and apparel design, can be computationally expensive for real‐time applications. Some parallelization techniques have been proposed for visual simulation of cloth using CPU or GPU clusters and often rely on parallelization using spatial domain decomposition techniques that have a large communication overhead. In this paper, we propose a novel time‐domain parallelization technique that makes use of the two‐level mesh representation to resolve the time‐dependency issue and develop a practical algorithm to smooth the state transition from the corresponding coarse to fine meshes. A load estimation and a load balancing technique used in online partitioning are also proposed to maximize the performance acceleration. Our method achieves a nearly linear performance scaling on manycore clusters and outperforms spatial‐domain parallelization on a diverse set of benchmarks.     

A Parallel Genetic Algorithm Based on Spark for Pairwise Test Suite Generation

Pairwise testing is an effective test generation technique that requires all pairs of parameter values to be covered by at least one test case. It has been proven that generating minimum test suite is an NP-complete problem. Genetic algorithms have been used for pairwise test suite generation by researchers. However, it is always a time-consuming process, which leads to significant limitations and obstacles for practical use of genetic algorithms towards large-scale test problems. Parallelism will be an effective way to not only enhance the computation performance but also improve the quality of the solutions. In this paper, we use Spark, a fast and general parallel computing platform, to parallelize the genetic algorithm to tackle the problem. We propose a two-phase parallelization algorithm including fitness evaluation parallelization and genetic operation parallelization. Experimental results show that our algorithm outperforms the sequential genetic algorithm and competes with other approaches in both test suite size and computational performance. As a result, our algorithm is a promising improvement of the genetic algorithm for pairwise test suite generation.     

并行二进制蚁群算法的多峰函数优化

针对已有蚁群算法在函数优化问题上存在的几个不足:如算法实现较难,占用过多的存储空间,需要记忆功能,不容易与其他算法结合等等,提出了二进制蚁群算法。实验证明该算法在处理单极值问题时有较好的表现,但是在处理多峰函数时存在着一定的缺陷,对此,论文对该算法进行了改进,将并行化引入算法。通过对几个函数的测试(包括多峰和单峰),结果表明该改进算法具有较好的稳定性和收敛速度,算法性能良好。     

Communication latency tolerant parallel algorithm for particle swarm optimization

Particle swarm optimization (PSO) algorithm is a population-based algorithm for finding the optimal solution. Because of its simplicity in implementation and fewer adjustable parameters compared to the other global optimization algorithms, PSO is gaining attention in solving complex and large scale problems. However, PSO often requires long execution time to solve those problems. This paper proposes a parallel PSO algorithm, called delayed exchange parallelization, which improves performance of PSO on distributed environment by hiding communication latency efficiently. By overlapping communication with computation, the proposed algorithm extracts parallelism inherent in PSO. The performance of our proposed parallel PSO algorithm was evaluated using several applications. The results of evaluation showed that the proposed parallel algorithm drastically improved the performance of PSO, especially in high-latency network environment.     

基于Spark的BIRCH算法并行化的设计与实现

在分布式计算和内存为王的时代,Spark作为基于内存计算的分布式框架技术得到了前所未有的关注与应用。着重研究BIRCH算法在Spark上并行化的设计和实现,经过理论性能分析得到并行化过程中时间消耗较多的Spark转化操作,同时根据并行化BIRCH算法的有向无环图DAG,减少shuffle和磁盘读写频率,以期达到性能优化。最后,将并行化后的BIRCH算法分别与单机的BIRCH算法和MLlib中的K-Means聚类算法做了性能对比实验。实验结果表明,通过Spark对BIRCH算法并行化,其聚类质量没有明显的损失,并且获得了比较理想的运行时间和加速比。     

An algorithmic framework for solving large-scale multistage stochastic mixed 0–1 problems with nonsymmetric scenario trees. Part II: Parallelization

This note is a sequel of paper (Escudero et al. (2012) [1]), in which the sequential Branch-and-Fix Coordination referred to as the BFC-MS algorithm was introduced for solving large-scale multistage mixed 0–1 optimization problems up to optimality under uncertainty. The aim of the note is to present the parallelization version of the BFC algorithm, referred to as PC-BFCMS, so that the elapsed time reduction on problem solving is analyzed. The parallelization is performed at two levels. The inner level parallelizes the optimization of the MIP submodels attached to the set of scenario clusters that have been created by the modeler-defined break stage to decompose the original problem, where the nonanticipativity constraints are partially relaxed. Several strategies are presented for analyzing the performance of the inner parallel computation based on MPI (Message Passing Interface) threads to solve scenario cluster submodels versus the sequential version of the BFC-MS methodology. The outer level of parallelization defines a set of 0–1 variables, the combinations of whose 0–1 values, referred to as paths (one for each combination), allow independent models to be optimized in parallel, such that each one can itself be internally optimized with the inner parallelization approach. The results of using the outer–inner parallelization are remarkable: the larger the number of paths and MPI threads (in addition to the number of threads that the MIP solver allows to be used), the smaller the elapsed time to obtain the optimal solution. This new approach allows problems to be solved faster, and, can thus solve very large scale problems that could not otherwise be solved by plain use of a state-of the-art MIP solver, or could not be solved by the sequential version of the decomposition algorithm in acceptable elapsed time.     

A method for speeding up beam-tracing simulation using thread-level parallelization

In recent years, the computational power of modern processors has been increasing mainly because of the increase in the number of processor cores. Computationally intensive applications can gain from this trend only if they employ parallelism, such as thread-level parallelization. Geometric simulations can employ thread-level parallelization because the main part of a geometric simulation can be divided into a subset of mutually independent tasks. This approach is especially interesting for acoustic beam tracing because it is an intensive computing task. This paper presents the parallelization of an existing beam-tracing simulation composed of three algorithms. Two of them are iterative algorithms, and they are parallelized with an already known technique. The most novel method is the parallelization of the third algorithm, the recursive octree generation. To check the performance of the multi-threaded parallelization, several tests are performed using three different computer platforms. On all of the platforms, the multi-threaded octree generation algorithm shows a significant speedup, which is linear when all of the threads are executed on the same processor.     

基于集群并行及指令优化的FDK重建算法

为提高锥束CT的FDK重建算法在重建高分辨率的图像时的速度,分析2种并行策略及其对应的通信时耗,研究集群并行与SSE指令优化计算相结合的FDK算法,在8个节点的集群系统上进行实现。实验结果表明,采用集群并行加指令优化的方式,可将分辨率为2563的图像的重建速度提高到原来的29倍。     

SGI系统上星载SAR并行成像算法

对星载合成孔径雷达(SAR)并行处理算法在分布式共享存储器(DSM)HPC平台下的实现作了深入研究，对比了用消息传递和OpenMP两种并行编程模型实现的并行方案，在此基础上提出了基于进程的共享变量并行模型。这种模型克服了前两种模型的缺点，经过实验测试和实际SAR成像应用，证明是一种高效、稳定的并行方案。     

GPU近实时线性双目立体代价聚合

目的 近年来双目视觉领域的研究重点逐步转而关注其“实时化”策略的研究,而立体代价聚合是双目视觉中最为复杂且最为耗时的步骤,为此,提出一种基于GPU通用计算(GPGPU)技术的近实时双目立体代价聚合算法。方法 选用一种匹配精度接近于全局匹配算法的局部算法——线性立体匹配算法(linear stereo matching)作为代价聚合策略;结合线性代价聚合的原理,对其主要步骤(代价计算、均值滤波及系数求解等)的计算流程进行有针对性地并行优化。结果 对于相同的实验样本,用本文方法在NVIDA GTX780 实验平台上能在更短的时间计算出代价矩阵,与原有的CPU实现方法相比,代价聚合的效率平均有了数十倍的提升。结论 实时双目立体代价聚合方法,为在个人通用PC平台上实时获取高质量双目视觉深度信息提供了一个高效可靠的途径。