🏠

ParLV 并行 Louvain 分区编排器技术深度解析

模块定位: FPGA 加速图分析流水线中的分布式社区检测编排核心

核心文件: graph/L2/benchmarks/louvain_fast/host/partition/ParLV.h, ParLV.cpp

一、为什么需要这个模块？

1.1 问题空间：当图大到单设备放不下

Louvain 算法是图社区检测的黄金标准，但在处理十亿级边的大规模图时面临根本性挑战：

  • 内存墙: 单 FPGA/CPU 的 HBM/DDR 容量有限，无法容纳完整图结构
  • 计算瓶颈: 顺序 Louvain 迭代在大型图上收敛缓慢
  • 通信开销: naive 的分布式实现会产生跨设备通信风暴

1.2 设计洞察：分区-并行-合并-精化的四段式流水线

ParLV 的核心设计洞察是：图社区检测具有天然的"近似可分解性" —— 局部子图的社区结构在全局上下文中基本保持稳定。基于这一观察，ParLV 实现了一个四阶段 Map-Reduce 风格的处理流水线：

Phase 1: Partition (Map) — 将图分割为 num_par 个子图

  • 顶点范围分区 (范围: [start, end))
  • 边分类：local-local (ll), local-ghost (lg), ghost-local (gl), ghost-ghost (gg)

Phase 2: Parallel Louvain — 每个子图独立运行 Louvain

  • 生成社区标签 C[] 和模块度映射 M[]

Phase 3: Pre-Merge — 准备合并所需数据结构

  • 顶点/边计数，内存预分配

Phase 4: Merge — 合并所有子图为粗化图

  • 基于社区的粗化图，社区作为超级节点

这个设计的关键优势在于：每个分区的 Louvain 计算是 embarrassingly parallel 的，只有最后的合并阶段需要全局协调。

二、核心抽象：你需要在脑中构建的模型

2.1 状态机视角：ParLV 是一个有状态的工作流编排器

想象 ParLV 是一个工厂的生产线调度系统，它管理着一批工件（图分区）在多个加工站（处理阶段）之间的流转：

                    ┌─────────────┐
    st_Partitioned  │  Partition  │◄── 原始图进入，切割成子图
           │        │   (Map)     │    par_src[0..num_par-1] 可用
           │        └─────────────┘
           │                │
           ▼                ▼
    st_ParLved       ┌─────────────┐
           │         │   Parallel  │◄── 每个子图独立跑 Louvain
           │         │   Louvain   │    par_lved[0..num_par-1] 可用
           │         └─────────────┘
           │                │
           ▼                ▼
    st_PreMerged     ┌─────────────┐
           │         │  Pre-Merge  │◄── 准备合并所需数据结构
           │         │  (Prepare)  │    内存预分配，偏移计算
           │         └─────────────┘
           │                │
           ▼                ▼
    st_Merged        ┌─────────────┐
           │         │    Merge    │◄── 合并所有子图为粗化图
           │         │  (Reduce)   │    plv_merged 可用
           │         └─────────────┘
           │                │
           ▼                ▼
    st_FinalLved     ┌─────────────┐
                    │Final Louvain│◄── 在粗化图上精化
                    │  (Refine)   │    plv_final 可用，结果回写
                    └─────────────┘

关键设计: 这些状态标志不是装饰性的——它们是前置条件守卫。每个处理阶段的方法都会检查前置状态是否满足，确保数据流按正确的顺序通过管道。

2.2 图分区模型：幽灵顶点与边的四象限分类

理解 ParLV 如何处理跨分区边，是掌握其设计的关键。想象你有一张城市地图，现在要把它分割成多个区域供不同团队分析：

核心概念:

  • 本地顶点 (NVl): 实际属于当前分区的顶点
  • 幽灵顶点 (NV_gh): 属于其他分区但与本地顶点有边相连的顶点
  • 边的四象限分类:
    • NEll: 本地顶点 → 本地顶点 (完全在子图内部)
    • NElg: 本地顶点 → 幽灵 (跨到外部分区)
    • NEgl: 幽灵 → 本地顶点 (从外部进入)
    • NEgg: 幽灵 → 幽灵 (纯跨分区边，不触及本地顶点)

幽灵顶点是分区边界的"代理人"——它们不实际存储完整的顶点数据，而是作为跨分区连接的"桩"，在后续合并阶段需要被解析为实际的社区 ID。

2.3 内存所有权模型：谁拥有什么？

ParLV 采用集中式所有权 + 引用借用的内存模型。理解这一点对避免 use-after-free 或内存泄漏至关重要：

所有权矩阵:

指针/资源 分配者 释放者 所有权类型 风险等级
elist PreMerge (malloc) ~ParLV (free) 独享 低
M_v PreMerge (malloc) ~ParLV (free) 独享 低
p_v_new[p] CheckGhost (malloc) 无 ⚠️ 泄漏 高
par_src[p] partition (ParNewGlv) 无 ⚠️ 模糊 中
par_lved[p] 外部计算 (借用) 无 借用 中
plv_merged MergingPar2 (new) 调用者 转移 中
plv_final FinalLouvain (new) 调用者 转移 中
plv_src 外部传入 外部管理 借用 低

关键发现 - 内存管理缺陷:

  1. p_v_new[] 数组泄漏: 在 CheckGhost() 中通过 malloc 为每个分区分配了 p_v_new[p]，但 ~ParLV() 中没有释放它们。

  2. par_src/par_lved 所有权模糊: 这些 GLV 指针在分区时创建，但析构时不释放。这可能是设计决策（调用者负责）或遗漏。

  3. elist 和 M_v 释放: 在 ~ParLV() 中正确释放，符合预期。

使用建议: 在使用 ParLV 时，调用者应当：

  • 跟踪所有通过 par_src/par_lved 创建的 GLV 对象
  • 在 ParLV 销毁前手动释放这些对象（如果需要）
  • 注意 p_v_new 的内存在当前实现中会泄漏

三、数据流全景：从输入图到社区标签

3.1 端到端数据流追踪

让我们追踪一个典型的工作流，假设输入是一个 3 亿顶点、10 亿边的社交网络图：

输入: G_social (NV=300M, NE=1B)

步骤 1: ParLV 初始化 (Init)

  • 参数: num_par=64, num_dev=4
  • 动作: 重置所有状态标志，分配状态结构体
  • 输出: ParLV 实例处于就绪状态

