基于图形处理器的STM研究与实现

梁 飞，胡大裟，蒲亦非

(四川大学 计算机学院，成都 610065)

胡大裟(1976- )，男(汉族)，四川泸州人，讲师，博士，研究方向：并行计算、编程语言、软件工程。

基于图形处理器的STM研究与实现

梁 飞，胡大裟，蒲亦非

(四川大学 计算机学院，成都 610065)

多核处理器和基于图形处理器通用计算(GPGPU)的发展，提出了简化并行编程的需求,而软件事务存储(STM)通过标记代码段并保证其执行的原子性为简化并行编程提供了很好的选择。为降低图形处理器(GPU)并行编程的复杂性，在分析GPU编程中存在的同步问题，结合统一计算设备架构(CUDA)的特点以及影响STM重要因素的基础上，提出在编程环境中引入STM模型的编程方法，测试结果表明相对基于CPU的计算依然具有良好的加速比。

图形处理器；软件事务存储；通用计算；统一计算设备架构

图形处理器(Graphics Processing Unit，GPU)具有高带宽、强大的浮点处理能力，适合高密度的科学计算[1]。随着GPU可编程性的不断提高，利用GPU进行通用计算的研究越来越多，但目前对GPGPU(General-purpose computing on graphics processing units)的研究大多集中在GPU应用程序的开发与优化上，对GPU编程、调试、容错方面的研究较少，基于GPU编程面临着开发移植困难、维护成本高等问题，如何开发并行可扩展应用以充分利用GPU的计算能力成为一大挑战[2]。这其中的一个关键问题在于如何简化多核平台下的开发模型，如何降低复杂的同步逻辑。

近年来，事务存储[3](Transactional Memory, TM)在多核并行程序开发方面的研究越来越多，它相对于锁机制的优势得到更多认识。TM允许开发人员只需标记并行代码段而不用关注同步逻辑，代码段并行执行的原子性由TM来保证。本文在GPU编程模型中引入TM以降低并行应用开发中的同步逻辑复杂性，提高基于GPU的通用计算的可编程性。

1 研究现状

最初针对GPU的编程局限于顶点处理器(vertex processor)和像素处理器(fragment processor)提供的有限功能，必须通过图形学的API进行调用。随后出现了完全可编程像素处理器，并提供伪汇编语言[4]。随着GPU硬件单元可编程性的不断提高以及DirectX 9的推出，出现了类C的高级绘制语言(High-level shading language, HLSL[5])、NVIDIA Cg[6]等，但是依然需要开发人员将计算任务映射为对纹理的渲染过程，然后通过编程调用图形学API执行计算。这些编程方式不仅要求开发人员熟悉需要实现的计算和并行算法，而且要对图形学硬件和编程接口有深入的了解，难以在普通开发人员中推广。

为解决绘制语言存在的问题，使开发人员在利用GPU计算的同时不必考虑GPU的图形结构，研究人员将GPU的结构纳入流处理机的模型，进而实现以高级语言编程。BrookGPU[7]是较早致力于将GPU抽象为流处理器，进而隐藏图形学API实现细节，推动基于GPU通用计算的科研项目。BrookGPU通过流数据类型定义数据流，开发人员只关注计算数据及其上的操作，由BrookGPU编译器完成从源程序到Cg的编译工作，然后由GPU厂家提供的Shader程序翻译为汇编代码，从而使开发人员从图形API中脱离出来。随后NVIDIA公司借鉴BrookGPU项目理念推出了GPU编程平台CUDA(Compute Unified Device Architecture)[8]，NVIDIA CUDA采用类C语言进行开发，提供了更高层次的抽象接口，利用CUDA进行通用计算开发完全不需要借助图形学API。同时支持CUDA的GPU采用了统一处理架构，并引入片内共享存储器，支持随机写入和线程块内通信，更有利于开发基于GPU的通用计算应用。

为了运用CUDA进行计算仍然需要分配管理存储器、建立启动核运算，研究人员设计了更抽象的编程语言如PyCUDA[9]、JCUDA[10]等。在PyCUDA中，开发人员使用Python编程，然后由编译器负责生成在GPU上执行的CUDA代码。而JCUDA利用JNI技术建立Java与CUDA的接口，开发人员可以在Java程序中嵌入CUDA代码实现应用加速。这些建立在CUDA之上的编程语言，降低了基于CUDA编程的复杂性，但是并没有考虑解决CUDA计算中的数据同步问题。

