基于图形处理器的通用计算技术.doc

基于图形处理器的通用计算技术
王少荣 孙晓鹏 刘丽艳 刁麓弘 李华

摘要 基于图形处理器（GPU Graphic Processing Unit
）的通用计算是近年来的一个热点研究方向。本文介绍了图形处理器的历史、发展，以及其在通用计算领域的几个应用。另外本文也给出中国数字人研究中，利用GPU进行体绘制硬件加速的一个例子。我们认为GPU在通用计算方面会发挥重要的辅助作用。

1引言
近年来，计算机图形处理器(GPU)得到极大的发展，并且开始应用于图形学之外的通用计算领域。GPU用于通用计算的研究也开始成为热点。世界上唯一的图形学硬件会议2003年(SIGGRAPH/EURPGRAPHICS Graphics Hardware 2003)关注的重点是GPU的非图形应用。也有人提出，GPU将变成通用处理器（General Processing Unit）。
GPU应用领域的拓宽和它的硬件发展有着极大关系。从1993年开始，GPU的性能以每年2.8倍的速度增长。现在几乎每隔半年更新一代。2004年，NVidia GeForce 6800 Ultra处理器峰值速度可达40 Gigaflops，对比Intel 3G Pentium 4，采用SSE Streaming SIMD(single instruction multiple data) Extension
指令集也只能达到6 Gigaflops。
本文第2部分介绍GPU的发展历史，并以NVidia GeForce 系列为例，介绍其硬件架构。第3部分中介绍基于GPU的通用计算模型。第4部分给出一个我们在进行数字人研究时，GPU用于可视化的一个应用。第5部分主要介绍GPU用于通用计算的几个主要成功领域。最后从硬件结构和软件发展两个方面总结GPU的发展和面临的挑战。