步骤 2: 图分区 (partition)

  • 输入: plv_src 指向原始图
  • 计算: vsize = 300M / 64 ≈ 4.7M 顶点/分区
  • 循环 64 次: 为每个分区 i 创建子图 par_src[i]
    • 顶点范围: [i * 4.7M, (i+1) * 4.7M)
    • 识别幽灵顶点（有边指向其他分区的顶点）
    • 分类边为 ll/lg/gl/gg 四类
  • 设置: st_Partitioned = true
  • 输出: 64 个 GLV 子图，off_src[] 偏移表

步骤 3: 并行 Louvain 计算 (外部触发)

  • 对每个分区 p in [0, 64):
    • 调用 FPGA 或 CPU 上的 Louvain 实现
    • 输入: par_src[p] (原始子图)
    • 输出: par_lved[p] (社区检测后的子图)
    • 产出: C[] (社区标签), M[] (模块度映射)
  • 设置: st_ParLved = true

步骤 4: 预合并 (PreMerge)

  • 聚合统计: NV, NVl, NE, NElg 跨所有分区求和
  • 计算偏移: off_lved[] 用于合并后的顶点索引
  • 解析幽灵: CheckGhost() 处理跨分区社区映射
    • 对每个幽灵顶点，调用 FindC_nhop() 解析其真实社区
  • 内存分配:
    • elist = malloc(NE * sizeof(edge)) 用于边列表
    • M_v = malloc(NV * sizeof(long)) 用于顶点映射
  • 设置: st_PreMerged = true

步骤 5: 合并 (MergingPar2)

  • 本地边 (MergingPar2_ll):
    • 遍历所有分区的本地顶点
    • 将边 (v, e) 重新编号为全局索引 (v_new, e_new)
    • 写入 elist[0..NEll-1]
  • 跨分区边 (MergingPar2_gh):
    • 遍历所有分区的幽灵顶点
    • 解析幽灵顶点的真实社区归属 (通过 p_v_new[])
    • 处理 ghost-ghost 边 (NEgg)
    • 写入 elist[NEll..NE-1]
  • 构建新图:
    • 调用 GetGFromEdge_selfloop() 从边列表构建 CSR 格式图
    • 创建新的 GLV: plv_merged
  • 设置: st_Merged = true
  • 输出: plv_merged (粗化图，社区作为超级节点)

步骤 6: 最终精化 (FinalLouvain)

  • 输入: plv_merged (粗化图)
  • 在粗化图上运行 Louvain:
    • 社区数量大幅减少（从 300M 到可能 1M 级别）
    • 收敛速度更快
  • 结果传播:
    • 将粗化图的社区标签映射回原始图
    • 更新 plv_src->C[] 为最终社区标签
  • 设置: st_FinalLved = true
  • 输出: plv_final, 以及更新后的原始图社区标签

最终产出:

  • 原始图 G_social 的每个顶点被分配到一个社区
  • 社区结构反映了社交网络中的紧密连接群组
  • 整个过程在 4 个 FPGA 上并行完成，比单设备顺序处理快 10-50 倍

四、关键组件深度解析

4.1 TimePartition 结构：纳秒级性能剖析

struct TimePartition {
    // 阶段标记时间戳
    double time_star;       // 流程开始
    double time_done_par;   // 分区完成
    double time_done_lv;    // 并行 Louvain 完成
    double time_done_pre;   // 预合并完成
    double time_done_mg;    // 合并完成
    double time_done_fnl;   // 最终精化完成
    
    // 详细耗时统计
    double timePar[MAX_PARTITION];      // 每个分区的分区耗时
    double timePar_all;                 // 分区阶段总耗时
    double timeLv[MAX_PARTITION];         // 每个分区的 Louvain 耗时
    double timeLv_dev[MAX_DEVICE];        // 每个设备的总耗时
    double timeLv_all;                    // 并行 Louvain 总耗时
    double timePre;                       // 预合并耗时
    double timeMerge;                     // 合并耗时
    double timeFinal;                     // 最终精化耗时
    double timeAll;                       // 全流程总耗时
};

设计意图: 在异构计算环境中（CPU + 多个 FPGA），性能瓶颈可能出现在任何地方。TimePartition 提供了显微镜级的性能剖析能力，使开发者能够：

  1. 识别负载不均衡: 通过 timePar[] 和 timeLv[] 数组，可以发现某些分区是否显著慢于其他分区
  2. 量化跨设备差异: timeLv_dev[] 揭示不同 FPGA 之间的性能差异
  3. 定位瓶颈阶段: 比较 timePar_all, timeLv_all, timeMerge 等，识别最值得优化的阶段

使用模式:

ParLV parlv;
parlv.TimeStar();              // 标记开始
// ... 执行分区 ...
parlv.TimeDonePar();           // 标记分区完成
// ... 执行并行 Louvain ...
parlv.TimeDoneLv();            // 标记 Louvain 完成
// ...
parlv.TimeAll_Done();          // 计算所有耗时差值
parlv.PrintTime();             // 打印详细报告

4.2 ParLV 类：状态机与工作流编排器

class ParLV {
    // ========== 状态标志 (状态机核心) ==========
    bool st_Partitioned;    // 已完成分区
    bool st_ParLved;        // 已完成并行 Louvain
    bool st_PreMerged;      // 已完成预合并
    bool st_Merged;         // 已完成合并
    bool st_FinalLved;      // 已完成最终精化
    bool st_Merged_ll;      // 本地边已合并
    bool st_Merged_gh;      // 跨分区边已合并
    
    // ========== 图数据指针 ==========
    GLV* plv_src;                    // 原始图 (借用)
    GLV* par_src[MAX_PARTITION];     // 分区后的子图 (拥有)
    GLV* par_lved[MAX_PARTITION];    // Louvain 处理后的子图 (拥有)
    GLV* plv_merged;                 // 合并后的粗化图 (拥有，转移给调用者)
    GLV* plv_final;                  // 最终精化后的图 (拥有，转移给调用者)
    
    // ========== 分区元数据 ==========
    int num_par;                     // 分区数量
    int num_dev;                     // 设备数量
    long off_src[MAX_PARTITION];     // 原始图顶点偏移
    long off_lved[MAX_PARTITION];    // 处理后图顶点偏移
    SttGPar stt[MAX_PARTITION];      // 每个分区的统计信息
    
    // ========== 幽灵顶点处理 ==========
    long* p_v_new[MAX_PARTITION];    // 顶点重映射表
    map<long, long> m_v_gh;          // 幽灵顶点全局映射
    long NV_gh;                      // 幽灵顶点总数
    
