您的位置 首页 制造

根据GPU的并行Voronoi图栅格生成算法

Voronoi图是一种空间分割算法。其是对空间中的n个离散点而言的,它将平面分割为n个区域,每个区域包括一个点,此区域是到该点距离最近的点的集合。由于

Voronoi图是一种空间切割算法。其是对空间中的n个离散点而言的,它将平面切割为n个区域,每个区域包括一个点,此区域是到该点间隔最近的点的调集。因为Voronoi图具有最附近性,邻接性等很多性质和完善的理论体系,其被广泛的运用在地理学、气象学、结晶学、航天、机器人等范畴。

Voronoi图的生成首要有矢量办法和栅格办法。矢量法中,典型的办法有增量法、分治法和直接法。分治法是一种递归办法,算法思路简略,可是很难在运用过程中完结动态更新。直接法则是依据其对偶图Delaunay三角网来结构Voronoi图,因而其功能的凹凸由所选用的Delaunay三角网的结构算法所决议。增量法经过不断向已生成的Voronoi图中添加点来动态构建Voronoi图。相对于前两种办法,增量法结构简略而且简单完结动态化,所以被广泛运用。矢量办法的优势是生成Voronoi图精度高,可是存在存储杂乱,成长元只能是点和线,以及难以向三维及高维空间扩展等问题。因而本文要点研讨了Voronoi图的栅格生成办法,首要比较了常见的栅格办法生成Voronoi图的优缺陷,然后结合CUDA的呈现,提出一种根据GPU的 Voronoi图并行栅格生成算法。

1 栅格法简介

栅格办法生成Voronoi 图首要是将二值图画转化为栅格图画,然后确认各个空白栅格归属。首要办法有两类,一类以空白栅格为中心,核算每个空白栅格到成长方针的间隔,以确认其归属,常见的办法有代数间隔改换法,逐个空白栅格确认法等;另一类以成长方针为中心,不断扩张成长方针的间隔半径,填充其间的空白栅格,直到将整个图画填充完结,首要有圆扩张法,数学形态学间隔改换法等。代数间隔改换法对间隔图画进行上行扫描(从上到下,从左到右)和下行扫描(从下向上,从右到左)两次扫描,核算出每个空白栅格最附近的成长方针,以此成长方针作为其归属。此办法中栅格间隔的界说直接影响了空白栅格的归属和Voronoi图的生成精度,一般运用的栅格间隔界说有街区间隔、八角形间隔、棋盘间隔等。间隔改换的栅格生成办法精度低、耗时长,所需求花费的时刻和栅格的数量成正比,当栅格为n×n大小时,其时刻杂乱度为O(n×n)。圆检测法以成长方针为圆心,以必定的步长为初始半径,一切成长方针一起对其构成的圆内的空白栅格进行掩盖。经过不断扩展成长方针的半径,将会有越来越多的空白栅格被各个圆所掩盖,直到终究掩盖完好个图画。数学形态学间隔改换法与圆检测法相似,其思维来源于数学形态学中胀大操作,胀大操作起到了扩展图画的作用,经过不断的对成长方针进行胀大操作,终究扩张到一切的空白栅格。这两种办法有个一起的缺陷,在每次扩张后,都需求判别整个栅格图画是否已完结扩张,而这需求遍历栅格图画,非常耗时。

2 GPU下的栅格生成办法

2.1 CUDA编程模型与GPU

CUDA是一个并行编程模型和一个软件编程环境,其选用了C言语作为编程言语,供给了很多的高功能核算指令开发才能,使开发者能够在GPU的强壮核算才能上建立起一种愈加高效的密布数据核算解决方案。

CUDA将CPU作为主机端,GPU作为设备端,一个主机端能够有多个设备端。其选用CPU和GPU协同作业的办法,CPU首要担任程序中的串行核算的部分,GPU首要担任程序中的并行核算的部分。GPU上运转的代码被称为内核函数,其能够被GPU上内置的多个线程并行履行。一个完好的使命处理程序由 CPU端串行处理代码和GPU端并行内核函数一起构成。当CPU中履行到GPU代码时,其首要将相关数据复制到GPU中,然后调用GPU的内核函数,GPU中多个线程并行履行此内核函数,当完结核算后,GPU端再把核算的成果回来给CPU,程序持续履行。经过将程序中耗时的且便于并行处理的核算转移到GPU中运用GPU并行处理,以进步整个程序的运转速度。CUDA是以线程网格(Grid),线程块(Block),线程(Thread)为三层的安排架构,每一个网格由多个线程块构成,而一个线程块又由多个线程构成,如图1所示。在GPU中,线程是并行运转的最小单元,由此可见,当存在很多的线程时,程序的并行程度将会非常高。现在的GPU上一个网格最多包括65535×65535个线程块,而一个线程块一般有512个或1024个线程,所以理论上能够对65535×65535×512个栅格一起进行核算。

2.2 并行Voronoi图栅格生成算法

传统的栅格生成算法中,不论是选用以空白栅格为中心确认其归属的办法,还是以成长方针为中心经过不断增加成长方针半径对空白栅格进行掩盖的办法,他们在核算每个空白栅格间隔时,只能经过遍历栅格,逐个处理。而栅格处理过程中的一个重要特点是,各个栅格的核算并不依赖于其他栅格的核算成果。即各个栅格的核算是彼此独立的,而因为CPU的串行性,导致了各个栅格只能次序处理,降低了处理速度。

图1GPU安排架构

因为GPU下的多个线程都是硬件完结的,各个线程的处理都是并行的,因而将栅格间隔的核算涣散到GPU端各个线程,必定能够进步其生成速度。为了并行处理栅格化图画,能够选用如下的主意,将每一个栅格点对应于一个线程,此线程核算此栅格到一切的成长方针的间隔,取最小间隔的成长方针作为其归属。即选用一个线程用来确认一个空白栅格归属的办法。

确认办法后,就需求对GPU端内核函数进行规划,因为内核函数是并行处理的履行单元,其规划办法直接决议了GPU端的程序运转功率。因而怎么规划杰出的内核函数是进步并行速度的要害。本文选用如下办法进行内核函数的规划,假定共分配了K个并行处理线程,栅格规划为M×N,设A[i]为第i个线程处理的栅格编号。当K

因为显卡上的内存是动态随机存储(DRAM),因而最有功率的存取办法,是以接连的办法存取。当选用第一种办法时,看似是一种接连的存取办法,实际上刚好对错接连的,当第i个线程处理第i个栅格时,因为处理需求必定的时刻,此刻GPU主动将下个一线程i+1需求的内存数据取出给其运用,此刻下一个线程的内存数据却是在i+C处,内存变成了接连存取。而在运用第二种办法进行处理时,刚好是一种接连的存取办法,因为第i个线程正在处理第i个栅格数据,此刻 GPU为第i+1个线程预备数据,而此刻的数据正好为第i+1内存处。满意了内存的接连存取特性。因而本文选用第二种办法,内核函数的规划伪代码如下:

声明:本文内容来自网络转载或用户投稿,文章版权归原作者和原出处所有。文中观点,不代表本站立场。若有侵权请联系本站删除(kf@86ic.com)https://www.86ic.net/bandaoti/zhizao/146626.html

为您推荐

联系我们

联系我们

在线咨询: QQ交谈

邮箱: kf@86ic.com

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

返回顶部