面向CPU+GPU异构平台的模板匹配目标识别并行算法

针对大数据量导致模板匹配目标识别算法计算时间长,难以满足快速检测的实际需求问题,在采用最新NVIDIA Tesla GPU构建的CPU+GPU异构平台上,设计了一种模板匹配目标识别并行算法.通过对模板图像数据常量化、输入图像数据极致流多处理器片上化和简化定位参数计算3方面优化了并行算法,并对算法进行性能测试.实验表明,该算法在保证识别效果的同时实时性明显提高.     

一种分布式后缀树构造与匹配算法

提出一种基于消息传递模式的分布式后缀树构造算法(DPSTG)及相应的并行匹配算法.DPSTG算法按不同的字符将原始字符串的后缀树分解成若干个子后缀树后由多个处理器并行构造.处理器间通过消息传递方式连接各个子后缀树,匹配时首先将要查找的字符串分割成若干不同首字符的子字符串,然后在构造相应首字符子后缀树的处理器上实现多个子字符串的并行匹配.理论分析表明DPSTG算法的时间复杂度要优于现有的大多数后缀树并行生成算法.模拟实验结果表明DPSTG算法的并行加速比随着待处理字符串的长度增加而提高.     

一种基于GPU的二维离散多分辨率小波变换加速方法

针对传统CPU平台下小波变换算法难满足当前高分辨率、 大数据规模下的实时性要求, 提出一种基于GPU的并行小波变换算法, 并通过改善Local Memory访存数据的局部性和增加Global Memory访存带宽的优化技术, 利用多Kernel并行提高多种分辨率下小波变换的性能. 实验结果表明, 与CPU串并行版本相比, GPU并行优化算
法在高分辨率变换情况下, 加速比最高可达30~60倍, 可满足对变换实时性的要求.     

CPU+GPU异构并行的矩阵转置算法研究

针对当前算法优化研究一般局限于单一硬件平台、很难实现在不同平台上高效运行的问题,利用图形处理器(GPU)提出了基于开放式计算语言(OpenCL)的矩阵转置并行算法.通过矩阵子块粗粒度并行、矩阵元素细粒度并行、工作项与数据的空间映射和本地存储器优化方法的应用,使矩阵转置算法在GPU计算平台上的性能提高了12倍.实验结果表明,与基于CPU的串行算法、基于开放多处理(OpenMP)并行算法和基于统一计算设备架构(CUDA)并行算法性能相比,矩阵转置并行算法在OpenCL架构下NVIDIA GPU计算平台上分别获得了12.26,2.23和1.50的加速比.该算法不仅性能高,而且实现了在不同计算平台间的性能移植.     

基于GPU的大规模基因片段并行匹配的方法

后缀树和后缀数组广泛用于生物信息学领域中,特别是通过启发式算法在对DNA基因片段进行匹配的阶段.本文提出了在GPU的平台下,利用多核和超多核体系构成的后缀树以及后缀数组并行匹配大规模基因片段,从而加速基因搜索匹配过程.相对于后缀树,后缀数组二分搜素算法具有内存占用少,缓存使用率高等优点.在GPU的性能评估中,后缀数组执行效率明显超过后缀树,后缀数组占用的空间仅为后缀树的20%~30%.相对于CPU的串行实现,后缀树组达到了约99倍的加速比.实验结果表明在基因片段匹配的过程中,基于GPU的后缀数组二分搜索是一种高效且实用的方法.     

基于GPU的流动影响枝晶生长相场方法

将自适应压力迭代法修正的Sola算法与相场模型相结合,建立过冷熔体在强迫流动状态下枝晶生长的Sola-相场模型.针对传统方法求解多场耦合相场模型时存在的计算量大,计算时间长,计算效率低等问题,提出基于CUDA+GPU软硬件体系结构的高性能计算方法.以高纯丁二腈(SCN)过冷熔体为例,在CPU+GPU异构平台上实现了存在流动时凝固微观组织演化过程的并行求解,并对基于CPU+GPU平台与CPU平台的计算结果及计算效率进行比较.结果表明,当计算规模达到百万量级时,与CPU平台上的串行算法相比,在CPU+GPU异构平台上达到了24.39倍的加速比,大大提高计算效率,并得到与串行计算相一致的结果.     

