From 2a856db72c6d050c364d6dd6544a0eb4539dc59d Mon Sep 17 00:00:00 2001 From: gatecat Date: Sun, 15 Aug 2021 09:34:27 +0100 Subject: router2: Adding some criticality heuristics Signed-off-by: gatecat --- common/router2.cc | 42 +++++++++++++++++++++++++++++------------- 1 file changed, 29 insertions(+), 13 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 3605a7fd..cb5f3eab 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -53,7 +53,6 @@ struct Router2 WireId sink_wire; ArcBounds bb; bool routed = false; - float arc_crit = 0; }; // As we allow overlap at first; the nextpnr bind functions can't be used @@ -352,7 +351,7 @@ struct Router2 ad.routed = false; } - float score_wire_for_arc(NetInfo *net, size_t user, size_t phys_pin, WireId wire, PipId pip) + float score_wire_for_arc(NetInfo *net, size_t user, size_t phys_pin, WireId wire, PipId pip, float crit_weight) { auto &wd = wire_data(wire); auto &nd = nets.at(net->udata); @@ -366,16 +365,16 @@ struct Router2 overuse -= 1; source_uses = nd.wires.at(wire).second; } - float present_cost = 1.0f + overuse * curr_cong_weight; + float present_cost = 1.0f + overuse * curr_cong_weight * crit_weight; if (pip != PipId()) { Loc pl = ctx->getPipLocation(pip); bias_cost = cfg.bias_cost_factor * (base_cost / int(net->users.size())) * ((std::abs(pl.x - nd.cx) + std::abs(pl.y - nd.cy)) / float(nd.hpwl)); } - return base_cost * hist_cost * present_cost / (1 + source_uses) + bias_cost; + return base_cost * hist_cost * present_cost / (1 + (source_uses * crit_weight)) + bias_cost; } - float get_togo_cost(NetInfo *net, size_t user, int wire, WireId src_sink, bool bwd = false) + float get_togo_cost(NetInfo *net, size_t user, int wire, WireId src_sink, float crit_weight, bool bwd = false) { auto &nd = nets.at(net->udata); auto &wd = flat_wires[wire]; @@ -385,7 +384,7 @@ struct Router2 } // FIXME: timing/wirelength balance? delay_t est_delay = ctx->estimateDelay(bwd ? src_sink : wd.w, bwd ? wd.w : src_sink); - return (ctx->getDelayNS(est_delay) / (1 + source_uses)) + cfg.ipin_cost_adder; + return (ctx->getDelayNS(est_delay) / (1 + source_uses * crit_weight)) + cfg.ipin_cost_adder; } bool check_arc_routing(NetInfo *net, size_t usr, size_t phys_pin) @@ -568,6 +567,13 @@ struct Router2 bool was_visited_fwd(int wire) { return flat_wires.at(wire).visited_fwd; } bool was_visited_bwd(int wire) { return flat_wires.at(wire).visited_bwd; } + float get_arc_crit(NetInfo *net, size_t i) + { + if (!timing_driven) + return 0; + return tmg.get_criticality(CellPortKey(net->users.at(i))); + } + ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, size_t i, size_t phys_pin, bool is_mt, bool is_bb = true) { // Do some initial lookups and checks @@ -586,6 +592,9 @@ struct Router2 ctx->nameOf(usr.cell)); int src_wire_idx = wire_to_idx.at(src_wire); int dst_wire_idx = wire_to_idx.at(dst_wire); + // Calculate a timing weight based on criticality + float crit = get_arc_crit(net, i); + float crit_weight = (1.0f - std::pow(crit, 2)); // Check if arc was already done _in this iteration_ if (t.processed_sinks.count(dst_wire)) return ARC_SUCCESS; @@ -621,7 +630,7 @@ struct Router2 WireScore base_score; base_score.cost = wire_cost; int wire_idx = wire_to_idx.at(wire); - base_score.togo_cost = get_togo_cost(net, i, wire_idx, dst_wire, false); + base_score.togo_cost = get_togo_cost(net, i, wire_idx, dst_wire, false, crit_weight); t.fwd_queue.push(QueuedWire(wire_idx, base_score)); set_visited_fwd(t, wire_idx, PipId()); }; @@ -651,7 +660,7 @@ struct Router2 WireScore base_score; base_score.cost = 0; int wire_idx = wire_to_idx.at(wire); - base_score.togo_cost = get_togo_cost(net, i, wire_idx, src_wire, true); + base_score.togo_cost = get_togo_cost(net, i, wire_idx, src_wire, true, crit_weight); t.bwd_queue.push(QueuedWire(wire_idx, base_score)); set_visited_bwd(t, wire_idx, PipId()); }; @@ -702,8 +711,9 @@ struct Router2 if (!thread_test_wire(t, nwd)) continue; // thread safety issue WireScore next_score; - next_score.cost = curr.score.cost + score_wire_for_arc(net, i, phys_pin, next, dh); - next_score.togo_cost = cfg.estimate_weight * get_togo_cost(net, i, next_idx, dst_wire, false); + next_score.cost = curr.score.cost + score_wire_for_arc(net, i, phys_pin, next, dh, crit_weight); + next_score.togo_cost = + cfg.estimate_weight * get_togo_cost(net, i, next_idx, dst_wire, false, crit_weight); set_visited_fwd(t, next_idx, dh); t.fwd_queue.push(QueuedWire(next_idx, next_score, t.rng.rng())); } @@ -746,8 +756,9 @@ struct Router2 if (!thread_test_wire(t, nwd)) continue; // thread safety issue WireScore next_score; - next_score.cost = curr.score.cost + score_wire_for_arc(net, i, phys_pin, next, uh); - next_score.togo_cost = cfg.estimate_weight * get_togo_cost(net, i, next_idx, src_wire, true); + next_score.cost = curr.score.cost + score_wire_for_arc(net, i, phys_pin, next, uh, crit_weight); + next_score.togo_cost = + cfg.estimate_weight * get_togo_cost(net, i, next_idx, src_wire, true, crit_weight); set_visited_bwd(t, next_idx, uh); t.bwd_queue.push(QueuedWire(next_idx, next_score, t.rng.rng())); } @@ -870,6 +881,11 @@ struct Router2 t.route_arcs.emplace_back(i, j); } } + // Route most critical arc first + std::stable_sort(t.route_arcs.begin(), t.route_arcs.end(), + [&](std::pair a, std::pair b) { + return get_arc_crit(net, a.first) > get_arc_crit(net, b.first); + }); for (auto a : t.route_arcs) { auto res1 = route_arc(t, net, a.first, a.second, is_mt, true); if (res1 == ARC_FATAL) @@ -1345,7 +1361,7 @@ struct Router2 do { ctx->sorted_shuffle(route_queue); - if (timing_driven && (int(route_queue.size()) > (int(nets_by_udata.size()) / 50))) { + if (timing_driven && (int(route_queue.size()) > (int(nets_by_udata.size()) / 500))) { // Heuristic: reduce runtime by skipping STA in the case of a "long tail" of a few // congested nodes tmg.run(iter == 1); -- cgit v1.2.3