基于gpu的lcs算法加速机

《基于gpu的lcs算法加速机》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于GPU的LCS算法加速机制研究与实现作者：张常志牟澄黄小红马严报告人：张常志北京邮电大学目录1背景介绍2CUDA简介3算法并行化研究和实现4实验及结果分析5结束语1.背景介绍传统的基于端口识别应用层协议的算法准确率低基本被淘汰基于负载的协议识别技术即DPI(DeepPacketInspection)技术被广泛应用LCS(LongestCommonSubsequence)算法即最长公共子序缺点：时间复杂度高，算法效率低2.CUDA简介提出了基于CUDA(ComputeUnifiedDeviceArch

2、itecture)平台的解决方案CPU和GPU数据传送结构图2.CUDA简介GPU的并行线程组织结构3.算法并行化研究和实现矩阵算法S1=“hang0an”S2=“09ngzhan”hang0an0000010090000000n0010001g0001000z0000000h1000000a0100010n00100013.算法并行化研究和实现经过改进后所得匹配矩阵hang0anh00000000000000010009000000000n000100000g000020000z000000000h010000

3、000a002000100n0003000203.算法并行化研究和实现矩阵算法优点：时间复杂度小缺点：空间复杂度大，如两个100K的文件需要消耗10G的内存，不现实该算法的并行化受文件大小的限制3.算法并行化研究和实现BF算法BF(BruteForce)算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和T的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果时间复杂度大，空间复杂度小

4、适合并行化3.算法并行化研究和实现并行化后的BF算法将其中一个文件进行扩展一趟比较作为一个thread来执行3.算法并行化研究和实现CPU与GPU算法流程图3.算法并行化研究和实现关键算法（核函数）流程图4.实验及结果分析实验环境系统搭载服务器环境为Ubuntu10.04CUDA各软件版本3.20GPU型号GeForce9800GT实验数据两个大小基本一致的文件4.实验及结果分析GPU和CPU运行时间比对File1大File2大CPU运行GPU运行加速比小/k小/k时间/s时间/s3.313.500

5、015.115.630356.656.647114.3103104165374.5150150342784.44.实验及结果分析加速比曲线54.543.53时间2.5GPU2加速比时间1.5CPU10.5031556103150文件大小/k4.实验及结果分析加速比（CPU运行时间/GPU运行时间）大概固定在4.5左右验证了GPU对LCS算法确实有加速作用，但是加速的倍数还是比较小，这主要是由于核函数中控制语句过多，影响了并行化效果5.结束语本文通过对LCS算法的并行化分析及CUDA平台的搭建，验证了GPU的加速作

6、用，对算法的并行化作了初步的探索同时发现，该平台的搭建还比较繁琐，编程有一定的难度，CUDA的学习理解还是一个复杂的过程从如何减少逻辑控制语句方面进行更深入的分析