机群系统上基于映射和抽样划分的并行聚类算法

采用映射和抽样划分方法,基于MPI消息传递编程模式,在机群系统上设计与实现一种并行聚类算法.该算法将生物基因序列映射成整数值,采用整数值取代字符串进行聚类,使得聚类过程快速,通过多次抽样一次聚类寻找初值在一定程度上避免了聚类结果陷入局部解的问题,优化了聚类质量.在PC机群系统上对基因序列进行并行聚类的实验结果表明该算法获得了较好的加速和可扩展性.     

基于SIMD-BF模型的并行FFT算法设计与实现

在单指令多数据流-蝶形网络模型(SIMD-BF)上设计实现FFT算法。当前算法中,W指数的获得需要进行位反,左移和补零操作。本算法采用按时间抽取(Decimation-in-Time)方式,其W指数可以由处理器所在位置轻松获得,只需进行简单左移操作,利用该算法中清晰简单的W指数规律进行递归运算,输出即为结果。在提出的算法中,SIMD-BF模型结构处理器的通信方式发生变化,满足选通直达无需选路时间。改进型算法结果表明,W指数规律明显简单,可节省W的计算时间,可处理倒序输入的待变换序列。     

基于并行计算模型的并行微粒群算法的性能分析

将微粒群算法与并行计算模型相结合,基于三种不同的并行计算模型(带中央控制器的并行计算模型、环形结构带缓存区的并行计算模型、BSP并行计算模型),设计出相应的并行微粒群算法,并对并行算法性能进行详细分析。大量实验表明:子种群之间的通讯周期是个重要的可变参数,当选取合适时,能提高解的质量以及算法的收敛性和最优性。     

并行CRC算法的实现

从实用角度出发,介绍了循环冗余校验码(CRC),并对CRC-16及CRC-32的算法、实现及其在雷达侦察接收机内部高速串行通信中的应用进行了阐述.     

基于统计模型的三线阵CCD影像并行匹配算法

在基于统计方法实现CCD影像匹配算法的基础上,提出了CCD影像匹配计算任务的分解方法和计算任务的调度策略,进一步构建了基于统计模型的三线阵CCD影像匹配算法的并行计算方案。并通过实验进行了验证,结果表明,对于CCD影像该并行匹配算法获得了良好的加速比,可扩展性好。适用于超大规模的三线阵CCD影像中同名像点的匹配计算。     

面向超大规模集成电路物理设计的通孔感知的并行层分配算法

随着集成电路规模的日益增长,需要处理的线网数量显著增多,层分配算法运行时间增大成为限制高效设计布线方案的重要因素;此外在生产工艺中,通孔的制造成本较高.针对以上两个问题,本文提出了两种新颖的策略分别用于优化算法运行时间和通孔数量:(1)一种高效的基于区域划分的并行策略,实现各区域在并行布线阶段负载均衡,以提高并行布线的效率;(2)基于线网等效布线方案感知的通孔优化策略,决定各线网对布线资源使用的优先级,进而减少层分配方案的通孔数量.最终将上述两种策略相结合,提出了一种面向超大规模集成电路物理设计的通孔感知的并行层分配算法.实验结果表明该算法对通孔数量和运行时间均有良好的优化效果.     

高效的H.264并行编码算法

 CABAC是H.264/AVC视频压缩标准主要档次中采用的熵编码机制,结合RDO模式选择技术,可以降低20％的编码码率,但是编码器计算复杂度却同时大大增加.对算法进行并行化是有效加快编码速度的方法,但是,由于CABAC具有自适应编码的特点和RDO模式选择对熵编码的使用,使得顺序编码的宏块之间存在着严格的数据相关性,限制了并行编码算法的开发.本文结合基于宏块区域划分的数据级并行编码机制MBRP和码率估计技术,为采用CABAC熵编码机制的H.264编码算法提供了一种高效的并行编码方案:将H.264编码算法划分为模式选择和码流生成两个部分,使之构成典型的生产者-消费者关系;将RDO模式选择中的CABAC替换为码率估计,去除模式选择过程中因CABAC导致的严格数据相关性;对模式选择部分采用MBRP并行机制;码流生成部分由单独的处理器完成,并和模式选择部分实现流水化并行处理.通过4处理器系统模拟器进行实验,发现在保持视频压缩性能几乎不变的情况下,该并行算法的加速比可以达到4.7.     

NCC区域气候模式算法分析及并行化实现

文章介绍了国家气候中心高分辨率区域气候模式的特点及基本原理，在分析了它的基本流程及串行算法的基础上，针对其算法及数据流特点，提出了基于经度划分的并行方案．并对I／O及通信作了比较有效的优化．在神威并行机上实现后，4处理机时取得了较好的效果，最大可扩展至16处理机。     

GPU优化的大规模线性方程组并行求解的研究与比较

采用CUDA平台提供的通用并行处理架构,在Gauss-Jordan消去法的基础上,给出了一种适合CUDA平台的并行算法来进行大规模线性方程组的加速求解。算法在GPU端进行整体线性方程组的求解,从Device传回的为方程组的解向量,大大减少了来自Host端和Device端数据传输所带来的延时。算法对任务划分及处理进行了充分的分析。在耗时最为严重的消去阶段,通过增加单个线程的算术逻辑运算来减少线程块之间切换带来的整体算法耗时,并对算法的其余每个阶段都进行了充分的优化。最后在本机上进行了不同线性方程组维数的并行算法与串行算法的加速比,实验结果表明了该并行算法能够充分利用GPU硬件特性,并充分降低了大规模线性方程组的求解时间。     

长持续时间数据流的并行检测算法