1图形处理器的发展及其硬件介绍
我们先对图形处理器的发展历史作一个简单回顾。
20世纪六、七十年代，受硬件条件的限制，图形显示器只是计算机输出的一种工具。限于硬件发展水平，人们只是纯粹从软件实现的角度来考虑图形用户界面的规范问题。图形用户界面国际标准GKS(GKS3D)，PHIGS就是其中的典型代表。
20世纪80年代初期，出现GE(Geometry Engine)为标志的图形处理器。GE芯片的出现使得计算机图形学的发展进入图形处理器引导其发展的年代。GE的核心是四位向量的浮点运算。它可由一个寄存器定制码定制出不同功能，分别用于图形渲染流水线中，实现矩阵，裁剪，投影等运算。12个这样的GE单元可以完整地实现三维图形流水线的功能。芯片设计者James Clark以此为核心技术建立的SGI公司，对图形学和图形工业发展产生巨大影响。基于SGI图形处理器功能的图形界面GL及其后的OpenGL，成为图形用户界面事实上的工业标准。
20世纪80年代和90年代。GE及其图形处理器功能不断增强和完善，使得图形处理功能逐渐从CPU向GPU转移。此前计算机图形特别是三维图形的应用主要集中在工作站以上的处理机上，图形处理流水线的大部分功能是由CPU完成的。现代图形处理的流水线主要功能分为顺序处理的两个部分。第一部分对图元实施几何变化以及对图元属性进行处理（含部分光照计算）。第二部分则是扫描转换进行光栅化以后完成一系列的图形绘制处理，包含各种光照效果和合成、纹理映射、遮挡处理、反混淆处理等。当越来越高级的图形绘制功能需要在光栅一级实现时，可以利用SIMD（单指令多数据）结构进行处理。20世纪80 年代北卡罗莱那大学的Pixel Plane系列和Pixel Flow就是使用这种技术的典型代表。
20世纪90年代，NVIDIA进入个人电脑3D市场。1999年推出具有标志意义的图形处理器，GeForce 256。第一次在图形芯片上实现了3D几何变换和光照计算。此后GPU进入高速发展时期，平均每隔6个月就出现性能翻番的新的GPU。
从SGI的GE到NVIDIA的GeForce GPU经历了20年，芯片的线宽从3μm缩小到0.13μm（2004年的GeForce 6800集成了2.2亿晶体管），集成电路的逻辑设计能力提高300倍，但处理器数据通道接口带宽仅提高十几倍。同时对图形处理器计算能力的需求不断增长，出现了可编程的图形处理器。以NVIDIA和ATI为代表的GPU技术正是适应这种趋势。
现代GPU的发展经历一个过程。在出现GPU概念出现以前，特殊的图形处理硬件只出现在诸如SGI等图形工作站上。
n 第一代GPU出现在1998年，这些处理器主要处理光栅化，有些处理器支持多纹理。主要代表有NVIDIA TNT2，ATI Rang和3DFX VooDoo3。
n 第二代GPU出现在1999年，图形处理器可以处理几何变换和光照计算，但不具备可编程性。主要代表为NVIDIA GeForce256，GeForce 2和ATI Radeon 7500。
n 第三代GPU出现在2001年，图形硬件流水线可看成流处理器。可在顶点级上支持可编程性，象素级上的可编程性则比较差。这个时候采用GPU进行通用计算开始出现。主要代表有NVIDIA GeForce3，GeForce4，ATI Radeon 8500。
n 第四代GPU出现在2003年，以NVIDIA GeForce FX，ATI Radeon 9700/9800为代表，象素和顶点可编程性更通用化，可以包含上千条指令。GPU具备浮点功能，纹理不再限制在[0,1]范围，从而可以用于处理任意数组。
n 第五代GPU，也就是最新的一代GPU，出现于2004年。功能相对以前更为丰富，灵活。顶点着色器(Vertex Shader)可以访问纹理，支持动态分支操作；象素着色器(Pixel Shader)支持分支操作、子函数调用、64位浮点纹理滤波和融合、多个绘制目标等。主要代表有NVIDIA GeForce 6800。NVIDIA GeForce 6800集成了2亿2千2百万晶体管，具有超标量的16条管线架构。
图1为现代GPU的渲染架构。GPU绘制管道的可编程并行处理部分主要在顶点处理器(Vertex Processor)和子素处理器(Fragment Processor)。它们是典型的流式处理机，具有以下特点：
n 一定的并行性。多个渲染通道和RGBA四个颜色通道同时计算；同一时钟周期同时获取多个纹理。
n 密集运算。图形处理器内部内存接口带宽高于CPU接口。
n 减少GPU与CPU的数据通讯。可以让CPU去做别的事情。
这些优势使得GPU比CPU更适用于流处理类型的通用计算。

图1 GPU绘制管道
2基于GPU通用计算的基本流程
在图形处理器可编程技术普及以前，也出现过一些基于图形卡的数值计算。近年来，GPU在通用计算领域的应用越来越普遍。一般说来，目前基于GPU的通用计算的基本过程如图2所示。图2最右边一列表示子素处理（Fragment Processing）可以选择的方法。这里我们介绍两种常用的思路：基于寄存器组合器(Register Combiner)和基于象素程序，它们和其他方式比较起来，显得更为灵活，能实现的运算也更为复杂。

图2 基于GPU的通用计算流程
如图3、4、5，在GeForce 2最先引入寄存器组合器（Register Combiner），最初只有2个 通用组合器（General Combiner）。目前最新的硬件上则可以支持8个通用组合器。末级组合器（Final Combiner）作为最后输出运算。基于通用组合器的运算需要根据其支持的运算形式和有限的组合器个数来设计整个流程。如图3所示，数据以顶点颜色的形式或者纹理的形式传入通用组合器，利用其支持的运算可以同时完成4个颜色通道的计算。
通用组合器分为RGB和alpha两个各自独立的部分。在这个硬件结构中，数据都存放在一套寄存器里。寄存器的内容可以通过一定的方式映射到A，B，C，D四个变量。然后这些变量进行诸如AB,A*B,AB+CD之类的运算并输出至寄存器。上一个阶段的输出寄存器作为下一个阶段的输入寄存器。这样几个阶段依次进行。末级组合器（Final Combiner ）输出到两个寄存器，一个存放RGB值：AB+(1-A)C+D，一个存放alpha值。结果再送到下一步进行子素操作。