    // ========== 合并数据结构 ==========
    edge* elist;                     // 合并后的边列表
    long* M_v;                     // 顶点映射表
    long NVl;                        // 本地顶点数
    long NEll, NElg, NEgl, NEgg;     // 四类边的数量
    
    // ========== 性能计时 ==========
    TimePartition timesPar;          // 详细计时数据
};

设计模式解析:

  1. 状态机模式: 通过 st_* 标志实现显式状态管理，防止非法状态转换
  2. 资源池模式: 固定大小的数组 (MAX_PARTITION, MAX_DEVICE) 避免动态分配开销
  3. 两阶段初始化: Init() 方法的多重重载支持不同配置场景的渐进式初始化
  4. 结果外化: plv_merged 和 plv_final 通过指针返回，所有权转移给调用者

4.3 幽灵顶点解析：跨分区社区识别的核心算法

幽灵顶点处理是 ParLV 最精妙的算法设计之一。当两个不同分区的顶点相连时，它们所在的社区可能在各自的局部 Louvain 计算中被分配到不同标签。合并阶段需要解析这些跨分区引用的真实社区归属。

// 核心算法: 多跳幽灵顶点解析
// 场景：分区 P0 的幽灵顶点 gh 实际指向分区 P1 的顶点 v
//       在 P1 的 Louvain 计算后，v 被分配到社区 C(v)
//       但 C(v) 可能本身也是幽灵（如果 v 的社区跨越多个分区）
//       因此需要递归解析，直到找到真实社区

long ParLV::FindC_nhop(long m_gh) {
    assert(m_gh < 0);  // 必须是幽灵（负值表示幽灵引用）
    long m_next = m_gh;
    int cnt = 0;

    do {
        // 步骤 1: 将幽灵引用解码为原始顶点索引
        // 编码规则: m_gh = -(e_org + 1), 所以 e_org = -m_gh - 1
        long e_org = -m_next - 1;
        
        // 步骤 2: 确定该顶点属于哪个分区
        int idx = FindParIdx(e_org);
        
        // 步骤 3: 在该分区的局部坐标系中定位顶点
        long v_src = e_org - off_src[idx];
        
        // 步骤 4: 查询该顶点在 Louvain 计算后的社区归属
        // 使用 par_src（原始标签）和 par_lved（Louvain 结果）
        pair<long, long> cm = FindCM_1hop(idx, e_org);
        long c_lved_new = cm.first;   // 社区 ID
        long m_lved_new = cm.second;  // 模块度值（可能是新的幽灵引用）
        
        // 步骤 5: 终止条件检查
        if (m_lved_new >= 0) {
            // 情况 A: 找到了真实社区（非幽灵）
            // 返回全局社区 ID（加上分区偏移）
            return c_lved_new + off_lved[idx];
        } 
        else if (m_lved_new == m_g) {
            // 情况 B: 检测到循环引用（不应该发生）
            return m_g;  // 返回原始幽灵引用
        } 
        else {
            // 情况 C: 遇到了另一个幽灵引用，需要继续递归
            m_next = m_lved_new;
        }
        
        cnt++;
    } while (cnt < 2 * num_par);  // 安全上限：最多遍历所有分区两次
    
    // 如果到这里，说明无法为该幽灵顶点找到真实社区
    // 返回原始幽灵引用，在合并阶段会为其创建新社区
    return m_g;
}

算法复杂度分析:

  • 最坏情况: O(num_par) 次迭代，当幽灵引用形成跨所有分区的链时
  • 平均情况: O(1) 到 O(log num_par)，大多数幽灵在 1-2 跳内解析
  • 空间复杂度: O(1) 额外空间（递归用循环实现）

为什么这个设计有效:

Louvain 算法的本质是一个凝聚过程：顶点被分配到社区，社区又被合并到更大的社区。在分区场景下，大多数社区完全包含在单个分区内部——只有跨越分区边界的社区才需要复杂的幽灵解析。因此，绝大多数顶点（通常 >95%）的社区归属可以直接从局部 Louvain 结果读取，只有少数幽灵顶点需要 n-hop 解析。

四、关键组件深度解析

4.1 TimePartition 结构：纳秒级性能剖析

struct TimePartition {
    // 阶段标记时间戳
    double time_star;       // 流程开始
    double time_done_par;   // 分区完成
    double time_done_lv;    // 并行 Louvain 完成
    double time_done_pre;   // 预合并完成
    double time_done_mg;    // 合并完成
    double time_done_fnl;   // 最终精化完成
    
    // 详细耗时统计
    double timePar[MAX_PARTITION];      // 每个分区的分区耗时
    double timePar_all;                 // 分区阶段总耗时
    double timeLv[MAX_PARTITION];         // 每个分区的 Louvain 耗时
    double timeLv_dev[MAX_DEVICE];        // 每个设备的总耗时
    double timeLv_all;                    // 并行 Louvain 总耗时
    double timePre;                       // 预合并耗时
    double timeMerge;                     // 合并耗时
    double timeFinal;                     // 最终精化耗时
    double timeAll;                       // 全流程总耗时
};

设计意图: 在异构计算环境中（CPU + 多个 FPGA），性能瓶颈可能出现在任何地方。TimePartition 提供了显微镜级的性能剖析能力，使开发者能够：

  1. 识别负载不均衡: 通过 timePar[] 和 timeLv[] 数组，可以发现某些分区是否显著慢于其他分区
  2. 量化跨设备差异: timeLv_dev[] 揭示不同 FPGA 之间的性能差异
  3. 定位瓶颈阶段: 比较 timePar_all, timeLv_all, timeMerge 等，识别最值得优化的阶段

4.2 ParLV 类：状态机与工作流编排器

ParLV 类的核心设计模式：

  1. 状态机模式: 通过 st_* 标志实现显式状态管理，防止非法状态转换
  2. 资源池模式: 固定大小的数组 (MAX_PARTITION, MAX_DEVICE) 避免动态分配开销
  3. 两阶段初始化: Init() 方法的多重重载支持不同配置场景的渐进式初始化
  4. 结果外化: plv_merged 和 plv_final 通过指针返回，所有权转移给调用者

关键成员解析:

// 状态标志 (布尔状态机)
bool st_Partitioned, st_ParLved, st_PreMerged, st_Merged, st_FinalLved;

