基于GPU的AES算法实现

摘要：近几年图形处理器GPU的通用计算能力发展迅速，现在已经发展成为具有巨大并行运算能力的多核处理器，而CUDA架构的推出突破了传统GPU开发方式的束缚，把GPU巨大的通用计算能力解放了出来。本文利用GPU来加速AES算法，即利用GPU作为CPU的协处理器，将AES算法在GPU上实现，以提高计算的吞吐量。最后在GPU和CPU平台上进行了实验，获得了GPU的加速结果，并对实验结果进行了优化。
关键词：图形处理器；统一计算架构；高级加密标准算法

0 引言
随着通信技术高速发展，信息安全也越来越重要。加密技术是对通信系统或者存储系统中的信息数据进行保护的一个很重要的方式。AES(高级加密标准)算法是一种分组密码算法，具有极高的安全性能，自提出之日起便成为信息安全领域研究的热点。由于该算法在实现方面具有设计简单，速度快，可并行处理，分组长度可以改变，对处理器结构无特殊要求等特点，在电子商务、网络安全和数据存储等多个领域得到了广泛的应用。然而，硬件实现需要较长的开发周期和很高的成本，并且硬件实现不灵活，不易后续的升级和维护，而且只适合做部分算法的实现，限制了应用领域和范围。近几年GPU(图形处理器)已经成为普及的电子消费品，在市场需求的驱动下，GPU已经发展成为具有巨大运算能力和极高内存带宽的并行多核处理器。近几年在某些信号处理任务中使用GPU的运算性能超过了FPGA。
传统的GPU开发具有很大的难度，而且由于无法充分利用GPU的资源，并且很多的开发精力是用在将应用转换到图形上，这就限制了GPU用作通用计算的应用范围，并且影响了GPU进行通用运算的性能。为了改变这一现状，NVIDIA公司在2006年年底推出了一种利用GPU进行通用计算开发的架构，称作统一计算设备架构，简称为CUDA。它对GPU的结构和资源进行了抽象表示，并且为GPU的资源提供了访问接口，这就使得开发者能够根据抽象的GPU结构进行通用计算应用的设计，并且可以充分利用到GPU中的资源。

1 AES算法分析
AES算法由NIST在2001年11月26日公布，并在2002年5月26日成为标准。AES算法具有分组长度和密钥长度均可变的分组密码。密钥长度和分组长度可以独立地指定为128bit、192bit或256bit。AES加密的圈数是一个变量，主要依赖于密钥长度，所有的运算都将在一个4×4字节的模块上进行。每圈包括4个顺序步骤：圈密钥加，字节代替，行移位，列混合。在加密以前，我们必须使用密钥扩展算法扩展密钥。
状态可以用字节为元素组成二维数组阵列，共4行，Nb列，Nb等于数据块长度除以32。密钥的设计类似二维字节数组，也是4行，Nk列，且Nk等于密钥块的长度除以32。AES算法使用的是圈变换，其变换的圈数Nr由Nb和Nk共同决定，如表1所示：

从具体规则上，AES算法在进行加解密运算时都会按照三大步骤进行，依次为1)初始化的圈密钥加法；2)(Nr-1)圈变换；3)最后一圈变换。这里以加密过程为例，其加密过程用伪代码表示如下。

解密过程是加密过程的逆过程。

2 CUDA编程简介
2．1 CUDA简介
CUDA全称是Compute Unified Device Architecture，是NVIDIA公司在2006年11月推出的一种在GPU上进行通用计算的架构。它具有全新的并行编程模型，不需要像传统GPU开发方式那样进行图形API的映射就可以使用GPU的资源进行并行计算。CUDA是一个包含软件和硬件的完整的并行计算架构，它的硬件设备是具有多个流处理器核的图形并且支持CUDA的GPU，软件部分包括编译工具、驱动程序、runtime库和一些常用的数学运算库。
2．2 CUDA中GPU结构
在CUDA架构下，开发者可以通过创建和管理大量的线程来使用GPU的硬件资源进行并行计算。在CUDA中线程的创建和切换是由硬件来实现的，不会占用软件的执行时间。在CUDA的rtmtime库中提供了访问GPU硬件资源的接口，用户通过调用runtime库中的函数就可以直接访问GPU的硬件资源。CUDA的编程语言是一种C语言的扩展，提供了通用的DRAM寻址方式，从而提供了很大的编程灵活性。操作系统可以管理多个并发运行的CUDA程序和图形应用程序来访问GPU。

