C++并行广度优先搜索：基于层同步的优化与分布式实现

本文主要探讨了在实时三维角色动画制作中，基于层同步策略的并行广度优先搜索算法在C++编程中的应用。广度优先搜索(Breadth-First Search, BFS)是一种经典的图遍历算法，用于寻找图中两点之间的最短路径。在这个背景下，算法的核心是利用层次结构来管理和并行处理搜索过程。 在并行实现中，传统的广度优先搜索可能会遇到竞态条件，尤其是在更新顶点的距离值和将顶点添加到对应层的集合（如bag）时。原始算法中有两个竞争点：一是当多个处理器尝试同时更新同一顶点的距离，二是插入顶点到bag的过程可能导致数据冗余。为了克服这些竞争，作者引入了互斥锁（mutex），通过锁定机制确保在更新和插入操作的原子性，避免数据不一致性。 数据结构方面，作者构建了一种动态无序集（bag）的数据结构，它是通过辅助数据结构“pennant”实现的。pennant是一个有2k节点的树，具有合并操作，两个大小为2k的pennant可以合并成一个更大的。这种设计允许高效地存储和管理层级结构，同时支持并行操作。 文章在Cilk++运行时环境中，提出了使用非共享的“bag”数据结构替换共享队列，以减少竞争和提高并行性能。这是一种基于层同步的思想，通过细化任务分解，使得并行代码更容易理解和执行。而在分布式系统中，作者还探讨了一维邻接矩阵划分的并行广度优先搜索算法，进一步扩展了算法的适用范围。 作者通过对现有并行广度优先搜索算法的深入分析，结合C++编程实践，提出了一种新的并行策略，旨在优化算法的性能，提高在实时3D动画中的应用效率。这种方法不仅解决了竞态条件，还简化了并行编程的复杂性，对于提升图形处理和多媒体应用中的性能具有重要意义。 本文的创新性体现在两个方面：一是通过层同步策略改进了并行BFS的实现，二是提出了针对实时3D场景的高效数据结构和算法设计。通过这些改进，论文为并行计算和图形处理领域的研究者提供了有价值的参考，特别是在处理大规模和复杂图数据时，层同步并行BFS算法的应用前景广阔。