Partition 模块技术手册

1. 模块总览与定位

Partition 模块是 EDIF_Part 项目中负责多片 FPGA 自动化逻辑分割的核心算法引擎。它接收一个以超图（Hypergraph）形式建模的电路网表，在满足资源容量、拓扑连通、固定分配等多种约束的条件下，将电路节点分配到不同的 FPGA 块上，使得跨片连线数（Cut Size）最小，同时兼顾时序质量。

模块源码结构

partition.h / .cpp          # 主入口与流程控制
defs.h                      # 核心数据结构定义（graph, fpga, PartitionParams 等）
coarsen.h / .cpp            # 多层粗化引擎（MultilevelCoarsener）
initial.h / .cpp            # 初始划分（Initial）
tools.h / .cpp              # 工具函数（并查集、约束校验等）
refine/
  RefinementFacade.h/.cpp   # 细化阶段门面类（Refinement）
  core/
    RefineTypes.h           # 细化基础类型（Gain, NetPartition, PartitionState）
    RefinementRunTypes.h    # 候选解管理（CandidateBuffers, LevelWorkset）
    RefinementContext.h     # 配置与会话上下文
  engine/
    GainEvaluator.h/.cpp    # 增益计算引擎
    MoveApplier.h/.cpp      # 移动执行与回滚
  bucket/
    MoveBucket.h            # 增益桶（PerPart / Global 两种）
    PerPartBucket.cpp       # 分区级增益桶实现
    GlobalBucket.cpp        # 全局增益桶实现
  pipeline/
    CandidatePoolService    # 并行候选解批处理
    CandidateSelector       # 最优解选择
    CandidateProjection     # 层间投影与拓扑重映射
    StrategyRunner          # 策略执行驱动
    StrategyPlanner         # 策略选择规划
    TimingMetricService     # 时序度量服务
    FPGARemapper            # FPGA 编号拓扑优化
  strategy/
    IRefineStrategy.h       # 策略抽象接口
    StrategyFactory         # 策略工厂
    FM / PM / DSFM / Greedy # 各细化策略实现

2. 快速上手（30 秒最小调用）

C++#include "partition/partition.h"
#include "partition/defs.h"
using namespace std;

// 1. 构造超图（详见第 4 节数据结构）
graph finest;
// ... 填充 nodes, nets, incident_nodes, incident_nets ...

// 2. 构造硬件平台（划分块数由 resources.size() 决定）
fpga fpgas;
// ... 填充 resources, topology, dist ...

// 3. 使用默认参数
PartitionParams para;
para.constraints.has_fix    = false;
para.constraints.has_timing = false;

// 4. 调用
vector<int> parts;                                    // 输出
HSFullTiming::HSPartitionFlow pFlow;                   // 不用时序时传空对象
int ret = partition(finest, fpgas, parts, para, 8, pFlow);

if (ret == 1) {
    // 划分成功: parts[i] = 节点 i 归属的 FPGA 编号
    for (int i = 0; i < (int)parts.size(); i++)
        printf("Node %d -> FPGA %d\n", i, parts[i]);
} else {
    // 划分失败（通常因资源总量超出容量）
    printf("Partition failed\n");
}

3. 算法框架：多级超图划分

Partition 模块的核心算法是多级超图划分（Multilevel Hypergraph Partitioning），这是一种经典的「分而治之」策略，将大规模组合优化问题分解为三个阶段：

三阶段职责

完整执行流程

4. 核心数据结构设计

4.1 超图模型：graph

graph 类是整个模块的核心负载，封装了超图的全部信息。它使用 CSR（Compressed Sparse Row）展平索引格式存储节点与超边的关联关系，以获得紧凑的内存布局和高效的遍历性能。

4.2 硬件平台：fpga

4.3 参数配置：PartitionParams

PartitionParams 采用分层结构体设计，将参数按阶段分组。所有子结构体均支持 JSON 序列化（通过 nlohmann/json 的 NLOHMANN_DEFINE_TYPE_NON_INTRUSIVE_WITH_DEFAULT 宏）。

4.4 评价指标：Metrics

5. 粗化阶段详解

粗化阶段由 MultilevelCoarsener 类实现，负责将原始大图逐层收缩为更小的抽象图。核心思想是：将紧密连通的节点对合并为超节点，从而在不损失重要结构信息的前提下指数级缩小问题规模。

5.1 粗化策略

5.2 粗化流程

5.3 关键数据结构

6. 初始划分阶段详解

初始划分由 Initial 类实现，在最粗层图上生成多个满足资源约束的候选解。这些解的多样性直接决定了最终优化的质量。