CUDA能够胜任高度并行的大数据量计算任务，在线程同步通信方面提供了原子操作和内存栅栏，以及线程块内的共享内存[11]。在CUDA的编程模型中，线程块内的线程可以使用共享内存通信，并由synchronize实现内存栅栏同步，而线程块之间并不能进行通信，只能在全局内存中使用原子操作，而对全局内存的同步操作将严重影响计算性能[12]。在线程块内，基于线程束(wrap)的执行机制也增加了同步的复杂性，线程束内的所有线程执行同一个指令，如果某个线程因为同步问题产生等待，就会导致整个线程块陷入忙等状态。而基于流的计算模式在实现复杂计算时需要多个流执行多个核(kernel)函数，以及核函数的并行，更是给数据同步带来了难以想象的复杂性[13]。

2 系统模型及设计

为了降低并行编程中同步逻辑的复杂性，本文在GPU编程模型中引入软件事务存储[14](Software Transactional Memory, STM)，由STM来保证事务执行的原子性，从而使开发人员从复杂的同步逻辑中解脱出来。而CUDA已经在各行业应用中表现出优异的加速效果，同时兼容CUDA并且计算能力2.0以上的GPU已经可以支持浮点数的原子操作，比如CAS(Compare And Swap)操作，可以用来实现锁互斥以及无锁(lock free)的数据结构[15]，进而为在CUDA平台上实现STM提供了基本保障，为此本文选择在CUDA平台基础上实现STM。

2.1 CUDA平台计算特点

CUDA是目前基于GPU通用计算平台的杰出代表，由于GPU强大的并行计算和浮点计算能力，使得利用CUDA解决以往的复杂任务成为可能。从任务划分编程来看，执行计算任务的内核(kernel)被组织成线程块(block)，线程块又被组成网格(grid)。同一个内核程序可以并行运行在网格中所有线程块中的线程上，线程块负责执行粗粒度的并行任务，而线程块内的线程可以通过线程块内的共享内存及同步操作协作完成细粒度的任务。从硬件架构上来看，兼容CUDA的GPU采用统一的计算架构，最基本的处理单元是流处理器(Streaming Processor, SP)，多个SP和寄存器、共享内存等组成流多核处理器(Streaming Multiprocessor, SM)，几个SM又组成计算阵列，进而从硬件上支持并行任务的划分及调度。从CUDA程序单指令多线程的执行模式来看，每个SP对应一个线程，每个SM对应一个或多个线程块，但SM执行计算时却是以wrap为单位而非线程块，因为线程块中分配的线程数可能远远高于SM中包含的SP数目，通常wrap由ID连续的32个线程组成，执行指令时由调度器选择一个准备好的wrap执行，如果某指令需要等待，SM会自动切换到下一个wrap块来执行，以此隐藏线程的延迟和等待达到大量并行的目的。

无论从GPU的硬件架构还是CUDA程序的执行模式来看，都是为了达到大量并行计算的目的，因而GPU通常具有相对CPU更大的内存带宽，更多的计算执行单元，这是GPU具备大量并行能力及强大的浮点计算能力的根本，但也同时带来CUDA计算的缺点，比如对并行程度不高、具有高度分支的程序运行效率较低，即便是对线程块内共享内存的操作，也有可能因为访问位置冲突而造成性能的严重下降，同时只提供了线程同步功能，并不能完全满足开发人员对并行编程数据同步的需要。

2.2 CUDA STM的策略选择

从开发人员的角度来看，STM需要提供以下几个基本操作。“begin”用来标记一个事务的开始，“read”从全局内存中读取数据，“write”记录更新的数据，最后如果事务没有发生冲突“commit”操作负责将更新的数据写回，否则事务中断并伺机重新执行。然而具体到如何实现这些操作，就必须根据STM的使用环境选择合适的实现策略，以下将结合CUDA平台架构及高并行高密度计算环境的特点，从演进性、冲突检测粒度、冲突检测时间、直写/回写方面分析CUDA环境下STM的设计需要关注的因素。

2.2.1 演进性

