基于GPU的AES算法实现

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函数时，首先要将内存中的数据块读到流中，处理完后，又要将流写回内存。