基于统一计算设备架构的并行串匹配算法

2009-9-15 作者: 唐定车 刘任任 谭建龙 来源: 万方数据

关键字: 统一计算设备架构 单指令多线程 并行 串匹配算法 

BF算法是串匹配算法经典算法之一,但并不适合GPU这种并行体系结构。提出了基于统一计算设备架构(CUDA)架构的解决方案,通过对需要处理的数据增加一定比例的冗余信息,设计了适合CUDA计算数据的独立性特点的并行BF算法。实验结果表明,基于CUDA架构的并行串匹配算法比同等CPU算法获得约10倍的加速比。此外还对该算法性能的影响因子做了分析。

  引言

  目前对串行的串匹配算法的研究已经相对成熟,但该类算法在现行各类应用中面临着新的挑战,即需要处理的数据规模越来越庞大,同时匹配效率要求更高,因此基于硬件的串匹配算法和并行串匹配算法研究正热。现有的基于硬件的方案,如基于TCA 、FPGA的匹配算法,其价格昂贵且稳定性不够好;基于GPU的方案,通过把KIDS的串匹配计算任务移植到GPU由其负责处理,如PixelSnort算法取得了一定程度的加速比。

  随着图形GPU的高速发展,特别在近年NV IDIA公司推出了基于GS。以上系列的GPU的统一计算设备架构(3)(Compute Unified Device Architecture,CUDA),其并行线程执行模型和线程同步技术为解决问题提供了一种崭新的研究视角与实现解决方案。

  BF算法是串匹配算法中最简单易用的单模式匹配算法。与KMP算法相比,BF算法不需要任何预处理过程,并且不需要额外的数据结构。本文的方法就是基于CUDA架构将串行的BF算法改进为适合GPU特点的并行串匹配算法。

  1、相关工作

  1. 1基于图形管道的串匹配算法

  PixelSnort方案利用GPU的多个着色处理器并行匹配多个规则,从而实现性能加速,实验结果表明当移植的计算部分增加时,PixeLSnort的性能就更稳定且能超出现有Snort性能的40%;文献提出了一种在网络人侵检测系统(Intrusion Detection Systems, IDS)中基于GPU的多模式匹配算法,该方法在进行GPU计算前使用哈希的方法对规则做预处理,这样减少了不必要的匹配,其实验结果表明该方法的性能是Snort中改进的Wu Manber算法性能的两倍。

  这些方案的硬件基础是图形硬件管道流水线。编程模型与流一核(stre二一kernel)编程模型非常相似。基于图形管道流水线的方案的不足之处是处理的数据大小受屏幕最大纹理大小限制,而且需要绘画命令来激发着色处理器执行内核。

  1.2  Cmatch算法

  串匹配长久以来就应用在计算生物学。文献出了基于GPU实现的后缀树搜索算法即Cmatch算法,该算法通过将后缀树按照宽度优先(Breadth First)存储为二维纹理,这种方式带来的数据的局部性质使得纹理Cache的命中率大有提高,当多个线程并行执行时减少了对显存带宽的需求从而提高了匹配速度,实骏结果表明速度比同等CPU边界版本程序提高了约35倍。

  2 、CUDA介绍

  CUDA是用于GPU计算的开发环境,它是一个全新的软硬件架构,可以将GPU视为一个并行数据计算的设备,对所进行的计算进行分配和管理,其巧妙的线程体系设计、存储体系和线程同步技术是CUDA成功的重要因素。

  CUDA的执行模型是SIMT,也就是说在一个多处理器上的每个线程在任何时间执行的指令都是相同的[;]。在CUDA中由多个线程组成线程块,多个线程块进一步组成线程格。线程块内的线程通过共享内存组成协作线程阵列( Cooperative Threads Array, CTA ) o CTA中的线程通过调用_syncthreads( )来设置同步点即壁垒来阻断CTA中所有线程直到所有线程都完成该同步点前的任务。

  CUDA的内存空间分为全局空间、局部空间、共享内存、常量空间和纹理空间。根据不同空间它的位置、访问方式、生存期等也不同,具体见表1。

  CUDA与传统的GPGPU方法有显著的不同之处。传统的GPCPU进行通用计算是通过把这些问题转换成为图形计算送到GPU中完成的,而现在基于CUDA则可以直接调用GPU的计算资源。此外,CUDA不仅支持多核技术同样也支持超级并行线程的开发平台。




<<首页 <上一页  1  2  3  下一页>  末页>>  
责任编辑:熊东旭