面向多核架构的高效流径遍历算法：栅格数字高程模型流域划分新方法

《Environmental Modelling & Software》：An Efficient Flow Path Traversal Algorithm for Watershed Delineation from Raster Digital Elevation Models for Multicore Architectures

　　本文提出一种高效的流径遍历算法（Flow Path Traversal Algorithm），用于从栅格流向网格（flow direction grid）中快速划分流域（watershed delineation）。该算法通过创新的追踪策略，将每个像元处理次数限制为常数，无需额外数据结构，时间复杂度为O(N)，显著提升了多核CPU架构下的计算效率。实验表明，其串行版本优于现有算法，并行版本在测试数据集上运行速度最快，为个人计算机实现高性能流域划分提供了重要技术支撑。

　　

现有流域划分算法概述

本节概述了四种基于栅格流向网格的现有流域划分算法。如需更全面的技术综述，读者可参考Koytra (2023)。为清晰一致，伪代码中常用符号列于表1，遵循Zhou等人(2019)的惯例。

值得注意的是，对于所有四类算法，输出网格（Watershed）应...

提出的流径遍历算法

如第2节所述，迭代算法和流径追踪算法专为GPU架构设计，利用其大规模并行性实现高效率。其中，流径归约算法运行最快（Koytra 2023）。相反，递归算法和区域生长算法最初为单核CPU设计，通常难以在多核CPU上高效并行。尽管存在高效的基于GPU的算法，我们的目标是充分利用多核CPU的计算能力。

我们提出的流径遍历算法采用了一种新颖的追踪策略。算法遍历每个像元，直至遇到已知流域标签的像元或追踪至研究区外。这种方法将每个像元的处理次数限制为常数，无需任何额外数据结构，并且无论要划分的流域数量多少，均能实现O(N)的时间复杂度。

实验与讨论

本节我们评估了提出的串行和并行流径遍历算法的性能，并与三种参考算法进行了比较。参考算法包括我们实现的递归算法、区域生长算法，以及Cho (2025a)提出的MESHED_m算法。我们未将迭代算法和流径归约算法纳入比较，因为它们主要针对GPU架构设计。如果...

结论

现有的高效流域划分算法要么旨在利用GPU的大规模并行性，要么难以在多核CPU上高效并行。在本研究中，我们提出了一种高效的流径遍历算法，用于从栅格流向网格划分流域。我们提出的算法持续追踪每个像元，直至遇到已知流域标签的像元或追踪移至研究区外，将像元处理中的冗余降至最低...