并发事务的演进性(Progress Guarantee)分为2种：阻塞和非阻塞[14]。在阻塞方式下，事务首先要获取共享对象的访问权才能访问共享对象，而非阻塞方式下检测到冲突的事务必须有一方放弃。非阻塞方式又分为3种：最严格的是无等待(wait-freedom)[15-16]，它要求一个事务必须在有限的步骤中完成，通常用于实时系统中，实现较为复杂而且性能偏低；较弱的是无锁(lock-freedom)[17]，在此条件下至少有一个事务必须在有限的步骤中完成，采用无锁方式系统不会产生死锁但是有可能出现饥饿现象；要求最弱的是无干扰[18](obstruction-freedom)，无干扰环境下要求没有发生冲突的事务能够执行成功，而产生冲突的事务可能会彼此放弃而导致饥饿，通常依赖冲突管理器来决定哪个冲突事务需要回退。而阻塞方式是基于锁的实现，不提供任务演进保证。

鉴于锁机制产生的种种问题，目前大多数STM实现方式是非阻塞的。在3种非阻塞方式中，文献[19-20]证实基于无干扰的实现方式相对无锁更简单，同时能够提供更好的并发性能。而CUDA平台的定位是高度并行计算，对复杂的逻辑控制要求较低，因而在CUDA平台上构建STM时选择无干扰的实现方式。

2.2.2 冲突检测粒度

STM的冲突检测粒度分为对象[20]和字2种。基于字的检测粒度在事务更新内存单元前，首先要通过原子操作进行声明，告知其他事务，成功获取更新内存的所有权后才能进行内存更新操作，完成后再以原子操作消除声明，如果获取所有权失败，当前事务就要中断并消除声明。而基于对象的检测粒度要求事务在更新对象前，由事务生成对象的副本，事务的更新操作在副本上进行，在提交阶段校验对象及副本的一致性，获取对象的访问权，然后将副本拷贝到对象位置。

结合CUDA的计算环境，对整数、浮点数都已提供原子操作[12]，基于字的实现在更新数据前后还要求原子声明及消除声明，更增添复杂性，另外基于GPU的通用计算中采用C++、Java进行编程已是大势所趋，应用开发中越来越多的采用动态分配和使用的数据结构，因此在CUDA平台上构建STM时采用基于对象的实现方式。

2.2.3 冲突检测时间

STM的冲突检测时间可分为早检测和晚检测[20]。早检测策略在事务中产生读写操作时都会检测是否有冲突存在，以此来保证共享对象的一致性。晚检测是在事务提交阶段才检测是否存在冲突事务，相对而言，早检测可以更及时地发现冲突，进而避免后续的不必要计算，且实现简单，但其开销明显大于晚检测。考虑到运用CUDA加速应用的初衷，在引入STM保证事务执行特性的基础上，尽可能的降低对CUDA性能的影响，同时在采用基于对象的检测粒度的前提下，采用晚检测策略更为方便。

2.2.4 直写和回写

在事务提交之前通常不知道事务能否成功提交，为保证事务执行的原子性和一致性，一旦事务提交失败就需要撤消事务做出的更改。我们借鉴数据库中常采取多版本并发控制策略(Multi-Version Concurrency Control, MVCC)，在事务中记录所有的更改，即第一次读取对象时，就在事务中创建一个对象的副本，随后的写操作都在本地副本上进行。到事务提交阶段获取所需的锁，再将本地副本写回到全局内存，这种方式称为回写。另一种更积极的并发控制策略(Optimistic Concurrency Control, OCC[21])是直接操作共享内存写入更新对象，如果没有冲突产生这种策略效率更高，但也有可能被中断，同时需要撤销日志来保存最初的对象。为了保证在引入STM后不带来太多的额外开销，以及前面采用基于对象的实现方式，构建CUDA平台上的STM采用回写方式。

3 实现

综合以上构建STM的设计策略并结合CUDA计算平台的特点，首先确定STM采用基于无干扰的实现方式，相对于无等待、无锁方式，实现方式更简单同时提供更好的并发性能，相对于阻塞型的实现方式，可以有效避免锁机制带来的死锁等问题。同时考虑到CUDA对整型、浮点型已提供原子操作，将STM的检测粒度定为对象级，有利于在计算中采用更复杂的数据结构。此外结合CUDA环境下计算高度并行冲突较低的特点，以及直写方式可能带来的可见性问题，基于CUDA的STM实现采用回写方式，晚检测策略。以下详细解析基于CUDA的STM如何实现4个基本操作。

