《探计算统一设备架构纹理算法》由会员分享，可在线阅读，更多相关《探计算统一设备架构纹理算法（3页珍藏版）》请在金锄头文库上搜索。
1、探计算统一设备架构的纹理算法1 引言*纹理合成是当前计算机的研究热点之一。该技术在图像编辑、计算机动画、数据高倍压缩、网络数据的快速传输、大规模场景的生成以及真实感和非真实感绘制等方面具有广泛的应用前景。纹理合成方法可分为基于过程的纹理合成和基于样图的纹理合成两类。基于过程的纹理合成需要反复调整过程纹理的相关参数，十分繁琐。而基于样图的纹理合成技术不仅可以克服传统纹理映射存在走样的缺点，而且避免了纹理合成过程中调整参数的繁琐，因而受到越来越多研究人员的关注。中国。Wei和Levoy提出的纹理合成算法(下文简称WL算法)是典型的基于样图的纹理合成算法之一。与其它基于样图的纹理合成算法相比，该算法
2、实现简单，能够处理的纹理类型较多，合成质量较高。但是由于需要搜索输入样图每个像素，导致其合成速度较慢。目前对WL纹理合成采用的加速算法，如TSVQ（树形矢量量化法），SPSO（标准粒子群算法）等，虽然在速度上有所提高，但是其实现方法过于复杂，且在合成速度和合成质量上难以达到较好的平衡。计算统一设备架构(简称CUDA)是NVIDIA公司于2007年推出的一种基于GPU的并行计算平台。利用GPU强大的计算能力，可以开发出高效的并行算法，特别适合应用于图形图像处理。本文提出了一种基于CUDA计算平台，在GPU里完成主要计算的点匹配纹理合成并行算法。实验证明，并行后的算法可以明显提高合成的速度。中国提
3、供大量经济学硕士论文 。在本文的第二部分，介绍了基于点的纹理合成算法，第三部分阐述了计算统一设备架构（CUDA）。第四部分给出了基于CUDA纹理合成算法的实现方法。第五部分给出了实验结果。第六部分进行了总结与展望。2 基于点的纹理合成算法介绍WL纹理合成算法是基于点纹理合成算法的代表，是一种确定性搜索的纹理合成算法。该算法使用像素L邻域相似度作为合成依据，L邻域只取像素邻域的上半部分，因其形状像字母L，故称为L邻域。在输入纹理中按照扫描线顺序搜索与当前合成像素的L邻域具有最大相似度的像素点来合成纹理。WL算法的具体步骤如下:(1)用随机噪声初始化输出图像。(2)对于输出图像的每个像素p，按照扫
4、描线顺序计算：a.构造输出图像当前像素p的L邻域，b.在输入纹理中同样按照扫描线顺序搜索与像素p的L邻域具有最大相似度L邻域的像素q；c. 将像素q拷贝到像素p。(3)重复步骤，直到图像合成完毕。3 计算统一设备架构介绍2006年NVIDIA推出的G80系列显卡引入了CUDA架构，使得GPU可以解决商业、工业以及科学方面的复杂计算问题。下面对CUDA进行简要介绍：3.1 CPU 与GPU 结构的区别传统的CPU由于摩尔定律失效，其计算速度目前已经基本达到顶峰，而GPU则是专为计算密集型、高度并行化的计算而设计的。可以看出，GPU的设计增强了数据处理能力，而数据缓存和流控制方面则不及CPU。这使
5、得GPU适用于解决不需要过多精密流控制的大规模并行计算问题。另外GPU具有极高的存储器带宽，也为其处理大规模的数据带来了方便。3.2 CUDA 的线程层次模型和存储器分配CUDA采用线程-线程块-线程块网格的线程层次模型。一个线程块网格可以划分为多个线程块，每个线程块包含了一定数量的线程。CUDA通过如图3所示的这种结构来管理线程的执行以及存储器的分配。每个线程有一个私有的本地存储器。每个线程块有一个共享存储器，该存储器对于块内的所有线程都是可见的，并且与块具有相同的生命周期。最后，所有线程都可访问全局存储器。3.3 CUDA 运行模式CUDA定了一种称为内核（kernel）的C语言函数，并且
6、扩展了C语言。在调用此类函数时，它将由N个不同的CUDA线程并行执行N次，这与普通的C语言函数只执行一次的方式不同。另外CUDA把CPU称作主机，GPU称作设备，在运行CUDA程序时，串行代码在主机上执行，并行代码即”kernel”在设备上执行。另外，可以通过主机和设备同步函数，使CPU和GPU同时计算，提高程序效率。4基于CUDA 的纹理合成在纹理合成过程中要求在输入样本中寻找与目标图像中的已有像素p具有最大相似度的像素来合成纹理。如前所述，算法运行时间相当耗时。本文使用CUDA在GPU中并行计算领域相似度和搜索过程，明显提高了算法效率。本部分介绍在CUDA平台上用GPU来计算像素L邻域相似
7、度并寻找最大相似度像素的算法。4.1 GPU 存储器的分配把数据传入GPU，需要合理分配存储器。输入与输出图像存入对于所有线程都是可读写的Global Memory。在计算L邻域相似度时为各线程分配高速的Local Memory；而在规约计算查找具有最大L邻域相似度的像素时，则使用对线程块可见的shared memory。4.2 并行计算输入纹理L 邻域的相似度值在输入纹理中寻找L邻域最大相似度像素时，对输入纹理的所有像素应用公式来计算与待合成像素的L邻域相似度。原始的WL算法每合成一个像素，都需要对输入图像的每个像素串行计算L邻域相似度值，其时间复杂度为NML，这里设L邻域相似度计算时间为L
8、，而N,M分别是输入和输出图像中的像素数目。在计算L邻域相似度时，输入图像存储在GPU的Global Memory中，其每个像素在计算时不发生变化，即只需对Global Memory进行读操作，多个线程并行读Global Memory不会发生冲突。基于以上原因，通过GPU对此过程进行并行优化。以6464大小的输入样图为例，可使用6464个线程来并行计算，由一个线程计算一个像素的L邻域相似度。定义一个含有64个线程块的网格，每个线程块包含64个线程。这样便完成了像素到CUDA线程的映射。通过线程的分配，使L邻域相似度串行计算转为并行计算，计算L邻域相似度的时间复杂度理论上可降为1ML。4.3 并
9、行查找具有最大L 邻域相似度的像素在并行计算输入纹理的L邻域相似度后，需要找出具有L邻域最大相似度的像素。所有数据在GPU中计算得出，如果将数据传回CPU计算后再传入GPU，会浪费大量的数据拷贝时间。为提高整个程序的效率，在GPU中使用改进的并行规约算法来进行查找。并行规约算法的思想类似归并排序，图4显示了在一个含有16个线程的线程块里规约的执行情况。把规约中的加运算改为比较运算，并且设置一个监视哨，用来存储由公式计算得到的Euclid距离最小值（即L邻域最大相似度值）的位置。线程块里的每个线程分别处理一个数据，线程块前半部分的数据分别与后半部分数据比较，得出相对较小的结果，并存入前半部分线程
10、所分配的空间，以此循环，直到只剩下最后一个数据。此时监视哨里也保存了最小值的位置，它对应输入纹理的像素位置。对于程序中所有的线程块，以及线程块里面的线程，以上过程都是并行的。由归并排序思想，容易得出其时间复杂度为LOG2N，再由上一节结果，可得出整个算法的时间复杂度为(LOG2N+L)M(理论值)。另外，从图中可以看出，在执行完第一次比较，进行第二次比较时，有一半线程是空闲的，执行到最后，就只剩下一个线程在运行，浪费了很多线程资源，尽管如此，其效率也比CPU常用的查找算法高的多。更高效的规约算法，在数据量特别大，比如几M的级别时，其性能才能充分体现，本文的数据量最多只有几K（像素数目），并且规
11、约时间在整个算法占的比重较小，只占整个运行时间约6%，因此，本文只将较简单的规约算法修改使用。并且可进一步认为(LOG2N+L)MLM1。在CUDA程序中，CPU和GPU之间的数据交换非常耗时，如果在程序中频繁的进行数据拷贝，势必会大大降低程序的效率，甚至比一般的串行算法还要慢。本文算法只在程序开始将输入样图和输出图像拷入GPU，由GPU负责主要计算，输入样图往输出图像像素的拷贝也在GPU中完成，合成完成后再把数据拷回CPU。这样便减少了CPU和GPU之间数据拷贝的数量和次数，提高了程序效率。在实验中，数据传输，L邻域相似度计算和规约计算所需的时间比例分别是0.1%,93.9%和6%。GPU并
12、行算法流程:(1)用随机噪声初始化输出图像。(2)将输入输出图像传入GPU。(3)并行计算各输入图像与输出图像当前像素的L邻域相似度值。(4)通过改进的规约算法找出具有最大L邻域相似度的像素，并拷入输出图像。(5)重复,直到图像合成完毕，并将其从GPU传出到CPU。5 实验结果及分析实验平台为INTEL CORE2 T5470cpu，显卡是常用的NVIDIA GEFORCE 8400MGS与9800GTX显卡。在LINUX下文本模式下实验(图形模式会消耗显卡资源)。程序使用C语言编写（目前CUDA只支持C语言）。为了便于比较，输入纹理像素均等于输出纹理。5.1 不同邻域尺寸的加速比分别对L3,
13、7,9,13邻域进行实验，输入纹理为6464像素，显卡采用GEFORCE 9800GTX使用基本WL算法和经过CUDA加速的算法，并且对照TSVQ,SPSO加速的WL算法，它们的运行时间如下表所示。CUDA的平均加速效果可达100倍以上。由于合成算法的计算量随L邻域的增大而增加，图表中也可以看出计算量越大，GPU的加速越高，这也体现了CUDA平台下GPU的大规模并行处理能力。且加速比要高于SPSO和TSVQ加速的WL算法。5.2 不同尺寸输入样图的加速比对于基于CUDA的GPU并行来说，数据量越大，线程数越多，获得的加速比将会越大。分别对64 64,96 94,128 128 样图进行实验，
14、后两个样图分别使用的线程数是96 94,128128。显卡采用GEFORCE 9800GTX,对第一节介绍4类L邻域在GPU运算与基本WL纹理合成算法比较所得到的平均加速。这里像素比指后一个样图与第一个样图像素数的比值，相对加速比定为这两个样图加速比的比值。由上表可见，随着样图像素的增加，即线程数量的增加，加速比也会增加，但是并没有随线程数量呈线性增加，这主要是由于GPU流处理器数目以及流处理器同时处理线程数目的限制6。可同时执行线程的数目并不完全由像素数目决定，即达不到实际由像素数目而分配的线程数，也表明虽然前面给出的时间复杂度有LM1,但其实际加速比没有达到N。5.3 不同显卡实验结果对比
15、分别使用较低端的的8400M GS显卡和中档9800GTX显卡实验，输入纹理为6464像素，对第一节介绍4类L邻域的平均加速。显卡的处理速度主要由处理核心和核心包含的流处理器决定，8400M GS有16个流处理器，9800GTX有128个流处理器，流处理器数目的差别造成了它们处理速度的差别。从本文的结果也可以看出，GPU流处理器越多，它的性能越好。6 小结为了加速计算L邻域的相似度值并寻找最匹配的像素，利用CUDA平台下GPU强大的计算能力，并行计算输入纹理的L邻域相似度值，并使用改进并行规约算法寻找具有最大相似度的像素，提高了算法效率。然而加速比并没有达到并行线程的数量，这主要是局限于GPU流处理器的数目，以及算法本身的优化质量。另外，对不同大小的输入样图，或者非正方形样图，需要手工指定线程数目与线程块数目，也是需要改进的地方。在未来的工作中，可以尝试使用CUDA并行算法来加速块拼接的纹理合成和与合成顺序无关的纹理合成算法。
