GPU编程模型

本文节选自本人2012年毕业论文

 

GPU(graphical processing unit)是显卡内用于图形处理的器件。和CPU相比,CPU是串行执行,而GPU是多个核并行执行。GPU是一个高性能的多核处理器,有很高的计算速度和数据吞吐率。在GPU上的运算能获得相对于CPU而言很高的加速比。第一、第二代GPU出现的时候,GPU不是可编程的[4]。当第三代GPU出现的时候,GPU开始用于图形编程,研究者们给GPU烧制程序,进行图像处理。GPU的并行流处理能力吸引了并行计算的研究者,研究者们借助图形编程的概念,把计算操作转化成图形纹理操作。这个时候GPU计算,需要对图形概念有比较深的了解,编程比较复杂。第四代GPU以NVIDIA的GeForce系列显卡为代表,开始提供专门用于通用计算的技术,并且出现了CUDA[17]、openCL[6]等基于c语言的通用编程语言。GPU用于并行计算的技术称为GPGPU(general purpose GPU)[4]。GPGPU涉及的范围很广,包括了几何计算、蛋白质模拟、优化计算、偏微分方程等。

目前的显卡市场,主要有两家公司的产品,一个是NVIDIA显卡,另一个是ATI显卡。通用计算语言有两个标准,第一个是NVIDIA公司的CUDA技术,另一个是由apple公司提出、多家公司共同开发的开放标准openCL。CUDA技术是NVIDIA公司的私有标准。由于NVIDIA公司最先尝试GPU通用计算,其研发的用于通用计算的显卡和用于通用计算的编程语言CUDA最早出现在市场上。因此,CUDA技术相对于其他的技术而言,拥有很强的优势,关于CUDA技术的资料和讨论也比较多。而openCL是一个开放标准,多家公司的产品都支持该标准,包括NVIDIA显卡,还有ATI显卡的stream技术也支持该标准。由于openCL开发的比较晚,在其开发时,CUDA技术已经很成熟了,因此openCL在很多概念上借鉴了CUDA技术。openCL相对于CUDA技术的优势是很明显的,因为openCL是一个开放的标准,任何一台机器上用openCL写出的程序,放到另一个有不同类型的显卡的机器上后不需要做任何修改。基于以上的考虑,本课题采用的是openCL标准。

遗传算法在两方面存在计算量比较大的问题。第一是遗传计算,从本质上来讲,遗传算法仍是一个搜索算法。随着科技的发展,遗传算法所求解的问题越来越复杂,遗传算法在求解效率和优化质量上,都显得有些不足。遗传算法本身有着很好的并行性。每个个体的适应值评价和产生下一代个体的过程,都互不干扰。在并行遗传算法中,各个种群之间也互不干扰。因此这些操作可以并行的执行。第二是遗传算法的理论分析,在理论分析中,需要进行势函数的求解,这个求解过程是非常复杂的,但是也可以做并行化处理。本课题就是采用GPU编程技术,在GPU上实现了传统遗传算法、分布估计算法UMDA和势函数模型。

在本章中,将详细介绍GPU的编程模型,为后文提供理论基础。

1.1.   GPU硬件架构

在GPU编程的硬件结构中,整体设备被分为两个部分。第一个部分是控制设备,称为Host(主机)。第二部分是计算设备,称为device。

Host 负责管理GPU的运行,以及资源的分配管理。准确的说,研究者是通过和Host交流,来控制GPU。Host通过openCL api 来和计算设备交互。Host是运行于CPU上的。运行于Host上的程序称为host program。

计算设备的整体又划分了很多的计算单元(compute Unit)。每个计算单元有一些共享资源,同一个计算单元内的处理元可以实现同步。每个计算单元又划分成若干个处理元。真正的计算发生在处理元上。运行在每个处理元上的实例称为kernel。

假设有N个计算单元,每个计算单元有M个处理元。那么总共有N*M个核。同一时刻,就可以再设备上运行N*M个实例。因此,如果不考虑I/O等其他因素,加速比的理论上限是N*M。

图 2-1  GPU硬件抽象模型

1.2.   GPU软件架构

图2-2 OpenCL编程模型

 

openCL把整个计算设备的空间划分成N维(N=1、2、3),称为NDRange。每一个维度上的又划分成若干个工作组(work group),每个工作组又包含了若干个工作单元(work item)。在每一个维度内,每一个工作组都有一个唯一group id标识。每一个工作单元都有一个唯一的global id。在每一个维度的每一个工作组内,每个工作单元都有一个唯一的local id标识。每一个工作单元的global id可以和所属工作组的group id和local id换算。

