基于图形处理器的高速并行算法研究

发布时间：2020-03-17 20:53

【摘要】：最早为图形渲染而专门设计的图形处理器(GPU),因其越来越强大的浮点运算能力和大规模并行处理能力,时至今日在通用计算领域也得到了广泛的应用,并且在科学计算领域获得了极大成功。GPU通用计算已成为当前工业界和学术界的研究热点。面对急剧增长的网络流量和包处理复杂度,网络设备面临越来越大的计算压力,利用GPU提高网络设备的处理能力成为GPU通用计算又一个新的应用领域。然而与科学计算领域以计算密集型问题为主、数据并行性易于利用不同,网络计算领域以访存密集型和I/O密集型任务为主,且数据并行性难以挖掘和利用。将GPU应用于网络处理领域需对既有算法进行并行化再设计,使之适应GPU的体系结构,以充分利用GPU的大规模并行计算能力。本论文选择正则表达式匹配和数据无损压缩两个尚未有效解决的问题,研究它们在GPU上的高效实现方法。正则表达式匹配无论是用硬件还是软件、在CPU上还是在GPU上实现,都面临难以调和的时空两难问题。基于DFA的正则表达式匹配速度快,但存在空间爆炸的问题；基于NFA的正则表达式匹配空间复杂度低,但匹配速度也慢。论文在深入研究GPU架构特点及NFA特征的基础上,提出一种高效的NFA实现方法。无损数据压缩无论是采用基于字典的压缩技术还是基于统计的压缩技术,数据压缩操作的数据间依赖性都很强,数据并行性难以挖掘和利用,GPU特有的单指令流多数据流并行执行模式又进一步增加了并行化的难度。论文研究以上两种压缩技术的代表性算法-基于字典的LZSS压缩算法和基于统计的哈夫曼编码算法在GPU上的高效实现,并在此基础上完成了基于这两种技术的Deflate数据压缩算法的并行化。论文的主要贡献和创新点如下：1针对正则表达式匹配的时空两难问题,论文以空间复杂度最低的NFA作为正则表达式匹配的基础实现,通过引入状态兼容组、兼容超级组、虚拟NFA状态等概念优化线程的任务分配,并通过数据包交织存储、全局存储器归并访问等技术提高线程的访存效率,实现了正则表达式匹配在GPU上的高效实现。该工作首次解决了正则表达式匹配的时空两难问题,在获得10Gbps匹配速度的同时仍然保持算法的线性空间复杂度。2针对基于字典的无损数据压缩算法LZSS在GPU上并行化程度低的问题,本文以哈希表作为字典的基础实现,通过精巧的数据结构及算法设计有效解决了并行化LZSS算法中最困难的线程串行化问题,并显著减少了对GPU计算资源的使用。该项工作在压缩率和压缩速率两个方面都明显优于目前在GPU上加速LZSS算法的最好工作。3本文在Deflate无损数据压缩算法的上下文中研究哈夫曼编码算法在GPU上的并行化,通过精巧的算法设计和CUDA原子操作有效解决了直方图计算、哈夫曼树构建和变长编码的并行化问题。该工作系首次在GPU上完成了Deflate算法的并行化实现,在压缩率接近Deflate算法的同时,压缩速率超过四核CPU上的Deflate算法实现。本文工作在高效实现正则表达式匹配和无损数据压缩在GPU上并行化的同时,也为其它算法在GPU上的高效实现提供了方法性指导及技术参考。
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TP332

【相似文献】

相关期刊论文 前10条

1 ;NVIDIA GeForce FX被评为2002年最佳图形处理器[J];CAD/CAM与制造业信息化;2003年Z1期

2 李海燕;张春元;李礼;任巨;;图形处理器的流执行模型[J];计算机工程;2008年22期

3 ;MathWorks为MATLAB提供GPU支持[J];电子与电脑;2010年10期

4 杨毅;郭立;史鸿声;郭安泰;;面向移动设备的3D图形处理器设计[J];小型微型计算机系统;2009年08期

5 ;MathWorks为MATLAB提供GPU支持[J];电信科学;2010年10期

6 ;MathWorks为MATLAB提供GPU支持[J];中国电子商情(基础电子);2010年10期

