● 摘要
随着并行计算技术的迅速发展，越来越多的算法开始应用到并行计算之中，GPU已经成为加速传统算法的有效工具。在航空领域，计算流体力学中的网格划分算法作为航空领域的典型应用，也是一种时间复杂度较高的算法。目前在飞行器设计中，对模型精度的要求越来越高，所需要的网格的粒度也越来越精细，计算网格划分的时间也就越来越长，所以急需将网格划分算法并行化，以提高模型精度进度和质量，提高飞行器的研发效率。此外，网格划分算法的并行因为数据依赖而变得困难，需要一个辅助方法来帮助程序员实现网格划分算法的并行。
本文以约束德劳内三角形网格划分并行算法为例，设计并实现了一种用于开发GPU航空应用的并行优化方案。本方案提供了一种全局线程同步机制，以保证算法执行过程中，各个线程可以互相协作并以正确的顺序执行，避免了节点之间由于数据依赖造成的访存冲突和数据不一致的错误。此外，方案还提供了两种可由编程人员使用的避免cache不一致的策略，弥补了GPU没有cache一致性协议的问题，增强了GPU的可编程性，最后用约束边插入算法对两种策略的使用做了解释和说明。
本文实现了并行化的网格划分算法和基于并行优化方案的约束边插入算法，并在现有的GPU上进行运行和验证，通过运行时间和cache出错率两个指标，分析了网格划分算法和并行优化方案的性能，实验取得了良好的效果。