Class MultilevelCoarsener

Class Documentation

class MultilevelCoarsener

多层次超图匹配收缩器（Coarsener）。

【职责链】：

  • 1.接收当前处于精细态（Finest）的原始超图。

  • 2.计算节点间的匹配聚合分数（如 Heavy-Edge 或时序收缩等机制）。

  • 3.逐层将匹配的节点合并为聚类（Cluster）。

  • 4.将所有层级的图栈（graphs）和映射表（maps）保存，供后续 V-Cycle 使用。

Public Functions

int buildGroupedGraph(const graph &finest, int group_count, const vector<int> &group_map, graph &grouped)

使用 group_map 将输入图预先收缩成一个抽象图。

void deduplicateHyperedges(graph &finest)

使用恒等节点映射合并输入图中的平行超边。

将端点集合完全相同的并行超边合并为一条并累加权重，在粗化前压缩图规模、 避免重复超边干扰匹配打分。配合 parallelContraction() 在并发收缩时使用。

Parameters:

finest – [inout] 输入超图，函数会就地修改其 nets 与 incident 结构。

void setCoarsenOrder(int s)

设置粗化遍历策略（随机、按面积、或按时序关键度排序）。

void setMultilevelId(int id)

分配当前调用执行的识别流水标记牌号用以标别和种子隔离。

int getMultilevelId() const

查询该套粗化构架目前跑在第几流水代上。

int COCP_coarsen(const graph &finest, vector<vector<int>> &candidate_parts, int thr_ilp)

面向 COCP 粗化特属流入口。有别于一般流转在此还会对初始聚类提出粗评估方案预演并产生粗糙方案列表喂回引用 candidate_parts 中去。

MultilevelCoarsener(const graph &finest, const fpga &fpgas, const PartitionConstraintConfig &constraints, const CoarsenConfig &config, int thread)

构造函数：初始化粗化器，准备多层聚类所需的图栈和映射表。

Parameters:

  • finest – [in] 最细层原始超图。

  • fpgas – [in] FPGA 平台约束。

  • constraints – [in] 跨阶段硬约束配置（has_fix, has_io, has_timing 等）。

  • config – [in] 粗化阶段参数（层数、阈值、粗化方法等）。

  • thread – [in] 并发线程数。

void multilevelCoarsening(const graph &finest)

主入口：从最细层开始逐层执行图的合并收缩，直至图规模达到停止阈值 thr_coarsen_vertice，生成所有中间层（graphs, maps）。

Public Members

int level

最深要收缩钻透下降探出多少层地壳控制档位。

vector<int> isolated_nodes

无网络关联的孤立节点。通常在初始划分完成后再分配到空闲位置。

vector<graph> graphs

层次图栈。按照 index 分层， [0]最细 [top]最粗，存储每层的收缩超图。

vector<vector<int>> maps

层间映射表。用于 Uncoarsening 阶段将粗层节点映射回细层节点。

vector<vector<int>> map2origins

反查表：由粗层节点直接映射回 finest.graph 中的原始节点。

Private Functions

void calTimingPathForGroup(const vector<TimingPath> &timing_paths, const vector<int> &map, const vector<int> &hyperedge_cluster_id_vec, graph &coarse, vector<TimingPath> &timing_paths_c, vector<set<int>> &ins_paths_c, flat_hash_map<int, set<pair<int, int>>> &net_insPin_set_c)

当组约束预聚合（compute_group_graph）导致时序路径出现断点时， 利用本功能将路径重新对接修复到粗图中。

void computeGroupGraph(const graph &finest, int index, const vector<int> &group_map, graph &coarse)

处理组群约束：将同一组内的节点预先合并为粗图上的单个节点（预处理阶段执行）。

void candidatePropagation()

收缩候选链的传波动作广播函数。

set<int> intersection(const set<int> &set1, const set<int> &set2)

内部求同构双边互联共同项提取功能库。

void coarsening(int l)

新版粗化方法：引入跳步约束控制和时序感知的紧缩聚类。

void contraction(int l)

扫尾，把确定拉手合体的点做真正的数据图收缩简化，并且建立本层到下一层的双向投射穿透关系表（Map）。

void parallelContraction(int l)

OMP/Intel TBB多执行提速版本的并发图收缩器。

Private Members

const fpga &fpgas

此划分操作对标的芯片资源容量卡控版图。

int fpga_num

目标分区数（由 fpgas.resources.size() 确定）。

int index

本粗化构建树的当前深度或者是全局游标标志。

int multilevel_id = 0

目前所指代的流水进程线大序，打印log用于标识避免冲突。

bool has_fix

是否存在固定归属约束节点。若存在，粗化器会避免将固定节点与无关节点非法合并。

bool has_region

是否有指定的框选区域硬约束。

bool has_io

对输入输出引脚具有锚点拉伸倾向指示。

bool force_topo

是否基于拓扑约束限制超远距离的跳步合并。

bool has_timing

是否开启了时序驱动综合合并法则标志。

int large_net_threshold

大规模超边过滤阈值：超过此引脚数的 net 在匹配和打分时被跳过。

int beta

用于限制粗化节点最小应保有候选分区数量的超参数，以防过度合并导致后续初始划分无解。

double coarsening_ratio

合并萎缩递进比率，若配置0.5，表示每一层大图点数缩减至上一层的50即可停止。

int coarsen_method = 1

收缩算子选择（1代表旧版打分，2代表时序打分等）。

int enable_weight_penalty = 0

若开启，合并时体量过大的团块将受到权重抑制，防止过度吸收相邻节点。

int thr_coarsen_vertice

粗化停止阈值：当节点数小于该值时停止粗化进入初始划分（不能过小否则初始划分质量差）。

int seed = 0

播撒用来随机扰动或者扰散确定性匹配的伪随机序列种子点。

int thread

并行线程数上限。

VectorXi resources_in_one_FPGA

缓存在此参考比对用单片满载天花板标杆用作粗化吃满预警。

CoarsenOrder coarsen_order = CoarsenOrder::SIZE

当前粗化遍历的节点排序策略。

kahypar::SparseMap<int, float> score_map

第一方快速散列数组记录打分用，打分值暂存表。

kahypar::SparseMap<int, float> matched_score_map

已匹配融合节点的历史积分记录，用于防冲突。

vector<net> tmp_nets

组网折叠时暂存新生网线的容器。

vector<int> tmp_incident_nodes

新网线悬挂的牵连连接点推车。

vector<vector<int>> hyperedge_cluster_id_vec_maps

跨层超边映射表：原始超边到粗化超边的编号映射。