利用GPU进行高性能数据并行计算

2009-10-15 作者: 丁艺明 刘波 来源: 程序员

关键字: 高性能计算 GPU CPU 

图形处理芯片GPU通过单指令多数据(SIMD)指令类型来支持数据并行计算,提供惊人的计算能力。本文探讨基于GPU的并行编程模型与并行编程等软件技术。虽然GPU最初专门是为图形渲染设计的,通过我们的DES 编解码, MD5密码破解, 字符串匹配等实验,证明GPU还可以有效地执行多种通用的基于整数的计算。本文还讨论了以通用计算为目的GPU发展趋势。

  实验

  我们的实验基于CUDA的SDK以及C语言编译器在8800GT显卡上开发运行的。CPU版程序为双线程,用VC++6.0开发,运行于Intel Core2Duo主频为2.6G赫兹。实验结果中,GPU版程序运行时间包括输入数据流和输出数据流上传和下载到显卡的I/O时间。

  1、DES 编解码

  DES算法对64位数据进行加密后输出64位数据。DES算法可以用流计算模型来实现,输入与输出流的基本数据类型为64位数据。核程序为DES算法。

表2:CPU/GPU DES编码实验结果

  2、MD5密码破解

  在我们的程序中,允许用户输入一长度为五的密码的MD5值,每位密码变化范围是A~Za~z[]\^_`{}|~,共64种字符。穷举所有的密码并用MD5算法得到所有的MD5值,与用户输入的MD5值比较,若枚举的密码MD5值与用户输入匹配,输出该密码。

  MD5 破解可以用流计算模型来实现,输入流基本数据为长度为5个字符的密码,可以枚举出来。所有基于密码产生的128比特 MD5值可看为中间结果流。核程序为MD5算法。最后,把中间结果和输入的MD5值比较的布尔值组成最终结果流。

  表3:CPU/GPU MD5 破解实验结果
 

  3、字符串匹配

  本实验随机产生64M字节的文本和64个长度为8的关键字,找出在输入的文本中出现的关键字。本实验的程序采用的是Boyer-Moore-Horspool-Sunday(BMHS)字符串匹配算法.

  字符串匹配问题用流计算模型来实现,输入流为64M字节文本。核程序为分别对64个关键字进行字符串匹配的算法。把64个关键字字符串匹配结果的布尔值组成结果流。

  值得一提的是,对每个关键词的搜索在窗口内进行,窗口的大小于关键词的长度相等,窗口沿着文本向右滑动。BMHS算法将窗口内文本的最后一个字符(L)和关键字的最后一个字符进行比较。如果相等,则需要在搜索窗口中从后向前对文本和关键字进行比较,直到完全相等或者在某个字符处不匹配。然后,都将根据L在关键字的下一个出现的位置将 窗口向右移动。对每个关键词移动的距离,也就是下次读取字符的位置,是不一样的。参见图 NVDIA GeForce 8体系结构,每次从GPU设备存储器(Device Memory)读取数据需要耗费400~600个时钟周期[1]。本实验把输入文本和一两维图像(纹理)进行绑定,这样也就利用了纹理缓存(Texture Cache)来提高设备存储器的访问速度,减少大量的I/O时间。

  表4:CPU/GPU字符串匹配实验结果
 

  4、实验结果小结

  吞吐量可由输入数据大小比上处理器运行时间。从图3 CPU/GPU吞吐量实验结果表明,GPU在通用计算方面的性能能够比CPU快10倍以上。MD5密码破解程序的I/O最小,DES编码程序次之,字符串匹配程序I/O最大。相对于CPU版程序吞吐量,GPU版MD5密码破解相对性能最高,DES编码程序次之,虽然字符串匹配程序相对性能最低,但GPU版程序也能比CPU版程序快一个数量级。

  GPU能取代CPU吗?

  GPU在运算能力的远远超越CPU,GPU是否能取代CPU呢?答案是否定的。GPU具有CPU所没有的局限性。GPU只提供单指令多数据类型处理,适合于数据并行计算。GPU在条件控制能力方面非常弱,若程序使用条件控制语句会极大影响GPU程序的执行效率。当然,有部分条件控制语句可以用计算来代替,例如,判断两个整数是否相等可以用两个整数异或后再映射成0和1来代替。本文中的实验中,利用了这些技巧来避免使用条件控制语句。另外现在的GPU与主机(host)数据交换只能通过总线来实现,对于需要大量I/O的应用,通讯就会成为GPU性能瓶颈。

  以通用计算为目的GPU发展趋势

  NVIDIA发布Tesla通用计算架构方案,Tesla GPU运算处理器不是一图形处理专业卡,可以看作之前的NVIDIA图形处理专业卡的通用计算版本。

  可以看出,以通用计算为目的GPU发展趋势是GPU和CPU的整合,适合于大量数据并行计算的任务由GPU来承担,GPU定位为CPU的协处理器。需要复杂条件控制的,只能串行处理的任务由CPU来承担。CPU和GPU互相配合工作。

  参考文献:

  [ 1 ] NVEDIA。CUDA Programming Guide。

  [ 2 ] Kapasi。流计算模型。

  [ 3 ] Gonzalo Navarro, Mathieu Raffinot。《柔性字符串匹配》。

  [ 4 ] 沈璐。《GPU为什么跑得快·》。




责任编辑:熊东旭