灰度图像匹配的快速算法

分析了传统的模板匹配算法 ,提出了一种新的基于投影的快速模板匹配算法 .该算法对图像计算一维投影 ,并将投影数据差分转化为描述图像特征的字符串 ,在快速字符串匹配的基础上 ,进行归一化的相关计算 ,既保证了匹配效果 ,又提高了匹配速度 .实验结果表明 ,这是一种有效的新算法     

一种带有长度和位置约束的字符串索引方法

提出了一种基于BWT(Burrows-wheeler-transform)的字符串集合的索引方法,以解决带有匹配字符串长度和匹配子串位置约束的子串确切匹配查找问题.讨论了BWT和基于BWT索引进行确切子串查找的基本原理.分析了字符串集合、匹配字符串长度和匹配子串位置约束对原BWT索引的影响.重点解决了快速地从匹配后缀位置到字符串ID和匹配子串位置的计算问题.在3个真实的数据集上进行了比对实验,结果表明:所提出的基于BWT索引方法在没有增加原索引大小的情况下,大大提升了带有匹配字符串长度和匹配位置约束的确切子串的查找的性能,因此该算法更加适用于大规模的字符串集合的索引进行近似字符串匹配和连接.     

基于OpenCL的图像灰度化并行算法研究

随着图像数据量的增加,传统单核处理器或多处理器结构的计算方式已无法满足图像灰度化实时处理需求.该文利用图像处理器(GPU)在异构并行计算的优势,提出了基于开放式计算语言(OpenCL)的图像灰度化并行算法.通过分析加权平均图像灰度化数据处理的并行性,对任务进行了层次化分解,设计了2级并行的并行算法并映射到“CPU+GPU”异构计算平台上.实验结果显示:图像灰度化并行算法在OpenCL架构下NVIDIA GPU计算平台上相比串行算法、多核CPU并行算法和CUDA并行算法的性能分别获得了27.04倍、4.96倍和1.21倍的加速比.该文提出的并行优化方法的有效性和性能可移植性得到了验证.     

Snort中字符匹配算法的分析及优化研究

分析了Snort中使用的字符串匹配BM算法, 在此基础上,着重对BM算法中字符串的比较次数和字符移动距离进行分析,通过增加遇到字符不匹配时字符串的移动距离来减少字符的比较次数,达到提高BM算法效率的目的.实验表明,优化后的算法比原算法的效率高7%左右.     

基于GPU的隐式不可压缩SPH流体模拟

提出一种基于图形处理单元(Graphic Processing Unit,GPU)的不可压缩流体并行模拟算法.该算法使用并行基数排序技术提升了邻居查找效率,同时使用了GPU上的片上高速共享存储器,将流体计算过程中所需用到的数据尽可能从GPU的全局存储器中拷贝至共享存储器中,减小数据访问延迟,提高模拟效率.实验结果表明,基于GPU的并行模拟算法可以大幅提高流体模拟程序的性能,与基于CPU的单线程实现相比,可以到达38.2倍的加速比.     

Horspool扩展算法在方块苗文模式匹配中的应用

分析了Horspool算法的原理及特点,提出了一种适用于方块苗文环境的字符串模式匹配算法.该算法结合方块苗文的编码方式及字符串查找的特点,通过对Horspool算法中的字符处理单位进行扩展来适应方块苗文的字符串匹配.实验结果表明,在单字词、双字词和多字词的方块苗文字符串匹配过程中,该算法均呈现出较好的性能,能够用于解决方块苗文的快速检索问题.     

基于Caffe的嵌入式多核处理器深度学习框架并行实现

