时序微调策略与代码导读¶
本页整理 Partition 模块时序驱动细化（refine）阶段的设计取舍与代码阅读路径，主要对应
src/partition/refine/strategy/LegacyOldStrategy.cpp（OldRefine::refinement）及其调用方src/partition/refine/RefinementFacade.cpp。
怎么平衡时序增益和cut增益？¶
仅优化maxhop的our1算法，当一个节点移动的时序增益为正时，不再考虑cut增益，一定接受这个节点移动；当一个节点移动的时序增益为0时，再看cut增益，如果cut增益为正则接受这个节点移动，cut增益不为正则拒绝这个节点移动；当一个节点移动的时序增益为负时，不再考虑cut增益，一定拒绝这个节点移动。总结来说只有时序增益为0时才会考虑cut增益来决定接不接受该节点移动的。
一个节点移动的时序增益是看这个节点移动之后maxhop是否降低，或者maxhop不变但slackData达到了maxhop的割边数量的减少量。如果maxhop降低或者maxhop不变但达到了maxhop的割边数量减少了就时序增益为正，maxhop不变且达到了maxhop的割边数量也不变就时序增益为0，maxhop增加或者maxhop不变但达到了maxhop的割边数量增加了就时序增益为负。
our2算法中也是总结来说只有时序增益为0时才会考虑cut增益来决定接不接受该节点移动的。但是our2算法的时序增益本身隐含了对cut增加的惩罚。因为our2算法计算的时序增益是，计算slack最小前α%的那些割网的slack之和的增加量，也就是slack最小的(cut * α%)条割网的slack之和的增加量，如果有增加就认为时序增益为正。那么当cut增加时（cut * α%）也就增加，这时这个slack之和就会需要多统计一部分slack，这些slack为负，所以会降低slack之和，让这个节点移动更难被接受。（注意：我们计算slack最小前α%的那些割网的slack之和时只记入负的slack，当遇到正的slack时就结束累加，例如实验中在测试j3_top时设置α=12，但是可能遇到优化得太好的情况，比如到前7%的最差slack的时候就已经变成正数了，那我们只统计前7%的最差slack之和，如果不这样做的话cut增加将会奖励时序增益，因为cut增加以后能够记入更多正的slack而不是负的slack了，这个时候cut增加也会增加最差前α%的slack之和，在实验中发现会把cut调得非常大）。
对每个边界点都计算时序增益还是只计算关键路径/割边上节点的时序增益？¶
采用的是对每个边界点都计算时序增益。虽然说只有挪动关键割边（也就是slackData达到了maxhop的割边）上的点才可能有正的时序增益，但是挪动一些非关键割边上的点会有时序增益为0但是可以减少cut的情况，如果我们只对关键割边上的节点计算时序增益可以节省运行时间，但是会牺牲掉一些时序增益为0但是能降低cut的节点移动，这样可能会让cut偏大。
所以要不要这样做，可能需要通过实验看到底能节省多少时间，以及会让cut变大多少，如果能节省大量运行时间同时cut又没增大多少就是划算的，但是也有可能节省的运行时间不多，cut又增大了很多就是不划算的。之前有做过一个简单的实验，是一开始就把所有关键割边上的点提取出来，然后对这些点进行移动，发现cut增大了很多，同时还让时序质量降低了，所以后续没有继续尝试。但是那个简单的实验也有些不合理指出，没有实时的维护这个关键割边上节点的集合，因为每次移动一个节点这个关键割边节点的集合可能发生改变。所以或许之后可以尝试每次节点移动以后重新计算（增量或者全量）关键割边上节点的集合，然后在尝试挪动边界点时，先检查这个边界点在不在这个集合中，如果不在这个集合中就直接拒绝这个移动这个节点，从而节省时序增益的计算开销，然后当接受一个节点移动时需要去更新一下这个关键割边上节点的集合。
代码阅读建议¶
//核心代码就是下面这个文件中定义的函数，把这个函数看明白，再顺着这个函数看一下它调用的时序代价评估的功能应该就没问题了
//src/partition/refine/strategy/LegacyOldStrategy.cpp
//用来实现某一层的时序微调
double OldRefine::refinement(const graph &finest, vector<int> &parts,
vector<VectorXi> &occupied_resources,
vector<NetPartition> &partition, int seed,
vector<float> &paths_cost,
const timing &updatedTimingInfo)
{
const auto eval_ctx = makeGainEvalContext();
const int n = finest.nodes.size();
int fpga_num = occupied_resources.size();
double gain = 0.0;
// 收集割边上可移动的点，后续只尝试挪动这些点
vector<bool> no_visited(n, false);
auto boundary_verts = FMLikeStrategyBase::collectBoundaryVertices(
finest, parts, no_visited, _k);
// 打乱这些割边上的点
shuffle(boundary_verts.begin(), boundary_verts.end(),
default_random_engine(seed));
int reads = 0, writes = 0;
// 遍历所收集到的割边上的点逐个尝试移动
for (const auto &i : boundary_verts) {
// 检查是否是一个固定节点，如果是就跳过
if (!has_fix || finest.fixed_assign[i] == -1) {
double max_gain = 0.0;
int best_p = -1;
Gain best_gain_cell;
// 尝试往其他各个FPGA上移动
for (int possible_p = 0; possible_p < fpga_num; possible_p++) {
VectorXi &actual_upper_resources = fpgas.bound_constraint
? fpgas.upper_resources
: fpgas.resources[possible_p];
// 检查讲节点i往编号为possible_p的FPGA上挪动是否符合一些基本约束
if ((actual_upper_resources - occupied_resources[possible_p] -
finest.nodes[i].resources)
.minCoeff() < 0)
continue;
if (!finest.region_fixed.empty() && finest.region_fixed[i] &&
finest.candidates[i].find(possible_p) == finest.candidates[i].end())
continue;
if (fpgas.bound_constraint) {
if (!ConstraintCheckerCore::checkBalance(fpgas, occupied_resources,
finest.nodes[i], parts[i]))
continue;
}
// 计算将节点i移动到possible_p上的时序增益（时序增益为0时将返回cut增益）
Gain gain_cell = GainEvaluatorCore::evaluate(
eval_ctx, i, parts[i], possible_p, partition, finest, parts,
paths_cost, updatedTimingInfo);
reads++;
// 记录时序增益最大的possible_p和对应的时序增益
if (gain_cell.get_gain() > max_gain) {
max_gain = gain_cell.get_gain();
best_p = possible_p;
best_gain_cell = gain_cell;
}
}
// 如果对于节点i存在一个能带来正增益的移动，则接受这个节点移动让它生效
if (best_p > -1) {
// 更新节点移动后的parts、资源使用情况等基本信息
MoveStateApplierCore::applyMoveToState(
makeMoveApplierContext(), best_gain_cell, finest, parts,
occupied_resources, partition, paths_cost);
gain += max_gain;
if (fpgas.cutweights_assignment.size() > 0) {
fpgas.computeCutWeightsOld(finest, parts, cut_weights);
}
writes++;
// 更新节点移动后的时序信息
if (timing_cfg.has_timing && timing_cfg.ourLocalData != nullptr) {
timing_cfg.ourLocalData->setEnableRollback(false);
vector<pair<int, int>> newParts;
// 展开粗化节点，因为我们直接在最底层时序图上进行操作，所以一个粗化节点的移动需要被展开为很多个最底层的节点移动
if (timing_cfg.originLevelNodeIds.empty()) {
newParts.emplace_back(i, best_p);
} else {
for (const auto &u : timing_cfg.originLevelNodeIds[i]) {
newParts.emplace_back(u, best_p);
}
}
// 调用增量时序更新来计算节点移动后的时序信息
timing_cfg.ourLocalData->updateTimingEdge(newParts);
// 检查cut矩阵变化量，当cut矩阵变化超过一个阈值时，将重新估计跨FPGA的割边时延，并全量刷新时序信息
updateFullTimingByCut(finest, parts);
}
}
}
}
// 打印该层微调查询节点移动的时序增益的次数，接受节点移动的次数以及二者的比值
if (timing_cfg.has_timing && timing_cfg.ourLocalData != nullptr) {
spdlog::trace("Candidate {}, Reads: {}, Writes: {}, Read / Write ratio: {}",
timing_cfg.ourLocalData->getId(), reads, writes,
(double)reads / writes);
}
return gain;
}
//上面这段代码是对一个层进行微调，然后可以再看一下src/partition/refine/RefinementFacade.cpp中的Metrics Refinement::refinement函数，这个函数会调用上面的函数来做逐层的微调具体是通过下面这个CandidatePoolService::runRefinementBatch函数调用到了上面的OldRefine::refinement，不过这个是之前用AI重构出来的代码，它用了比较高级的语法特性比如一些函数参数，所以可能乍一看不知道是在这里调用了，细看了才能发现它调的就是OldRefine::refinement
CandidatePoolService::runRefinementBatch(
run_config.thread, mc.graphs.at(level), fpgas, buffers.parts,
buffers.occupied_resources, buffers.paths_costs, remaining_solutions,
pFlow, buffers.worst_slacks, refinement_fn);