和上一小节相比,在上一小节中提到的计算单元和处理元的概念都是硬件概念。而本小节提到的维度、工作组、工作单元的概念是抽象概念,和硬件概念之间没有关联。每一个工作单元,可以由一个或者多个处理元构成。

每一个维度上的每个工作组的大小有一定的限制[1],所有维度内属于同一个工作组的工作单元的数目不能超过硬件一个计算机群的大小。假设每个维度的工作组大小分别是N1,N2,N3,计算单元的大小是size,那么有N1*N2*N3<=size。

图2-2中展示的是一个二维空间。其形式类似于二维矩阵,只是每个维度上还有工作组的概念。

1.3.   openCL存储模型

openCL的存储根据作用域可以分成四个级别。依次是:全局内存,常量内存,局部内存,私有内存。

全局内存,对于所有工作组内的所有工作单元都可读和可写。但是对这部分内存的读写可能会被缓存,因此多个处理单元处理同一块内存时,要注意进行同步。

常量内存,作用域和全局内存一样,但是只可读,不可写。全局内存和常量内存都是由host进行分配空间和初始化的。

局部内存,顾名思义,只对部分处理单元可操作。其作用域在同一个工作组内。这部分的硬件位于计算单元内部。

私有内存,仅限于单个工作单元可读写,其硬件位于处理单元内部。通常,在工作单元上运行的kernel实例,其函数局部变量是分配在私有内存上的。

openCL的全局内存通常用于放置gpu的入口参数,以及GPU的运行结果。openCL的程序本身是不提供返回值的,因此如果要获得返回值,就需要把运行结果放入全局内存。在程序结束后,由host程序读取全局内存区的数据,从而获得返回值。

1.4.   openCL的执行模型

对于openCl而言,有两种类型的执行方式,第一种是任务并行模型,第二种是数据并行模型。

任务并行模型是指,每个工作单元内,运行一个kernel实例,但是不同的单元运行的实例可能不一样。

数据并行模型是指,每个工作单元内,运行的是同一个kernel实例,只是每个单元处理的数据不一样,由于每个单元都有一个唯一的id标识,所以,可以通过这个id来指定这个单元处理的是哪些数据。

在遗传算法的实现方式中,本文采取了数据并行模型。

1.5.   同步

在遗传算法中,对于每一次迭代,有些操作需要等待所有的工作单元完成后才能进行。比如,对于传统遗传算法,在选择操作前,需要所有的个体同时完成个体适应值的评价。因此需要同步操作。

在openCL中,存在一个API:barrier(cl_mem_fence_flag)。标志位有两个选项,LOCAL_MEM_FENCE 和GLOBAL_MEM_FENCE,分别用于同步局部内存和全局内存。同步的处理单元必须在等待所有的处理单元都执行到该函数时,才能执行下一条语句。

然而,正如前文讲到的,一个工作组的大小是有限制的,这个限制就是一个计算单元的大小。计算单元的划分是硬件限制,属于同一个计算单元的处理单元共享计算单元内的内存和其他资源。GPU对同步的实现也依赖于硬件,因此,只有属于同一个计算单元的处理单元才能够实现同步。对于程序开发者而言,openCL弱化了硬件架构,开发者只知道工作组这一概念,不清楚计算机群这一概念。因此,openCL的同步只发生在同一个工作组中。

在遗传算法中,随机过程往往需要很大的基数才能保证一些小概率事件的发生。比如变异操作,这个操作的概率很小,如果样本数量小的话,很难保证会发生变异。但是,如果样本数量超过了一个计算单元的大小,那么就会导致同步问题。因此在这一点需要折中考虑。同一个群体的个体可以放到同一个计算单元中运行,不同的群体放到不同的计算单元上。种群间无需同步。这样既满足了样本的数量需求,也满足了同步要求。

1.6.   GPU程序的执行流程

GPU程序分两部分,一部分在CPU上执行,这部分程序称为host program,一部分在GPU上执行,这部分程序称为kernel[2]。Host 程序负责初始化环境,包括GPU运行环境和参数。Kernel则负责计算,并把计算结果写入内存,由host读取。完整流程如图2-3:

图2-3: GPU程序完整运行流程

 

1.7.   本章小结

本章详细介绍了GPU编程模型,包括GPU的硬件框架,介绍硬件相关的背景;编程模型介绍软件的框架;存储模型讲述GPU的内存模型,执行模型讲述GPU的编程框架。此外还有在GPU中编程需要注意的一些问题,比如随机数,同步问题。最后介绍了一个完整的GPU并行程序的流程。

 

 

[1] 硬件限制,原因在“同步”小节“中指出。

[2] Kernel(核)是运行在一个工作单元上的实例,为了简单,在本文后边提到核和工作单元时,指同一事物

发表评论

电子邮件地址不会被公开。 必填项已用*标注