图匹配问题与分布式模型中局部性的定义及优劣解析

一、什么是局部性？ #

在这篇分布式图匹配算法的论文语境里，局部性指的是图的边在分布式存储下的归属集中程度：

• 如果一条边的两个端点都被分配给同一个处理单元（PE），这条边就是「本地边」，处理时不需要和其他PE通信；
• 如果两个端点分属不同PE，这条边就是「跨PE边」，算法执行时必须和对应PE交换数据才能处理。

简单说，就是看边能不能被单个PE“自留处理”，不用跨节点折腾。

二、怎么区分优、劣局部性？ #

高（优）局部性 #

• 核心特征是绝大多数边都是本地边，跨PE边占比极低。对应论文里的实验场景：PE分配的是连续编号区间的节点，如果图里的边大多连接编号相近的节点，这些边自然就归同一个PE管，不需要跨PE交换信息。
• 这种场景下算法通信开销极小，性能表现最好。

低（劣）局部性 #

• 核心特征是大量边都是跨PE边，本地边占比低。比如图里的边经常连接编号跨度极大的节点，这些边就会被拆分到不同PE手里。
• 对应论文里说的最坏情况：算法第二阶段需要交换几乎所有PE处理的边信息，通信开销暴增，直接拖慢算法效率。

论文原文相关描述：

我们基于p个处理单元（PE或MPI进程）的分布式内存并行化（采用MPI）将节点分配给PE，并将节点的所有关联边存储在本地。若没有节点的度数超过m/p，则可实现负载均衡。第2节中基础算法的第二阶段需要交换跨PE边界的候选边信息。最坏情况下，这会涉及PE处理的所有边，即若能让大多数边保持在本地，性能会更优。在我们的实验中，一个PE拥有编号为输入连续区间的节点。因此，输入编号包含的局部性程度决定了当前是高局部性还是高非局部性场景。

内容的提问来源于stack exchange，提问作者Reem