6.1 多策略生成

Initial::initialPartition() 会综合运用以下多种策略来生成初始解：

6.2 精英选择

生成 num_initial_solutions 个候选解后，按 cut 指标排序，仅保留前 num_best_initial_solutions 个精英解进入细化阶段。这既控制了细化阶段的计算量，又保证了进入细化的解具有较高的起点质量。

流程// Initial::initialPartition() 内部逻辑
for seed in [0, num_initial_solutions):
    switch (seed % num_strategies):
        case 0: randomPart()        // 随机
        case 1: greedyPart()        // 贪心
        case 2: progressiveMinCutPart()  // 最小割生长
        case 3: globalGrowPart()    // 全局生长
        case 4: sequentialGrowPart() // 顺序填充
        case 5: roundRobinGrowPart() // 轮询
        ...

// 按指标排序，保留精英
sort candidates by cut
retain top num_best_initial_solutions candidates

7. 细化阶段详解

细化阶段是整个划分流程中最核心的优化环节，负责将初始解逐层映射回原始图的过程中持续优化。细化采用 门面模式（Refinement Facade）设计，通过统一的 Refinement::refinement() 接口屏蔽内部复杂的策略调度细节。

7.1 整体架构

7.2 细化策略对比

7.3 策略组合机制

细化阶段支持 primary + suffix 策略组合。每次细化会先运行 primary 策略（如 PM），再运行 suffix 策略（如 Greedy），形成「先精细优化，再快速清扫」的效果。

7.4 增益计算与移动机制

7.5 增益桶 (MoveBucket)

增益桶是 FM 系列算法的核心数据结构，提供 O(log n) 的最大增益节点选取。模块提供两种实现：

7.6 细化流程：逐层展开

8. 约束体系

Partition 模块支持多种物理约束，贯穿粗化、初始划分、细化全流程。所有约束标志集中在 PartitionConstraintConfig 中。

// 通过名字兼容入口设置
fixed_assignment["cpu_core"] = {2, {}};
para.constraints.has_fix = true;

// 设置区域约束（通过名字前缀匹配）
fixInfo info;
info.fpgaNo = -2;  // -2 表示区域约束
info.id = {{0,0,0}, {0,0,1}};  // 候选块 0 和 1
fixed_assignment["mem_ctrl"] = info;
para.constraints.has_region = true;

// 设置组约束
group_assignment["group_a"] = {"node_1", "node_2", "node_3"};

para.constraints.has_timing = true;
// pFlow 由 sta 模块解析生成：
// sta::parse(pFlow, circuitFolder);
// sta::buildNextObjInfo(pFlow);

9. 时序驱动划分详解

时序驱动划分是 Partition 模块中最复杂的运行模式。与纯 cut 优化不同，时序模式需要在减少割边数的同时兼顾关键路径的时序质量（Worst Negative Slack, WNS）。当前实现的核心机制是通过 HSFullTiming::HSPartitionFlow（简称 pFlow）对象与 sta 模块交互，而非模块内嵌的时序评估器。

9.1 时序数据的来源与传递

pFlow 是由外部 sta 模块生成的时序分析上下文，内部为每个候选解维护一个独立的 LocalData 对象，负责：

• 割边延迟矩阵（setCutDelays）：记录每对 FPGA 间的割边延迟，由 TDM 延迟模型或固定常量计算
• 时序图构建（buildTimingEdge）：根据当前划分建立时序约束图
• 时序更新（updateTimingEdge）：在节点移动后刷新时序状态
• 指标查询：getMinSlack()（WNS）、getCriticalCut()（关键路径割边数）、getWorstIndex()（最大跳数）、getTopkMinSlackRatio()（Top-K slack 比值）

9.2 时序模式下的流程调整

当时序模式开启（has_timing = true）时，partition() 内部会做以下关键调整：

9.3 TimingMetricService 的工作机制

9.4 割边延迟矩阵

每对 FPGA 之间的割边延迟由 buildCutDelayMatrix() 计算：

• 有 IO 带宽配置（cutweights_assignment 非空）：使用 fpgas.tdmEstimate.getTdmCutDelay(i, j) 获取基于 TDM 复用率的延迟值
• 无 IO 配置：使用固定默认值 extra_delay_cut（默认 100.0 ns）

9.5 时序解的评估与选择

时序模式下，CandidateSelector::chooseBestCandidate() 的选择逻辑变为：

1. 优先选 worstSlack 最好（最大）的解 — 确保关键路径时序质量
2. 在 slack 相近的解中，选 cost（关键路径割边数）更小的
3. fewer_cuts 标志影响选择权重：当整体割边偏少时倾向选更小 cut

