基于CUDA的位并行近似串匹配算法

为满足文本检索、计算生物学等领域海量数据匹配对高性能计算的要求,提出一种基于计算统一设备架构(CUDA)的位并行近似串匹配算法。结合图形处理器(GPU)的高并行计算结构及存储带宽特性,通过优化数据存储方式,实现并行化动态规划矩阵算法(BPM)的加速,并对加速性能进行对比测试。实验结果表明,BPM算法通过GPU加速能获得20倍左右的加速比。     

串匹配算法的简单并行实现

结合BM模式匹配算法和并行计算的思想,提出了一种快速的串匹配并行实现策略,该策略将文本串划分成一定长度的子串,将子串分配到不同的处理器中,在各个处理器中分别并行执行BM模式匹配,即便是在最坏的情况下也能达到较好的时间复杂度。     

串匹配算法的简单并行实现

结合BM模式匹配算法和并行计算的思想,提出了一种快速的串匹配并行实现策略,该策略将文本串划分成一定长度的子串,将子串分配到不同的处理器中,在各个处理器中分别并行执行BM模式匹配,即便是在最坏的情况下也能达到较好的时间复杂度。     

基于GPU的串匹配算法研究

BF算法是串匹配算法中最基础的算法，但它是串行算法，不适合图形处理器（Graphic Processing Unit, GPU）的体系结构。结合GPU的特殊体系结构，通过数据存取方式和计算策略的改进，充分利用了GPU的并行处理能力，从而基于GPU实现了BF算法。实验结果表明基于GPU的并行算法能够取得较好的加速比，同时也给出了在现有GPU架构上有效实现通用计算的瓶颈。     

基于GPU的精确串匹配算法综述

精确 串匹配是计算机领域的一个经典问题。在大数据时代,海量的数据给串匹配问题带来巨大的挑战。当前,GPU的应用得到学术界和工业界的广泛关注。近年,基于GPU的串匹配算法研究已成为学术界的焦点。为展示近年的研究,本文综述了基于GPU的精确串匹配技术,针对不同的算法和GPU架构介绍精确串匹配技术在GPU上的改进：不同算法的改进具有差异性,研究时需扩展具体算法,并比较上述算法的优缺点。最后对评测指标进行介绍,展望其发展趋势。     

基于统一计算设备架构和基因表达式编程的自动聚类算法

针对基于基因表达式编程(GEP)的自动聚类算法GEP-Cluster中聚类中心的筛选和聚合、计算数据对象到各聚类中心距离两个关键步骤效率不高的问题,提出了一种基于统一计算设备架构(CUDA)和GEP的自动聚类改进算法(CGEP-Cluster)。CGEP-Cluster算法采用基因阅读运算器方法对GEP-Cluster算法的聚类中心筛选和聚合步骤进行改进,并基于CUDA将GEP-Cluster算法中数据对象到各聚类中心距离的计算并行化。实验结果表明,在数据对象规模较大时,CGEP-Cluster算法可获得8倍左右的加速比。CGEP-Cluster算法可用于聚类数未知且数据对象规模较大情况下的自动聚类。     

基于计算统一设备架构的高铁故障诊断方法

为解决传统高铁振动信号故障诊断方法速度慢、难以满足实时处理的要求,提出一种基于计算统一设备架构(CUDA)加速的高铁振动信号故障诊断方法。首先利用CUDA架构对高铁数据进行经验模态分解(EMD),进而计算分解所得到的各个分量的模糊熵,最后利用最近邻分类(KNN)算法对多个模糊熵特征组成的特征空间进行故障分类。实验结果表明,该方法能高效地对高铁振动信号进行故障分类,运行速度较传统方法有明显提高。     

一个改进的BM串匹配算法

文中利用ＢＭ算法中依据ｄ函数来右移模式距离大小的特点，在一定条件下，将模式分解成具有一定性质的两个子串。通过子模式各自的性质及相互间的关系，控制模式匹配过程，以减少字符重复比较次数，从而提高算法匹配效率。     

统一计算设备架构下的F-X域预测滤波并行算法

针对传统F-X域预测滤波去除地震资料随机噪声耗时巨大的问题,提出了基于统一计算设备架构(CUDA)的并行算法.首先,对算法进行模块化分析以找到算法的计算瓶颈;然后从每个窗口数据计算相关矩阵、求滤波因子、滤波等步骤入手,使用图形处理器(GPU)将滤波过程分解为多个任务并行处理;最后,对算法进行并行实现,并对相邻滤波窗口的...     

基于CUDA的彩色超声血流成像

