Class Initial¶

Defined in File initial.h

Class Documentation¶

class Initial¶

初始划分控制类。

当图通过粗化缩减到只剩少量节点时（最高层级图），利用各类初始化策略将节点分配到不同的分区中（生成初始划分）。初始解的质量直接影响最终优化的效果。

Public Functions

Initial(const PartitionConstraintConfig &constraints, const InitialPartitionConfig &config)¶

实例化一个初始划分生成器。

Parameters:

constraints – [in] 跨阶段共享的硬约束配置。
config – [in] 初始划分阶段配置。

int initialPartition(MultilevelCoarsener &mc, const fpga &fpgas, vector<vector<int>> &candidate_parts, vector<vector<VectorXi>> &candidate_occupied_resources)¶

核心入口：一站式生成多组候选初始解并推入细化流程。

该函数整合所有已配置的初始生成策略，以获取多样化的初始解。

Parameters:

mc – [in] 多层粗化器（包含当前层级图和环境信息）。
fpgas – [in] FPGA 容量约束与拓扑距离矩阵。
candidate_parts – [out] 生成的有效候选划分方案集合。
candidate_occupied_resources – [out] 各候选方案对应的资源占用记录。

Returns:

若成功生成至少一个合法方案返回 1，若空间不足无法分配则返回 -1。

bool COCP_ILP(MultilevelCoarsener &mc, const fpga &fpgas, bool has_fix, vector<int> &candidate_parts, vector<VectorXi> &candidate_occupied_resources)¶

供 COCP 使用整数线性规划（ILP）精确求解功能。

Returns:: ILP 是否成功求得最优解。

Private Functions

void constructGraph(const graph &g)¶: 预处理提建简易连排网用来帮助在特定初始算法（如SPFA）内推算跳距。

void improvedSPFA(const graph &g, vector<int> &parts, vector<VectorXi> upper_resources, vector<VectorXi> &occupied_resources)¶: 基于改进版最短路径算法（SPFA）引伸发散出的时延或距离阻抗推算导排选型器，它力图分配减少长跳开销。

int selectInitialNodes(const graph &g, vector<int> &parts, vector<VectorXi> upper_resources, vector<VectorXi> &occupied_resources, vector<int> &order)¶: 辅助挑选出最初的初始种子节点，用于后续贪心扩展算法。

int randomPart(const graph &g, vector<int> &parts, VectorXi upper_resources, VectorXi lower_resources, vector<VectorXi> &occupied_resources, int seed)¶: 使用随机分配策略生成初始解，以有效探索解空间，增加解的多样性。

int greedyPart(const graph &g, vector<int> &parts, vector<VectorXi> upper_resources, vector<VectorXi> &occupied_resources, int seed)¶: 贪心分配函数：每步选择当前增益最大的节点进行分配。

int progressiveMinCutPart(const graph &g, vector<int> &parts, vector<VectorXi> upper_resources, vector<VectorXi> &occupied_resources, int seed)¶: 采用稳扎稳打分步步进最小割（Progressive Min-Cut）核心生长初始划分策略。

double calculateGain(const graph &g, const vector<int> &parts, int vertex, int to, int type)¶: （内部评估函）算一算将某个未决预审点推送到当前分包阵营里能否增加吸引增益或消灭违规跳线。

int growPart(const graph &g, vector<int> &parts, vector<VectorXi> upper_resources, vector<VectorXi> &occupied_resources, int i, int seed)¶: 基于选好的种子节点，按邻接关系逐步扩展策略，直到达到容量限制（Grow）。

int globalGrowPart(const graph &g, vector<int> &parts, vector<VectorXi> upper_resources, vector<VectorXi> &occupied_resources, int type, int seed)¶: 全局扩展生长策略：所有分区同时扩展。

int sequentialGrowPart(const graph &g, vector<int> &parts, vector<VectorXi> upper_resources, vector<VectorXi> &occupied_resources, int type, int seed)¶: 顺序填充策略：按硬件块顺序依次填满一个再装下一个。

int roundRobinGrowPart(const graph &g, vector<int> &parts, vector<VectorXi> upper_resources, vector<VectorXi> &occupied_resources, int type, int seed)¶: 轮询策略（Round-Robin）：各分区轮流扩展一个节点，均衡同步增长。

int initialPartitionTopo(const graph &g, const fpga &fpgas, vector<int> &parts, vector<VectorXi> upper_resources, vector<VectorXi> &occupied_resources, bool has_fix, const vector<int> &fixed_assign, vector<set<int>> candidate, int allow_hop, int i, int seed)¶: 拓扑约束下的初始划分策略，避免初始解在空间上过度分散。

Private Members

bool has_fix¶: 是否存在固定归属约束（Fixed Assignment）节点。

bool force_topo¶: 是否严格遵循硬件拓扑距离约束。

int multilevel_id = 0¶: 当前打穿下来的V-Cycle批次流道编识。

int max_hop¶: 最大硬忍跳距制约。

int num_initial_solutions¶: 要求生成的不同随机种子初始化方案数量。

int num_best_initial_solutions¶: 从初始方案中选出最优的几份进入细化阶段。

vector<flat_hash_map<int, pair<int, double>>> hypergraph¶: 将缩短简化好的图模型在此提取折算成的简化版引力关系结构体辅助生成推演。