9.6 时序配置参数速查

10. 完整流程控制（COCP / V-Cycle）

10.1 主流程模式

10.2 COCP（Coarsening Optimization Candidate Processing）

COCP 是一种后处理优化机制：以当前最优候选解的分区信息作为社区提示（community hint），重新执行一轮粗化-细化，从而在已有解的基础上进行更深层次的结构优化。

10.3 V-Cycle 迭代优化

V-Cycle 是多级划分的经典增强技术：以当前最优解为起点，重复执行完整的「粗化 → 初始划分 → 细化」流程，每次都可能发现更优的解。

V-Cycle 伪代码for iter in [0, V_Cycle_run):
    community = candidate_parts[best]     // 以当前最优解为社区提示
    mc = MultilevelCoarsener(finest, ...)  // 新建粗化器
    mc.multilevelCoarsening(finest)        // 受引导粗化
    initial.initialPartition(mc, ...)      // 重新初始划分
    refinement.refinement(mc, ...)         // 细化
    candidate_parts[0] = best result      // 更新最优解

10.4 候选解选择 (CandidateSelector)

在多个候选解中，CandidateSelector::chooseBestCandidate() 综合以下指标选择最优解：

• 非 IO / 非时序模式：优先选 cut 最小的解
• IO 模式：考虑 cost（TopK slack 之和）和 topkratio
• 时序模式：在 cut 可接受的前提下，优先选 worstSlack 最好的解
• fewer_cuts 标志：当整体割边数偏少时，调整选择策略偏向更小 cut

11. 层次化（多层级）划分

前面章节描述的 partition() 是扁平划分：它把所有 FPGA 视作平级节点，目标是把超图切成 K 块。而真实的多片 FPGA 系统具有物理层级——机柜（Rack）→ 簇（Cluster）→ 板（Board）→ FPGA，命名形如 R*.C*.B*.F*，其下还可细分 Die。同板 FPGA 之间的互连带宽远大于跨板，资源也需按层级管控。层次化（多层级）划分就是为这种场景设计的递归外壳。

11.1 动机与定位

扁平 partition() 有两个局限：① 它无法表达「同板近、跨板远」的层级拓扑，只能用一个统一的最短跳数矩阵近似；② 它无法按物理层级分层控制资源上限。层次化划分通过把硬件建模成一棵递归树，逐层分割、逐层约束，最终让每个电路节点落到一个叶子 FPGA，并记录其层次路径。

11.2 层次数据结构

层次结构定义在 defs.h，核心是一个递归类 hierarchy：每个节点既描述本层资源与拓扑，又通过 contents 持有子节点，天然形成一棵与物理硬件同构的树。

11.3 算法思路：自顶向下分治

层次化划分的入口是 partitionHierarchyGraph()（partition.h）。它按 hierarchy_root 定义的树自顶向下递归：在每一层调用扁平 partition() 把当前子图切成若干份，再用 separateGraph() 按结果拆成子图，递归交给下一层，直到叶子 FPGA。

递归伪代码// partition.cpp ：partitionHierarchyNode（单节点递归）
int partitionHierarchyNode(graph &cur, const hierarchy &node, prefix, ...) {
    int part_num = node.contents.size();     // 本层要切成几份
    // 基线：只剩 1 份或已是叶子 → 把当前路径回填到 node_paths
    if (part_num == 1 || node.contents.empty()) {
        assignLeafPaths(cur, prefix, parts, node_paths);  // node_paths[i] = [rack,cluster,board,fpga]
        return 1;
    }
    // 递归：先扁平划分当前层，再切图，再对每个子节点递归
    partition(cur, node.fpgas, parts, para, thread, pFlow);   // 内层仍是完整多级划分
    separateGraph(cur, node.fpgas, parts, child_graphs, id2node);
    for (int c = 0; c < part_num; ++c)
        partitionHierarchyNode(child_graphs[c], node.contents[c], prefix + [c], ...);
}

separateGraph(finest, fpgas, parts, sub_graphs, id2node) 负责把划分结果落地：遍历所有节点与超边，按 parts 归入对应子图，并重建每个子图的 incident_nets 索引（id2node 记录子图节点到原图节点的映射，保证递归回溯时身份不丢）。最终每个 graph node 都获得一条层次路径，写入 node_paths[i]。

11.4 资源上限分层设置

层次化场景下，资源约束必须按层级分级设置：顶层不能直接占满所有叶子的物理容量，否则下层无平衡空间。本项目用「两层容量 + 自底向上 reset + 分布式 slack 衰减」三件套解决。