彩色超声血流成像在医学超声诊断中得到了广泛的运用。对前期所提出的超声血流成像图形处理器(GPU)的处理框架做出了两点改进：在壁滤波器模块并行实现Regression滤波器,替换原来的并行有限冲激响应(FIR)滤波器;在后处理模块中,加入了并行实现的Threshold box滤波器,改善了血流的均匀性。实验结果表明：GPU并行实现的运算效率是中央处理器(CPU)串行实现的16.2倍,帧率可以达到70帧/秒。与传统的FIR滤波器相比,Regression滤波器能够得到更高质量的超声血流图像,并且Threshold box滤波器提高了组织/血流鉴定的精确度。     

Implementation of graphic vertex-coloring parallel synthesis algorithm based on genetic algorithm and compute unified device architecture

Graphic vertex-coloring has long been a classical problem for combinatorial optimization in the field of science and technology. No algorithm can give an optimal solution for graphic vertex-coloring in polynomial time so far, though it plays an important role in the field of mathematical science and technology. Hence the problem has always been a non-deterministic polynomial (NP) complete problem. The current computer parallel technology based on compute unified device architecture (CUDA) is a hot spot in the relevant field. This study put forward a method integrating parallel genetic algorithm and CUDA to solve the problem of graphic vertex-coloring. First, color sequences were coded and parallel genetic operators were designed, which was beneficial to the improvement of algorithm efficacy. Then parallelization reformation was performed on the above integrated algorithm using CUDA. Experimental results demonstrated that, the newly developed algorithm improved the calculation efficiency and reduced the computation time compared to traditional algorithms based on central processing unit (CPU). Thus plenty of cases can be effectively solved if the minimum coloring number of a known graphics is found.     

Parallel genetic algorithm for N-Queens problem based on message passing interface-compute unified device architecture

N-Queens problem derives three variants: obtaining a specific solution, obtaining a set of solutions and obtaining all solutions. The purpose of the variant I is to find a constructive solution, which has been solved. Variant III is aiming to find all solutions and the largest number of queens currently being resolved is 26. Variant II whose purpose is to obtain a set of solutions for larger-scale problems relies on various intelligent algorithms. In this paper, we use a master-slave model genetic algorithm that combines the idea of the evolutionary algorithm and simulated annealing algorithm to solve Variant III, and use a parallel fitness function based on compute unified device architecture. Experimental results show that our scheme achieved a maximum 60-fold speedup over the single-CPU counterpart. On this basis, a two-level parallel genetic algorithm based on the island model and master-slave model is implemented on the GPU cluster by using message passing interface technology. Using two-node and three-node GPU cluster, speedup of 1.46 and 2.01 are obtained on average over single-node, respectively. Compared with the sequential genetic algorithm, the two-level parallel genetic algorithm makes full use of the parallel computing power of GPU cluster in solving N-Queen variant II and improves the performance by 99.19 times in the best case.     

WCCS环境下连续r位串匹配算法及其并行化研究

通过将免疫系统中连续r位匹配规则引入到串匹配算法中,在传统KMP串匹配算法的基础上提出了r-KMP算法,该算法使用匹配闽值r来控制文本串与模式串的匹配程度.然后在WCCS(Windows compute cluster server)平台下部署了并行化的r-KMP算法,通过实验分析了算法的性能和时间复杂度.实验结果表明,该算法能有效的控制串匹配程度,它的并行化减少了执行时的运算时间,提高了串匹配效率.     

一种改进的BM字符串匹配算法

经典字符串匹配算法的本质都是从左向右或者从右向左顺序进行字符匹配的,在主串中存在大量子串与模式串前缀或者后缀相同时效率较低,并且模式串最大右移长度为模式串长度。改进算法采用二分匹配字符串的方法,有效地避免了由主串中大量子串与模式串前缀相同或者后缀相同引起的无意义比较次数。模式串的移动距离根据改进的坏字符规则进行计算,增大了模式串的移动距离。实验结果表明,改进的字符串匹配算法可以有效地减少字符串的匹配次数和移动次数,达到了提高算法效率的目的。     

基于压缩后缀数组的近似字符串匹配算法

近似字符串匹配是模式匹配研究领域中的一个重要研究方向。压缩后缀数组是字符串匹配、数据压缩等领域广泛使用的索引结构,具有检索速度快和适用广泛的优点。利用压缩后缀数组,提出了适合近似字符串匹配搜索算法的数据结构,并在此基础上提出了一种匹配搜索算法。实验结果表明,相对于现有的算法,提出的算法在小字母表的情况下具有计算优势。     

一种改进的字符串多模式匹配算法

基于字符串匹配的检测方法是入侵检测系统中的一种重要方法。通过分析几种常见的字符串匹配算法（AC、AC_BMH、Sunday等）的基础,提出了一种对AC算法的改进,新算法每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮匹配,使得匹配次数大大减少,从而提高了匹配效率。分析了该算法的性能,并用具体的实验数据给出了几种匹配算法的测试结果。