（计算机系统结构专业论文）基于gpu的串匹配算法的实现.pdf

摘要 随着集成电路技术的发展，g p u ( g r a p h i c sp r o c e s s i n gu n i t ，图形处理器) 的发展相 当的迅速。当前，一个典型的g p u 的实际程序运算速度可达2 0g f l o p s ，内存带宽可 达2 5 3g b s e e ，远远超过通用的c p u 处理器。由于g p u 具有如此巨大的运算潜力，越 来越多的应用试图将通用计算任务移植到g p u 上来做。利用g p u 的s i m d 流处理器作 为通用计算平台已经得到了广泛的研究和应用，这使得g p u 能够成为一个有效的c p u 协处理器，获得较高的性价比。 串匹配算法是生物信息学、信息检索领域的基础算法。随着近年来基因数据和网络 数据的爆炸式增长，对串匹配算法性能的需求也日益增长。但是串匹配算法本身所具有 的较强的数据依赖关系和很差的数据重用性的特点极大地限制了该算法在现有的c p u 结构上的效率。尽管数据重用性差限制了在c p u 上的性能，但是其流式的特点比较适合 流媒体的结构，然而其数掘依赖关系给在g p u 上挖掘其并行性提出了挑战。 本文从g p u 的体系结构出发，研究如何在g p u 上有效编程，如何开发串匹配算法 的数据并行性，以及适合在g p u 上运行的串匹配算法。本文的主要工作包括： ( 1 )g p u 上通用计算编程方法的研究：研究了o p e n g l 、b r o o k 、c g 等g p u 上通用计算的编程方法，以及如何开发基于g p u 的数据并行性。在此基础 上，进行了g p u 数据存取方式的研究，以串匹配操作中涉及的字符串文件 为例，研究了充分利用了图形处理中纹理这一数据结构，将一般通用计算的 数据结构映射到g p u 中去的方法，以及在g p u 中利用二维纹理方式高效计 算的算法设计方法。 ( 2 )适合g p u 的串匹配算法的设计与实现：b f 算法是串匹配算法中最基础的算 法，但它是串行算法，不适合g p u 的体系结构。本文对b f 算法进行了重 新设计，将条件分支语句转化为计算语句，以充分利用g p u 的并行处理能 力实验结果表明，基于g p u 的并行算法能够取得较好的加速比。 ( 3 )研究提高g p u 体系结构下通用算法效率的方法：以b f 串匹配算法为例， 测试了各种参数变化对g p u 性能的影响，从而给出了在现有g p u 架构上有 效实现通用计算的瓶颈，并推导出了在g p u 体系结构上提高通用算法效率 的一些方法。 关键词：g p t l ；s i m d ；通用计算；串匹配算法：并行；算法优化 a b s t r a c t i m p l e m e n t a t i o no f s t r i n gm a t c h i n g a l g o r i t h mb a s e do ng p u z h a n gq i n g d a n ( c o m p u t e ra r c h i e c t u r e ) d i r e c t e db ys u nn i n g h n i w i t ht h ea c h i e v e m e n to fi c ( i n t e g r a t e dc i r c u i t ) t e c h n o l o g y , g p u ( g r a p h i c sp r o c e s s i n g u n i oi sb e c o m i n gv e r yp o w e r f u l r e c e n t l y , at y p i c a ls h a d i n gp r o g r a mr u n n i n go i lt h eg p u c a n r e a c ht h ep e a kp e r f o r m a n c eo f2 0 g f l o p sa n dt h em e m o r yb a n d 谢d t ho f2 5 3 g b s e c , w h i c h i sm u c hb e t t e rt h a nt h a to ft h ec p u f o rs a k eo fs u c hh u g ep o t e n t i a lc o m p u t i n gc a p a b i l i t y , i i 加怫a n dm o r ea p p l i c a t i o n s 骶w r i n gt op o r tt h e i rc o m p u t i n gt a s k st ot h eg p u u t i l i z i n gt h e g p u 勰as i m ds t r e a mp r o c e s s o rf o rg e n e r a lp u r p o s ec o m p u t a t i o n s i th a sb _ e g x r n eat o p i co f c o n s i d e r a b l ei n t e r e s tn o w a d a y s n 圮g p uc o u l db o o o l n ea ne f f i c i e n tc o - p r o c e s s o ro f t h ec p u , g a i n i n gt h eh i g hp e r f o r m a n c ep r i c e r a t i o t h es t r i n gm a t c h i n ga l g o r i t h mi sab a s i ca l g o r i t h mi nt h eb i o i n f o n n a t i e sa n di n f o r m a t i o n s e a r c h i n gf i e l d s w i t ht h eb o m b i n gg r o w i n go ft h eg e n ed a t aa n dw e bd a t a , t h en e e df o rh i 出 p e r f o r m a n c es u i n gm a t c h i n ga l g o r i t h m si sg r o w i n 吕b u tt h es t r i n gm a t c h i n ga l g o r i t h m sh a v e t h ed a t ad e p e n d e n c yp r o b l e m s , w h i c hb a d l yr e s t r i c tt h ee f f i c i e n c yi nc p u 1 1 l i st h e s i si sc o n c e n t r a t e do nt h es y s t e ma r c h i t e c t a r eo f t h eg p u , s t u d y i n gt h ee f f i c i e n t l y p r n g r - d m m i n gm e t h u d so nt h eg p u , d e v e l o p i n gt h ed a t ap a r a l l e l l i s mo ft h es t r i n gm a t c h i n g a l g o r i t h m s , a n dt h ec h a d c t e d s t i c so f g e n e r a la l g o r i t h m sw h i c h s u i t a b l et ob ep o r t e dt o 碡 g p u t h em a i nt a s k so f t h et h e s i si n c l u d e ： ( 1 ) 1 1 1 et h e s i sd o e st h er e s e s f c ho nt h es y s t e ma x c h i t e c t u r ea n dp r o g r a m m i n gm c 蛆l o d so f t h eg p u , s u c ha so p e n g l , b r o o k , c qa n dt h ei m p r o v e m e n t 印p m a c ho ft h ed a t aa c c e s s p a t t e r n b yu t i l i z i n gt h et e x t u r ed a t as t r u c t u r ei ng r a p h i c sp r o c e s f i n ge l e m e n t s , t h ed a t a s t r u c t u r e si ng e n e r a lc o m p u t a t i o n s , s u c ha st h es t r i n gf i l e si ns t r i n gm a t c h i n ga l g o r i t h m s , a r e m a p p e di n t ot h eg p u a n dt h ea l g o r i t h m si ng p ua r ca l s od e s i g n e do nt h eb a s i so f t e x t u r e ( 2 ) b fa l g o r i t h mi st h eb a s i ca l g o r i t h mi ns t r i n gm a t c h i n gf i e l d b u ti ti sn o tp a r a l l e l e d ， a n dd o e sn o tm a t c ht h es y s t e ma r c h i t e c t u r eo ft h eg p u c o n c e r n i n gt h es p e c i f i ch a r d w a r e a r c h i t e c t u r eo ft h eg p u , an e wm e t h o do fd a t aa c c e s s i n ga n dap a r a l l e lb fa l g o r i t h ma l e d e s i g n e d b e c a u s eo ff u l l yu t l i z i n gt h ep a r a l l e l i s mo f t h eg p u , t h ee x p e r i m e n t ss h o wt h a tt h e a p p l i c a t i o ni nt h eg p uc a n 删u pm u c hc o m p a r e d1 i t lt h a ti nt h ec p u ( 3 ) b a s e do nt h eb fs i z i n gm a t c h i n ga l g o r i t h mo ng p u a sac a s es t u d y , t h ep d f o m m c e i m p r o v e m e n ta p p r o a c hi ss t u d i e do nt h eg p u t h ep e r f o r m a n c ei n f l u e n c ef a c t o r e so ft h e a l g o r i t h mo nt h eg p ua r e 锄i a l y d ，a n dt h ep o s s i b l eb o t t l e n e c k so fn o w a d a y sg p u a r c h i t e c t u r e sa r es t u d i e d a l s o8 0 m ec o n c l u s i o n so ft h ec h a r a c t e r i s t i c so fg e n e r a la l g o r i t l m l s , i i i 0 。，。 ， ；4， 摹于g p u 的串匹配算法的实现： a b s t r a c t w h i c h nb ep e r f o r m e do nt h eg p u e f f i c i e n t l y , a r er e a c h e d k e y w o r d s ：g p u ；s i m d ；g e n e r a lp u r p o s ec o m p u t a t i o n ；s t r i n gm a t c h i n g a l g o r i t h m ；p a r a h e lp r o c e s s i n g ；a l g o r i t h mo p t i m i z a t i o n 誊 图1 1g p u 及c p u 发展示意图 图1 2g p u 结构图 图目录 图2 1 图形处理流程图 图2 2g p u 渲染管道 图2 3g p u 中的计算流程 图2 4g e f o r c e 6 8 0 0 g t 的内核架构 图2 6 v e r t e xp i p e l i n e 图2 1 0 图2 1 1 g p u 中处理的数据格式 图形加速卡工作示意图 l o l o l l “ 1 2 图2 1 3o p e n g l 图形处理系统的层次结构 图2 1 4o p e n g l 的体系结构 图2 1 5 按行折叠将二维数组转换为纹理 图2 1 6 按列折叠将二维数组转换为纹理 图2 1 7 按2 * 2 块折叠将二维数组转换为纹理 图2 1 8 一维数组转换为一维纹理 图2 1 9 一维数组转换为二维纹理 图2 2 0 三维数组转换为二维纹理 图2 2 1 稠密矩阵转换为二维纹理 图2 2 2 稀疏矩阵转换为二维纹理 v n n h h ：2 打 竹 掩 体 博 硌 侉 摹于g p u 的串匹配算法的实现：圈目录 图4 1 图4 2 图4 3 图4 4 字符串文件的二维纹理表示 字符串文件的二维纹理表示 串匹配的g p u 计算过程 算法改进日口后时间对比图 3 3 3 5 图4 5串匹配所用g p u 及c p u 时间比对图3 5 图4 6 匹配所用c g 计算时间 图4 7 两类算法的时间比较 图5 1 初始时间用图。 图5 2 纹理上传时间4 l 图5 3g p u 上不做任何操作时计算时间4 1 图5 4 算法执行过程中各类时间分配图 v i l l 4 2 表目录 表4 1条件语句转化为数值计算语句i ； 后匹配时问列表 表4 2c p u 及g p u 匹配时间列表 表4 3 算法时f b j 比较得到的数据 表5 1g p u 串匹配时问分配 3 4 3 4 3 7 3 9 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，本论文中不包含 其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：弘彦册日期：2 0 0 6 、4f 8 论文版权使用授权书 本人授权中国科学院计算技术研究所可以保留并向国家有关部门或机 构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可以将本 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 储躲涨祸导师签蝴嘭彳期毗f 8 第一章引言 英特尔联合创始人戈登摩尔在1 9 6 5 年4 月1 9r 出版的电子学杂志提出了著 名的摩尔定律：预测集成电路中的晶体管数目每1 8 - 2 4 个月就翻一番，且计算机芯片的 性能每年增加一倍，而制造成本也会相应减少。这一著名定律，引导了全球半导体特别 是c p u ( v e 央处理器) 技术的4 0 年的研究和发展。c p u 是计算机的头脑，9 0 以上的数掘 信息都是由它来完成的。c p u 集成上万个晶体管，可分为控制单元( c o n t r o lu n i t ；c u ) 、 逻辑单元( a r i t h m e t i cl o g i cu n i t ；a t , u ) 、存储单元( m e m o r yu n i t ；m u ) 三大部分。 以内部结构来分可分为：整数运算单元，浮点运算单元，m m x 单元，l ic a c h e 单元和 寄存器等。尽管多级c a c h e 的使用使得c p u 的计算效率更高，然而它占据的芯片面积 成为制约其时钟频率和硬件性能提高的瓶颈。 近年来，随着图形处理器技术的发展，其处理速度的提高已经超越了摩尔定律的发 展规律，在图形处理方面已经大大地超过了c p u 的处理效率。 1 1g p u 的发展史 g p u ，即g r a p h i c sp r o c e s s i n gu n i t 的简写，是图形处理器的意思。它是现代的显卡 中非常重要的一个部分，其地位与c p u 在主板上的地位一致，主要负责的任务是加速图 形处理速度。 1 1 1g p u 发展 g p u 作为新兴的体系结构与c p u 的不同之处在于；g p u 是一种针对图形处理的专 用处理器，它的特点就是控制部件相对较少，芯片上大面积的部分都为计算器所占据， 片内c a c h e 也很少，因此它的专用性决定了它的计算速度是很快的。 最早期的电脑上用的显卡是不带有g p u 的。随着人们生活水平和欣赏需要的提高， 图形图像处理的要求也越来越高。而通用的c p u 处理速度已经慢慢地跟不上图形处理的 要求。这样就使得在显卡上慢慢地引进了c p u 中的处理功能。最早期引进的是图形显示 的连贯性，然后是t & l ( t r a n s l a f o na n dl i g h t i n g ) 功能的引进，再然后图形处理流程中 的光栅处理，顶点像素处理等等也都慢慢由g p u 来完成了。最终将c p u 从繁重的劳动 中解放了出来。3 d 处理的数掘量大及实时渲染的特点使得其计算量大，且要求处理速度 快。原有的通用c p u 在处理时会遇上瓶颈，将这部分的功能提取出给g p u 后，c p u 能 空闲下来处理别的事务，而二者的分工协作也使得现代的图形影像播放顺畅而清晰 最近的报道表明，一个运行在n v i d i ag e f o r c ef x5 9 0 0u l t r a 的s h a d e r 程序运算速 度可达2 0g f l o p s ，相当于1 0 g h z 的p e n t i u m4 ，而且图形系统的内存带宽为2 5 3 g b s e c ，相比p e n t i m n4 只有5 9 6g b s e c 。从这两个原始数据不难看出g p u 是一个非常 中同科学院颂十学位论文草于g p u 的串匹影算法的实现 快的运算引擎，与c p u 相比，它在图形处理方面能带来更高的加速比。图1 1 中给出了 近年来c p u 与g p u 的发展趋势的比较，可以看到g p u 的发展速度与c p u 相比，增长 更为快速。这样强大的数据处理能力以及g p u 处理大量顶点及像素的体系结构使得它 能够用简单的运算处理大量的数据，这使得人们丌始研究用g p u 进行通用的算法的实 现与加速。 m u l t i p l i e sp e rs e c o n d j u l y o l j a n0 2 j u t y 0 2 j a n0 3 j u l y0 3 j a n 0 4 1 1 2g p u 特点 圈i ig p u 及c p u 发展示意图 在硬件上，流处理模型及s i m d 类似的结构使得用g p u 进行通用计算是可行的， 我们从图l - 2 中可以看到，在g p u 的结构中，芯片上占大多数面积的是计算器，而不像 c p u 中一样，大部分的面积为控制器及寄存器等存储器所占据，这使得它适合进行计算 密集型的算法处理。然而早期的g p u 通用编程受到诸多因素的约制。使用g p u 进行通 用编程必须掌握图形处理语言及具备图形处理的相应知识，在g p u 能进行编程的早期， 也只有通用汇编语言才能进行程序的编写及执行，这是很费事的。然而，随着c g 、h l s l 等高端语言的出现，在g p u 上编程已经容易了很多【1 1 。c g 语占即c f o r g r a p h i c s ，它具 有良好的通用性和可移植性，可以绕开具体的g p u 的核心，达到更高的虚拟层。c g 语 言为在g p u 上编程提供了极大的便利。 2 如 如 加 m o 厶0 1 止哆 第一章引言 m u l t l s a n l p i e a n t m | t a s m g t e x t r e eu n i t h o c g ti n t e r f a c e ( a g p 4 x w f w ) f ： v i s i b d z t ys u b s y s t e m d u a l ，d u a l ，。 h 7 r 6 n v c r t c x v e f t e x i c r o s s b a 。rm e m o r yi f s l l a d 口s ：? s h a d e r s ； f，一 ；p 口唧1 “o d7 _ l o s s l e s sd a t a c o m p r e g s l o n p l x e is h a d e r ； _。 “”! ，拍g 沁 p 嚣 t ? f r , 掣! o a c ；塞 卜：_卜委冀 图1 2g p u 结构图 1 1 3 利用g p u 进行通用计算 a f i m t o f xi ih g i 坤 2 n ，v 订e 删d v p 硬件以及软件上的可编程性使得在g p u 上做通用计算成为可能。近年来基于g p u 的通用研究逐渐成为研究热点很多数值计算等通用的算法都已经在g p u 上得到了实 现，并且有着不俗的性能表现，而可视化或者音频处理等等应用也都在g p u 上得到了 很好的展现。使用g p u 作为c p u 的协处理器并得到性能的提高，从而大大提高实际应 用中的性价比成为一种提供高性能计算平台的重要途径。 基于g p u 的通用计算是随着图形芯片的发展而发展起来的，虽然以前的图形卡主 要只是针对图形本身的应用，如光照计算、深度检测、光栅化、反走样等等，但针对其 他更为通用的应用也有出现，如利用颜色来标示物体序号等田但真正全面开展起来是 因为可编程性的普及。随着2 0 0 1 年g e f o r e e 3 的出现，顶点级可编程开始普及【3 】，即v e r t e x p r o g r a m ，人们使用它进行了通用编程的初步尝试【4 】。虽然这个时候像素级上还只是固定 的几条指令，但这方面的应用已经开始全面展开到了2 0 0 2 年人们开始利用t e x t u r e s h a d 瞳结合r e g i s t e rc o m b i n e r 来求解扩散方程四，而到了2 0 0 3 年像素级可编程性出现， 很多人开始利用像素程序来求解一般代数问题，甚至有限差分方程组求解( p d e s ) 6 , 7 , s l 和优化问题的求解【9 i o 】。现在随着时间的推移g p u 在通用计算的应用也越来越广“1 在2 0 0 4 年，由斯坦福大学研究的b r o o k g p u 项引z l 使得在g p u 上进行通用计算 更加可行它设计了一个实时的编译器，编程人员只需掌握与c 语言很类似的流处理语 言b r o o k 即可对g p u 进行通用编程的操作，而图形处理的基本知识也可以很少涉及， 甚至不需要了解图形图像在处理时是如何进行运作的。这为更多的科学人员使用g p u 进行通用编程提供了便利。 3 中国科学院颂i i 学位论史牡十g p u 的串卧配算法的实现 1 2 论文主要内容 1 2 1 研究动机 虽然近年来c p u 依然遵循着摩尔定律快速地发展着，但是待其处理的数据也飞速的 增长，这使得c p u 出现计算瓶颈，尤其是对于三维图形处理操作。因此使得g p u 逐渐 兴起，现在图形处理中的很多操作已经慢慢移交给专用的图形处理器g p u 去做。而近 年来g p u 也不负众望地发展得越来越快，g p u 在做图形处理操作时的高效率引发了人 们将其应用于通用计算上的兴趣。 1 2 2 研究内容 本文中将以基于g p u 的串匹配的实现做为一个研究点，通过对它的性能分析等进 行一般性分析，推导出适合g p u 实现的通用算法特点。主要的研究内容如下： g p u 上通用计算编程方法的研究：研究了o p e n g l 、b r o o k 、c g 等g p u 上通用 计算的编程方法，以及如何开发基于g p u 的数据并行性。在此基础上，进行了g p u 数 据存取方式的研究，以串匹配操作中涉及的字符串文件为例，研究了充分利用了图形处 理中纹理这一数据结构，将一般通用计算的数据结构映射到g p u 中去的方法，以及在 g p u 中利用二维纹理方式高效计算的算法设计方法。 适合g p u 的串匹配算法的设计与实现：b f 算法是串匹配算法中最基础的算法，但 它是串行算法，不适合g p u 的体系结构。本文对b f 算法进行了重新设计，将条件分支 语句转化为计算语句，以充分利用g p u 的并行处理能力。实验结果表明，基于g p u 的 并行算法能够取得较好的加速比。 研究提高g p u 体系结构下通用算法效率的方法：以b f 串匹配算法为例，测试了各 种参数变化对g p u 性能的影响，从而给出了在现有g p u 架构上有效实现通用计算的瓶 颈，并推导出了在g p u 体系结构上提高通用算法效率的一些方法。 1 2 3 论文的组织 论文组织如下： 第一章论述了g p u 的发展及其与c p u 发展速度的比较及基于g p u 做通用计算的研 究动机，并明确了本文的工作方向。 第二章介绍了基于c p u 进行编程的相关工作，包括图形处理流水线结构，g p u 的 体系结构，基于g p u 的编程方法的研究等。并给出了一个具体的实现实例。 第三章介绍了单模式串精确串匹配算法的基础知识，并给出了串匹配算法适用的应 用领域。 第四章分析了基于g p u 的串匹配算法的研究现状，具体说明了基于g p u 的串匹配 的实现，提出了需要解决的技术难点以及改进方法，并进行了算法的性能测试与分析 4 ， 第一章, - j i 苦 第五章基于b f 串匹配算法在g p u 上的成功实现分析了本文的研究成果，通过各类 性能参数的更换对实验结果进行了分析，总结了适合g p u 高效运行的通用算法的特点。 第六章对全文工作所取得的经验教训进行了总结归纳，提出了进一步工作的展望和 设想。 5 墓 2 1 图形处理体系结构 第二章相关工作 2 1 1 图形处理原理 由于g p u 是为了加速图形处理而出现的，首先我们介绍一下图形处理中g p u 中的 流水线结构的过程。 三维图像处理技术是在个人电脑上按照长度、宽度与深度等三个坐标描绘景物，以 便在二维平面( 如显示器) 上产生立体的视觉效果。若要在电脑上创造一个效果逼真的立 体世界，需要强大的电脑运算能力，其中更涉及复杂的浮点及整数运算。长期以来，高 性能的精简指令集运算0 u s c ) t 作站一直占领着高质量图像处理市场，应用领域包括好 莱坞的电脑动画到电脑辅助设计和t 程( c a d c a e ) 及科学模型的建造。 ： 现在，三维图像己在全球p c 消费市场上占有一定的地位。根据j o np c d d i c a s s o c i a t e s 0 p a ) 的数据显示，三维图像在p c 市场中成长最快，预计未来两年将会倍增。支持这个 发展的先进技术包括更强劲的个人电脑处理器、更高性能的三维图像加速卡、更快但价 格更合理的内存以及适用于三维图像处理的应用程序接m ( a p o 如d i r e c t x 和o p c n g l ， 这些应用程序接口为软件开发供应商提供了一个开放的开发环境 图像处理通道常常被喻为“拿着水桶救火的消防队”，它是主处理器( c p u ) 与描绘装 置( 即图像加速器) 之问的一段通道，涉及多个步骤的指令及其它工作均在这里执行( 见图 2 n 图2 1 图形处理流程图 从图中可以看到，图像处理通道分为四个不同步骤：物理实体、几何转换、三角形 设定以及像素渲染。 ( 1 ) 物理实体一电脑利用数学模型描绘物体的方式，用来模拟真实世界中 各种物体的物理特征及事件发生过程。电脑创造的虚拟世界是一个全 3 6 0 度的立体景观或物体坐标世界，全部模拟过程均通过数学运算完成。 换言之，个人电脑在同一时间内采用全部视点观看所有物体以及物体问 7 、 中冈科学院颅f 学位论文犟十g p i j 的串蜓配算法的实现 的相互作用。这正是p c 电脑游戏所采用的方式，但同样的原则也可用 来提高其他应用程序的三维图像处理性能。物理运算无可避免是一个浮 点运算密集的过程，因此这类运算交由c p u 内含的软件处理。 ( 2 )几何运算三维几何运算主要也由c p u 执行，这类运算包括多种浮 点密集的运算( 转换、光效及剪切) 。数学坐标可以用来创造构成虚拟世 界影像的多边形或三角形，例如，以数学式表达的球体可转化为一组看 似球体的三角形。转变过程中会添加动作( 变焦、旋转等) 。光效是在指 定地点将光源照向物体，会影响我们观看物体的视点以及阴影投射。通 过剪切功能，受i ； 面物体遮挡的后面部分物体可以被删掉。 ( 3 )三角形设定浮点及整数运算必须在这个阶段内进行，所涉及的运算 非常复杂。基本上，c p u 先将要处理的工作在描绘前交给三维加速器。 在进行设定时由某一视点或角度观看景物。 ( 4 )像素渲染这个步骤亦称光栅化过程，整个过程需要进行大量整数运 算，以便产生由一点点像素构成的形象，并对数学物体加以真实性的纹 理处理。渲染工序将有关不同颜色、阴影与位置的数据按照每一像素为 基准计算，使观看者可以在平面的屏幕上看到立体的影像。大部分渲染 工作由三维图像加速器执行。 现代图形处理的流水线在g p i j 上的计算主要集中在顺序处理的两大部分：第l 部分 是对图元实施几何变换及对图元属性进行处理，即将几何模型的多边形三角形顶点数据 流从c p u 交由图形处理部件实现几何变换及属性处理( 包括部分光照计算) ；第2 部分 则是在实现扫描转换进行光栅化以后进行一系列图形绘制处理，包括各种光照效果的合 成、纹理映射、遮挡处理、反混淆处理等。图形输出处理本身具有规范的流水线操作， 当越来越高级的图形绘制功能需要在光栅一级处理时，s i m i ) ( 单指令多数据) 结构的处 理机是最合适的并行硬件结构。 为加强图形处理的效率，c p u 在硬件上提高处理速度的同时还辅助了很多软件上的 改动，如m m x 、s s e 、3 d n o w ! 等各种s i m d 指令集的出现。它们的目的都是为了很 好地进行流媒体的处理，即充分用上流水线功能及一拍多发射处理等功能。种种的改进 都是为了加速c p u 的图形处理速度，然而，硬件上的限制使得它处理的性能和效率并走 不太远。事实上，现在三维图形加速器的性能每9 个月加快一倍，比c p u 的发展还要快。 因此g p u 的图形处理速度还是远远高于c p u 的。 现代的商用g p u 的结构与图形处理中的流水线结构是对应的。这种流水线结构的 目的是要让硬件通过并行处理来得到算法映射执行时效率的大幅度提高。通过上面对图 形处理操作的阐述，我们可以详细看看在g p u 中都有哪些流水部件以及它们都是如何 运作的。 8 第二章相关t 作 2 1 2g p u 体系结构 在图形处理中，几何顶点等流水线的输入数据是最基本的部分。主要表现为顶点的 坐标等等，而输出则是存在f r a m e b u f f e r 里的。可以通过数据传输读回内存，也可 以通过r m d c 接口直接在显示屏上得到图像的输出。图形处理中流水线的第一阶段主要 是把顶点由三维的物体坐标转为屏幕坐标。随后通过光栅化的处理得到很多的像素片断 从而传入像素处理器并得到最终的图像输出结果。 图2 2g p u 渲染管道u 3 1 如图2 2 所示，g p u 绘制管道的可编程并行处理能力分布在两部分：顶点处理器 ( v e r t e x p r o c e s s o r ) 和像素处理器( t i a g m e n t p r o c e s s o r ) 。它们都是典型的流处理机( s t r e a m p r o c e s s o r ) 。这种流处理机与向量处理机的主要区别在于：它不具有大容量的快存，存储 器可以读写，只是直接在芯片上利用临时寄存器作流数据的操作。 对于g p u 而言，图形流数据分别是顶点图元及光栅化后的像素。根据图形处理的 特点，g p u 流处理的元素为4 个单元的向量，可以用它表示三维齐次坐标、三维空问齐 次向量、颜色等。正是这种流处理机的并行结构，为通用计算提供了并行计算的平台。 其中，顶点处理器操作在空问的几何点上，因而比较适用于除图形绘制以外的几何操作 类的应用上，而像素处理器由于是操作在像素一级的单元上，具有较大容量的“纹理” 空间，可以模拟纹理数据及其操作，因而可以更广泛地用于各种通用计算。这是g p u 用于通用计算的最主要的平台。 一 9 中因科学院坝i ：学位论文苹十g p u 的串匹配算法的实现 图2 3g p u 中的计算流程 图2 3 中给出了g p u 渲染管道中执行的详细的计算流程。其中顶点及像素处理器是 可编程的部件，对g p u 进行编程操作主要就是在这两大块实现的。而光栅处理现在还 不是人为可以控制的。 本文所做的实验中用的是n v i d i a 公司生产的g e f o r c e6 8 0 0 g t ，图2 4 是n v i d i a 官方公布的这款g p u 的内核架构图。 g o n e r jg p um 嚏 l 呻“ ；a o p 扭 凰圈圜；h s ic l 峰 j l p c 。z 嫩 一 l上tl l ”“m 抽“椭枷相一q ”“ t l ”。“” 黟婚耐硒g 掰鼯磺御搿鼍 k 胤j a o 。瞬- 十础止 r 2x q 旧dp o o l i 冀咖畔。”6l 7 n q m “ 雾 2 i t m u ” m z m r iu l “1 w c 拓哺i i 咄。if r a e a n th ，1 2 l 越。 lt n a t w 咖m t | f r 棚m m i 甜明蛔互8 l 雠止 l ， il，“ 幽2 4g e f o r c e6 8 0 0 g t 的内核架构 从图2 4 中可以看到，这款g p u 具备6 个顶点着色器，1 6 个像素着色器和1 6 条像 素输出管线( r i ) p ) 。本文中的主要实验就是在1 6 个像素处理器上执行完成的。这两类 1 0 第一帝相关t 作 可编程部件的工作情况在下一章节中进行了详细介绍。 2 1 3g p u 中的可编程部件 v e r t e xp r o c e s s o d ”1 ( 见图2 6 ) 所需要做的工作主要是对顶点实施几何变换及对顶点属 性进行处理，即将几何模型的多边形或是三角形顶点数据流从c p u 交由此顶点处理器 实现几何变换及属性处理。 f r a g n c n tp r o c 鹤s o r 的工作( 见图2 7 ) 是实现扫描转换进行光栅化以后进行一系列 图形绘制处理，包括各种光照效果的合成、纹理映射、遮挡处理、反混淆处理等。 图2 6v e r t e x la p p l i c a t i o nl t e x a d d r e s si i i c o m m a n d l t e x f i l t e r l ig e o m e t r yl c o m b i n e r l ir a s t e r i z a t i o nlf o gl i t e x t u r e i i b l e n d i h if r a g m e n ti伍s , zt e s t s l ld i s p l a yil o g i c a lo p si 幽2 7f r a g m e n tp i p d i 从上面两幅图中我们可以看到，顶点处理器及像素处理器所能处理的工作是与图形 处理流水中的各种阶段及具体工作一一对应的。这正是g p u 能高效进行图形图像处理 的决窍所在。通过各个阶段部分的分工协作，它能最终实现图形图像的加速显示输出等 等工作而这些工作中数值计算，如矩阵乘等操作居多，因此人们会想到甩它来进行一 般通用计算的实现。 它们工作时的数掘交换情况如下图所示( 见图2 8 及2 9 ) 。 中国科学院坝l 。学位论文苹卡6p l l 的串挫配算法的，实现 m o d w m b l e m l l y o u 把i d eo f g l l 3 e g m g g l e n dp m l r e a d - o n l y r e a d w r i l e - a b l c r 髓d - o n l y r e e d w r i t e 4 b l e 图2 9f r a g m e n tp r o g 衄岫g 由于基于像素处理器的编程是本文工作的重点，基于它的实现细节在之后的章节中 会有详细的介绍，因此本节中我们主要介绍顶点处理器的结构。 从图2 8 中我们可以看到本文所用g p u 中v e 衄e x s h a d c 茁的构成： 1 6 个输入寄存器( v 0 - v 1 5 ，每一个寄存器都由1 2 8 位的四元浮点数构成) 来读 取输入的数掘。通过输入寄存器，v e r t e xs h a d 盯可以非常容易的表示一个典型顶 点的数据：位置坐标，法线，漫反射颜色和镜面反射颜色，雾坐标和贴图大小 信息。 1 个地址寄存器( a 0 x ) 。 9 6 个常量寄存器( c 0 - c 9 5 ) 。在v e r t e xs h a d e r 开始执行指定程序之前被c p u 加 载常量寄存器是只读的，一般用于储存例如光源位置、材质、特殊动画所需 数据等参数。常量寄存器可以通过地址寄存器a 0 x 来白j 接寻址。常量寄存器除 了在v e r t e xs h a d e r 中还可以在程序中被使用，但是在每一条指令中仅仅可以引 用一个常量就寄存器。如果一条指令需要引用超过一个的常量寄存器，它只能 1 2 第二章相关t 作 通过暂存寄存器来引用。 1 2 个暂存寄存器( r o - r 1 1 ) 。它们是可读写的，可以用于数据的存储和读取。 1 3 个输出寄存器。每个输出寄存器都以。打头。输出寄存器在光栅化时可以被 使用。存在输出寄存器中的最终结果是另外的一个顶点，一个转换入“同源剪 裁空间”的顶点。 这些寄存器都含有4 x 3 2 b i t 的值，每一个3 2 b i t 的值可以通过x , y , z 和w 来访问。为 了访问这些寄存器部件，就必须加上】【 m z 和w 在这些寄存器名字的末尾。数掘格式如 图2 1 l 所示。 f l o 曝f 、l q 蝌f l o 矾 f l o a t 4 m - 3 2b i t s l e a d t t 0 4x 3 2 l i l t s - 1 2 6 冰， 图2 1 0g p u 中处理的数据格式 因为使用一个指令但处理一组数据，v e r t e xs h a d e r 及f r a g m e n ts h a d e r 的硬件都可以 被看成是典型的s m i d ( 单指令多数据) 处理器。如图2 1 0 所示，单个的可编程处理器 在一次操作中可以同时处理四个3 2 位的数据。 ； 通过本节的介绍我们了解了g p u 的结构，下一节主要介绍普通的通用算法映射到 g p u 这类专门用于图形处理的专用部件上去的方法。 2 2g p u 编程方法研究 2 2 1 图形接口 图形接口是在g p u 上进行编程很重要的一个部分 三维图形接口能让编程人员所设计的三维软件只要调用其图形接口内的程序，从而 让图形接口自动和硬件的驱动程序沟通，启动图形处理器强大的三维图形处理功能，从 而大幅度地提高三维程序的设计效率。 现在比较流行和通用的图形接口有两个：o p e n g l 和d i r e c t x 。二者都是为了方便 人们对g p u 进行编程而出现的。如果没有这两个图形接口，在进行基于g p u 的编程时， 人们可能需要自己写一些最基本的函数，如画点画线等等，这些都会浪费人们的时间和 精力，而且实现起来效率可能还并不高。因此为了避免人们做重复且低效的无用功，图 形a p i 出现了。 图2 1 1 图形加速卡工作示意图 1 3 中田科学院坝l ：学位论文雌于g p 0 的串匹配算法的实现 d i r e c t x 是现在流行