第一步：自底向上 reset（resetHierarchyResourcesFromLeaves，partEDIF.h）。先用 collectLeafResources() 把所有叶子 FPGA 的 fpgas0（物理容量）平铺成一维列表，交给 checkResources() 计算平衡后的目标值，再写回叶子并逐级聚合到上层 fpgas。checkResources() 的核心是找瓶颈资源维度并按比例设定目标：

checkResources 核心逻辑（partEDIF.cpp）// 1. 找需求/容量比最高的资源维度作为瓶颈
int index = 0;
double ratio = required[0] / (double)total[0];
for (int r = 1; r < R; ++r)
    if (required[r] / (double)total[r] > ratio) { index = r; ratio = required[r]/total[r]; }
// 2. 按瓶颈比率和用户设定推导目标 FPGA 数与每块资源上限
int target_fpga_num = max(1, (int)ceil(ratio * f.resources.size() * fpgaResourceRatioSet));
// fpgaResourceRatioSet == 0 表示自动估计

第二步：分布式 slack 衰减（aggregateHierarchyResourcesWithDistributedSlack，tools.h）。并非所有资源维度都需要分布式限制——只有总容量超过实际需求的维度才需要。流程为：getDistributedResourceDims() 识别这些维度 → computeHierarchySlacks() 计算每维 slack（slack = 总容量 / 需求上界，上限 kMaxHierarchyResourceSlack = 2.0）→ 自底向上聚合时对分布式维度施加渐进式 slack 衰减。

11.5 超边去重

网表中常存在大量平行超边——端点集合完全相同的多条 net（例如同一组宏之间的多比特信号被拆成多条线）。它们会让粗化阶段的匹配打分重复计算，也干扰后续时序/路由评估。粗化器提供 MultilevelCoarsener::deduplicateHyperedges(finest)（coarsen.h）在粗化前压缩这类冗余。

算法（coarsen.cpp）：① 为每条超边计算特征哈希（ContractedHyperedgeInformation.hash，含引脚数 size）；② 按 (hash, size) 分桶排序；③ 桶内用 check_if_hyperedges_are_parallel() 做精确结构比对（逐端点比较 incident_nodes，仅当哈希相同且端点序列完全一致才认定平行）；④ 合并平行超边——权重累加到保留边，重复边标记为 invalid 跳过。该步配合 parallelContraction()（TBB 并发收缩）使用。

超边去重小例// 两条 net 都连接节点 {0, 1, 2}，是平行超边
net A: incident = [0,1,2], weight = 1.0
net B: incident = [0,1,2], weight = 1.0
          ↓ deduplicateHyperedges
net A: incident = [0,1,2], weight = 2.0   // 合并，权重累加
net B: 标记为 invalid，跳过                // 图规模下降，打分不再重复

11.6 时序评价（跨 FPGA 拓扑感知）

层次化把硬件拍平后，跨 FPGA 通信的代价取决于 FPGA 对的物理距离。本项目的时序评价由 TimingMetricService（构建延迟矩阵）、HSTimingLocalData（分区级时序状态）和 HSTimingDelta（增量评估器）协同完成，最近的提交又加入了拓扑距离与去重图两项增强。

拓扑距离 vs 简单 hop。 简单 hop 只数跨越的 FPGA 跳数；拓扑距离则结合物理拓扑矩阵给出更贴合真实延迟的距离。时序引擎用拓扑距离为每条 timing edge 估延迟，使关键路径评估更准确。

去重图（net + FPGA pair 去重）。 同一条 net 在同一 FPGA pair 上可能被重复计入关键割线 slack。HSTimingLocalData / HSTimingDelta 维护按 net + FPGA pair 去重的最差 slack bucket 统计，避免重复计数导致评估偏置，让候选解排序更可靠。

增量时序评估。 HSTimingDelta 为一次候选分区变更维护独立的差分账本而不改写基准状态：用 traceInfo（hop / slack / preEdgeId / edgeId）记录单步传播轨迹，updateTimingEdge() 增量更新，并支持 rollbackUndo()。最终把 cut delays + fpga distances 下发到每个候选的 local data 后即可快速评价。

11.7 端到端编排

层次化的端到端入口是 partHierarchyOnly()（partEDIF.h），它串联起建模、图构建、资源校准、递归分割与可选输出：

flattenHierarchyToFpgasForRouting(hierarchy_root, flat_fpgas, flat_fpgas0, path_to_fpga, fallback_capacity, delay_lib_path) 是层次化与扁平世界的桥梁：它把所有叶子 FPGA 拍平成一组平级的 flat_fpgas（含拓扑、容量、TDM 互联），并建立层次路径到全局 FPGA ID 的映射 path_to_fpga，供时序与路由评估复用前面章节的扁平算法。