针对开源深度学习快速特征嵌入的卷积框架(Caffe)在Android移动端进行前向计算时存在的兼容性和时间性能差的问题,提出了基于Caffe的嵌入式同构、异构并行化改进设计方法。该方法将Caffe及其第三方库通过交叉编译移植到嵌入式移动平台后,利用同构的多核多线程方法分别对卷积层、输入帧之间的部分前向计算过程进行了并行化;实现了采用开放运算语言(OpenCL)的异构图形处理器(GPU)卷积计算,进一步提升了框架的处理速度。对3种经典的深度神经网络模型MNIST、Cifar-10和CaffeNet进行了测试对比,测试结果表明:在没有任何模型精度损失的条件下,并行后的前向计算耗时明显低于并行前,时间性能提升最高达到2倍。所提方法能够将深度学习框架Caffe高效地、并行地部署和应用于嵌入式移动多核芯片上。     

并行后缀树的构造及查询算法

针对生物信息领域中传统后缀树构造算法在时间和空间上的限制,从结构并行的角度提出了一种新颖的、适用于生物信息学应用的并行后缀树结构和相应的构造算法·该算法首先将给定字符串分成若干连续的片段,并在各个处理机上分别构造这些片段的后缀树,形成了一种分布于多个处理机上的并行后缀树结构·该并行算法不仅大大缩短了后缀树的构造时间,而且避免了主存大小的限制·经分析,其性能优于现有的任何一种并行算法·在此基础上,提出了一种高效的基于这种并行后缀树的字符串匹配算法,解决了传统后缀树的基本查询问题·     

快速散列算法在智能移动代理中的应用

针对搜索引擎后台的移动代理从互联网中抓取信息资源时,存在对URL字符串处理能力的不足,提出了一种快速处理存取数据的散列算法,通过在真实值和键值之间建立一一对应关系,快速把进入到移动代理队列中的字符串转化为一种线性表结构,改善队列处理字符串的能力.在Heritrix框架基础上,利用Eclipse 3.3开发平台实现了相应功能.实验结果表明:在加入快速散列算法之后,移动代理在搜索效率和抓取速度等方面得到明显提高.     

基于CPU-GPU异质架构的SAR实时成像加速

对于大规模SAR回波数据,单纯依靠CPU实现实时成像处理存在较大挑战。近年来出现的GPU图像处理单元为SAR成像处理提供了一个理想的处理平台。本文结合GPU和CPU的特点,利用基于CPU-GPU的异构协同处理平台来加速SAR成像算法。同时,为了充分发挥该异质架构的性能,文中提出了一种改进的基于子孔径架构的成像算法,并在此架构上对超大规模SAR回波数据进行了成像处理,取得良好的成像效果和加速比。     

基于多GPU的正则表达式匹配技术

针对传统正则匹配性能低下的问题,设计了基于多GPU的正则表达式匹配引擎,并采用折半分组优化算法解决了有限状态自动机在大规模正则集合情况下由于空间爆炸无法使用的问题,并做了相关的优化,提升了数据匹配速度.实验结果表明:基于多GPU的正则表达式匹配性能较CPU提升了61倍,其数据吞吐率远优于其他加速方式.     

基于GPU 改进的并行人工蜂群算法

针对搜索引擎后台的移动代理从互联网中抓取信息资源时,存在对URL字符串处理能力的不足,提出了一种快速处理存取数据的散列算法,通过在真实值和键值之间建立一一对应关系,快速把进入到移动代理队列中的字符串转化为一种线性表结构,改善队列处理字符串的能力．在Heritrix 框架基础上,利用Eclipse 3.3 开发平台实现了相应功能．实验结果表明: 在加入快速散列算法之后,移动代理在搜索效率和抓取速度等方面得到明显提高.     

基于CPU-GPU异质架构的子孔径算法实现

对于大规模遥感数据处理,单纯依靠CPU实现实时成像处理存在较大挑战。近年来出现的GPU图像处理单元为大规模数据处理提供了一个理想的处理平台。结合GPU和CPU的特点,利用基于CPU-GPU的异构协同处理平台来加速图像处理。同时,为了充分发挥该异质架构的性能,提出了一种改进的基于子孔径架构的成像算法,并在此架构上对超大规模遥感数据进行了成像处理,取得良好的成像效果和加速比。