通信学报 ›› 2013, Vol. 34 ›› Issue (Z2): 9-13.doi: 10.3969/j.issn.1000-436x.2013.Z2.003

• 网络工程 • 上一篇    下一篇

基于GPU的LCS算法加速机制研究与实现

张常志,牟澄,黄小红,马严   

  1. 北京邮电大学 网络技术研究院信息网络中心,北京 100876
  • 出版日期:2013-12-25 发布日期:2017-06-16
  • 基金资助:
    国家自然科学基金资助项目;国家CNGI专项基金资助项目;可演进的下一代高智能网络架构研究和实验基金资助项目

Research and implementation of the GPU-based LCS algorithm acceleration mechanism

Chang-zhi ZHANG,Cheng MU,Xiao-hong HUANG,Yan MA   

  1. Network Information Center,Institute of Networking Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China
  • Online:2013-12-25 Published:2017-06-16
  • Supported by:
    The National Natural Science Foundation of China;China Next Generation Internet (CNGI) Project;Research and Trial on Evolving Next Generation Network Intelligence Capability Enhancement

摘要:

协议特征识别技术中用到了一种重要的LCS算法,它是一种字符串比对算法,提取出字符串中的最长连续公共子串。然而,通过理论分析和实验表明:这个查找过程是一个时间复杂度较高的运算过程,如果输入的数据分组比较大,那么运行的时间将会非常长,为此不得不控制输入数据分组的大小和数量,这严重限制了所采用样本集的大小。提出了基于GPU对LCS运算实现加速的方法。在此基础上搭建和配置了CUDA平台,在此平台下研究井实现了LCS算法的井行性。通过对LCS算法在CUDA下井行性的研究,有效地加快了LCS算法的运行速度。实验结果表明,GPU下LCS算法的运行效率比CPU有了显著的提高。

关键词: 协议特征识别, LCS算法, CUDA平台, GPU加速

Abstract:

The LCS algorithm used in protocol feature recognition is a string matching algorithm to extract the longest string of continuous public substring.However,through theoretical analysis and some experimental situation,it can be seen that this process is a time complexity of higher computing process.If the input data packet is relatively large,the running time will be very long.To this end,the size and number of input packets have to be controled,which severely limits the size of the sample set.A GPU based method for accelerating the LCS algorithm was proposed.The CUDA platform was built and dedoyed and the parallel of LCS algorithm was researched on this platform.By the parallel study of LCS algorithm on the CUDA,the operation speed of the LCS is effectively enhanced.Highly competitive experimental results show that the LCS algorithm in the GPU is more effective and efficient than that in the CPU.

Key words: protocol feature recognition, LCS algorithm, CUDA platform, GPU acceleration

[1] 夏 明,董亚波,鲁东明,薛 平. RelicNet:面向野外文化遗址微气象环境监测的高可靠无线传感系统[J]. 通信学报, 2008, 29(11): 23 -185 .
[2] 江金光,李天望. 低电压环形振荡器设计[J]. 通信学报, 2007, 28(6): 10 -65 .
[3] 孙 君,朱洪波. 物联网距离和业务特征结合的频谱接入方法[J]. 通信学报, 2012, 33(4): 4 -30 .
[4] 金章赞,廖明宏,肖 刚. 否定选择算法综述[J]. 通信学报, 2013, 34(1): 18 -170 .
[5] 许瑞琛,蒋挺. 基于POMDP的认知无线电自适应频谱感知算法[J]. 通信学报, 2013, 34(6): 6 -56 .
[6] 朱旭东,李乐民,许都. 多维分组交换结构中的一种缓存设置方法[J]. 通信学报, 2006, 27(5): 16 -99 .
[7] 陈晓冬,林衡华,王庆扬,蔡康. cdma2000移动无线网演进[J]. 电信科学, 2011, 27(11): 6 -13 .
[8] 王瑞峰. 基于WLAN构建无线城市的规划设计分析[J]. 电信科学, 2011, 27(6): 121 -127 .
[9] 魏浩1,2,郑宝玉1,3,侯晓赟1,2,朱艳1,3. 基于压缩感知的放大转发双向中继信道估计[J]. 通信学报, 2013, 34(10): 20 -182 .
[10] 廖勇,王韬,陈欢,周昕,李瑜锋. 基于DBF的星—地异构共存认知MIMO系统的干扰减缓[J]. 通信学报, 2014, 35(10): 6 -49 .