针对现有长持续时间数据流检测算法的实时性差、检测精度与估计精度低的问题,提出长持续时间数据流的并行检测算法。基于共享数据结构的长持续时间数据流的并行检测算法中不同线程访问共享数据结构,线程之间的同步开销过大。在此基础上,基于独立数据结构的长持续时间数据流的并行检测算法中不同线程具有本地数据结构,线程之间不需要同步,产生较少的开销。理论分析与实验结果表明,基于独立数据结构的长持续时间数据流的并行检测算法具有良好的时间效率、较高的检测精度和流持续时间估计精度。     

空间索引并行批量加载算法研究

空间索引是提高空间数据库查询性能的关键技术。空间数据具有海量、空间目标不规则、结构和关系复杂等特征,要动态地维护空间索引结构,传统R树的构建方法插入代价非常高。在深入分析空间索引批量加载算法基础上,面向多核处理器的新型硬件架构,基于OpenMP并行编程模型,实现Hilbert R树索引的并行批量加载算法。实验结果表明,相对于串行经典算法,该算法的并行效率接近50%,通过查询实验验证,并行加载算法保持了串行算法生成索引的优良查询性能。     

一种快速高效的Hough变换并行算法

本文提出了一种基于流水光总线可重构线性阵列(LARPBS)模型的快速高效Hough变换算法.该算法利用LARPBS有力的通讯功能和计算能力,对直线上的黑色象素进行抽取和统计.对于大小为n×n的二值数字图象、m个θ参数值,本算法可以使用mn²个处理机在O(1)时间完成,从而使速度和效率都达到最优.文中还给出当LARPBS中处理机个数少于mn²时的算法分解执行方法,说明算法具有很好的可扩放性.     

基于多层竞争的高效并行遗传算法

借鉴生态进化中普遍存在的竞争现象,本文提出了一种基于多层竞争的并行遗传算法(GAMLC,geneticalgorithm based On multi-level competition).仿真结果表明,该算法能较好地解决遗传算法中的早熟现象及收敛速度慢的问题,提高了搜索到全局最优解的概率.     

A Practical Parallel Algorithm for All-Pair Shortest Path Based on Pipelining

On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.     

A Special Purpose Array Processor Architecture for the Molecular Dynamics Simulation of Point-Mutated Proteins

Point mutation of amino acids is a means used by biotechnologists to improve the performance of proteins. To study a point-mutated polypeptide, one requires its global minimum energy conformation. This conformation can be determined by molecular dynamics via Langevin's equations of motion. Molecular dynamics simulations belong to the most difficult problems to parallelize in a scalable manner. We provide a method for defining a special purpose 3D array processor architecture for the molecular dynamics simulation of point-mutated polypeptides. The architecture is derived from a spatial decomposition of a known conformation of the point-mutated polypeptide or the native conformation of the given protein. By using an approximation scheme for the deterministic forces, the interprocessor communication can be kept local. The architecture affords a simple distributed load balancer and is scalable. The computational workload of the array processor architecture to perform molecular dynamics simulations under realistic conditions is addressed. An example architecture is given by point-mutated penicillin amidase.     

基于OPENMP求解旅行商问题的并行蚁群算法

蚁群算法具有自组织性、正反馈性、较强的鲁棒性和天生的并行性等优点,不足之处是需要较长的搜索时间.为了解决其搜索时间过长的问题,文中提出了一种并行实现策略,用OPENMP应用编程接口采用C++语言编程实现,能明显减少搜索所用的时间.给出了一种解决旅行商问题(TSP)的并行蚁群算法,并通过串并算法执行时间的比较,说明并行算法的优越性.     

经典分子动力学模拟的主要技术

综述了分子动力学模拟的基本原理、发展过程及主要应用,介绍了原子间势函数的发展及势参数的确定,给出了分子动力学模拟中相关的有限差分算法、初始条件及边界条件的选取、平衡态系综及其调控、感兴趣量的提取及主要过程。最后还指出了分子动力学模拟方法本身进一步的研究方向。     

一种分层置信传播立体匹配并行算法

立体匹配是计算机视觉中一个重要的研究课题。目前主要的全局匹配方法虽然能得到比较准确的立体匹配结果,但是其计算速度较慢。通过对一种自适应分层置信传播算法的分析,对其进行了并行实现,加快算法的计算速度。该立体匹配方法在传统的HBP算法基础上对消息计算的收敛性进行判断,停止消息计算已收敛节点的迭代计算,从而减少算法整体迭代次数。通过利用该算法迭代过程中的并行性,对该算法进行并行实现。实验表明,这里并行实现方法在不损失计算效率的前提下,在双核处理器上平均加速比达到1.88。     

用于综合PWM芯片的并行遗传算法

提出了基于遗传算法的脉冲宽度调制(PWM)芯片的自动综合方法.为保证综合结果准确实用,对电路性能的评价基于HSPICE的仿真结果,提出的并行遗传算法采用了电路划分和参数关联技术,并运用互联网实现并行计算.综合实例表明了该方法的有效性     

基于基因表达式编程的多数据流压缩并行算法

针对大规模数据流需要巨量存储空间,以及串行处理速度瓶颈,着力于解决处理后的精确度及数据压缩.在并行平台下,利用阈值滑动窗口技术将数据流分段送入各处理器,并使用基因表达式编程（Gene Expression Programming,GEP）的函数发现算法实现对数据模型的函数挖掘,提出了基于基因表达式编程的多数据流压缩并行函数替代算法PFR-GEP（Parallel Function Replace-GEP）.在PC机群上的实验结果表明：该算法有效提高了压缩比例与运算速度,且具有线性加速比.