顶点程序模型如图6。目前的顶点程序，如NVIDIA ClineFX，每个顶点能支持64Ｋ条指令；开始支持动态和静态控制流的循环和分支和子函数，无论指令数和寄存器个数都较以前有了很大的提高。象素程序模型为图7。目前能够独立访问多达16个纹理；支持指令1024条，寄存器个数增加到64。由图6和图7可以看出，顶点程序和象素程序十分相似。但图形处理器象素处理能力比顶点处理能力高一个数量级，因而象素程序更适合用于通用计算。目前大多数的工作也均采用这种方式。
输入
映射：

RGB部分

AB+(1-A)C+D
D
C
B
A
输入
映射：

求和

二次幂阶颜色
空闲单元
色度求和单元
可用
RGB输入：

EF
乘法器
F
RGB输入：
输入映射
E
RGB输出
钳位至[0，1]
Alpha输出
Alpha输入
Alpha部分

Vertex
Program
M Instructions
Temporary
Variables
4T variables
Vertex Result
Registers
4R registers
Address
Variables
4A variables
Program Environment Parameters
4E registers
Program Local Parameters
4L registers

图6 Vertex Program
Fragment
Program
Temporary
Variables
4T variables
Attributes
Result
Registers
Program Environment Parameters
Program Local Parameters

图7 Fragment Program
3基于寄存器组合器方式的直接体绘制
在我们进行中国数字人课题研究中，我们使用GPU的寄存器组合器方式来进行体绘制加速。
体数据都以M×N×L的网格形式存储。基于纹理的体绘制一般将体数据当成纹理映射到3D物体空间中。绘制时，按照一定的方向对体数据采样，得到一系列的纹理多边形面片，然后按由后往前的顺序绘制这些纹理多边形。根据所用纹理的不同，基于纹理的体绘制分为基于3D纹理的绘制和基于2D纹理的绘制。
n 图8-b所示为基于2D纹理的体绘制。该模式下，体数据的采样主轴为其自身网格数据的3个轴方向之一。按采样主轴方向进行采样，得到一系列大小相同相互平行的矩形，然后将这些面片按视线方向由后往前绘制。随着视线方向的改变，采样的主轴方向也应该相应调整，使得视线和采样主轴方向尽可能小。这种绘制方法一般需要按三个主轴方向各存储一套数据，因而使用内存较多。另外，对不同方向上的采样率可能不一致；2D纹理硬件一般不能做三线性插值，只能二线性插值，这些对绘制效果都有一定影响。
n 图8-a所示为基于3D纹理的体绘制。这种方式下，体数据直接作为3D纹理，因而要求显卡必须支持3D纹理。绘制时，按照视线方向对体数据进行采样，得到一系列的平行多边形，将这些纹理多边形由后往前绘制即可。支持3D纹理的显卡一般也支持纹理的三线性插值，故这种绘制方式能对体数据进行三线性插值。体绘制时，使用alpha blending可以实现体绘制的半透明效果。

a

b
图8 两种体绘制方式
为了增强可视化效果，我们引入Phong光照模型。

其中为环境光，为点光源强度，为绘制面法线，为入射光方向，为将入射到观察者方向的理想镜面的法向量，是漫反射系数，是镜面反射系数，n为镜面高光系数。其中用体数据的梯度替代表示，存放在3D纹理的RGB部分。显卡直接支持点积运算，为了硬件计算方便，n可以取为2的整数次幂。
图9为示意的一个不含镜面反射的组合器设置示意图。图10为绘制得到的结果。

Texture 0
Texture 1
Color 1
Color 0
Fog
A
B
C
D

AB+CD
A
B
C
D