图1 STM事务描述符

图2 对象访问互斥锁

3.1 Begin

在CUDA环境中，线程块作为任务粗粒度划分及并行计算调度的基本单位，也只有在线程块内才能进行线程间的通信同步[12]，因此笔者选择在线程块内初始化事务的执行环境，以及事务的相关描述配置信息。通过在线程块内构建事务描述符来记录事务读写对象的位置指针、版本号等信息。图1展示了事务描述符的结构，version是用于MVCC的版本号，global指针用于指向全局内存中要读写的数据，local指向事务创建的数据副本，布尔型变量update用以指示线程块内的副本是否被更新，如果数据副本没有更新，在提交阶段就不必拷贝回全局内存。

3.2 Read

Read操作首先检测要读取的数据是否加有排它锁，以判断当前是否有其他事务正在更新数据。若没有则从全局内存中读取对象并在事务中创建对象副本，同时记录当前对象的版本号，并更新事务描述符中的version字段，将global和local指针分别指向全局内存中对象及本地的对象副本。Read操作将返回指向本地副本的local指针，以便后续进行读写操作。用于实现对象访问互斥锁的结构如图2所示，version代表版本号，lock代表commit阶段获取对象写权限的锁，利用CUDA提供的CAS操作可以方便的实现排它锁。

3.3 Write

Write操作是在副本上进行的更新，因为数据副本属于线程私有，所以此阶段无需加锁。调用Write操作首先通过传入指针参数查找到要写入数据的位置，然后将传入的数据参数写入到副本位置上，同时将事务描述符中的布尔变量update设置为true，以便在Commit阶段判断是否需要将副本写回到全局内存。

3.4 Commit

在Commit阶段首先尝试获取全局对象的互斥锁，成功获取锁后比较事务描述符中版本号和互斥锁版本号是否一致，如果一致则将local指向的对象副本写回到global指向的全局内存位置，同时使用原子递增操作更新互斥锁的版本号。如果无法获取互斥锁，或者版本号匹配不一致，当前事务中断并重新执行，伪代码如图3所示。通过MVCC及互斥锁机制，可以保证全局内存数据的一致性，同时采用回写策略避免了数据可见性问题。

图3 STM commit

4 实验结果与分析

表1 CPU、CUDA、CUDA STM下双调排序耗时统计 ms

从表1中可以看出，在CUDA平台中引入STM后，确实带来了一定的开销，但从统计数据来看，随着数据量的增加，带来的性能开销呈现明显的下降趋，相对基于CPU的排序算法，依然保持着大约4～5倍的加速比。

5 结语

本文分析了在CUDA环境下STM的设计选择策略及基本操作的实现，最后通过测试验证了基于GPU平台STM的可行性。相对于CUDA支持整型、浮点的原子操作，引入STM后可以构建更复杂的数据类型，并保证其执行的原子性，简化了编程的同步逻辑。当然相对于功能完善可以提供较复杂的事务执行配置及动态竞争管理策略[23]的STM而言，基于GPU平台的STM在性能上还存在一定的差距，但完全适用于GPU计算数据密度大高度并行的计算环境，引入STM带来的开销完全可以由GPU强大的处理能力和高带宽来弥补。相信随着GPU的不断完善和STM研究的不断深入，两者的结合必然可以有效推动GPGPU的发展。

[1] 吴恩华.图形处理器用于通用计算的技术、现状及其挑战[J].软件学报,2004,15(10):1493-1504.

[2] 陈庆奎,王海峰,那丽春,等.图形处理器通用计算的研究综述[J].黑龙江大学自然科学学报,2012,29(5):672-679.

[3] HERLIHY M,MOSS J.Transactional memory:architectural support for lock-free data structures[C]//In Proceedings of the Twentieth Annual International Symposium on Computer Architecture,1993.

[4] LINDHOLM E,KILGARD M,MORETON H.A user-programmable vertex engine[C]//In:Proc.Of the SIGGRAPH,2001:149-158.

[5] PEEPER C,MITCHELL J.Introduction to the directX 9 high-level shader language[J].ShaderX2: Introduction and Tutorials with DirectX, 2003,9.