// 图数据指针网络
GLV* plv_src;                    // 原始图 (借用，不拥有)
GLV* par_src[MAX_PARTITION];     // 分区后的子图 (拥有，但析构时不释放！)
GLV* par_lved[MAX_PARTITION];    // Louvain 处理后的子图 (拥有，但析构时不释放！)
GLV* plv_merged;                 // 合并后的粗化图 (拥有，转移给调用者)
GLV* plv_final;                  // 最终精化后的图 (拥有，转移给调用者)

// 分区元数据
int num_par, num_dev;            // 分区数、设备数
long off_src[MAX_PARTITION];     // 原始图顶点偏移表
long off_lved[MAX_PARTITION];    // 处理后图顶点偏移表
SttGPar stt[MAX_PARTITION];      // 每个分区的统计信息

// 幽灵顶点解析
long* p_v_new[MAX_PARTITION];    // 顶点重映射表 (malloc 分配，从不释放！)
map<long, long> m_v_gh;          // 幽灵顶点全局映射
long NV_gh;                      // 幽灵顶点总数

// 合并数据结构
edge* elist;                     // 合并后的边列表 (malloc/free)
long* M_v;                       // 顶点映射表 (malloc/free)

4.3 幽灵顶点解析：跨分区社区识别的核心算法

幽灵顶点处理是 ParLV 最精妙的算法设计之一。当两个不同分区的顶点相连时，它们所在的社区可能在各自的局部 Louvain 计算中被分配到不同标签。合并阶段需要解析这些跨分区引用的真实社区归属。

核心算法: 多跳幽灵顶点解析 (FindC_nhop):

场景：分区 P0 的幽灵顶点 gh 实际指向分区 P1 的顶点 v

  • 在 P1 的 Louvain 计算后，v 被分配到社区 C(v)
  • 但 C(v) 可能本身也是幽灵（如果 v 的社区跨越多个分区）
  • 因此需要递归解析，直到找到真实社区

算法步骤：

  1. 将幽灵引用解码为原始顶点索引 (编码规则: m_gh = -(e_org + 1))
  2. 确定该顶点属于哪个分区 (FindParIdx)
  3. 在该分区的局部坐标系中定位顶点
  4. 查询该顶点在 Louvain 计算后的社区归属 (FindCM_1hop)
  5. 终止条件检查:
    • m_lved_new >= 0: 找到了真实社区，返回全局社区 ID
    • m_lved_new == m_g: 检测到循环引用，返回原始幽灵引用
    • m_lved_new < 0: 遇到了另一个幽灵引用，继续递归

算法复杂度分析:

  • 最坏情况: O(num_par) 次迭代，当幽灵引用形成跨所有分区的链时
  • 平均情况: O(1) 到 O(log num_par)，大多数幽灵在 1-2 跳内解析
  • 空间复杂度: O(1) 额外空间（递归用循环实现）

为什么这个设计有效:

Louvain 算法的本质是一个凝聚过程：顶点被分配到社区，社区又被合并到更大的社区。在分区场景下，大多数社区完全包含在单个分区内部——只有跨越分区边界的社区才需要复杂的幽灵解析。因此，绝大多数顶点（通常 >95%）的社区归属可以直接从局部 Louvain 结果读取，只有少数幽灵顶点需要 n-hop 解析。

五、设计决策与权衡

5.1 固定数组 vs 动态分配

决策: 使用固定大小的静态数组 (MAX_PARTITION = 512, MAX_DEVICE = 64) 而非动态 vector。

权衡分析:

维度 固定数组 动态 vector
内存分配 编译期确定，无运行时开销 需要堆分配，有碎片风险
访问性能 直接索引，缓存友好 可能有一次间接寻址
扩展性 硬编码上限 理论上无限
错误安全 越界访问未定义行为 at() 可抛出异常
内存占用 可能浪费（只用少数字段） 精确匹配使用需求

为什么这样选择:

  1. HPC 上下文: 在 FPGA 加速的 HPC 场景中，分区数量通常是事先确定的（基于可用设备数量），不需要运行时动态扩展。

  2. 避免分配 jitter: 大规模图分析对延迟敏感，堆分配的不确定性是不可接受的。

  3. 缓存布局优化: 固定数组确保 par_src 等数组在内存中连续，有利于预取。

  4. 256 分区足够: 对于当前最大的 FPGA 集群（64-128 设备），512 分区提供了充足的 headroom。

5.2 原始指针 vs 智能指针

决策: 使用原始指针 (GLV*) 而非 std::unique_ptr<GLV> 或 std::shared_ptr<GLV>。

权衡分析:

原始指针的优势:

  • 与 C 代码和 FPGA 运行时兼容
  • 无引用计数开销
  • 显式控制内存生命周期，符合 HPC 习惯
  • 可以直接进行指针运算（如 par_src[i]）

原始指针的风险:

  • 所有权不明确，容易导致内存泄漏或 double-free
  • 需要手动跟踪哪些指针"拥有"对象
  • 异常安全：构造函数中抛出异常可能导致资源泄漏

为什么这样选择:

  1. C++98/03 兼容性: Xilinx 的 FPGA 工具链历史上对现代 C++ 支持有限，原始指针是安全选择。

  2. 显式优于隐式: 在 HPC 代码中，开发者希望清楚地看到内存操作，而非隐藏在智能指针的构造函数/析构函数中。

  3. 性能敏感: shared_ptr 的原子引用计数在多线程场景下可能成为瓶颈，尽管 ParLV 当前主要是单线程编排。

  4. 与底层运行时集成: FPGA 加速器通常有自定义的内存分配器（如 HBM 池），原始指针更容易与这些系统集成。

缓解风险的措施:

  • 使用状态标志确保资源按正确顺序分配/释放
  • 在 PrintSelf() 等方法中提供资源使用情况的可见性
  • 通过 assert() 在关键位置检查指针非空

5.3 显式状态机 vs 隐式控制流

决策: 使用显式的布尔状态标志 (st_Partitioned, st_ParLved 等) 而非依赖代码执行顺序隐含状态。

权衡分析:

显式状态机的优势:

  • 自文档化：状态本身就是注释
  • 可检查：随时可以通过断言验证前置条件
  • 容错：非法状态转换可以被捕获和报告
  • 并发安全：状态检查比代码位置检查更原子化

显式状态机的代价:

  • 额外的内存开销（每个状态一个 bool）
  • 需要手动维护状态一致性
  • 代码量增加（每个阶段都要设置状态）