AB+CD
A
B
C
D
A*B
A
B
C
D
AB+(1-A)C+D
one
one
General combiner G
alpha
Slice texture
Gradient
Ambient
Light intentsity

Light
direction
General combiner 0

General combiner 2
Final combiner
图9 考虑环境光和一个光源的漫反射的combiners设置
General combiner 1

a
b
图10数字人绘制结果

4基于GPU的通用计算
利用GPU进行通用计算的领域越来越宽，从图形输出流水线之外的非绘制处理，到几何计算、碰撞检测、运动规划、代数运算、优化方程、偏微分方程数值解等。
我们选择几个典型的例子进行介绍。这些例子包括偏微分方程（Partial Differential Equation--PDE）数值解、数据库、频谱分析。
5.1 偏微分方程数值解
很多实际问题都可以归结为PDE的求解，而PDE的数值解则是问题的关键和难点。目前基于GPU的PDE数值求解比较成功的领域有：
n 流体力学问题。如流体模拟，人们用复杂的运动方程描述流动现象，如Navier-Stokes方程组（NSEs）。然而对NSEs的求解相当耗时，且对时间步长非常敏感，很容易因步长设置不当而导致不收敛。
n 热传导问题。
n Level Set方法。这是一种经典的变型模型(Deform Model)方法，其核心也是求解定义模型的PDE。
求解流体运动方程，在GPU上采用稳定性好的半拉格朗日方法求解NSEs:
(1)
其中u为速度，ν为运动粘性系数，f是外部作用力，p是流体压强，ρ是密度，T是温度。整个方程描述流体中的对流扩散现象。通过结合模板缓冲器对三维场景进行剪切操作，加上修正因子处理任意的边界条件。图11为一个系统算法流程，首先不考虑压强的影响求一个中间速度分布，然后求解压强泊松方程，以修正速度场。

图11 求解NS方程流程
图12-a是一个2D流体模拟示意，基于GPU算法比基于CPU速度高出10多倍。图12-b是一个基于GPU运行城市气流流动的计算。

a

