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

时间:2009-12-13   来源:   网友评论:0   人气: 331 作者:

高性能计算

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

  GPU 强大计算能力

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

  表1:CPU/GPU计算能力比较

  为什么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算法。

表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)字符串匹配算法.


 

文章评论