CUDA加速的地图代数并行算法.pdfVIP

第3l卷第1期 桂林理工大学学报 V01．31No．1 2011年2月 JournalofGuilin ofTechnology Feb． 201l University 文章编号：1674—9057(2011)01-0139—05 CUDA加速的地图代数并行算法 张剑波，周斯波，张 帅 (中国地质大学信息工程学院，武汉430074) 摘要：针对传统地图代数实现方法应用于海量栅格数据计算时效率低下的问题，在一种全新的GPU 并行编程模型CUDA上，利用地图代数算子体现出来的基于栅格点集、处理流程相对固定、数据处理 具有内在的并行性等特点，将传统的串行算法映射到GPU并行处理架构上，旨在从串行算法的并行化 映射、计算机图形处理器资源的自适应参数调整等多角度来研究地图代数空间并行算法的实现机制， 为空间分析算法的优化研究提供一种新的解决思路。 关键词：地图代数；统一计算设备架构(CUDA)；并行计算 中图分类号：TP3ll；P282 文献标志码：A 地图代数是一种以栅格点集的变换和运算来 1国内外研究现状 解决地理信息图形符号的可视化和空间分析的理 论和方法，它采用代数观点全面阐述地理信息处 地图代数是Tomlin等口。提出的一种栅格建模 理和可视化本质与过程…。作为栅格数据空间分 语言，其中栅格数据以图层形式表示地理信息， 析的核心技术，地图代数可被广泛应用于包括气 地图代数则是对这些图层进行操作和变换的工具。 象监测、土地利用、农业产量分析等多个专业领 域。与此同时，随着可编程图形处理器(graphic类型的高阶函数，区别体现在函数操作对象的范 unit，GPU)并行处理能力的大幅提高，围不同：Local函数以单个像元为基础；Focal函数 processing on GPU，GPG· GPU通用计算(generalcomputation 以像元邻域内的像元集为基础；Zonal函数以分区 PU)被逐步应用到其他众多高性能计算领域，诸内的像元集为基础，而Global函数则是面向栅格 如偏微分方程组求解、优化问题、串匹配算法、 内所有像元数据。 遗传算法、微粒群算法等。在一些计算密集型领 近年来，很多学者在Tomlin的基础上不断扩展 域。GPU比单独的CPU更具优势旧J。 考虑到地图代数分析算法具有基于栅格点集、 可以将控制结构和动态模型结合进入地图代数中； 处理流程相对固定、数据处理具有内在的并行性 Service 等特点，笔者选取一种全新的GPU并行编程模型互操作性。提出了将地图代数嵌入到Web unifieddevicear- ——统一计算设备架构(compute 中的建议和实现步骤；Mennis等∞1提出一种用于 chitecture，CUDA)作为技术支撑，研究将基于地时空数据处理的地图代数扩展——立方体地图代 图代数的栅格数据分析算法移植到CUDA并行编数函数；Frank【．¨提出如何将地图代数形式化为一 程模型上的映射机制，使得利用GPU实现栅格数种函数编程语境，并说明该研究分支如何同时提 据的高性能并行计算成为可能，为空间分析算法 供对空间数据和时空数据的操作支持；Gilberto 的优化研究提供一种新的解决思路。 等聃1在Tomlin地图代数的基础上引入拓扑谓词和 收稿日期：2010一05一14 基金项目：国家自然科学基金项目 作者简介：张剑波(1975一)，男，博士，副教授，研究方向：栅格数据存储模型及空间分析应用，zjbtlgers@126．CO