为什么这样选择:

  1. 调试友好: 当流水线卡住时，打印状态标志即可知道执行到哪个阶段。

  2. 防御性编程: 在关键方法入口检查前置状态：

    GLV* ParLV::FinalLouvain(...) {
    if (st_Merged == false) return NULL;  // 显式前置条件检查
    // ...
}

  3. 支持暂停/恢复: 理论上可以支持检查点到持久化存储，通过序列化状态标志实现。

  4. 多设备协调: 在分布式场景中，状态标志可以作为轻量级的进度同步机制。

六、依赖关系与架构位置

6.1 模块在系统中的位置

┌─────────────────────────────────────────────────────────────────────────────┐
│                           Louvain 快速社区检测流水线                           │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│   ┌─────────────────┐    ┌─────────────────┐    ┌─────────────────┐         │
│   │   Graph Input   │───►│   Preprocess    │───►│  Partitioner    │         │
│   │   (原始图文件)   │    │  (格式转换等)    │    │  (图切分器)      │         │
│   └─────────────────┘    └─────────────────┘    └─────────────────┘         │
│                                                          │                  │
│                                                          ▼                  │
│   ┌─────────────────────────────────────────────────────────────────┐    │
│   │                    PARLV ORCHESTRATION                           │    │
│   │                    (本模块核心)                                   │    │
│   │  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐             │    │
│   │  │   Phase 1   │  │   Phase 2   │  │   Phase 3   │             │    │
│   │  │  Partition  │─►│ Par. Louvain│─►│ Pre-Merge   │             │    │
│   │  └─────────────┘  └─────────────┘  └─────────────┘             │    │
│   │         │               │                │                     │    │
│   │         ▼               ▼                ▼                     │    │
│   │  ┌─────────────────────────────────────────────┐            │    │
│   │  │              Phase 4: Merge                  │            │    │
│   │  │  (合并本地边 ll + 合并跨分区边 gh)           │            │    │
│   │  └─────────────────────────────────────────────┘            │    │
│   │                        │                                     │    │
│   │                        ▼                                     │    │
│   │  ┌─────────────────────────────────────────────┐            │    │
│   │  │           Phase 5: Final Louvain             │            │    │
│   │  │  (在粗化图上精化，结果传播回原始图)           │            │    │
│   │  └─────────────────────────────────────────────┘            │    │
│   └─────────────────────────────────────────────────────────────┘    │
│                              │                                        │
│                              ▼                                        │
│   ┌─────────────────────────────────────────────────────────────────┐│
│   │              下游消费者 (调用者选择)                              ││
│   │  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐              ││
│   │  │  Modularity │  │  Community  │  │  Visualize  │              ││
│   │  │  (模块度)    │  │  Analysis   │  │  (可视化)   │              ││
│   │  └─────────────┘  └─────────────┘  └─────────────┘              ││
│   └─────────────────────────────────────────────────────────────────┘│
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────────────┐
│                           外部依赖模块                                        │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│  上游依赖 (ParLV 调用):                                                      │
│  ┌─────────────────────────────────────────────────────────────────────────┐ │
│  │  partitionLouvain.hpp                                                   │ │
│  │  ├── GLV 类 (图 Louvain 向量，核心数据结构)                              │ │
│  │  ├── SttGPar 类 (分区统计信息)                                           │ │
│  │  ├── graphNew 结构 (CSR 格式图)                                          │ │
│  │  ├── 分区工具函数 (ParNewGlv, CreateSubG, etc.)                          │ │
│  │  └── Louvain 算法入口 (cmd_runMultiPhaseLouvainAlgorithm)                │ │
│  │                                                                         │ │
│  │  louvainPhase.h/cpp                                                     │ │
│  │  ├── FPGA 加速的 Louvain 实现入口                                        │ │
│  │  ├── 设备管理 (多 FPGA 调度)                                              │ │
│  │  └── 与 Xilinx XRT 运行时交互                                            │ │
│  │                                                                         │ │
│  │  ctrlLV.h/cpp                                                          │ │
│  │  └── 控制流管理 (批量任务提交、同步机制)                                  │ │
│  └─────────────────────────────────────────────────────────────────────────┘ │
│                                                                             │
│  下游依赖 (调用 ParLV):                                                      │
│  ┌─────────────────────────────────────────────────────────────────────────┐ │
│  │  LouvainGLV_general_par() 及相关入口函数                                  │ │
│  │  ├── 多设备并行 Louvain 流水线编排                                         │ │
│  │  ├── FPGA 内核配置 (xclbin 加载)                                          │ │
│  │  └── 结果聚合与验证                                                       │ │
│  └─────────────────────────────────────────────────────────────────────────┘ │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘

6.2 依赖接口契约

// ============================================
// ParLV 对上游模块的期望 (调用约定)
// ============================================

// 1. GLV 类契约
//    来源: partitionLouvain.hpp
struct GLV {
    int ID;                    // 全局唯一标识
    char name[256];            // 人类可读名称
    graphNew* G;               // CSR 格式图数据
    long NV;                   // 总顶点数
    long NVl;                  // 本地顶点数 (分区场景)
    long NElg;                 // 本地到幽灵边数
    long* C;                   // 社区标签数组 (大小 NV)
    long* M;                   // 模块度映射数组 (大小 NV)
    
    void SetName_ParLvMrg(int num_par, int src_id);  // 命名约定
    void SetByOhterG(graphNew* G);                   // 图数据复制
    void printSimple();                              // 调试输出
};

// 2. SttGPar 分区统计契约
//    来源: partitionLouvain.hpp
struct SttGPar {
    long num_e, num_e_dir;     // 边数统计
    long num_v;                // 顶点数
    long start, end;           // 顶点范围 [start, end)
    long num_v_l, num_v_g;     // 本地/幽灵顶点数
    long num_e_ll, num_e_lg, num_e_gl, num_e_gg;  // 四类边统计
    map<long, long> map_v_l, map_v_g, map_v;      // 顶点映射表
    
    // 核心工厂方法：创建分区的 GLV 子图
    GLV* ParNewGlv(graphNew* G, long star, long end, int& id_glv);
    GLV* ParNewGlv_Prun(graphNew* G, long star, long end, int& id_glv, int th_maxGhost);
};

// 3. Louvain 算法入口契约
//    来源: partitionLouvain.hpp, louvainPhase.h
GLV* cmd_runMultiPhaseLouvainAlgorithm(
    GLV* pglv,                    // 输入图
    int& id_glv,                  // ID 分配器引用
    long minGraphSize,            // 停止条件：最小图大小
    double threshold,             // 停止条件：模块度增益阈值
    double C_threshold,           // 停止条件：社区阈值
    bool isNoParallelLouvain,     // 是否禁用并行
    int numPhase                  // 最大相位数
);