b
图12流体模拟结果
5.2 数据库操作
近年来GPU用于数据库的研究工作有了新的进展，北卡罗莱那大学在用GPU实现数据库的某些基本操作时取得很好的结果。这些操作主要有关系查询(Relation Query)、合取选择、（Conjunctive Selection）、聚集（Aggregation）。其基本方法是将数据库的属性存入GPU的纹理，利用象素处理器对纹理进行并行操作和检测，利用深度缓冲区(Depth Buffer)和模板缓冲(Stencil Buffer)的深度检测和模板检测协作以完成数据库的操作。
如对数据库某项属性进行范围查询(Range query)，图13所示，首先将纹理拷贝到深度缓冲，然后使用深度限界检测绘制具有下界深度的长方形，最后在模板缓冲生成一个通过深度限界检测的结果，结果中每个为1的像素对应于符合条件的数据库项。
Range( tex, low, high )
1 SetupStencil()
2 CopyToDepth( tex )
3 Set depth bounds based on [low, high]
4 Enable depth bounds test
5 RenderQuad(low)
6 Disable depth bounds test
图13 Range query流程
对数据库操作的研究在NVIDIA GeForce 5900上进行，对比测试的是双CPU 2.8GH的Intel Xeon。测试结果表明，大多数数据库操作GPU相对于CPU有明显优势：
n 关系查询，选择查询，GPU比CPU速度高一个数量级。
n 第k个最大数查询，2~4倍性能改进。
n 累加运算，基于GPU比基于CPU慢。
5.3 频谱变换和滤波
频谱变换和滤波运算一般是在其离散的函数上实施统一的计算操作，即使用选定的核作卷积运算，这种特点适合SIMD运算和流处理。
傅立叶变换是最常用的频谱变换之一，Morland等在GPU上实现快速傅立叶变换(FFT)。测试结果表明，在GeForce5800 Ultra上和1.7GH Intel Zeon具有相当效率。对512×512点的图像快速傅立叶变换均能在1秒内完成。
小波变换作为多分辨率表示和分析的重要工具，近年来得到广泛关注。在边缘检测、图像压缩等方面具有重要的应用价值。早在1999年Hopf等人在SGI Octane实现Haar和Daubechies小波变换和反变换。测试效率比纯软件高2-5倍。2004年，王剑晴等在GPU上实现了完整的小波变换，包括多尺度分解和重建。离散小波变换(DWT Discrete Wavelet Transform
)是图像压缩标准JPEG2000的主要开销部分，测试表明基于GPU的DWT使得编码速度显著提高。在2048×2048的图像上，基于GPU（GeForce5900 Ultra）比基于CPU（Intel P4 2GH）快一个数量级。
5软件研究
以NVIDIA和ATI为代表的GPU产品正处在不断改进过程中，每过一段时间就会出现新一代的产品，功能更多，处理能力更强，但同时也带来新的问题，那就是如何使用这些新的功能。
GPU以芯片产品方式直接提供给用户，而近年来GPU产品更新速度是大规模集成电路各类产品发展历史上最快的。这种情况下，GPU的应用方式一般通过图形API Application Program Interface
（OpenGL或DirectX）扩充，其扩充功能由GPU厂家或者API软件开发者提供。
OpenGL作为事实上的工业标准为学术界和工业界普遍接受，因而大部分与图形有关的应用产品一直以OpenGL为实现界面。OpenGL通过包括GPU设计者（如NVIDIA）以及OpenGL架构委员会（ARB）所扩充的函数来使用GPU的扩充。DirectX则及时地定义新的版本对GPU新产品功能的扩充与进展进行支持。但无论那种方式对使用者而言都相当繁琐和困难，因为应用中往往需要考虑硬件结构的许多具体问题。
使用高级语言对GPU直接编程一直是计算机图形学界的一个努力目标，目前，对绘制语言（Shading Language）和实时绘制语言的研究取得一定的进展，关于新型绘制语言的研究，近来影响比较大的有，OpenGL Shading Language，斯坦福大学的Real-time Shading Language，Microsoft的High-Level Shading Language，以及NVIDIA的CG。
使用绘制语言编程依然需要使用者了解最新的API以及图形处理器的特点，且进行通用计算时需要把算法表达为GPU中的纹理，三角形等。因此，当前研究者们试图将GPU的结构纳入流处理机的模型而以高级语言编程，使得程序说明、运算操作、模块化定义等一系列运算和控制规范化。使得用户使用GPU时不必考虑GPU的具体结构。Brook-for-GPU就是一个典型代表。
6结论
近年来GPU一直保持持续高速发展，其原因是相关应用领域，如虚拟现实、计算机仿真、计算机游戏等的强大驱动。单游戏产业的庞大市场就足以成为GPU以及相关软件发展的强大动力。有人甚至预言5年左右，GPU的集群服务器可以构成以GPU为主的超级计算机。但我们认为实现这个目标还有很长的一段路要走。对于通用计算而言，GPU在软硬件方面依然存在很多需要克服的问题。首先GPU是面向图形的，和真正通用计算的CPU有本质差别，而工业界未必致力于发展GPU的通用计算。其次软件方面需要更多的努力，如需要制定统一的界面和工具软件。至于当前的GPU，主要有以下问题：
n GPU编程依然过于繁杂，且缺乏对应用算法和图形绘制都熟悉的研究开发人员。
n 浮点精度问题。GPU现在支持IEEE单精度浮点标准。对于GPU的大多数图形绘制而言单精度浮点已经足够，但对于很多应用领域，需要双精度的浮点。近期GPU可能不会支持双精度浮点。
n 存储问题。GPU当前最大存储是256M，这对通用计算是个很大限制。但GPU本身似乎不太可能大量扩充存储。
n GPU和系统接口带宽。GPU访问系统内存开销太大。
我们有理由相信，至少在某些领域的通用计算，GPU将发挥重要的作用。然而，GPU只是辅助计算部件，不大可能成为通用计算的专门部件。
目前，中国正在开辟自行设计通用CPU的道路，如计算所的龙芯CPU，采用MIPS指令系统。我们或许可以借鉴GPU的通用计算思路，设计一些用于大规模计算的结构，以提高CPU的计算能力。
参考文献
[1]
[2]
[3]
[4] http://www.gpgpu.org
[5] http://www.cgshader.org
[6]
[7] http://www.opengl.org
[8] Herry Fuchs and John Poulton, Pixel-planes: A VLSI-Oriented Design for a Raster Graphics Engine[J], VLSI Design, 2(3), 3rd Quarter, 1981. 20~28.
[9] João Luiz Dihl Comba, Carlos A. Dietrich, Christian A. Pagot and Carlos E. Scheidegger. Computation on GPUs: From A Programmable Pipeline to an Efficient Stream Processor[J]. Revista de Informática Teórica e Aplicada, Volume X, Número 2, 2003.41~70.
[10] Suresh Venkatasubramanian. The Graphics Card As A Stream Computer[A]. In Proceedings of SIGMOD Workshop on Management and Processing of Data Streams. San Diego, 2003.
[11] Kenneth Moreland and Edward Angel. The FFT on a GPU[A]. In Proceedings of Graphics Hardware, San Diego, 2003. 112~119.
[12] Matthias Hopf and Thomas Ertl. Accelerating 3D convolution using graphics hardware[A]. In Proceedings of IEEE Visualization, San Francisco, 1999. 471~474.
[13] Matthias Hopf and Thomas Ertl. Hardware accelerated wavelet transformations[A]. In Proceedings of EG/IEEE TCVG Symposium on Visualization VisSym, Netherlands, 2000. 93~103.
[14] Naga Govindaraju, Stephane Redon, Ming C. Lin and Dinesh Manocha. CULLIDE: Interactive Collision Detection Between Complex Models in Large Environments Using Graphics Hardware[A]. In Proceedings of Graphics Hardware, San Diego, 2003. 25~32.
[15] Aaron E. Lefohn, Joe M. Kniss, Charles D. Hansen and Ross T. Whitaker. Interactive Deformation and Visualization of Level Set Surfaces Using Graphics Hardware[A]. In IEEE Visualization, Seattle, 2003. 75~82.
[16] Chris Batty, Mark Wiebe and Ben Houston. High Performance Production-Quality Fluid Simulation Via Nvidia’s Quadro FX. docs/CP/4449/frantic_GPUAccelerationofFluids.pdf, 2003.
[17] Naga K. Govindaraju, Brandon Lloyd, Wei Wang, Ming C. Lin, Dinesh Manocha. Fast Database Operations using Graphics Processors, In Proc. Of the SIGMOD 2004
[18] Youquan Liu, Xuehui Liu, Enhua Wu, Real-Time 3D Fluid Simulation on GPU with Complex Obstacles, Proceedings of Pacific Graphics 2004, IEEE Computer Society, Oct. 2004, pp247-256.
[19] 吴恩华, 柳有权,基于图形处理器(GPU)的通用计算，计算机辅助设计与图形学学报, 16(5), 2004年9月,pp601-612. 

下转 23 页
[20] 吴恩华, 图形处理器用于通用计算的技术现状及其挑战，软件学报,2004年10月,15(10),pp206-214
[21] 王少荣,贾富仓,刘丽艳,李华. 基于数字人切片数据的硬件加速体绘制(已录用)

作者
王少荣 中国科学院计算技术研究所智能信息处理实验室 博士生
孙晓鹏 中国科学院计算技术研究所智能信息处理实验室 博士生
刘丽艳 中国科学院计算技术研究所智能信息处理实验室 博士生
刁麓弘 中国科学院计算技术研究所智能信息处理实验室 博士生
李 华 中国科学院计算技术研究所智能信息处理实验室 研究员、博士生导师