基于CUDA快速凸包并行设计与研究的中期报告.docx

基于CUDA快速凸包并行设计与研究的中期报告
本文主要围绕基于CUDA的快速凸包计算进行研究和探讨，本项目中期进展如下：
一、研究背景和意义
快速凸包算法是计算机图形学和计算几何学中的重要问题之一，它被广泛应用于计算机辅助设计、图形图像处理、计算机视觉等领域。而并行计算则是当前计算机科学领域的热门话题，可以通过并行计算提高计算机计算速度、降低计算成本。
本研究的意义在于，结合CUDA并行计算能力，实现基于GPU的快速凸包计算算法，提高计算效率，为相关领域的研究和应用提供支持。
二、完成的工作
1.研究CUDA并行计算技术
本项目首先对CUDA并行计算技术进行了深入的学习和探究，包括CUDA的工作模式、线程分配、内存管理、异步传输等方面。了解了CUDA的特点和使用方法，为后面实现GPU加速提供了基础。
2.梳理快速凸包算法思路
在对快速凸包算法进行研究后，我们发现该算法可以分为两个阶段：排序和求凸包。在排序阶段，我们采用快速排序的方式将输入点按照x坐标排序；在求凸包阶段，使用GrahamScan算法或JarvisMarch算法解决问题。
3.实现基本的快速凸包算法
针对分析的结果和算法思路，我们基于C++和OpenMP实现了基本的快速凸包算法，得到了预期的结果，但其计算效率不高，在处理大规模数据时容易出现性能问题。
4.基于CUDA的快速凸包算法并行设计
为了提高计算效率，我们决定使用CUDA并行计算技术对快速凸包算法进行加速。我们设计了具有多个线程块和每个线程块有多个线程的CUDA快速凸包计算模型，针对具体问题进行了优化调整。我们使每个线程块计算一个子凸包，然后合并子凸包，最终得到整个凸包。这样可以有效利用CUDA的并行计算优势，加快计算速度。
5.实现基于CUDA的快速凸包算法
在对CUDA并行计算技术及其应用进行了深入地学习和掌握之后，我们基于NVIDIA官方提供的CUDA开发工具包，使用C++结合CUDA编写了快速凸包算法程序。该程序实现了数据输入、CUDA加速计算、结果输出等功能，并且实现了显卡自动分配内存等功能。
三、下一阶段计划
接下来的研究，我们将会：
1.进一步优化设计算法
对于已实现的算法，我们将继续进行性能优化，包括加入OpenMP等多线程优化技术，使得算法效率得到更好的提升；
2.拓展应用范围
将快速凸包算法应用到更多领域，例如云计算和大数据处理。此外，我们计划将多处理器器上的多GPU进行优化，进一步提高并行计算的效率。
3.完善实现的程序
完善程序功能，提高程序的鲁棒性和健壮性，以适应更广的应用场景。
四、总结
本中期报告介绍了我们在基于CUDA的快速凸包并行设计与研究中取得的进展。我们通过对CUDA并行计算技术的学习和掌握，成功实现了基于CUDA的快速凸包计算算法。下一步，我们将进一步优化算法性能和程序鲁棒性，同时探索更多的应用场景。