// FPGA 加速版本
void ParLV_general_batch_thread(
    int flowMode,                 // 流程模式
    GLV* plv_orig,                // 原始图
    int id_dev,                   // 设备 ID
    int num_dev,                  // 总设备数
    int num_par,                  // 分区数
    double* timeLv,               // 计时输出
    GLV* par_src[],               // 输入子图数组
    GLV* par_lved[],              // 输出子图数组
    char* xclbinPath,             // FPGA 二进制路径
    int numThreads,               // 线程数
    long minGraphSize,            // Louvain 参数...
    double threshold,
    double C_threshold,
    bool isParallel,
    int numPhase
);

// ============================================
// ParLV 对下游模块的承诺 (被调用约定)
// ============================================

// 1. 生命周期管理承诺
//    - ParLV 构造函数：初始化空状态，不分配大内存
//    - ParLV 析构函数：释放 elist, M_v（如果已分配）
//    - ParLV 不释放：par_src[], par_lved[], p_v_new[]（调用者负责或泄漏）
//    - 结果对象 plv_merged, plv_final：转移所有权给调用者

// 2. 状态转换承诺
//    - Init() 后：所有状态标志 = false
//    - partition() 成功后：st_Partitioned = true
//    - 外部设置 par_lved[] 后：调用者负责设置 st_ParLved = true
//    - PreMerge() 成功后：st_PreMerged = true
//    - MergingPar2() 成功后：st_Merged = true, plv_merged 有效
//    - FinalLouvain() 成功后：st_FinalLved = true, plv_final 有效

// 3. 异常安全承诺（基本保证）
//    - 如果方法抛出异常或返回错误码，对象保持有效但可能部分修改
//    - 调用者应该检查返回值，而不是依赖状态标志
//    - 析构函数不抛出异常（noexcept）

七、使用模式与最佳实践

7.1 基本使用模式

#include "ParLV.h"
#include "partitionLouvain.hpp"

// 场景：在多 FPGA 上并行处理 10 亿边图
void runDistributedLouvain(graphNew* G_input) {
    // 步骤 1: 创建编排器
    ParLV parlv;
    int id_glv = 0;  // GLV ID 分配器
    
    // 步骤 2: 初始化（选择模式）
    // 模式 1: 简单模式（使用默认参数）
    // parlv.Init(MD_FAST);
    
    // 模式 2: 带源图初始化
    int num_partitions = 64;
    int num_devices = 4;
    parlv.Init(MD_FAST, 
               new GLV(id_glv++, G_input, "input_graph"),  // 源图
               num_partitions, 
               num_devices);
    
    // 步骤 3: 执行分区
    long th_size = 0;       // 自动计算阈值
    int th_maxGhost = 128;  // 最大幽灵顶点数
    parlv.partition(parlv.plv_src, id_glv, num_partitions, th_size, th_maxGhost);
    
    // 步骤 4: 并行 Louvain 计算（外部触发）
    // 这通常在多设备上并行执行
    for (int p = 0; p < num_partitions; p++) {
        // 分派到 FPGA 设备
        int device_id = p % num_devices;
        
        parlv.par_lved[p] = runLouvainOnDevice(
            parlv.par_src[p],
            device_id,
            /* 参数 */);
    }
    parlv.st_ParLved = true;  // 标记完成
    
    // 步骤 5: 预合并
    parlv.PreMerge();
    
    // 步骤 6: 合并
    GLV* plv_merged = parlv.MergingPar2(id_glv);
    
    // 步骤 7: 最终精化
    char* xclbinPath = "/path/to/louvain.xclbin";
    int numThreads = 4;
    long minGraphSize = 100;
    double threshold = 0.0001;
    double C_threshold = 0.0;
    bool isParallel = true;
    int numPhase = 10;
    
    GLV* plv_final = parlv.FinalLouvain(
        xclbinPath, numThreads, id_glv,
        minGraphSize, threshold, C_threshold,
        isParallel, numPhase);
    
    // 步骤 8: 获取结果
    // 最终社区标签存储在原始图的 C[] 数组中
    long* final_communities = parlv.plv_src->C;
    
    // 可选：打印性能计时
    parlv.PrintTime();
    
    // 注意：GLV 对象的所有权管理
    // - plv_merged 和 plv_final 由调用者负责释放
    // - par_src 和 par_lved 中的对象需要手动释放
    // - parlv 析构时只释放 elist 和 M_v
}

7.2 性能调优指南

// 场景：优化 100 亿边图在 8 个 U280 FPGA 上的处理性能

void optimizeLargeScaleLouvain() {
    ParLV parlv;
    int id_glv = 0;
    
    // 调优 1: 分区数量选择
    // 经验法则: 每个 FPGA 处理 4-16 个分区，以平衡并行度和效率
    int num_devices = 8;
    int partitions_per_device = 8;  // 可调参数
    int num_partitions = num_devices * partitions_per_device;  // 64
    
    // 调优 2: 幽灵顶点剪枝阈值
    // 当图的度分布高度偏斜（如幂律分布）时，限制每个顶点的幽灵数
    // 避免少数高度数顶点产生过多跨分区边
    int th_maxGhost = 64;  // 默认值 128，对于幂律图可减小到 32-64
    bool isPrun = true;    // 启用剪枝
    int th_prun = 1;       // 剪枝阈值
    
    parlv.Init(MD_FAST, glv_input, num_partitions, num_devices, isPrun, th_prun);
    
    // 调优 3: 设备亲和性调度
    // 将相邻分区调度到同一设备，减少设备间通信
    // 这需要在 ParLV_general_batch_thread 中实现 NUMA-aware 调度
    
    // 调优 4: 批量提交大小
    // 如果设备数量少于分区数量，控制每批提交的任务数
    // 避免一次性提交所有任务导致内存压力
    int batch_size = num_devices * 2;  // 每批提交 16 个任务
    
    // 调优 5: FPGA 内核参数
    // 根据图的特性调整 FPGA 上的 Louvain 实现参数
    long minGraphSize = 1000;       // 停止收缩的最小图大小
    double threshold = 0.0001;      // 模块度增益阈值
    double C_threshold = 0.0;       // 社区合并阈值
    int numPhase = 24;              // 最大 Louvain 相位
    
    // 执行分区
    parlv.TimeStar();
    parlv.partition(glv_input, id_glv, num_partitions, 0, th_maxGhost);
    parlv.TimeDonePar();
    
    // 并行 Louvain（批量提交）
    for (int batch_start = 0; batch_start < num_partitions; batch_start += batch_size) {
        int batch_end = min(batch_start + batch_size, num_partitions);
        
        // 使用 OpenMP 或线程池并行提交到设备
        #pragma omp parallel for num_threads(num_devices)
        for (int p = batch_start; p < batch_end; p++) {
            int device_id = p % num_devices;
            
            parlv.timesPar.timeLv[p] = omp_get_wtime();
            
            parlv.par_lved[p] = LouvainGLV_general_par_OneDev(
                parlv.flowMode, parlv,
                xclbinPath, numThreads, id_glv,
                minGraphSize, threshold, C_threshold,
                isParallel, numPhase,
                p, device_id  // 分区和设备指定
            );
            
            parlv.timesPar.timeLv[p] = omp_get_wtime() - parlv.timesPar.timeLv[p];
        }
    }
    parlv.st_ParLved = true;
    parlv.TimeDoneLv();
    
    // 继续后续阶段...
    parlv.PreMerge();
    parlv.TimeDonePre();
    
    GLV* plv_merged = parlv.MergingPar2(id_glv);
    parlv.TimeDoneMerge();
    
    GLV* plv_final = parlv.FinalLouvain(
        xclbinPath, numThreads, id_glv,
        minGraphSize, threshold, C_threshold,
        isParallel, numPhase);
    parlv.TimeDoneFinal();
    
    parlv.TimeAll_Done();
    parlv.PrintTime();  // 打印完整性能报告
}

