基于CUDA的D-P曲线压缩算法并行实现

摘要

数字地图、定位导航等领域无时无刻不在产生大量的曲线数据，这些数据规模庞大，具有占用存储空间大且传输速度慢的特点，为了解决这个问题，Douglas-Peucker曲线压缩算法成为了一个研究热点。
　　Douglas-Peucker曲线压缩算法效果显著，应用广泛。但是，目前关于Douglas-Peucker的研究主要集中在CPU串行方面，随着曲线数据规模的增大，CPU串行运行时间长，性能无法满足要求，而串行优化方案对性能的提升有限，因此并行化为其提供了一个好的解决方案。2007年，NVIDIA发布GPU CUDA，该平台编程简单且计算能力强，为并行计算提供了一个优秀的选择。
　　基于CUDA平台，以Douglas-Peucker算法作为研究重点。通过阅读大量相关文章了解该算法的研究现状，从理论上分析Douglas-Peucker是否适合CUDA并行，设计相应的并行方案，并对涉及的相关其他算法也提供了并行化方案，采用多种优化策略提高算法效率，最后利用不同类型的曲线数据进行了大量的实验，并归纳总结了常见的算法优化思路。实验表明，在实验效果方面，基于CUDA的Douglas-Peucker并行算法压缩效果明显;在性能方面，通过与CPU串行版本算法对比发现，随着曲线数据规模的增大，GPU并行版本算法较串行版本算法达到了加速目的且具有明显优势，因此具有工程和科研价值。

目录

声明

摘要

引言

1 GPGPU并行计算概述

1．1 GPGPU并行计算

1．2 CUDA并行编程平台

1．2．1 CUDA编程模型

1．2．2 CUDA软件结构

1．2．3 CUDA存储器模型

2 Douglas-Peucker算法及可并行化分析

2．1 Douglas-Peucker算法分析

2．1．1 D-P算法背景

2．1．2 D-P算法实现步骤

2．1．3 D-P算法研究现状

2．2 Scan算法分析

2．2．1 数组Scan算法

2．2．2 数组分段Scan算法

2．3 Douglas-Peucker算法可并行化分析

3 Douglas-Peucker算法的CUDA并行设计与实现

3．1 Scan算法并行设计与实现

3．1．1 数组Scan算法并行设计与实现

3．1．2 数组分段Scan算法并行设计与实现

3．2 Douglas-Peucker算法并行设计

3．2．1 D-P算法并行思路

3．2．2 D-P算法并行设计流程

3．3 Douglas-Peucker算法并行实现

3．3．1 算法数据结构

3．3．2 初始化点标记值

3．3．3 计算各点垂距

3．3．4 标记各段新发现的点

3．3．5 生成临时结果点集

3．3．6 更新各点标记值

3．4 D-P算法改进(FD-P算法)

3．5 D-P算法并行优化策略

3．5．1 访存优化

3．5．2 并行度优化

3．5．3 数据拷贝优化

4 实验结果以及性能分析

4．1 实验环境介绍

4．2 实验结果分析

4．2．1 闭合曲线实验结果分析

4．2．2 非闭合曲线实验结果分析

4．3 实验性能分析

4．3．1 不同阈值下性能分析

4．3．2 串并行D-P算法性能分析

4．3．3 并行D-P算法稳定性分析

4．3．3 串并行FD-P及D-P算法性能分析

结论

参考文献

攻读硕士学位期间发表学术论文情况

致谢