[6] MARK WR,GLANVILLE S,AKELEY K,et al.Cg:A system for programming graphics hardware in a C-like language[C]//ACM Trans on Graphics(TOG).ACM,2003,22(3):896-907.

[7] BUCK I,FOLEY T,HORN D,et al.Brook for GPUs: Stream computing on graphics hardware[C]//ACM Transaction on Graphics(TOG).ACM, 2004,23(3):777-786.

[8] NVIDIA Corporation.什么是NVIDIA CUDA? 2012[EB/OL].[2010-02-01].http://www.nvidia.cn/object/cuda-cn.html.

[9] KLOCKNER A,Pinto N,LEE Y,et al.PyCUDA:GPU runtime code generation for high performance computing[R].Providence,RI:Brown University,2009.

[10] YAN Y H,GROSSMAN M,SARKAR V.Jcuda:a programmer-friendly interface for accelerating java programs with cuda[C]// Euro-Par’09: Proceedings of the 15th International Euro-Par Conference on Parallel Processing. Berlin Heidelberg: Springer-Verlag, 2009:887-899.

[11] NVIDIA Corporation. CUDA C programming guide, 2012[EB/OL].[2013-02-01].http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html.

[12] 张舒,禇艳利.GPU高性能运算之CUDA[M].北京:中国水利水电出版社,2009.

[13] HOU Q M,ZHOU K,GUO B N.Bsgp:bulk-synchronous GPU programming[C]//SIGRAPH’08: ACM SIGGRAPH 2008 papers.New York:ACM, 2008:1-12.

[14] SHAVIT N,TOUITOU D.Software transactional memory[C]//In PODC’95:Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing .New York,1995:204-213.

[15] DUBLA P,DEBATTISTA L,CHALMERS A.Wait-free shared-memory irradiance cache[C]//In Eurographics Symposium on Parallel Graphics and Visualization,Eurographics,2009,3:57-64.

[16] HERLIHY M.Wait-free synchronization[J].ACM Transactions on Programming Language and System,1991,13(1):124-149.

[17] FRASER K.Practical lock-freedom[D].Thesis:King’s College,University of Cambridge,2003.

[18] HERLIHY K,LUCHANGCO V,MOIR M.Obstruction-free synchronization: double-ended queue as an example[C]//In Proceedings of the 23rd International Conference on Distributed Computing Systems,2003.

[19] HARRIS T,FRASER K.Language support for lightweight transactions[C]//In Proceedings of OOPSLA,2003.

[20] HERLIHY M,LUCHANGCO V,MOIR M,et al.Software transactional memory for dynamic-sized data structures[C]//In Twenty-Second Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing,2003.

[21] KUNG H,ROBINS J.On optimistic methods for concurrency control[J].ACM Transactions on Database Systems,1981,6(2):213-226.

[22] YE X,FAN D,LIN W,et al.High performance comparison-based sorting algorithm on many-core GPUs[C]//In Proc. Of the 24th International Symposium on Parallel and Distributed Processing (IPDPS).IEEE Computer Society, 2010.

[23] 石东旭.软件事务存储动态竞争管理策略[J].软件导刊,2012,11(4):6-8.

ResearchandImplementationofSoftwareTransactionalMemoryBasedonGraphicsProcessorUnite

LIANGFei,HUDasha,PUYifei

(College of Computer Science，Sichuan University，Chengdu 610065，China)

The development of multi-core processor and GPGPU (general purpose computing on graphics processors) creates a demand for ease of parallelization. STM (Software transactional memory) provides a good choice to simplify the development of concurrent code by allowing the programmer to mark sections of code to be executed atomically. To simplify the relatively complex of parallel programming on GPU (Graphics Processing Unit), synchronization problems of GPU programming are analyzed. Based on the comprehensive consideration of significant factors of STM and characteristics of CUDA (Compute Unified Device Architecture), the introduction of STM in GPU programming environment is proposed and the test results show that speedup ratio sustains well by comparison with computing on CPU.

GPU; STM; GPGPU; CUDA

2013-02-19

国家自然科学基金“分数阶微积分应用于医学核磁共振图像处理的理论与技术”(60972131)

梁飞(1987- ),男(汉族),河南驻马店人，在读硕士研究生,研究方向：数据库与信息系统。

TP334.7

A

2095-5383(2013)02-0013-05