7 ;MathWorks为MATLAB提供GPU支持[J];电信科学;2010年S2期

8 韩俊刚;刘有耀;张晓;;图形处理器的历史现状和发展趋势[J];西安邮电学院学报;2011年03期

9 ;产品推介[J];电子产品世界;2012年09期

10 ;产业信息[J];单片机与嵌入式系统应用;2013年12期

相关会议论文 前7条

1 张春燕;;一种基于图形处理器的数据流计算模式[A];全国第19届计算机技术与应用（CACIS）学术会议论文集（下册）[C];2008年

2 徐侃;陈如山;杜磊;朱剑;杨阳;;可编程图形处理器加速无条件稳定的Crank-Nicolson FDTD分析三维微波电路[A];2009年全国微波毫米波会议论文集（下册）[C];2009年

3 周国亮;冯海军;何国明;陈红;李翠平;王珊;;基于图形处理器的Cuboid算法[A];第26届中国数据库学术会议论文集（B辑）[C];2009年

4 毕文元;陈志强;;利用可编程图形处理器加速CT重建与体数据的绘制[A];第十一届中国体视学与图像分析学术会议论文集[C];2006年

5 刘伟峰;杨权一;曹邦功;孟凡密;周洁;;基于GPU的高度并行Marching Cubes改进算法[A];2008年全国开放式分布与并行计算机学术会议论文集(上册)[C];2008年

6 林旭生;田绪红;冯志炜;陈茂资;;GPU加速的蚁群算法在HP模型中的应用[A];第十四届全国图象图形学学术会议论文集[C];2008年

7 方建文;于金辉;陈海英;;三维卡通水与物体交互作用的动画建模[A];中国计算机图形学进展2008--第七届中国计算机图形学大会论文集[C];2008年

相关重要报纸文章 前10条

1 乐山　乐水;图形处理技术的全球专利布局形势[N];中国知识产权报;2010年

2 严威川;明明白白显卡“芯”[N];中国电脑教育报;2007年

3 ;NEC图形处理器每秒运行50.2G条指令[N];计算机世界;2003年

4 游讯;图形处理器GPU[N];人民邮电;2011年

5 本报记者 姜姝;AMD嵌入式技术为波音飞机保驾护航[N];中国信息化周报;2014年

6 均儿;人人都有台超级计算机[N];电脑报;2008年

7 ;AMD启动“Fusion”企业品牌推广计划[N];人民邮电;2008年

8 本报记者 田梦;Adobe CS4全面支持GPU加速[N];计算机世界;2009年

9 赵欣;“玩”3D，笔记本也行！[N];中国计算机报;2003年

10 ;HP Compaq Evo D210教育信息化的好帮手[N];中国计算机报;2003年

相关博士学位论文 前5条

1 祖渊;基于图形处理器的高速并行算法研究[D];中国科学技术大学;2014年

2 杨珂;基于图形处理器的数据管理技术研究[D];浙江大学;2008年

3 穆帅;针对不规则应用的图形处理器资源调度关键技术研究[D];清华大学;2013年

4 夏健明;基于图形处理器的大规模结构计算研究[D];华南理工大学;2009年

5 黄涛;基于GPU的多点地质统计逐点模拟并行算法的研究[D];中国科学技术大学;2013年

相关硕士学位论文 前10条

1 黄伟钿;面向移动平台的3D图形处理器的设计[D];华南理工大学;2011年

2 王旭;图形处理器的仿真验证[D];哈尔滨工业大学;2007年

3 陈林桦;基于图形处理器的视频转换技术的研究与应用[D];上海交通大学;2009年

4 张杨;图形处理器并行计算应用研究[D];西南交通大学;2006年

5 阙恒;嵌入式图形处理器设计[D];南京航空航天大学;2007年

6 饶志恒;图形处理器图形管线的研究与实现[D];湖南大学;2011年

7 杨国东;嵌入式图形处理器的研究与实现[D];山东大学;2010年

8 王晋君;图形处理器在锥束CT成像中的应用研究[D];首都师范大学;2009年

9 杨新强;基于GPU加速FDTD计算速度的研究与仿真[D];青岛大学;2011年

10 李凯伦;基于计算机图形处理器的海底三维地形可视化[D];哈尔滨工程大学;2013年

，

本文编号：2587689