EDN China > 设计实例 > 微处理器与DSP > CPU/GPU > 正文
? 2016博客大赛-不限主题,寻找电子导师,大奖升级??

基于GPU的并行Voronoi图栅格生成算法

屠文森?? 汪佳佳?? 南京理工大学 现代电子技术?? 2015年07月10日 ?? 收藏0

2.2 并行Voronoi图栅格生成算法

传统的栅格生成算法中,不论是采用以空白栅格为中心确定其归属的方法,还是以生长目标为中心通过不断增长生长目标半径对空白栅格进行覆盖的方法,他们在计算每个空白栅格距离时,只能通过遍历栅格,逐一处理。而栅格处理过程中的一个重要特点是,各个栅格的计算并不依赖于其他栅格的计算结果。即各个栅格的计算是相互独立的,而由于CPU的串行性,导致了各个栅格只能顺序处理,降低了处理速度。

图1 GPU组织架构
图1 GPU组织架构

由于GPU下的多个线程都是硬件实现的,各个线程的处理都是并行的,因此将栅格距离的计算分散到GPU端各个线程,必然能够提高其生成速度。为了并行处理栅格化图像,可以采用如下的想法,将每一个栅格点对应于一个线程,此线程计算此栅格到所有的生长目标的距离,取最小距离的生长目标作为其归属。即采用一个线程用来确定一个空白栅格归属的方法。

确定方法后,就需要对GPU端内核函数进行设计,由于内核函数是并行处理的执行单元,其设计方式直接决定了GPU端的程序运行效率。因此如何设计良好的内核函数是提高并行速度的关键。本文采用如下方式进行内核函数的设计,假设共分配了K 个并行处理线程,栅格规模为M×N,设A[i]为第i 个线程处理的栅格编号。当K<M×N 时,只需要将栅格与线程按序依次分配,即第i个线程处理第i个栅格(式(1))即可。当线程个数少于栅格个数时,一个线程必须负责处理多个栅格。首先可以计算出每个线程平均需要处理的栅格个数C=M × N K ,然后对栅格采用具体的分配方式,可以有两种分配方式,一种将连续的C 个栅格分配给一个线程处理,即第i 个线程处理第i×C,i×C+1,i×C+2,…,i×C+C-1个栅格(式(2))。另一种方式为将栅格按C大小分块,将每块的第i 个栅格分配给第i 个线程,即第i 个线程处理第i,C+i,2×C+i,3×C+i,…,(C-1)×C+i 个栅格(式(3))。

并行Voronoi图栅格生成算法

由于显卡上的内存是动态随机存储(DRAM),因此最有效率的存取方式,是以连续的方式存取。当采用第一种方式时,看似是一种连续的存取方式,实际上恰好是非连续的,当第i 个线程处理第i 个栅格时,由于处理需要一定的时间,此时GPU自动将下个一线程i+1需要的内存数据取出给其使用,此时下一个线程的内存数据却是在i+C 处,内存变成了间断存取。而在使用第二种方式进行处理时,恰好是一种连续的存取方式,由于第i 个线程正在处理第i 个栅格数据,此时GPU为第i+1个线程准备数据,而此时的数据正好为第i+1内存处。满足了内存的连续存取特性。因此本文采用第二种方式,内核函数的设计伪代码如下:

并行Voronoi图栅格生成算法

具体步骤如下:(这里假设栅格的规模为M×N):

Step1:根据栅格图像的规模,确定GPU端线程块和线程的分配方式和分配数量,初始化GPU端的参数。

Step2:程序调用GPU端内核函数,同时将待处理栅格图像数据传入GPU中。数据主要是图像的栅格距离,一般是二维数组,0表示空白栅格,其他各生长目标可由1,2等不同的数字定义。

Step3:GPU分配M×N 个thread对栅格进行处理,当M×N 大于所有的thread的总数时,可以将M×N 个栅格分块处理,即将其分成A 行×B 列×C 块,其中A×B 小于thread的总数。对于分成了C 块的栅格来说,每个线程只需要处理C 个栅格。

Step4:当生长目标数目不多时,每一个线程计算其对应的栅格到所有的生长目标点的距离,取距离最小的生长目标,为此线程对应的空白栅格的归属,转Step6。当生长目标过多时,则转Step5。

Step5:当生长目标较多时,为了减少遍历生长目标的时间,通过借鉴王新生的算法,不计算栅格点到每一个生长目标的距离,通过对空白栅格不断的进行邻域扩张,直到遇到目标生长点的方法确定此栅格的归属。

Step6 将生成后的数据返回CPU端,CPU端完成栅格图像的显示与后处理。

【分页导航】


?? ?? ??


打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

1.扫描左侧二维码
2.点击右上角的分享按钮
3.选择分享给朋友
?? ??

Voronoi图? 栅格法? GPU? CUDA?

相关文章

我来评论
美国的游客
美国的游客 ??? (您将以游客身份发表,请登录 | 注册)
?
有问题请反馈