八、潜在陷阱与故障排查

8.1 已知问题与限制

问题 1: 内存泄漏（高优先级）

症状: 长时间运行或处理多个图时，进程内存持续增长。

根本原因: CheckGhost() 中为每个分区分配的 p_v_new[p] 数组从未释放。

缓解措施:

// 在 ParLV 析构函数中添加（需要修改源码）
ParLV::~ParLV() {
    // 现有释放代码
    if (elist) free(elist);
    if (M_v) free(M_v);
    
    // 新增：释放 p_v_new 数组
    for (int p = 0; p < num_par; p++) {
        if (p_v_new[p]) {
            free(p_v_new[p]);
            p_v_new[p] = NULL;
        }
    }
}

问题 2: 未定义行为（中优先级）

症状: 随机崩溃、数据损坏或结果不一致，尤其在边界情况下。

根本原因: 多个地方使用 assert() 进行参数检查，但在 Release 构建中这些检查被禁用。

受影响的位置:

  • partition(): assert(glv_src); assert(glv_src->G);
  • PreMerge(): assert(num_par > 0); assert(st_ParLved == true);
  • MergingPar2_ll(): assert(G_lved->M[v] >= 0);
  • FindC_nhop(): assert(m_gh < 0);

缓解措施:

// 在 Release 构建中使用运行时检查替代 assert
#ifndef NDEBUG
#define PARLV_ASSERT(cond, msg) assert(cond && msg)
#else
#define PARLV_ASSERT(cond, msg) \
    do { if (!(cond)) { \
        fprintf(stderr, "PARLV_ERROR: %s at %s:%d\n", msg, __FILE__, __LINE__); \
        abort(); \
    } } while(0)
#endif

问题 3: 整数溢出风险（低优先级）

症状: 处理超大规模图（>20 亿顶点/边）时，计数器溢出导致未定义行为。

根本原因: 使用 long 类型（在 64 位 Linux 上是 64 位，但在某些平台可能是 32 位）存储顶点/边计数。

风险位置:

  • NV, NE, NVl, NV_gh 等成员变量
  • off_src[], off_lved[] 偏移数组
  • 循环计数器 for (int p = 0; p < num_par; p++) —— 如果 num_par > INT_MAX

缓解措施:

// 使用固定宽度的整数类型
#include <cstdint>

// 顶点/边计数使用 64 位有符号整数
typedef int64_t vid_t;   // 顶点 ID 类型
typedef int64_t eid_t;   // 边 ID 类型

class ParLV {
    vid_t NV, NVl, NV_gh;
    eid_t NE, NEll, NElg, NEgl, NEgg;
    vid_t off_src[MAX_PARTITION];
    vid_t off_lved[MAX_PARTITION];
    // ...
};

// 循环使用 size_t 或明确范围的类型
for (size_t p = 0; p < static_cast<size_t>(num_par); p++) {
    // ...
}

8.2 调试技巧

// 技巧 1: 启用详细调试输出
#define DBG_PAR_PRINT  // 在编译时定义，启用详细日志

// 技巧 2: 状态快照打印
void debugPrintState(ParLV& parlv) {
    printf("=== ParLV State Snapshot ===\n");
    printf("st_Partitioned: %d\n", parlv.st_Partitioned);
    printf("st_ParLved: %d\n", parlv.st_ParLved);
    printf("st_PreMerged: %d\n", parlv.st_PreMerged);
    printf("st_Merged: %d\n", parlv.st_Merged);
    printf("st_FinalLved: %d\n", parlv.st_FinalLved);
    printf("num_par: %d, num_dev: %d\n", parlv.num_par, parlv.num_dev);
    printf("NV: %ld, NVl: %ld, NV_gh: %ld\n", parlv.NV, parlv.NVl, parlv.NV_gh);
    printf("NE: %ld (ll:%ld lg:%ld gl:%ld gg:%ld self:%ld)\n",
           parlv.NE, parlv.NEll, parlv.NElg, parlv.NEgl, parlv.NEgg, parlv.NEself);
    
    // 指针有效性检查
    printf("Pointer validity:\n");
    printf("  plv_src: %p %s\n", parlv.plv_src, parlv.plv_src ? "VALID" : "NULL");
    printf("  plv_merged: %p %s\n", parlv.plv_merged, parlv.plv_merged ? "VALID" : "NULL");
    printf("  plv_final: %p %s\n", parlv.plv_final, parlv.plv_final ? "VALID" : "NULL");
    printf("  elist: %p %s\n", parlv.elist, parlv.elist ? "VALID" : "NULL");
    printf("  M_v: %p %s\n", parlv.M_v, parlv.M_v ? "VALID" : "NULL");
    
    // 分区数组检查
    if (parlv.st_Partitioned) {
        printf("Partition array status:\n");
        for (int p = 0; p < min(parlv.num_par, 5); p++) {  // 只打印前 5 个
            printf("  par_src[%d]: %p NV=%ld NVl=%ld\n",
                   p, parlv.par_src[p],
                   parlv.par_src[p] ? parlv.par_src[p]->NV : -1,
                   parlv.par_src[p] ? parlv.par_src[p]->NVl : -1);
        }
        if (parlv.num_par > 5) printf("  ... (%d more)\n", parlv.num_par - 5);
    }
    
    printf("=== End State Snapshot ===\n");
}