11.8 层次化 API / 产物速查

12. API 接口与调用方法

12.1 主入口（纯抽象版）

定义在 partition.h，直接操作图级别的约束：

C++int partition(
    graph &finest,                                  // [输入] 超图网表
    fpga &fpgas,                                    // [输入] 硬件平台
    vector<int> &parts,                             // [输出] 节点->FPGA 映射
    const PartitionParams &para,                     // [输入] 算法参数
    int thread,                                      // [输入] 线程数
    HSFullTiming::HSPartitionFlow &pFlow            // [输入] 时序上下文
);
// 返回值: 1 = 成功, -1 = 失败

12.2 兼容入口（名字级约束适配器）

提供了从名字级约束到图内节点 ID 的自动转换：

C++int partition(
    graph &finest,
    fpga &fpgas,
    vector<int> &parts,
    const PartitionParams &para,
    int thread,
    flat_hash_map<string, fixInfo> &fixed_assignment,        // 固定/区域约束
    unordered_map<string, vector<string>> &group_assignment,  // 组约束
    flat_hash_map<string, int> &name_map,                     // 名字->ID 映射
    HSFullTiming::HSPartitionFlow &pFlow
);

12.3 完整调用示例

示例 1：纯图分割（无约束）

C++#include "partition/partition.h"
using namespace std;

graph g;
// ... 填充 nodes, nets, incident_nodes, incident_nets ...

fpga fpgas;
// ... 填充 resources, topology, dist ...

PartitionParams para;
para.refine.num_best_initial_solutions = 10;

vector<int> parts;
HSFullTiming::HSPartitionFlow pFlow;
int ret = partition(g, fpgas, parts, para, 8, pFlow);

示例 2：有固定分配约束

C++flat_hash_map<string, fixInfo> fixed_assignment;
flat_hash_map<string, int> name_map;
unordered_map<string, vector<string>> group_assignment;

name_map["cpu_core_0"] = 42;
fixed_assignment["cpu_core_0"] = {2, {}};  // 固定到块 2

para.constraints.has_fix = true;

int ret = partition(g, fpgas, parts, para, 8,
                    fixed_assignment, group_assignment, name_map, pFlow);

示例 3：使用时序数据

C++HSFullTiming::HSPartitionFlow pFlow;
// pFlow 由 sta 模块解析生成（需外部调用 sta::parse / sta::buildNextObjInfo）

para.constraints.has_timing = true;
para.timing.timing_hold_solution_num = 4;

int ret = partition(g, fpgas, parts, para, 8, pFlow);

示例 4：验证划分结果

C++// 计算割边权重
int cut = fpgas.computeCutWeight(g, parts);
printf("Cut = %d\n", cut);

// 计算完整指标（含 TDM）
vector<vector<int>> cut_weights(fpgas.resources.size(),
    vector<int>(fpgas.resources.size(), 0));
Metrics m = fpgas.computeCutWeights(g, parts, cut_weights);
printf("Cut=%d TDM=%d Topo=%d Violation=%d MaxHop=%d\n",
       m.cut, m.tdm, m.topo, m.violation, m.maxHop);

13. 参数配置速查

13.1 常用参数

13.2 时序相关参数

14. 常见问题与调优

Q1: 资源向量维度必须一致吗？

是的。node.resources、fpga.resources[i]、fpga.upper_resources、fpga.lower_resources 的维度必须相同，代表同一组资源类型（如 LUT, FF, DSP, BRAM）。

Q2: 不需要时序优化时，pFlow 怎么传？

传一个默认构造的空 HSFullTiming::HSPartitionFlow 对象即可。确保 para.constraints.has_timing = false。

Q3: name_map 是必须的吗？

如果不需要固定分配约束（has_fix=false）和区域约束（has_region=false），name_map 可以为空。否则必须包含约束中引用的所有节点名到 ID 的映射。

Q4: topology 和 dist 需要手算吗？

topology 是邻接矩阵，需要你提供。dist 可以用 Floyd-Warshall 从 topology 推导。如果不需要拓扑约束，可以不填 topology 和 dist，并将 force_topo 和 has_io 设为 false。

Q5: 划分结果质量不满意怎么办？

Q6: 如何选择合适的粗化方法？

推荐使用默认的 HEM（coarsen_method=1）。它通过权重合并去重，显著降低了对输入顺序的敏感性。基础贪心（coarsen_method=0）仅在快速模式或特定测试中使用。

Q7: 时序模式和纯 cut 模式有什么区别？