利用CUDA实现矢量地图栅格化的并行处理.docxVIP

2246．2014．0373利用CUDA实现矢量地图栅格化的并行处理程博艳1，2，刘强1，李小文1，张涛1(1．电子科技大学资源与环境学院，四川成都611731;95007部队，广东广州510071)2．ParallelＲasterizationofVectorPolygonBasedonCUDACHENGBoyan，LIUQiang，LIXiaowen，ZHANGTao摘要:为了解决矢量地图栅格化的计算效率问题，提出了基于计算统一设备架构(CUDA)实现矢量地图栅格化的并行处理方案。根据矢量地图中多边形的数目和图形处理器(GPU)的硬件性能，定义并行执行的线程数目，每一个线程对相应的多边形进行边填充栅格化。试验结果表明，加速比达到了10倍以上，相比中央处理器(CPU)栅格化的处理方法，运算效率有显著提升。关键词:矢量栅格化;边填充法;图形处理器(GPU);计算统一设备架构(CUDA)中图分类号:P208文献标识码:B文章编号:0494-0911(2014)11-0097-05便于空间分析的问题，武广臣［7］提出了基于计算几何转角理论的环绕数法;李青元等［8］提出了绘制—检出的矢量数据栅格化方法。目前大多数计算机中最重要的两种处理器是多核的中央处理器(centralprocessingunit，CPU)和众核的图形处理器(graphicprocessingunit，GPU)。传统上，GPU只用于处理3D图像渲染任务，其他多数的任务都交给CPU。GPU在处理能力和存储器带宽上相对于CPU有明显优势。图形渲染的高度并行性，使得GPU可以通过增加并行处理单元和存储器控制单元的方法提高处理能力和存储器带宽［9］。GPU并行计算已广泛应用于模式识别［10-11］、遥感图像处理［12-14］、GIS数字地形分析［15］等众多领域。近年来，GPU的硬件性能有了飞速提升，2007年NVIDIA公司公布了一种不需要借助图形学应用一、引言地理信息系统中对现实世界的表达可以采用矢量和栅格两种数据结构实现。两类结构都可用来描述地理实体的点、线、面3种基本类型。表示具有确定位置与形状的离散要素选择矢量数据结构较为理想，而表示连续现象则最好选择栅格数据模型。在栅格模型中，空间被规则地划分为栅格(通常为正方形)。地理实体的位置和状态是用它们占据的栅格的行、列来定义的。每个栅格的大小代表了定义的空间分辨率，栅格的值表达了这个位置上实体的类型或状态。GIS中将矢量数据转换成栅格数据的过程称为矢量栅格化(vectorconversion)或栅格化toraster(rasterization)。多边形要素的矢量格式向栅格格式转换又称为多边形填充，即在矢量表示的多边形界内部的所有栅格上赋予相应的多边形编号，从而形成栅格数据阵列。多边形栅格化的传统方法主要有内部点扩散法、复数积分法、射线法、扫描法、边填充法等［1］。随着计算机等相关技术的发展，矢量栅格化的问题又出现了许多新的方法。李志清［2］提出一种所谓“掩模”(MASK)法进行面状图的栅格化;黄波和陈勇［3］提出颜色填充法;吴华意［4］和王建［5］对任伏虎提出的边界代数多边形填充算法(boundaryalgebrafilling，BAF)进行了改进，分别提出了无边界游程编码的边界追踪方法和折线边界(数据串)跟踪方法;章孝灿等［6］提出一种快速栅格化算法———差分边界标志与累加扫描算法;针对边界代数法不程序编程接口(applicationprogramminginterface，API)就可以使用类C语言进行通用计算的开发环境和软件体系———计算统一设备架构(computeuni-fieddevicearchitecture，CUDA)，有效地利用了GPU的硬件资源进行通用计算，并且编程更简单、功能更强大、应用领域更广泛。二、CUDA编程技术1．主机与设备CUDA编程模式将CPU作为主机(host)，GPU作为协处理器(co-processor)或设备(device)，一个系统中可以存在一个主机和若干个设备。CPU负责进行逻辑性强的事务处理和串行计算，GPU负责执行高度线程化的并行处理任务。CPU和GPU各收稿日期:2013-11-24作者简介:程博艳(1977—)，女，山西永济人，博士生，研究方向为GIS。98测绘通报2014年第11期自拥有相互独立的存储器地址空间:主机端的内存和设备端的显存。一个CUDA程序也分为两个部分:主机端程序和设备端程序。前者指运行在CPU上的串行代码，后者指运行在GPU上的并行代码。2．kernel函数运行在GPU上的CUDA并行计算函数称为kernel(内核函数)。一个kernel函数并不是一个完整的程序，而是整个CUDA程序中的一个可以被并行执行的步骤。kernel函数必须通过“—