《利用GPU进行高性能数据并行计算》附MD5破解源码

《利用GPU进行高性能数据并行计算》
丁艺明，刘 波 (趋势科技）

(全文文发表于《程序员》2008第4期)

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

高性能计算

数据库技术的成熟，数据挖掘应用，生物基因技术的发展，历史数据的几何级膨胀等要求高性能计算(High Performance Computing，HPC)。虽然通过创建分布式系统可以解决部分大型计算的问题，但是分布式系统有通信开销大，故障率高；数据的存取结构复杂，开销大；数据的安全性和保密性较难控制等弱点。随着计算机处理器，特别是GPU (Graphical Processing Unit)计算能力的飞速提高，高性能计算逐步进入桌面（低端）领域，这就要求我们探讨并行编程模型与并行编程等软件技术。

GPU 强大计算能力

早期的3D游戏，显卡只是为屏幕上显示像素提供一个缓存，所有的图形处理都是由CPU单独完成。图形渲染适合并行处理，擅长于执行串行工作的CPU实际上难以胜任这项任务。直到1995年，PC机领域第一款GPU 3dfx Voodoo出来以后，游戏的速度、画质才取得了一个飞跃。GPU的功能更新很迅速，平均每一年多便有新一代的GPU诞生，运算速度也越来越快。

Intel Core2Due
Woodcrest G80 Chip 运算能力比较
24 GFLOPS 520 GFLOPS GPU快21.6倍

为什么GPU跑得快？

GPU具有两点主要特征：超长流水线与并行计算[4]。

如果装配一台汽车需要10个时间单元，将它分成10个流水线阶段，每个阶段分配一个时间单元，那么一条装配线每一个时间单元就可以生产一辆汽车。显然流水线模式的生产在理想状况下要比串行方式快了十倍。
GPU通过单指令多数据(SIMD)指令类型来支持数据并行计算。在单指令多数据流的结构中，单一控制部件向每条流水线分派指令，同样的指令被所有处理部件同时执行。例如NVIDIA 8800GT显卡中包含有14组多处理器(Multiprocessor)，每组处理器有8个处理单元(Processor)，但每组多处理器只包含一个指令单元(Instruction Unit)。

GPU流式编程模型

GPU编程以流式编程模型为基础，它以允许高效计算和通信的方式构造程序[3]。在流式编程模型中，所有数据都表现为流。我们把流定义为具有相同数据类型的数据的有序集。数据类型可以是简单的(整数或浮点数流)或复杂的(点或三角形或变换矩阵流)。流可以是任意长度，如果流很长(流中有上百或更多的元素)，那么流上的操作并行度将很高。流上允许的操作包括复制它们，从它们导出子流，用一个单独的索引流索引入它们，以及用核在它们上执行计算。GPU程序称为核，核操作整个流，获取一个或多个流作为输入并产生一个或多个流作为输出。核的特征是它操作多个流上的所有元素而不是独立的元素。

CPU程序以异步的方式调用GPU核程序。GPU作为CPU的协处理器(Coprocessor)提供服务。


实验

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

1　DES 编解码

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

DES 编码 CPU 时间 GPU时间 GPU版比CPU版快
64 M字节 11.4秒 1秒 11.4 倍

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

2　MD5密码破解

在我们的程序中，允许用户输入一长度为五的密码的MD5值，每位密码变化范围是A~Za~z[]\^_`{}|~，共64种字符。穷举所有的密码并用MD5算法得到所有的MD5值，与用户输入的MD5值比较，若枚举的密码MD5值与用户输入匹配，输出该密码。
MD5 破解可以用流计算模型来实现，输入流基本数据为长度为5个字符的密码，可以枚举出来。所有基于密码产生的128比特 MD5值可看为中间结果流。核程序为MD5算法。最后，把中间结果和输入的MD5值比较的布尔值组成最终结果流。

MD5 破解 CPU 时间 GPU时间 GPU版比CPU版快
穷举1G种可能 201秒 15.3秒 13.1 倍

表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时间。

字符串匹配 CPU 时间 GPU时间 GPU版比CPU版快
64 M字节文本 14.5秒 1.4秒 10 倍

表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为什么跑得快?》。

附MD5破解源码, License： GPL V2.

我不能上传源码,错误提示为“不能打开文件”。请发邮件给我 (ding.yiming # gmail.com) 索要源码。