From 2de98386a7e0a4846ce4117cad414348e6271437 Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 14 Jan 2020 15:00:15 +0000 Subject: router2: Experiment with data structures Signed-off-by: David Shah --- common/router2.cc | 99 +++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 63 insertions(+), 36 deletions(-) (limited to 'common/router2.cc') diff --git a/common/router2.cc b/common/router2.cc index d190904f..f7962ae8 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -64,16 +64,31 @@ struct Router2 int total_route_us = 0; }; + struct WireScore + { + float cost; + float togo_cost; + delay_t delay; + float total() const { return cost + togo_cost; } + }; + struct PerWireData { // net --> number of arcs; driving pip - std::unordered_map> bound_nets; + boost::container::flat_map> bound_nets; // Historical congestion cost float hist_cong_cost = 1.0; // Wire is unavailable as locked to another arc bool unavailable = false; // This wire has to be used for this net int reserved_net = -1; + // Visit data + struct + { + bool dirty = false, visited = false; + PipId pip; + WireScore score; + } visit; }; float present_wire_cost(const PerWireData &w, int net_uid) @@ -87,14 +102,6 @@ struct Router2 return 1 + other_sources * curr_cong_weight; } - struct WireScore - { - float cost; - float togo_cost; - delay_t delay; - float total() const { return cost + togo_cost; } - }; - Context *ctx; // Use 'udata' for fast net lookups and indexing @@ -211,13 +218,7 @@ struct Router2 } double curr_cong_weight, hist_cong_weight, estimate_weight; - // Soft-route a net (don't touch Arch data structures which might not be thread safe) - // If is_mt is true, then strict bounding box rules are applied and log_* won't be called - struct VisitInfo - { - WireScore score; - PipId pip; - }; + struct ThreadContext { // Nets to route @@ -228,13 +229,13 @@ struct Router2 std::vector route_arcs; std::priority_queue, QueuedWire::Greater> queue; - std::unordered_map visited; // Special case where one net has multiple logical arcs to the same physical sink std::unordered_set processed_sinks; // Backwards routing std::queue backwards_queue; - std::unordered_map backwards_pip; + + std::vector dirty_wires; }; enum ArcRouteResult @@ -401,6 +402,29 @@ struct Router2 } } + void reset_wires(ThreadContext &t) + { + for (auto w : t.dirty_wires) { + wires.at(w).visit.visited = false; + wires.at(w).visit.dirty = false; + wires.at(w).visit.pip = PipId(); + wires.at(w).visit.score = WireScore(); + } + t.dirty_wires.clear(); + } + + void set_visited(ThreadContext &t, WireId wire, PipId pip, WireScore score) + { + auto &v = wires.at(wire).visit; + if (!v.dirty) + t.dirty_wires.push_back(wire); + v.dirty = true; + v.visited = true; + v.pip = pip; + v.score = score; + } + bool was_visited(WireId wire) { return wires.at(wire).visit.visited; } + ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, size_t i, bool is_mt, bool is_bb = true) { @@ -436,7 +460,6 @@ struct Router2 // bidirectional approach int backwards_iter = 0; int backwards_limit = ctx->getBelGlobalBuf(net->driver.cell->bel) ? 20000 : 15; - t.backwards_pip.clear(); t.backwards_queue.push(dst_wire); while (!t.backwards_queue.empty() && backwards_iter < backwards_limit) { WireId cursor = t.backwards_queue.front(); @@ -466,7 +489,7 @@ struct Router2 if (p == PipId()) break; cursor2 = ctx->getPipSrcWire(p); - t.backwards_pip[cursor2] = p; + set_visited(t, cursor2, p, WireScore()); } break; } @@ -480,7 +503,7 @@ struct Router2 if (cpip != PipId() && cpip != uh) continue; // don't allow multiple pips driving a wire with a net WireId next = ctx->getPipSrcWire(uh); - if (t.backwards_pip.count(next)) + if (was_visited(next)) continue; // skip wires that have already been visited auto &wd = wires.at(next); if (wd.unavailable) @@ -490,20 +513,20 @@ struct Router2 if (wd.bound_nets.size() > 1 || (wd.bound_nets.size() == 1 && !wd.bound_nets.count(net->udata))) continue; // never allow congestion in backwards routing t.backwards_queue.push(next); - t.backwards_pip[next] = uh; + set_visited(t, next, uh, WireScore()); } if (did_something) ++backwards_iter; } // Check if backwards routing succeeded in reaching source - if (t.backwards_pip.count(src_wire)) { + if (was_visited(src_wire)) { ROUTE_LOG_DBG(" Routed (backwards): "); WireId cursor_fwd = src_wire; bind_pip_internal(net, i, src_wire, PipId()); - while (t.backwards_pip.count(cursor_fwd)) { - auto &v = t.backwards_pip.at(cursor_fwd); - cursor_fwd = ctx->getPipDstWire(v); - bind_pip_internal(net, i, cursor_fwd, v); + while (was_visited(cursor_fwd)) { + auto &v = wires.at(cursor_fwd).visit; + cursor_fwd = ctx->getPipDstWire(v.pip); + bind_pip_internal(net, i, cursor_fwd, v.pip); if (ctx->debug) { auto &wd = wires.at(cursor_fwd); ROUTE_LOG_DBG(" wire: %s (curr %d hist %f)\n", ctx->nameOfWire(cursor_fwd), @@ -513,11 +536,12 @@ struct Router2 NPNR_ASSERT(cursor_fwd == dst_wire); ad.routed = true; t.processed_sinks.insert(dst_wire); + reset_wires(t); return ARC_SUCCESS; } // Normal forwards A* routing - t.visited.clear(); + reset_wires(t); WireScore base_score; base_score.cost = 0; base_score.delay = ctx->getWireDelay(src_wire).maxDelay(); @@ -525,8 +549,7 @@ struct Router2 // Add source wire to queue t.queue.push(QueuedWire(src_wire, PipId(), Loc(), base_score)); - t.visited[src_wire].score = base_score; - t.visited[src_wire].pip = PipId(); + set_visited(t, src_wire, PipId(), base_score); int toexplore = 25000 * std::max(1, (ad.bb.x1 - ad.bb.x0) + (ad.bb.y1 - ad.bb.y0)); int iter = 0; @@ -559,6 +582,8 @@ struct Router2 #endif // Evaluate score of next wire WireId next = ctx->getPipDstWire(dh); + if (was_visited(next)) + continue; #if 1 if (debug_arc) ROUTE_LOG_DBG(" src wire %s\n", ctx->nameOfWire(next)); @@ -575,7 +600,8 @@ struct Router2 next_score.delay = curr.score.delay + ctx->getPipDelay(dh).maxDelay() + ctx->getWireDelay(next).maxDelay(); next_score.togo_cost = 1.75 * get_togo_cost(net, i, next, dst_wire); - if (!t.visited.count(next) || (t.visited.at(next).score.total() > next_score.total())) { + const auto &v = wires.at(next).visit; + if (!v.visited || (v.score.total() > next_score.total())) { ++explored; #if 0 ROUTE_LOG_DBG("exploring wire %s cost %f togo %f\n", ctx->nameOfWire(next), next_score.cost, @@ -583,19 +609,18 @@ struct Router2 #endif // Add wire to queue if it meets criteria t.queue.push(QueuedWire(next, dh, ctx->getPipLocation(dh), next_score, ctx->rng())); - t.visited[next].score = next_score; - t.visited[next].pip = dh; + set_visited(t, next, dh, next_score); if (next == dst_wire) { toexplore = std::min(toexplore, iter + 5); } } } } - if (t.visited.count(dst_wire)) { + if (was_visited(dst_wire)) { ROUTE_LOG_DBG(" Routed (explored %d wires): ", explored); WireId cursor_bwd = dst_wire; - while (t.visited.count(cursor_bwd)) { - auto &v = t.visited.at(cursor_bwd); + while (was_visited(cursor_bwd)) { + auto &v = wires.at(cursor_bwd).visit; bind_pip_internal(net, i, cursor_bwd, v.pip); if (ctx->debug) { auto &wd = wires.at(cursor_bwd); @@ -613,8 +638,10 @@ struct Router2 } t.processed_sinks.insert(dst_wire); ad.routed = true; + reset_wires(t); return ARC_SUCCESS; } else { + reset_wires(t); return ARC_RETRY_WITHOUT_BB; } } -- cgit v1.2.3