3 CUDA编程模型
由于GPU的特点，它很适合做高密度数据的并行运算，但是对于不能并行的具有复杂执行路径的程序执行效率就会很低。因此当通过CUDA在GPU上进行通用计算的开发时，是把在应用程序中高密度数据可以进行并行计算的部分做成一个称作kernel的函数在GPU设备上执行，而应用程序中的其他串行执行的部分由主机上的CPU来完成。一个在GPU上执行的kernel可以包含极高数量并发执行的线程，在CUDA架构中是通过设计kernel中的线程来完成通用计算的GPU实现的。主机和GPU设备之间的交互是通过在主机和设备各自的DRAM之间传输数据来实现的，而这种数据传输是由设备的DMA引擎完成的，因此数据的传输并不会造成太多主机CPU开销。
一个kernel中的线程是被分成具有相同大小的线程块的，线程块可以是一维、二维或者三维的，因此对应的线程就可以具有一维、二维或者三维的索引。在一个线程块中每个线程都具有一个一维的ID，这个ID和索引具有以下kernel关系：对于一维的线程块，线程就等于其索引；对于大小为ID(Dx，Dy)的二维线程块，索引为(x，y)的线程ID为(x+v Dx)；对于大小为(Dx，Dy，Dz)的三维线程块，索引为(x，y，z)的线程ID为(x+y Dx+z Dx Dy)。
同一个线程块中的线程之间可以通过同步操作来协同内存访问。当通过调用内置函数_syncthreads()在kernel中建立同步点时，一个线程块中的执行到同步点的线程会被挂起直到这个线程块中所有的线程都到达这个同步点。
为了线程之间能够有效地协同工作，同步操作被设计成只需要一条指令就可以实现，并且同一个线程块中的线程需要在同一个多核处理器上执行。因此每个线程块中全部线程的数量就受到一个处理器核上的存储资源的限制。在当前的GPU上，一个线程块可以包含最多512个线程。
虽然一个线程块可以包含的线程数量有限制，但是一个kernel可以包括多个大小相同的线程块，kernel中的线程数就等于每个块中线程的数量乘以线程块的数量。线程块之间是独立的，它们可以并行地执行，也可以串行地顺序执行。这就允许线程块在多个处理器核之间按照任何顺序调度，从而使得开发具有灵活性和可扩展性。而且这样线程块的数量就可以根据待处理数据的大小决定，而不是由系统中多核处理器的个数决定，也就是说线程块的数量可以大于多核处理器的数量。因此kernel中可以具有大量的线程块，从而具有极高的线程数。但是由于线程块之间执行的不确定性，不同线程块的线程之间不能进行同步操作。
3．1 算法设计
首先把待处理的大数据块划分为尺寸相同的多个小数据块，然后使用标准的AES算法对各个小数据块进行并行的运算，运算完成后把每个小数据块的值按顺序保存在一起，最后再把所有的输出结果使用标准的AES算法来处理得到最后的结果，这样就可以使用大量的线程来并行地对每个小数据块进行运算。但是当数据分块足够多线程数很大时，就需要将线程划分为多个线程块。由于不同线程块中的线程之间不能进行同步，所以设计了两个kernel，第一个kernel的任务是使用大量并发执行的线程对原始数据分成的多个小块数据进行运算，并把结果按照顺序保存在设备DKAM中。等第一个kernel执行完成后，由主机启动第二个kernel，这个kernel会根据主机提供的地址和数据大小对第一个kernel的计算得到的中间值进行运算，这一步只需用一个线程来执行，由于中间值的大小远远小于原始数据，所以这一步的计算开销是很小的。
3．2 算法优化
GPU计算虽然高效，但是也有瓶颈。CPU代码在调用GPU的kernel函数时，首先要将内存中的数据块读到流中，处理完后，又要将流写回内存。
GPU和内存的数据交换是一笔很大的开销，因此从整体上减小这部分的开销是优化的关键。从GPU执行的特点来看，每个线程都独自从内存中读取一个分组长度的数据块，加密完成后写回到内存中。这样，每加密一个分组长度都要读写一次内存，整体IO效率低。根据程序的局部性原理，如果一次读入相邻的多个分组，IO效率会大大提高。在前面的GPU程序中，我们是在一个线程里加密一个分组。现在我们一次读取多个分组进行加密。这样从整体上提高了IO效率。鉴于线程处理器还可以进行并行操作，我们还可以使用流数据类型，进一步提高并行度。
改进的算法如下：
brook：：Streamint>*datastream；
datastream．read(Block[m][n])；
AESEncrypt_CPU_Simple(dtatastream)；
Datastream．write(Block[m][n])；
改进后，每个线程一次读取n个相邻的分组进行加密。

4 实验设计
实验采用的CPU是GeForce 9800 GTX+，软件使用GUDA2．1，是在WmdowsXP操作系统下运行的。
CPU对AES算法的加速结果如图1所示。从图中可以看出，当数据量较小时(小于100kB)，GPU上的运行性能要低于CPU，这是因为GPU的特点是适合用作高密度数据的并行计算，而当数据量较小时并无法充分利用到GPU的计算资源，而且从主机向设备传输输入数据和由设备向主机返回数据又会占用一定的开销，因此对于小数据量的处理并不适合使用GPU。随着数据量的增加，GPU运算的性能就会明显高于CPU。当数据量大于1MB时，GPU具有将近两倍的加速倍数，之后加速倍数就基本稳定下来，达到饱和，这是因为当数据量已经足够多，充分利用了GPU的计算资源。由于GPU的计算能力远远高于它访问设备内存的带宽以及主机与设备之间的数据传输带宽，在应用中这些数据传输的开销会成为限制GPU运算整体性能的瓶颈，需要对GPU进行优化，才能充分开发出GPU的计算优势。
图1 GPU对AES算法的加速效果