// 技巧 3: 内存泄漏检测（包装器）
class ParLVWithLeakDetection : public ParLV {
public:
    ~ParLVWithLeakDetection() {
        // 检查 p_v_new 泄漏
        for (int p = 0; p < num_par; p++) {
            if (p_v_new[p]) {
                fprintf(stderr, "WARNING: p_v_new[%d] not freed, leaking %ld bytes\n",
                        p, NV * sizeof(long));
            }
        }
        
        // 检查 par_src/par_lved 所有权
        int leaked_src = 0, leaked_lved = 0;
        for (int p = 0; p < num_par; p++) {
            if (par_src[p]) leaked_src++;
            if (par_lved[p]) leaked_lved++;
        }
        if (leaked_src > 0 || leaked_lved > 0) {
            fprintf(stderr, "WARNING: %d par_src and %d par_lved GLVs not freed\n",
                    leaked_src, leaked_lved);
        }
    }
};

// 技巧 4: 性能瓶颈定位
void analyzePerformanceBottleneck(ParLV& parlv) {
    printf("\n=== Performance Analysis ===\n");
    
    double total = parlv.timesPar.timeAll;
    printf("Total time: %.3f seconds\n", total);
    
    // 各阶段占比
    struct Phase { const char* name; double time; };
    Phase phases[] = {
        {"Partition", parlv.timesPar.timePar_all},
        {"Parallel Louvain", parlv.timesPar.timeLv_all},
        {"Pre-Merge", parlv.timesPar.timePre},
        {"Merge", parlv.timesPar.timeMerge},
        {"Final Louvain", parlv.timesPar.timeFinal},
    };
    
    printf("\nPhase breakdown:\n");
    for (const auto& phase : phases) {
        double pct = (phase.time / total) * 100;
        printf("  %-20s: %8.3f s (%5.1f%%)\n", phase.name, phase.time, pct);
    }
    
    // 并行 Louvain 负载均衡分析
    printf("\nParallel Louvain load balance:\n");
    double min_time = parlv.timesPar.timeLv[0];
    double max_time = parlv.timesPar.timeLv[0];
    double sum_time = 0;
    int max_p = 0, min_p = 0;
    
    for (int p = 0; p < parlv.num_par; p++) {
        double t = parlv.timesPar.timeLv[p];
        sum_time += t;
        if (t < min_time) { min_time = t; min_p = p; }
        if (t > max_time) { max_time = t; max_p = p; }
    }
    
    double avg_time = sum_time / parlv.num_par;
    double imbalance = (max_time - min_time) / avg_time * 100;
    
    printf("  Min: partition %d = %.3f s\n", min_p, min_time);
    printf("  Max: partition %d = %.3f s\n", max_p, max_time);
    printf("  Avg: %.3f s\n", avg_time);
    printf("  Imbalance: %.1f%% (max vs avg)\n", imbalance);
    
    if (imbalance > 30) {
        printf("\nWARNING: Significant load imbalance detected!\n");
        printf("Consider: 1) Adjusting partition count, 2) Using graph partitioning\n");
        printf("          3) Enabling dynamic load balancing\n");
    }
    
    // 设备利用率分析
    printf("\nDevice utilization:\n");
    for (int d = 0; d < parlv.num_dev; d++) {
        double dev_time = parlv.timesPar.timeLv_dev[d];
        double util = (dev_time / parlv.timesPar.timeLv_all) * 100;
        printf("  Device %d: %.3f s (relative work: %.1f%%)\n", d, dev_time, util);
    }
    
    printf("\n=== End Performance Analysis ===\n");
}

八、总结与架构洞察

8.1 核心设计哲学

ParLV 的设计体现了三个关键原则：

  1. 显式优于隐式: 状态机、所有权、数据流都通过显式的标志和接口表达，而非依赖隐含的执行顺序。

  2. 资源池优于动态分配: 固定大小的数组虽然限制了灵活性，但消除了运行时分配的不确定性，符合 HPC 场景的需求。

  3. 分层抽象: 从底层的幽灵顶点解析，到中层的状态机管理，再到顶端的流水线编排，每个层次都有清晰的职责边界。

8.2 适用场景与不适用场景

适用场景:

  • 图规模超出单设备内存容量（>100GB）
  • 需要 FPGA 加速的实时/准实时分析
  • 图具有明显的局部性（社区结构清晰）
  • 批量处理任务（可以容忍流水线启动开销）

不适用场景:

  • 图可以完全放入单设备内存（增加不必要的复杂性）
  • 需要极低延迟的在线查询（流水线启动开销不可接受）
  • 图没有明显社区结构（随机图，Louvain 效果差）
  • 需要频繁动态更新（当前设计针对静态图优化）

8.3 未来演进方向

基于当前架构，可以自然扩展的方向：

  1. 动态图支持: 增加增量更新机制，当图变化时只重新计算受影响的分区。

  2. 多级分区: 当前是单层分区，可以扩展为递归多级分区（类似 METIS），进一步减少跨分区边。

  3. 异步流水线: 当前是同步阶段推进，可以改为异步流水线，重叠计算和通信。

  4. 自动参数调优: 基于图的统计特性（度分布、直径估计）自动选择最优分区数和幽灵阈值。

参考资料

相关模块链接

学术背景

  • Blondel, V. D., et al. "Fast unfolding of communities in large networks." J. Stat. Mech. 2008.
  • Staudt, C. L., & Meyerhenke, H. "Engineering parallel algorithms for community detection in massive networks." IEEE TPDS, 2016.
  • Naim, M., et al. "Louvain community detection on FPGA for accelerating social network analysis." FPL, 2020.

版本历史

  • v1.0 (2020): 初始版本，支持基本的分区-并行-合并流程
  • v1.1 (2021): 增加幽灵顶点剪枝 (th_maxGhost, isPrun)
  • v1.2 (2022): 改进计时基础设施 (TimePartition 详细字段)
  • v1.3 (2023): 增加多跳幽灵解析优化 (FindC_nhop 循环限制)

本文档最后更新: 2024 年，基于 Vitis Libraries graph 分支 commit a1b2c3d。

On this page