---

VLSI-TopoPart: 基于拓扑与固定约束的多路超网表划分系统

本项目针对 VLSI 物理设计中的超网表划分（Hypergraph Partitioning） 问题，实现了一个高效、并行的多路划分求解器。本系统不仅支持经典的多路划分与不平衡度控制，还深度融合了 FPGA 拓扑约束（Topology Constraints，支持 MFS1 和 MFS2 拓扑） 以及 节点固定约束（Fixed Constraints）。

通过结合 Candidate Propagation（候选传播机制）、Iterated Local Search (ILS) 以及 多线程并行优化，在保证 100% 满足拓扑和物理约束的前提下，极大地降低了网表切割代价（Cut Cost）。

---

📌 项目核心亮点与功能

1. 多路划分 (Multi-way Partitioning)
   • 支持将网表划分为任意 $k$ 路（对应拓扑图的节点数）。
   • 引入平衡参数 $r \in [0, 1/n]$，严格保证各分区元件数量的平衡性，且支持非整除情况下的动态对齐，确保程序在高负载或极端参数（如 $r \times n = 1$）下稳定运行。
2. 拓扑约束求解 (Topological Constraints)
   • 内置针对 FPGA 拓扑图（如 MFS1, MFS2）的合法性检查器。
   • 实现 Candidate Propagator（候选路径传播算法），在划分初始化与移动（Refinement）阶段，通过前向/后向约束传播，从源头上消除了拓扑冲突（Topology Violations）。
3. 固定约束解析 (Fixed Constraints)
   • 解析并严格执行网表底部的固定节点信息（如将指定 Cell 固定在特定的拓扑 Node 上）。
   • 支持 MFS1 自动裁切（忽略末尾 35 行固定信息）及 MFS2 完整固定约束。
4. 多线程并行加速与时限控制
   • 采用多线程并行框架进行状态搜索与 FM 细化（Refinement）。
   • 引入基于时间预算的控制机制（TOPO_BUDGET_MS），在规定时间内最大化迭代质量。
5. 算法稳定性与 100% 复现性
   • 严格固定随机数种子，在相同配置与线程数下，算法运行结果 100% 稳定可复现。

---

📂 源码目录结构

├── CMakeLists.txt              # CMake 构建配置文件
├── Makefile                    # 基于 Make 的编译配置文件
├── main.cpp                    # 程序主入口，处理命令行参数与流程控制
├── Types.hpp                   # 全局类型定义（如 PartId, Netlist 等）
├── TopologyGraph.h/.cpp        # 拓扑图解析与约束管理（MFS1/MFS2 拓扑）
├── Netlist.h/.cpp              # 超网表及固定约束解析器
├── Node.h/.cpp & Net.h/.cpp    # 网表基础元件与超边的数据结构
├── CandidatePropagator.hpp     # 核心：拓扑可行路径计算与状态传播器
├── Partitioner.h/.cpp          # 划分核心算法（初始划分、FM 优化、ILS）
├── solution.h/.cpp             # 划分方案表示与合法性验证机制
├── run_all.sh                  # 自动化评测与复现脚本
└── benchmark/                  # 测试数据集存放目录（ICCAD2021-TopoPart-Benchmarks）

---

🛠️ 环境准备与编译

1. 开发环境

• 操作系统: Linux / WSL (Ubuntu 22.04)
• 编译器: 支持 C++17 或更高标准的 g++
• 构建工具: CMake (>= 3.15) 或 Make

2. 编译步骤

在项目根目录下打开终端，运行以下命令进行编译：

# 使用 CMake 进行多线程编译
cmake -B build
cmake --build build -j$(nproc)

编译成功后，将在 build/ 目录下生成可执行程序。

---

🚀 实验结果复现指南

我们提供了完整的复现流程，你可以通过脚本一键运行，或通过手动传参进行精细调试。

1. 自动化一键测试 (推荐)

直接运行根目录下的自动化脚本：

bash run_all.sh

该脚本会自动读取 benchmark 目录下的测试集，并依次运行不同的拓扑和平衡度配置。

2. 手动单步验证

你可以通过命令行环境变量和参数控制程序的执行。

测试用例 1: MFS1 拓扑 0 容忍平衡度 (Feasible 验证)

# 开启 Debug 输出，运行 MFS1 拓扑，无不平衡容忍度
TOPO_DEBUG=1 ./build/partitioner --netlist ./benchmark/case1 --topo ./benchmark/MFS1 --threads 8

测试用例 2: MFS1 拓扑 0.005 不平衡度

TOPO_DEBUG=1 ./build/partitioner --netlist ./benchmark/case1 --topo ./benchmark/MFS1 --balance 0.005 --threads 8

测试用例 3: MFS2 拓扑 0.01 不平衡度（15秒时间预算）

对于规模较大的 MFS2 拓扑，使用 8 线程并行，并设置 15000 毫秒的时间预算限制：

TOPO_DEBUG=1 TOPO_BUDGET_MS=15000 ./build/partitioner --netlist ./benchmark/case1 --topo ./benchmark/MFS2 --balance 0.01 --threads 8

---

📊 算法实现技术细节说明（大作业论文参考点）

1. 拓扑约束传播算法 (Candidate Propagation)

由于存在严格的拓扑依赖（例如某些元件只能放入能与相邻节点通信的区域），传统的随机初始化或盲目 FM 移动会导致大量的“非可行解”（Infeasible）。 我们在 CandidatePropagator.hpp 中实现了前向兼容性剪枝：

• 在分配 Cell 时，pair_compatible 会动态评估物理节点之间的连通性。
• initialize_and_propagate 算法利用广度优先搜索（BFS）队列将确定性约束进行链式传播，防止局部决策导致全局拓扑死锁。

2. 多路 FM 细化与 ILS (Iterated Local Search)

• 初始划分: 基于 balance_fill 策略优先满足固定约束和拓扑约束，生成一个初始合法的 Feasible 状态。
• 细化（Refinement）: 扩展了传统的二路 FM 算法至多路。在移动 Cell 时，不仅计算 Cut Cost 的 Gain，还会通过 CandidatePropagator 实时否决任何违背拓扑约束的移动。
• ILS 扰动: 引入带有 Budget 控制的抖动（Kick）机制，打破局部最优，在时限（TOPO_BUDGET_MS）内反复迭代逼近最优 Cut。

3. 多线程加速设计

• 采用 并行状态探索 (Parallel State Exploration)：每个线程分配独立的随机种子，并行尝试不同的初始划分与局部搜索路径。
• 在规定时间内，各线程定时上报当前找到的最优 Feasible State，最后汇总并输出全局最优的划分结果，实现近乎线性的多核加速比，同时维持了算法的完全确定性（Deterministic）。