From 51c0642ee0b945d6467416ac05c38b97d48f0d23 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 3 Nov 2019 09:56:34 +0000 Subject: router2: Basic infrastructure Signed-off-by: David Shah --- common/router2.cc | 202 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 202 insertions(+) create mode 100644 common/router2.cc (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc new file mode 100644 index 00000000..f833e1e9 --- /dev/null +++ b/common/router2.cc @@ -0,0 +1,202 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2019 David Shah + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include +#include +#include +#include "log.h" +#include "nextpnr.h" +#include "util.h" + +NEXTPNR_NAMESPACE_BEGIN + +namespace { +struct Router2 +{ + struct arc_key + { + NetInfo *net_info; + int user_idx; + + bool operator==(const arc_key &other) const + { + return (net_info == other.net_info) && (user_idx == other.user_idx); + } + bool operator<(const arc_key &other) const + { + return net_info == other.net_info ? user_idx < other.user_idx : net_info->name < other.net_info->name; + } + + struct Hash + { + std::size_t operator()(const arc_key &arg) const noexcept + { + std::size_t seed = std::hash()(arg.net_info); + seed ^= std::hash()(arg.user_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2); + return seed; + } + }; + }; + + struct arc_entry + { + arc_key arc; + delay_t pri; + int randtag = 0; + + struct Less + { + bool operator()(const arc_entry &lhs, const arc_entry &rhs) const noexcept + { + if (lhs.pri != rhs.pri) + return lhs.pri < rhs.pri; + return lhs.randtag < rhs.randtag; + } + }; + }; + + struct BoundingBox + { + int x0, x1, y0, y1; + }; + + struct PerArcData + { + std::vector> wires; + BoundingBox bb; + }; + + // As we allow overlap at first; the nextpnr bind functions can't be used + // as the primary relation between arcs and wires/pips + struct PerNetData + { + std::vector arcs; + BoundingBox bb; + }; + + struct PerWireData + { + // net --> driving pip + std::unordered_map bound_nets; + // Which net is bound in the Arch API + int arch_bound_net = -1; + // Historical congestion cost + float hist_cong_cost = 0; + }; + + 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 + std::vector nets_by_udata; + + struct QueuedWire + { + + explicit QueuedWire(WireId wire = WireId(), PipId pip = PipId(), WireScore score = WireScore{}, int randtag = 0) + : wire(wire), pip(pip), score(score), randtag(randtag){}; + + WireId wire; + PipId pip; + + WireScore score; + int randtag = 0; + + struct Greater + { + bool operator()(const QueuedWire &lhs, const QueuedWire &rhs) const noexcept + { + float lhs_score = lhs.score.cost + lhs.score.togo_cost, + rhs_score = rhs.score.cost + rhs.score.togo_cost; + return lhs_score == rhs_score ? lhs.randtag > rhs.randtag : lhs_score > rhs_score; + } + }; + }; + + 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 ThreadContext + { + std::priority_queue, QueuedWire::Greater> queue; + std::unordered_map visited; + }; + + enum ArcRouteResult + { + ARC_SUCCESS, + ARC_RETRY_WITHOUT_BB, + ARC_FATAL, + }; + +// Avoid log_error in MT +#define ARC_ERR(...) \ + do { \ + if (is_mt) \ + return ARC_FATAL; \ + else \ + log_error(__VA_ARGS__); \ + } while (0) +#define ARC_DBG(...) \ + do { \ + if (!is_mt && ctx->debug) \ + log(__VA_ARGS__); \ + } while (0) + + ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, size_t i, bool is_mt, bool is_bb = true) + { + auto &usr = net->users.at(i); + ARC_DBG("Routing arc %d of net '%s'", int(i), ctx->nameOf(net)); + WireId src_wire = ctx->getNetinfoSourceWire(net), dst_wire = ctx->getNetinfoSinkWire(net, usr); + + if (src_wire == WireId()) + log_error("No wire found for port %s on source cell %s.\n", ctx->nameOf(net->driver.port), + ctx->nameOf(net->driver.cell)); + if (dst_wire == WireId()) + log_error("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port), + ctx->nameOf(usr.cell)); + } +#undef ARC_ERR +#undef ARC_DBG + bool route_net(ThreadContext &t, NetInfo *net, bool is_mt) + { + + // Define to make sure we don't print in a multithreaded context + + if (!t.queue.empty()) { + std::priority_queue, QueuedWire::Greater> new_queue; + t.queue.swap(new_queue); + } + t.visited.clear(); + for (size_t i = 0; i < net->users.size(); i++) { + } + } + + void bind_and_check_legality(NetInfo *net) {} +}; +} // namespace + +NEXTPNR_NAMESPACE_END \ No newline at end of file -- cgit v1.2.3 From a0ac9d62f2569bee4438145b5681345506113aa9 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 3 Nov 2019 11:26:21 +0000 Subject: router2: infrastructure Signed-off-by: David Shah --- common/router2.cc | 122 +++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 83 insertions(+), 39 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index f833e1e9..02c7e1c6 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -54,32 +54,10 @@ struct Router2 }; }; - struct arc_entry - { - arc_key arc; - delay_t pri; - int randtag = 0; - - struct Less - { - bool operator()(const arc_entry &lhs, const arc_entry &rhs) const noexcept - { - if (lhs.pri != rhs.pri) - return lhs.pri < rhs.pri; - return lhs.randtag < rhs.randtag; - } - }; - }; - - struct BoundingBox - { - int x0, x1, y0, y1; - }; - struct PerArcData { std::vector> wires; - BoundingBox bb; + ArcBounds bb; }; // As we allow overlap at first; the nextpnr bind functions can't be used @@ -87,7 +65,7 @@ struct Router2 struct PerNetData { std::vector arcs; - BoundingBox bb; + ArcBounds bb; }; struct PerWireData @@ -112,16 +90,56 @@ struct Router2 // Use 'udata' for fast net lookups and indexing std::vector nets_by_udata; + std::vector nets; + void setup_nets() + { + // Populate per-net and per-arc structures at start of routing + nets.resize(ctx->nets.size()); + nets_by_udata.resize(ctx->nets.size()); + size_t i = 0; + for (auto net : sorted(ctx->nets)) { + NetInfo *ni = net.second; + ni->udata = i; + nets_by_udata.at(i) = ni; + nets.at(i).arcs.resize(ni->users.size()); + + // Start net bounding box at overall min/max + nets.at(i).bb.x0 = std::numeric_limits::max(); + nets.at(i).bb.x1 = std::numeric_limits::min(); + nets.at(i).bb.y0 = std::numeric_limits::max(); + nets.at(i).bb.y1 = std::numeric_limits::min(); + + for (size_t j = 0; j < ni->users.size(); j++) { + auto &usr = ni->users.at(j); + WireId src_wire = ctx->getNetinfoSourceWire(ni), dst_wire = ctx->getNetinfoSinkWire(ni, usr); + if (src_wire == WireId()) + log_error("No wire found for port %s on source cell %s.\n", ctx->nameOf(ni->driver.port), + ctx->nameOf(ni->driver.cell)); + if (dst_wire == WireId()) + log_error("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port), + ctx->nameOf(usr.cell)); + // Set bounding box for this arc + nets.at(i).arcs.at(j).bb = ctx->getRouteBoundingBox(src_wire, dst_wire); + // Expand net bounding box to include this arc + nets.at(i).bb.x0 = std::min(nets.at(i).bb.x0, nets.at(i).arcs.at(j).bb.x0); + nets.at(i).bb.x1 = std::max(nets.at(i).bb.x1, nets.at(i).arcs.at(j).bb.x1); + nets.at(i).bb.y0 = std::min(nets.at(i).bb.y0, nets.at(i).arcs.at(j).bb.y0); + nets.at(i).bb.y1 = std::max(nets.at(i).bb.y1, nets.at(i).arcs.at(j).bb.y1); + } + i++; + } + } struct QueuedWire { - explicit QueuedWire(WireId wire = WireId(), PipId pip = PipId(), WireScore score = WireScore{}, int randtag = 0) - : wire(wire), pip(pip), score(score), randtag(randtag){}; + explicit QueuedWire(WireId wire = WireId(), PipId pip = PipId(), Loc loc = Loc(), WireScore score = WireScore{}, + int randtag = 0) + : wire(wire), pip(pip), loc(loc), score(score), randtag(randtag){}; WireId wire; PipId pip; - + Loc loc; WireScore score; int randtag = 0; @@ -136,6 +154,13 @@ struct Router2 }; }; + int bb_margin_x = 3, bb_margin_y = 3; // number of units outside the bounding box we may go + bool hit_test_pip(ArcBounds &bb, Loc l) + { + return l.x >= (bb.x0 - bb_margin_x) && l.x <= (bb.x1 + bb_margin_x) && l.y >= (bb.y0 - bb_margin_y) && + l.y <= (bb.y1 - bb_margin_y); + } + 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 @@ -152,15 +177,15 @@ struct Router2 ARC_FATAL, }; -// Avoid log_error in MT -#define ARC_ERR(...) \ +// Define to make sure we don't print in a multithreaded context +#define ARC_LOG_ERR(...) \ do { \ if (is_mt) \ return ARC_FATAL; \ else \ log_error(__VA_ARGS__); \ } while (0) -#define ARC_DBG(...) \ +#define ROUTE_LOG_DBG(...) \ do { \ if (!is_mt && ctx->debug) \ log(__VA_ARGS__); \ @@ -169,31 +194,50 @@ struct Router2 ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, size_t i, bool is_mt, bool is_bb = true) { auto &usr = net->users.at(i); - ARC_DBG("Routing arc %d of net '%s'", int(i), ctx->nameOf(net)); + ROUTE_LOG_DBG("Routing arc %d of net '%s'", int(i), ctx->nameOf(net)); WireId src_wire = ctx->getNetinfoSourceWire(net), dst_wire = ctx->getNetinfoSinkWire(net, usr); if (src_wire == WireId()) - log_error("No wire found for port %s on source cell %s.\n", ctx->nameOf(net->driver.port), - ctx->nameOf(net->driver.cell)); + ARC_LOG_ERR("No wire found for port %s on source cell %s.\n", ctx->nameOf(net->driver.port), + ctx->nameOf(net->driver.cell)); if (dst_wire == WireId()) - log_error("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port), - ctx->nameOf(usr.cell)); + ARC_LOG_ERR("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port), + ctx->nameOf(usr.cell)); + + return ARC_SUCCESS; } #undef ARC_ERR -#undef ARC_DBG bool route_net(ThreadContext &t, NetInfo *net, bool is_mt) { - - // Define to make sure we don't print in a multithreaded context - + ROUTE_LOG_DBG("Routing net '%s'...\n", ctx->nameOf(net)); if (!t.queue.empty()) { std::priority_queue, QueuedWire::Greater> new_queue; t.queue.swap(new_queue); } t.visited.clear(); + bool have_failures = false; for (size_t i = 0; i < net->users.size(); i++) { + auto res1 = route_arc(t, net, i, is_mt, true); + if (res1 == ARC_FATAL) + return false; // Arc failed irrecoverably + else if (res1 == ARC_RETRY_WITHOUT_BB) { + if (is_mt) { + // Can't break out of bounding box in multi-threaded mode, so mark this arc as a failure + have_failures = true; + } else { + // Attempt a re-route without the bounding box constraint + ROUTE_LOG_DBG("Rerouting arc %d of net '%s' without bounding box, possible tricky routing...\n", + int(i), ctx->nameOf(net)); + auto res2 = route_arc(t, net, i, is_mt, false); + // If this also fails, no choice but to give up + if (res2 != ARC_SUCCESS) + log_error("Failed to route arc %d of net '%s'.\n", int(i), ctx->nameOf(net)); + } + } } + return !have_failures; } +#undef ARC_LOG_DBG void bind_and_check_legality(NetInfo *net) {} }; -- cgit v1.2.3 From dbb771dfe49092127cabec9d5e89afebc60f827e Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 6 Nov 2019 19:47:27 +0000 Subject: router2: helper functions Signed-off-by: David Shah --- common/router2.cc | 97 +++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 94 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 02c7e1c6..48314437 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -15,6 +15,15 @@ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. * + * Core routing algorithm based on CRoute: + * + * CRoute: A Fast High-quality Timing-driven Connection-based FPGA Router + * Dries Vercruyce, Elias Vansteenkiste and Dirk Stroobandt + * DOI 10.1109/FCCM.2019.00017 [PDF on SciHub] + * + * Modified for the nextpnr Arch API and data structures; optimised for + * real-world FPGA architectures in particular ECP5 and Xilinx UltraScale+ + * */ #include @@ -56,7 +65,7 @@ struct Router2 struct PerArcData { - std::vector> wires; + std::unordered_map wires; ArcBounds bb; }; @@ -66,18 +75,30 @@ struct Router2 { std::vector arcs; ArcBounds bb; + // Coordinates of the center of the net, used for the weight-to-average + int cx, cy, hpwl; }; struct PerWireData { - // net --> driving pip - std::unordered_map bound_nets; + // net --> number of arcs; driving pip + std::unordered_map> bound_nets; // Which net is bound in the Arch API int arch_bound_net = -1; // Historical congestion cost float hist_cong_cost = 0; + // Wire is unavailable as locked to another arc + bool unavailable = false; }; + float present_wire_cost(const PerWireData &w) + { + if (w.bound_nets.size() <= 1) + return 1.0f; + else + return 1 + (int(w.bound_nets.size()) - 1) * curr_cong_weight; + } + struct WireScore { float cost; @@ -130,6 +151,23 @@ struct Router2 } } + std::unordered_map wires; + void setup_wires() + { + // Set up per-wire structures, so that MT parts don't have to do any memory allocation + // This is possibly quite wasteful and not cache-optimal; further consideration necessary + for (auto wire : ctx->getWires()) { + wires[wire]; + NetInfo *bound = ctx->getBoundWireNet(wire); + if (bound != nullptr) { + wires[wire].bound_nets[bound->udata] = std::make_pair(1, bound->wires.at(wire).pip); + wires[wire].arch_bound_net = bound->udata; + if (bound->wires.at(wire).strength > STRENGTH_STRONG) + wires[wire].unavailable = true; + } + } + } + struct QueuedWire { @@ -191,6 +229,57 @@ struct Router2 log(__VA_ARGS__); \ } while (0) + void bind_pip_internal(NetInfo *net, size_t user, WireId wire, PipId pip) + { + auto &b = wires.at(wire).bound_nets[net->udata]; + ++b.first; + if (b.first == 1) { + b.second = pip; + } else { + NPNR_ASSERT(b.second == pip); + } + nets.at(net->udata).arcs.at(user).wires[wire] = pip; + } + + void unbind_pip_internal(NetInfo *net, size_t user, WireId wire, bool dont_touch_arc = false) + { + auto &b = wires.at(wire).bound_nets[net->udata]; + --b.first; + if (b.first == 0) { + wires.at(wire).bound_nets.erase(net->udata); + } + if (!dont_touch_arc) + nets.at(net->udata).arcs.at(user).wires.erase(wire); + } + + void ripup_arc(NetInfo *net, size_t user) + { + auto &ad = nets.at(net->udata).arcs.at(user); + for (auto &wire : ad.wires) + unbind_pip_internal(net, user, wire.first, true); + ad.wires.clear(); + } + + float score_wire_for_arc(NetInfo *net, size_t user, WireId wire, PipId pip) + { + auto &wd = wires.at(wire); + auto &nd = nets.at(net->udata); + float base_cost = ctx->getDelayNS(ctx->getPipDelay(pip).maxDelay() + ctx->getWireDelay(wire).maxDelay() + + ctx->getDelayEpsilon()); + float present_cost = present_wire_cost(wd); + float hist_cost = wd.hist_cong_cost; + float bias_cost = 0; + int source_uses = 0; + if (wd.bound_nets.count(net->udata)) + source_uses = wd.bound_nets.at(net->udata).first; + if (pip != PipId()) { + Loc pl = ctx->getPipLocation(pip); + bias_cost = 0.5f * (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; + } + ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, size_t i, bool is_mt, bool is_bb = true) { auto &usr = net->users.at(i); @@ -204,6 +293,8 @@ struct Router2 ARC_LOG_ERR("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port), ctx->nameOf(usr.cell)); + bind_pip_internal(net, i, src_wire, PipId()); + return ARC_SUCCESS; } #undef ARC_ERR -- cgit v1.2.3 From 37d57756944eadee5a31a2f6cd737a79096af631 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 8 Nov 2019 17:42:08 +0000 Subject: router2: A* main loop Signed-off-by: David Shah --- common/router2.cc | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 80 insertions(+), 8 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 48314437..b63db747 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -202,10 +202,15 @@ 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 { std::priority_queue, QueuedWire::Greater> queue; - std::unordered_map visited; + std::unordered_map visited; }; enum ArcRouteResult @@ -280,8 +285,21 @@ struct Router2 return base_cost * hist_cost * present_cost / (1 + source_uses) + bias_cost; } + float get_togo_cost(NetInfo *net, size_t user, WireId wire, WireId sink) + { + auto &wd = wires.at(wire); + int source_uses = 0; + if (wd.bound_nets.count(net->udata)) + source_uses = wd.bound_nets.at(net->udata).first; + // FIXME: timing/wirelength balance? + return ctx->getDelayNS(ctx->estimateDelay(wire, sink)) / (1 + source_uses); + } + ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, size_t i, bool is_mt, bool is_bb = true) { + + auto &nd = nets[net->udata]; + auto &ad = nd.arcs[i]; auto &usr = net->users.at(i); ROUTE_LOG_DBG("Routing arc %d of net '%s'", int(i), ctx->nameOf(net)); WireId src_wire = ctx->getNetinfoSourceWire(net), dst_wire = ctx->getNetinfoSinkWire(net, usr); @@ -292,20 +310,74 @@ struct Router2 if (dst_wire == WireId()) ARC_LOG_ERR("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port), ctx->nameOf(usr.cell)); + // Ripup arc to start with + ripup_arc(net, i); - bind_pip_internal(net, i, src_wire, PipId()); + if (!t.queue.empty()) { + std::priority_queue, QueuedWire::Greater> new_queue; + t.queue.swap(new_queue); + } + t.visited.clear(); - return ARC_SUCCESS; + // Add source wire to queue + WireScore base_score; + base_score.cost = 0; + base_score.delay = ctx->getWireDelay(src_wire).maxDelay(); + base_score.togo_cost = get_togo_cost(net, i, src_wire, dst_wire); + t.queue.push(QueuedWire(src_wire, PipId(), Loc(), base_score)); + t.visited[src_wire].score = base_score; + t.visited[src_wire].pip = PipId(); + + while (!t.queue.empty()) { + auto curr = t.queue.top(); + t.queue.pop(); + // Explore all pips downhill of cursor + for (auto dh : ctx->getPipsDownhill(curr.wire)) { + // Skip pips outside of box in bounding-box mode + if (is_bb && !hit_test_pip(ad.bb, ctx->getPipLocation(dh))) + continue; + // Evaluate score of next wire + WireId next = ctx->getPipSrcWire(dh); + WireScore next_score; + next_score.cost = curr.score.cost + score_wire_for_arc(net, i, next, dh); + next_score.delay = + curr.score.delay + ctx->getPipDelay(dh).maxDelay() + ctx->getWireDelay(next).maxDelay(); + next_score.togo_cost = get_togo_cost(net, i, next, dst_wire); + if (!t.visited.count(next) || (t.visited.at(next).score.total() > next_score.total())) { + // 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; + if (next == dst_wire) + goto loop_done; + } + } + if (0) { + loop_done: + break; + } + } + if (t.visited.count(dst_wire)) { + WireId cursor_bwd = dst_wire; + while (t.visited.count(cursor_bwd)) { + auto &v = t.visited.at(cursor_bwd); + bind_pip_internal(net, i, cursor_bwd, v.pip); + if (v.pip == PipId()) { + NPNR_ASSERT(cursor_bwd == src_wire); + break; + } + cursor_bwd = ctx->getPipSrcWire(v.pip); + } + return ARC_SUCCESS; + } else { + return ARC_RETRY_WITHOUT_BB; + } } #undef ARC_ERR bool route_net(ThreadContext &t, NetInfo *net, bool is_mt) { ROUTE_LOG_DBG("Routing net '%s'...\n", ctx->nameOf(net)); - if (!t.queue.empty()) { - std::priority_queue, QueuedWire::Greater> new_queue; - t.queue.swap(new_queue); - } - t.visited.clear(); + bool have_failures = false; for (size_t i = 0; i < net->users.size(); i++) { auto res1 = route_arc(t, net, i, is_mt, true); -- cgit v1.2.3 From 0ca07e5a6b22b9eb05ab7dde2814de8f0968f755 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 9 Nov 2019 11:45:37 +0000 Subject: router2: Add some test glue Signed-off-by: David Shah --- common/router2.cc | 97 +++++++++++++++++++++++++++++++++++++++---------------- common/router2.h | 26 +++++++++++++++ 2 files changed, 96 insertions(+), 27 deletions(-) create mode 100644 common/router2.h (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index b63db747..0e1281ee 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -38,30 +38,6 @@ NEXTPNR_NAMESPACE_BEGIN namespace { struct Router2 { - struct arc_key - { - NetInfo *net_info; - int user_idx; - - bool operator==(const arc_key &other) const - { - return (net_info == other.net_info) && (user_idx == other.user_idx); - } - bool operator<(const arc_key &other) const - { - return net_info == other.net_info ? user_idx < other.user_idx : net_info->name < other.net_info->name; - } - - struct Hash - { - std::size_t operator()(const arc_key &arg) const noexcept - { - std::size_t seed = std::hash()(arg.net_info); - seed ^= std::hash()(arg.user_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2); - return seed; - } - }; - }; struct PerArcData { @@ -295,6 +271,24 @@ struct Router2 return ctx->getDelayNS(ctx->estimateDelay(wire, sink)) / (1 + source_uses); } + bool check_arc_routing(NetInfo *net, size_t usr) + { + auto &ad = nets.at(net->udata).arcs.at(usr); + WireId src_wire = ctx->getNetinfoSourceWire(net); + WireId dst_wire = ctx->getNetinfoSinkWire(net, net->users.at(usr)); + WireId cursor = dst_wire; + while (ad.wires.count(cursor)) { + auto &wd = wires.at(cursor); + if (wd.bound_nets.size() != 1) + return false; + auto &uh = ad.wires.at(cursor); + if (uh == PipId()) + break; + cursor = ctx->getPipSrcWire(uh); + } + return (cursor == src_wire); + } + ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, size_t i, bool is_mt, bool is_bb = true) { @@ -310,6 +304,9 @@ struct Router2 if (dst_wire == WireId()) ARC_LOG_ERR("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port), ctx->nameOf(usr.cell)); + // Check if arc is already legally routed + if (check_arc_routing(net, i)) + return ARC_SUCCESS; // Ripup arc to start with ripup_arc(net, i); @@ -338,6 +335,9 @@ struct Router2 continue; // Evaluate score of next wire WireId next = ctx->getPipSrcWire(dh); + auto &nwd = wires.at(next); + if (nwd.unavailable) + continue; WireScore next_score; next_score.cost = curr.score.cost + score_wire_for_arc(net, i, next, dh); next_score.delay = @@ -352,7 +352,7 @@ struct Router2 goto loop_done; } } - if (0) { + if (false) { loop_done: break; } @@ -374,6 +374,7 @@ struct Router2 } } #undef ARC_ERR + bool route_net(ThreadContext &t, NetInfo *net, bool is_mt) { ROUTE_LOG_DBG("Routing net '%s'...\n", ctx->nameOf(net)); @@ -400,10 +401,52 @@ struct Router2 } return !have_failures; } -#undef ARC_LOG_DBG +#undef ROUTE_LOG_DBG - void bind_and_check_legality(NetInfo *net) {} + int total_wire_use = 0; + int overused_wires = 0; + int total_overuse = 0; + + void update_congestion() + { + total_overuse = 0; + overused_wires = 0; + total_wire_use = 0; + for (auto &wire : wires) { + total_wire_use += int(wire.second.bound_nets.size()); + int overuse = int(wire.second.bound_nets.size()) - 1; + if (overuse > 0) { + wire.second.hist_cong_cost += overuse * hist_cong_weight; + total_overuse += overuse; + overused_wires += 1; + } + } + } + + void router_test() + { + setup_nets(); + setup_wires(); + curr_cong_weight = 0.5; + hist_cong_weight = 1.0; + ThreadContext st; + int iter = 1; + while (total_overuse > 0) { + for (auto net : nets_by_udata) + route_net(st, net, false); + update_congestion(); + log_info("iter=%d wires=%d overused=%d overuse=%d\n", iter, total_overuse, overused_wires, total_overuse); + ++iter; + } + } }; } // namespace +void router2_test(Context *ctx) +{ + Router2 rt; + rt.ctx = ctx; + rt.router_test(); +} + NEXTPNR_NAMESPACE_END \ No newline at end of file diff --git a/common/router2.h b/common/router2.h new file mode 100644 index 00000000..da750af5 --- /dev/null +++ b/common/router2.h @@ -0,0 +1,26 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2019 David Shah + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "nextpnr.h" + +NEXTPNR_NAMESPACE_BEGIN + +void router2_test(Context *ctx); + +NEXTPNR_NAMESPACE_END \ No newline at end of file -- cgit v1.2.3 From 1c686101fcda75aee4f939bbb6d9daee4ae2b1d9 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 9 Nov 2019 13:04:33 +0000 Subject: router2: Fixes Signed-off-by: David Shah --- common/router2.cc | 33 ++++++++++++++++++++++++++++----- 1 file changed, 28 insertions(+), 5 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 0e1281ee..f89e6a8f 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -27,6 +27,7 @@ */ #include +#include #include #include #include "log.h" @@ -109,6 +110,8 @@ struct Router2 for (size_t j = 0; j < ni->users.size(); j++) { auto &usr = ni->users.at(j); WireId src_wire = ctx->getNetinfoSourceWire(ni), dst_wire = ctx->getNetinfoSinkWire(ni, usr); + if (ni->driver.cell == nullptr) + src_wire = dst_wire; if (src_wire == WireId()) log_error("No wire found for port %s on source cell %s.\n", ctx->nameOf(ni->driver.port), ctx->nameOf(ni->driver.cell)); @@ -127,7 +130,7 @@ struct Router2 } } - std::unordered_map wires; + boost::container::flat_map wires; void setup_wires() { // Set up per-wire structures, so that MT parts don't have to do any memory allocation @@ -295,7 +298,7 @@ struct Router2 auto &nd = nets[net->udata]; auto &ad = nd.arcs[i]; auto &usr = net->users.at(i); - ROUTE_LOG_DBG("Routing arc %d of net '%s'", int(i), ctx->nameOf(net)); + ROUTE_LOG_DBG("Routing arc %d of net '%s'\n", int(i), ctx->nameOf(net)); WireId src_wire = ctx->getNetinfoSourceWire(net), dst_wire = ctx->getNetinfoSinkWire(net, usr); if (src_wire == WireId()) @@ -328,13 +331,22 @@ struct Router2 while (!t.queue.empty()) { auto curr = t.queue.top(); t.queue.pop(); +#if 1 + ROUTE_LOG_DBG("current wire %s\n", ctx->nameOfWire(curr.wire)); +#endif // Explore all pips downhill of cursor for (auto dh : ctx->getPipsDownhill(curr.wire)) { // Skip pips outside of box in bounding-box mode +#if 1 + ROUTE_LOG_DBG("trying pip %s\n", ctx->nameOfPip(dh)); +#endif if (is_bb && !hit_test_pip(ad.bb, ctx->getPipLocation(dh))) continue; // Evaluate score of next wire - WireId next = ctx->getPipSrcWire(dh); + WireId next = ctx->getPipDstWire(dh); +#if 1 + ROUTE_LOG_DBG(" src wire %s\n", ctx->nameOfWire(next)); +#endif auto &nwd = wires.at(next); if (nwd.unavailable) continue; @@ -344,6 +356,10 @@ struct Router2 curr.score.delay + ctx->getPipDelay(dh).maxDelay() + ctx->getWireDelay(next).maxDelay(); next_score.togo_cost = get_togo_cost(net, i, next, dst_wire); if (!t.visited.count(next) || (t.visited.at(next).score.total() > next_score.total())) { +#if 1 + ROUTE_LOG_DBG("exploring wire %s cost %f togo %f\n", ctx->nameOfWire(next), next_score.cost, + next_score.togo_cost); +#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; @@ -358,9 +374,12 @@ struct Router2 } } if (t.visited.count(dst_wire)) { + ROUTE_LOG_DBG(" Routed: "); WireId cursor_bwd = dst_wire; while (t.visited.count(cursor_bwd)) { + ROUTE_LOG_DBG(" wire: %s\n", ctx->nameOfWire(cursor_bwd)); auto &v = t.visited.at(cursor_bwd); + ROUTE_LOG_DBG(" pip: %s\n", ctx->nameOfPip(v.pip)); bind_pip_internal(net, i, cursor_bwd, v.pip); if (v.pip == PipId()) { NPNR_ASSERT(cursor_bwd == src_wire); @@ -379,6 +398,10 @@ struct Router2 { ROUTE_LOG_DBG("Routing net '%s'...\n", ctx->nameOf(net)); + // Nothing to do if net is undriven + if (net->driver.cell == nullptr) + return true; + bool have_failures = false; for (size_t i = 0; i < net->users.size(); i++) { auto res1 = route_arc(t, net, i, is_mt, true); @@ -431,13 +454,13 @@ struct Router2 hist_cong_weight = 1.0; ThreadContext st; int iter = 1; - while (total_overuse > 0) { + do { for (auto net : nets_by_udata) route_net(st, net, false); update_congestion(); log_info("iter=%d wires=%d overused=%d overuse=%d\n", iter, total_overuse, overused_wires, total_overuse); ++iter; - } + } while (total_overuse > 0); } }; } // namespace -- cgit v1.2.3 From d5f6661bfb43dce427f11145706f1e78599f6803 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 9 Nov 2019 13:32:52 +0000 Subject: router2: Net data fixes Signed-off-by: David Shah --- common/router2.cc | 36 +++++++++++++++++++++++++++++------- 1 file changed, 29 insertions(+), 7 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index f89e6a8f..fa87b5b9 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -63,7 +63,7 @@ struct Router2 // Which net is bound in the Arch API int arch_bound_net = -1; // Historical congestion cost - float hist_cong_cost = 0; + float hist_cong_cost = 1.0; // Wire is unavailable as locked to another arc bool unavailable = false; }; @@ -106,6 +106,14 @@ struct Router2 nets.at(i).bb.x1 = std::numeric_limits::min(); nets.at(i).bb.y0 = std::numeric_limits::max(); nets.at(i).bb.y1 = std::numeric_limits::min(); + nets.at(i).cx = 0; + nets.at(i).cy = 0; + + if (ni->driver.cell != nullptr) { + Loc drv_loc = ctx->getBelLocation(ni->driver.cell->bel); + nets.at(i).cx += drv_loc.x; + nets.at(i).cy += drv_loc.y; + } for (size_t j = 0; j < ni->users.size(); j++) { auto &usr = ni->users.at(j); @@ -125,7 +133,15 @@ struct Router2 nets.at(i).bb.x1 = std::max(nets.at(i).bb.x1, nets.at(i).arcs.at(j).bb.x1); nets.at(i).bb.y0 = std::min(nets.at(i).bb.y0, nets.at(i).arcs.at(j).bb.y0); nets.at(i).bb.y1 = std::max(nets.at(i).bb.y1, nets.at(i).arcs.at(j).bb.y1); + // Add location to centroid sum + Loc usr_loc = ctx->getBelLocation(usr.cell->bel); + nets.at(i).cx += usr_loc.x; + nets.at(i).cy += usr_loc.y; } + nets.at(i).hpwl = std::min( + std::abs(nets.at(i).bb.y1 - nets.at(i).bb.y0) + std::abs(nets.at(i).bb.x1 - nets.at(i).bb.x0), 1); + nets.at(i).cx /= int(ni->users.size() + 1); + nets.at(i).cy /= int(ni->users.size() + 1); i++; } } @@ -175,7 +191,7 @@ struct Router2 bool hit_test_pip(ArcBounds &bb, Loc l) { return l.x >= (bb.x0 - bb_margin_x) && l.x <= (bb.x1 + bb_margin_x) && l.y >= (bb.y0 - bb_margin_y) && - l.y <= (bb.y1 - bb_margin_y); + l.y <= (bb.y1 + bb_margin_y); } double curr_cong_weight, hist_cong_weight, estimate_weight; @@ -307,6 +323,9 @@ struct Router2 if (dst_wire == WireId()) ARC_LOG_ERR("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port), ctx->nameOf(usr.cell)); + // Case of arcs that were pre-routed strongly (e.g. clocks) + if (net->wires.count(dst_wire) && net->wires.at(dst_wire).strength > STRENGTH_STRONG) + return ARC_SUCCESS; // Check if arc is already legally routed if (check_arc_routing(net, i)) return ARC_SUCCESS; @@ -331,32 +350,34 @@ struct Router2 while (!t.queue.empty()) { auto curr = t.queue.top(); t.queue.pop(); -#if 1 +#if 0 ROUTE_LOG_DBG("current wire %s\n", ctx->nameOfWire(curr.wire)); #endif // Explore all pips downhill of cursor for (auto dh : ctx->getPipsDownhill(curr.wire)) { // Skip pips outside of box in bounding-box mode -#if 1 +#if 0 ROUTE_LOG_DBG("trying pip %s\n", ctx->nameOfPip(dh)); #endif if (is_bb && !hit_test_pip(ad.bb, ctx->getPipLocation(dh))) continue; // Evaluate score of next wire WireId next = ctx->getPipDstWire(dh); -#if 1 +#if 0 ROUTE_LOG_DBG(" src wire %s\n", ctx->nameOfWire(next)); #endif auto &nwd = wires.at(next); if (nwd.unavailable) continue; + if (nwd.bound_nets.count(net->udata) && nwd.bound_nets.at(net->udata).second != dh) + continue; WireScore next_score; next_score.cost = curr.score.cost + score_wire_for_arc(net, i, next, dh); next_score.delay = curr.score.delay + ctx->getPipDelay(dh).maxDelay() + ctx->getWireDelay(next).maxDelay(); next_score.togo_cost = get_togo_cost(net, i, next, dst_wire); if (!t.visited.count(next) || (t.visited.at(next).score.total() > next_score.total())) { -#if 1 +#if 0 ROUTE_LOG_DBG("exploring wire %s cost %f togo %f\n", ctx->nameOfWire(next), next_score.cost, next_score.togo_cost); #endif @@ -379,12 +400,12 @@ struct Router2 while (t.visited.count(cursor_bwd)) { ROUTE_LOG_DBG(" wire: %s\n", ctx->nameOfWire(cursor_bwd)); auto &v = t.visited.at(cursor_bwd); - ROUTE_LOG_DBG(" pip: %s\n", ctx->nameOfPip(v.pip)); bind_pip_internal(net, i, cursor_bwd, v.pip); if (v.pip == PipId()) { NPNR_ASSERT(cursor_bwd == src_wire); break; } + ROUTE_LOG_DBG(" pip: %s\n", ctx->nameOfPip(v.pip)); cursor_bwd = ctx->getPipSrcWire(v.pip); } return ARC_SUCCESS; @@ -460,6 +481,7 @@ struct Router2 update_congestion(); log_info("iter=%d wires=%d overused=%d overuse=%d\n", iter, total_overuse, overused_wires, total_overuse); ++iter; + curr_cong_weight *= 2; } while (total_overuse > 0); } }; -- cgit v1.2.3 From 54ca2e9b9cc5ec0e34c9dd42f80becd03f960900 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 9 Nov 2019 14:15:09 +0000 Subject: router2: nearly there Signed-off-by: David Shah --- common/router2.cc | 29 +++++++++++++++++++++-------- 1 file changed, 21 insertions(+), 8 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index fa87b5b9..b1e108ed 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -68,12 +68,15 @@ struct Router2 bool unavailable = false; }; - float present_wire_cost(const PerWireData &w) + float present_wire_cost(const PerWireData &w, int net_uid) { - if (w.bound_nets.size() <= 1) + int other_sources = int(w.bound_nets.size()); + if (w.bound_nets.count(net_uid)) + other_sources -= 1; + if (other_sources == 0) return 1.0f; else - return 1 + (int(w.bound_nets.size()) - 1) * curr_cong_weight; + return 1 + other_sources * curr_cong_weight; } struct WireScore @@ -138,7 +141,7 @@ struct Router2 nets.at(i).cx += usr_loc.x; nets.at(i).cy += usr_loc.y; } - nets.at(i).hpwl = std::min( + nets.at(i).hpwl = std::max( std::abs(nets.at(i).bb.y1 - nets.at(i).bb.y0) + std::abs(nets.at(i).bb.x1 - nets.at(i).bb.x0), 1); nets.at(i).cx /= int(ni->users.size() + 1); nets.at(i).cy /= int(ni->users.size() + 1); @@ -206,6 +209,8 @@ struct Router2 { 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; }; enum ArcRouteResult @@ -266,7 +271,7 @@ struct Router2 auto &nd = nets.at(net->udata); float base_cost = ctx->getDelayNS(ctx->getPipDelay(pip).maxDelay() + ctx->getWireDelay(wire).maxDelay() + ctx->getDelayEpsilon()); - float present_cost = present_wire_cost(wd); + float present_cost = present_wire_cost(wd, net->udata); float hist_cost = wd.hist_cong_cost; float bias_cost = 0; int source_uses = 0; @@ -329,6 +334,10 @@ struct Router2 // Check if arc is already legally routed if (check_arc_routing(net, i)) return ARC_SUCCESS; + // Check if arc was already done _in this iteration_ + if (t.processed_sinks.count(dst_wire)) + return ARC_SUCCESS; + t.processed_sinks.insert(dst_wire); // Ripup arc to start with ripup_arc(net, i); @@ -375,7 +384,7 @@ struct Router2 next_score.cost = curr.score.cost + score_wire_for_arc(net, i, next, dh); next_score.delay = curr.score.delay + ctx->getPipDelay(dh).maxDelay() + ctx->getWireDelay(next).maxDelay(); - next_score.togo_cost = get_togo_cost(net, i, next, dst_wire); + next_score.togo_cost = 1.5 * get_togo_cost(net, i, next, dst_wire); if (!t.visited.count(next) || (t.visited.at(next).score.total() > next_score.total())) { #if 0 ROUTE_LOG_DBG("exploring wire %s cost %f togo %f\n", ctx->nameOfWire(next), next_score.cost, @@ -398,9 +407,12 @@ struct Router2 ROUTE_LOG_DBG(" Routed: "); WireId cursor_bwd = dst_wire; while (t.visited.count(cursor_bwd)) { - ROUTE_LOG_DBG(" wire: %s\n", ctx->nameOfWire(cursor_bwd)); auto &v = t.visited.at(cursor_bwd); bind_pip_internal(net, i, cursor_bwd, v.pip); + if (ctx->debug) { + auto &wd = wires.at(cursor_bwd); + ROUTE_LOG_DBG(" wire: %s (curr %d hist %f)\n", ctx->nameOfWire(cursor_bwd), int(wd.bound_nets.size()) - 1, wd.hist_cong_cost); + } if (v.pip == PipId()) { NPNR_ASSERT(cursor_bwd == src_wire); break; @@ -424,6 +436,7 @@ struct Router2 return true; bool have_failures = false; + t.processed_sinks.clear(); for (size_t i = 0; i < net->users.size(); i++) { auto res1 = route_arc(t, net, i, is_mt, true); if (res1 == ARC_FATAL) @@ -479,7 +492,7 @@ struct Router2 for (auto net : nets_by_udata) route_net(st, net, false); update_congestion(); - log_info("iter=%d wires=%d overused=%d overuse=%d\n", iter, total_overuse, overused_wires, total_overuse); + log_info("iter=%d wires=%d overused=%d overuse=%d\n", iter, total_wire_use, overused_wires, total_overuse); ++iter; curr_cong_weight *= 2; } while (total_overuse > 0); -- cgit v1.2.3 From a4ab9b19d79e10a0d83c656fa74b0eb960a8a466 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 10 Nov 2019 15:08:09 +0000 Subject: router2: Bounding box improvements Signed-off-by: David Shah --- common/router2.cc | 44 ++++++++++++++++++++++++++++++++++++-------- 1 file changed, 36 insertions(+), 8 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index b1e108ed..c8379d29 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -190,7 +190,7 @@ struct Router2 }; }; - int bb_margin_x = 3, bb_margin_y = 3; // number of units outside the bounding box we may go + int bb_margin_x = 4, bb_margin_y = 4; // number of units outside the bounding box we may go bool hit_test_pip(ArcBounds &bb, Loc l) { return l.x >= (bb.x0 - bb_margin_x) && l.x <= (bb.x1 + bb_margin_x) && l.y >= (bb.y0 - bb_margin_y) && @@ -319,7 +319,8 @@ struct Router2 auto &nd = nets[net->udata]; auto &ad = nd.arcs[i]; auto &usr = net->users.at(i); - ROUTE_LOG_DBG("Routing arc %d of net '%s'\n", int(i), ctx->nameOf(net)); + ROUTE_LOG_DBG("Routing arc %d of net '%s' (%d, %d) -> (%d, %d)\n", int(i), ctx->nameOf(net), ad.bb.x0, ad.bb.y0, + ad.bb.x1, ad.bb.y1); WireId src_wire = ctx->getNetinfoSourceWire(net), dst_wire = ctx->getNetinfoSinkWire(net, usr); if (src_wire == WireId()) @@ -337,7 +338,6 @@ struct Router2 // Check if arc was already done _in this iteration_ if (t.processed_sinks.count(dst_wire)) return ARC_SUCCESS; - t.processed_sinks.insert(dst_wire); // Ripup arc to start with ripup_arc(net, i); @@ -356,9 +356,12 @@ struct Router2 t.visited[src_wire].score = base_score; t.visited[src_wire].pip = PipId(); - while (!t.queue.empty()) { + int toexplore = 5000 * std::max(1, (ad.bb.x1 - ad.bb.x0) + (ad.bb.y1 - ad.bb.y0)); + int iter = 0; + while (!t.queue.empty() && (!is_bb || iter < toexplore)) { auto curr = t.queue.top(); t.queue.pop(); + ++iter; #if 0 ROUTE_LOG_DBG("current wire %s\n", ctx->nameOfWire(curr.wire)); #endif @@ -368,8 +371,14 @@ struct Router2 #if 0 ROUTE_LOG_DBG("trying pip %s\n", ctx->nameOfPip(dh)); #endif +#if 0 + int wire_intent = ctx->wireIntent(curr.wire); + if (is_bb && !hit_test_pip(ad.bb, ctx->getPipLocation(dh)) && wire_intent != ID_PSEUDO_GND && wire_intent != ID_PSEUDO_VCC) + continue; +#else if (is_bb && !hit_test_pip(ad.bb, ctx->getPipLocation(dh))) continue; +#endif // Evaluate score of next wire WireId next = ctx->getPipDstWire(dh); #if 0 @@ -411,15 +420,18 @@ struct Router2 bind_pip_internal(net, i, cursor_bwd, v.pip); if (ctx->debug) { auto &wd = wires.at(cursor_bwd); - ROUTE_LOG_DBG(" wire: %s (curr %d hist %f)\n", ctx->nameOfWire(cursor_bwd), int(wd.bound_nets.size()) - 1, wd.hist_cong_cost); + ROUTE_LOG_DBG(" wire: %s (curr %d hist %f)\n", ctx->nameOfWire(cursor_bwd), + int(wd.bound_nets.size()) - 1, wd.hist_cong_cost); } if (v.pip == PipId()) { NPNR_ASSERT(cursor_bwd == src_wire); break; } - ROUTE_LOG_DBG(" pip: %s\n", ctx->nameOfPip(v.pip)); + ROUTE_LOG_DBG(" pip: %s (%d, %d)\n", ctx->nameOfPip(v.pip), ctx->getPipLocation(v.pip).x, + ctx->getPipLocation(v.pip).y); cursor_bwd = ctx->getPipSrcWire(v.pip); } + t.processed_sinks.insert(dst_wire); return ARC_SUCCESS; } else { return ARC_RETRY_WITHOUT_BB; @@ -463,12 +475,15 @@ struct Router2 int total_wire_use = 0; int overused_wires = 0; int total_overuse = 0; + std::vector route_queue; + std::set congested_nets; void update_congestion() { total_overuse = 0; overused_wires = 0; total_wire_use = 0; + congested_nets.clear(); for (auto &wire : wires) { total_wire_use += int(wire.second.bound_nets.size()); int overuse = int(wire.second.bound_nets.size()) - 1; @@ -476,6 +491,8 @@ struct Router2 wire.second.hist_cong_cost += overuse * hist_cong_weight; total_overuse += overuse; overused_wires += 1; + for (auto &bound : wire.second.bound_nets) + congested_nets.insert(bound.first); } } } @@ -488,10 +505,21 @@ struct Router2 hist_cong_weight = 1.0; ThreadContext st; int iter = 1; + + for (size_t i = 0; i < nets_by_udata.size(); i++) + route_queue.push_back(i); + do { - for (auto net : nets_by_udata) - route_net(st, net, false); + ctx->sorted_shuffle(route_queue); + for (size_t j = 0; j < route_queue.size(); j++) { + route_net(st, nets_by_udata[route_queue[j]], false); + if ((j % 1000) == 0 || j == (route_queue.size() - 1)) + log(" routed %d/%d\n", int(j), int(route_queue.size())); + } + route_queue.clear(); update_congestion(); + for (auto cn : congested_nets) + route_queue.push_back(cn); log_info("iter=%d wires=%d overused=%d overuse=%d\n", iter, total_wire_use, overused_wires, total_overuse); ++iter; curr_cong_weight *= 2; -- cgit v1.2.3 From 599236bbc6dda7f7f45d522775a603303a28ea60 Mon Sep 17 00:00:00 2001 From: David Shah Date: Mon, 11 Nov 2019 12:57:05 +0000 Subject: router2: Special backwards mode for gnd/vcc-like nets Signed-off-by: David Shah --- common/router2.cc | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 67 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index c8379d29..05e4e98b 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -211,6 +211,10 @@ struct Router2 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; }; enum ArcRouteResult @@ -345,18 +349,78 @@ struct Router2 std::priority_queue, QueuedWire::Greater> new_queue; t.queue.swap(new_queue); } - t.visited.clear(); + if (!t.backwards_queue.empty()) { + std::queue new_queue; + t.backwards_queue.swap(new_queue); + } + // First try strongly iteration-limited routing backwards BFS + // this will deal with certain nets faster than forward A* + // and comes at a minimal performance cost for the others + // This could also be used to speed up forwards routing by a hybrid + // bidirectional approach + int backwards_iter = 0; + int backwards_limit = 125; + 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(); + t.backwards_queue.pop(); + auto &cwd = wires.at(cursor); + PipId cpip; + if (cwd.bound_nets.count(net->udata)) + cpip = cwd.bound_nets.at(net->udata).second; + bool did_something = false; + for (auto uh : ctx->getPipsUphill(cursor)) { + did_something = true; + 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)) + continue; // skip wires that have already been visited + auto &wd = wires.at(next); + if (wd.unavailable) + continue; + 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; + } + if (did_something) + ++backwards_iter; + } + // Check if backwards routing succeeded in reaching source + if (t.backwards_pip.count(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); + if (ctx->debug) { + auto &wd = wires.at(cursor_fwd); + ROUTE_LOG_DBG(" wire: %s (curr %d hist %f)\n", ctx->nameOfWire(cursor_fwd), + int(wd.bound_nets.size()) - 1, wd.hist_cong_cost); + } + } + NPNR_ASSERT(cursor_fwd == dst_wire); + t.processed_sinks.insert(dst_wire); + return ARC_SUCCESS; + } - // Add source wire to queue + // Normal forwards A* routing + t.visited.clear(); WireScore base_score; base_score.cost = 0; base_score.delay = ctx->getWireDelay(src_wire).maxDelay(); base_score.togo_cost = get_togo_cost(net, i, src_wire, dst_wire); + + // 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(); - int toexplore = 5000 * std::max(1, (ad.bb.x1 - ad.bb.x0) + (ad.bb.y1 - ad.bb.y0)); + int toexplore = 25000 * std::max(1, (ad.bb.x1 - ad.bb.x0) + (ad.bb.y1 - ad.bb.y0)); int iter = 0; while (!t.queue.empty() && (!is_bb || iter < toexplore)) { auto curr = t.queue.top(); -- cgit v1.2.3 From fa217a50a5aa9b1a915728bea035e368a376ceee Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 15 Nov 2019 11:30:39 +0000 Subject: router2: Binding nextpnr wires/pips Signed-off-by: David Shah --- common/router2.cc | 96 +++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 90 insertions(+), 6 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 05e4e98b..b6875ef0 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -372,6 +372,8 @@ struct Router2 bool did_something = false; for (auto uh : ctx->getPipsUphill(cursor)) { did_something = true; + if (!ctx->checkPipAvail(uh) && ctx->getBoundPipNet(uh) != net) + continue; if (cpip != PipId() && cpip != uh) continue; // don't allow multiple pips driving a wire with a net WireId next = ctx->getPipSrcWire(uh); @@ -442,6 +444,8 @@ struct Router2 #else if (is_bb && !hit_test_pip(ad.bb, ctx->getPipLocation(dh))) continue; + if (!ctx->checkPipAvail(dh) && ctx->getBoundPipNet(dh) != net) + continue; #endif // Evaluate score of next wire WireId next = ctx->getPipDstWire(dh); @@ -540,14 +544,14 @@ struct Router2 int overused_wires = 0; int total_overuse = 0; std::vector route_queue; - std::set congested_nets; + std::set failed_nets; void update_congestion() { total_overuse = 0; overused_wires = 0; total_wire_use = 0; - congested_nets.clear(); + failed_nets.clear(); for (auto &wire : wires) { total_wire_use += int(wire.second.bound_nets.size()); int overuse = int(wire.second.bound_nets.size()) - 1; @@ -556,11 +560,86 @@ struct Router2 total_overuse += overuse; overused_wires += 1; for (auto &bound : wire.second.bound_nets) - congested_nets.insert(bound.first); + failed_nets.insert(bound.first); } } } + bool bind_and_check(NetInfo *net, int usr_idx) + { + bool success = true; + auto &nd = nets.at(net->udata); + auto &ad = nd.arcs.at(usr_idx); + auto &usr = net->users.at(usr_idx); + WireId src = ctx->getNetinfoSourceWire(net); + WireId dst = ctx->getNetinfoSinkWire(net, usr); + WireId cursor = dst; + + std::vector to_bind; + + while (cursor != src) { + if (!ctx->checkWireAvail(cursor)) { + if (ctx->getBoundWireNet(cursor) == net) + break; // hit the part of the net that is already bound + else { + success = false; + break; + } + } + if (!ad.wires.count(cursor)) { + log("Failure details:\n"); + log(" Cursor: %s\n", ctx->nameOfWire(cursor)); + log(" route backtrace: \n"); + for (auto w : ad.wires) + log(" %s: %s (src: %s)\n", ctx->nameOfWire(w.first), ctx->nameOfPip(w.second), + ctx->nameOfWire(ctx->getPipSrcWire(w.second))); + log_error("Internal error; incomplete route tree for arc %d of net %s.\n", usr_idx, ctx->nameOf(net)); + } + auto &p = ad.wires.at(cursor); + if (!ctx->checkPipAvail(p)) { + success = false; + break; + } else { + to_bind.push_back(p); + } + cursor = ctx->getPipSrcWire(p); + } + + if (success) { + if (ctx->getBoundWireNet(src) == nullptr) + ctx->bindWire(src, net, STRENGTH_WEAK); + for (auto tb : to_bind) + ctx->bindPip(tb, net, STRENGTH_WEAK); + } else { + ripup_arc(net, usr_idx); + failed_nets.insert(net->udata); + } + return success; + } + + int arch_fail = 0; + bool bind_and_check_all() + { + bool success = true; + std::vector net_wires; + for (auto net : nets_by_udata) { + // Ripup wires and pips used by the net in nextpnr's structures + net_wires.clear(); + for (auto &w : net->wires) + net_wires.push_back(w.first); + for (auto w : net_wires) + ctx->unbindWire(w); + // Bind the arcs using the routes we have discovered + for (size_t i = 0; i < net->users.size(); i++) { + if (!bind_and_check(net, i)) { + ++arch_fail; + success = false; + } + } + } + return success; + } + void router_test() { setup_nets(); @@ -582,12 +661,17 @@ struct Router2 } route_queue.clear(); update_congestion(); - for (auto cn : congested_nets) + if (overused_wires == 0) { + // Try and actually bind nextpnr Arch API wires + bind_and_check_all(); + } + for (auto cn : failed_nets) route_queue.push_back(cn); - log_info("iter=%d wires=%d overused=%d overuse=%d\n", iter, total_wire_use, overused_wires, total_overuse); + log_info("iter=%d wires=%d overused=%d overuse=%d archfail=%s\n", iter, total_wire_use, overused_wires, + total_overuse, overused_wires > 0 ? "NA" : std::to_string(arch_fail).c_str()); ++iter; curr_cong_weight *= 2; - } while (total_overuse > 0); + } while (!failed_nets.empty()); } }; } // namespace -- cgit v1.2.3 From 385380401afb9f2f5cbfef766be30f39c3bbd34b Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 15 Nov 2019 11:38:11 +0000 Subject: router2: Deal with some special cases Signed-off-by: David Shah --- common/router2.cc | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index b6875ef0..152878c6 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -572,7 +572,17 @@ struct Router2 auto &ad = nd.arcs.at(usr_idx); auto &usr = net->users.at(usr_idx); WireId src = ctx->getNetinfoSourceWire(net); + // Skip routes with no source + if (src == WireId()) + return true; WireId dst = ctx->getNetinfoSinkWire(net, usr); + // Skip routes where the destination is already bound + if (dst == WireId() || ctx->getBoundWireNet(dst) == net) + return true; + // Skip routes where there is no routing (special cases) + if (ad.wires.empty()) + return true; + WireId cursor = dst; std::vector to_bind; -- cgit v1.2.3 From abdaa9c8a1953bc1a48fd5d141fc6ce7bf86fdfd Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 16 Nov 2019 11:04:39 +0000 Subject: ecp5: Router2 test integration Signed-off-by: David Shah --- common/nextpnr.h | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) (limited to 'common') diff --git a/common/nextpnr.h b/common/nextpnr.h index 61e04415..a786608d 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -199,6 +199,28 @@ struct Loc bool operator!=(const Loc &other) const { return (x != other.x) || (y != other.y) || (z != other.z); } }; +struct ArcBounds +{ + int x0 = -1, y0 = -1, x1 = -1, y1 = -1; + + ArcBounds() {} + ArcBounds(int x0, int y0, int x1, int y1) : x0(x0), y0(y0), x1(x1), y1(y1){}; + + int distance(Loc loc) const + { + int dist = 0; + if (loc.x < x0) + dist += x0 - loc.x; + if (loc.x > x1) + dist += loc.x - x1; + if (loc.y < y0) + dist += y0 - loc.y; + if (loc.y > y1) + dist += loc.y - y1; + return dist; + }; +}; + struct TimingConstrObjectId { int32_t index = -1; -- cgit v1.2.3 From a8351b265fb7a8ddf91b78edb2d5ae0a39384c8b Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 16 Nov 2019 12:07:17 +0000 Subject: router2: Changes for ECP5 Signed-off-by: David Shah --- common/router2.cc | 20 +++++++++++++++++++- 1 file changed, 19 insertions(+), 1 deletion(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 152878c6..b189c6d1 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -145,6 +145,10 @@ struct Router2 std::abs(nets.at(i).bb.y1 - nets.at(i).bb.y0) + std::abs(nets.at(i).bb.x1 - nets.at(i).bb.x0), 1); nets.at(i).cx /= int(ni->users.size() + 1); nets.at(i).cy /= int(ni->users.size() + 1); + if (ctx->debug) + log_info("%s: bb=(%d, %d)->(%d, %d) c=(%d, %d) hpwl=%d\n", ctx->nameOf(ni), nets.at(i).bb.x0, + nets.at(i).bb.y0, nets.at(i).bb.x1, nets.at(i).bb.y1, nets.at(i).cx, nets.at(i).cy, + nets.at(i).hpwl); i++; } } @@ -359,7 +363,7 @@ struct Router2 // This could also be used to speed up forwards routing by a hybrid // bidirectional approach int backwards_iter = 0; - int backwards_limit = 125; + int backwards_limit = 10; t.backwards_pip.clear(); t.backwards_queue.push(dst_wire); while (!t.backwards_queue.empty() && backwards_iter < backwards_limit) { @@ -509,6 +513,12 @@ struct Router2 bool route_net(ThreadContext &t, NetInfo *net, bool is_mt) { + +#ifdef ARCH_ECP5 + if (net->is_global) + return true; +#endif + ROUTE_LOG_DBG("Routing net '%s'...\n", ctx->nameOf(net)); // Nothing to do if net is undriven @@ -567,6 +577,10 @@ struct Router2 bool bind_and_check(NetInfo *net, int usr_idx) { +#ifdef ARCH_ECP5 + if (net->is_global) + return true; +#endif bool success = true; auto &nd = nets.at(net->udata); auto &ad = nd.arcs.at(usr_idx); @@ -633,6 +647,10 @@ struct Router2 bool success = true; std::vector net_wires; for (auto net : nets_by_udata) { +#ifdef ARCH_ECP5 + if (net->is_global) + continue; +#endif // Ripup wires and pips used by the net in nextpnr's structures net_wires.clear(); for (auto &w : net->wires) -- cgit v1.2.3 From 010e7ba8cbff440c10b4482da4e0f9bf4a9210fa Mon Sep 17 00:00:00 2001 From: David Shah Date: Mon, 18 Nov 2019 15:23:47 +0000 Subject: router2: Add IPIN cost to model Signed-off-by: David Shah --- common/router2.cc | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index b189c6d1..ee298ae4 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -300,7 +300,9 @@ struct Router2 if (wd.bound_nets.count(net->udata)) source_uses = wd.bound_nets.at(net->udata).first; // FIXME: timing/wirelength balance? - return ctx->getDelayNS(ctx->estimateDelay(wire, sink)) / (1 + source_uses); + float ipin_cost = ctx->getDelayNS(ctx->getWireDelay(sink).maxDelay() + ctx->getDelayEpsilon()); + return std::max(0.0f, ctx->getDelayNS(ctx->estimateDelay(wire, sink)) - ipin_cost) / (1 + source_uses) + + ipin_cost; } bool check_arc_routing(NetInfo *net, size_t usr) -- cgit v1.2.3 From c21db8a0c1ea94fc042e77311840c15bb5703023 Mon Sep 17 00:00:00 2001 From: David Shah Date: Mon, 18 Nov 2019 16:06:47 +0000 Subject: router2: Congestion map generation Signed-off-by: David Shah --- common/router2.cc | 46 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 46 insertions(+) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index ee298ae4..67c6dae2 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -29,6 +29,7 @@ #include #include #include +#include #include #include "log.h" #include "nextpnr.h" @@ -670,6 +671,45 @@ struct Router2 return success; } + void write_heatmap(std::ostream &out, bool congestion = false) + { + std::vector> hm_xy; + int max_x = 0, max_y = 0; + for (auto &w : wires) { + auto &wd = w.second; + int val = int(wd.bound_nets.size()) - (congestion ? 1 : 0); + if (wd.bound_nets.empty()) + continue; + // Estimate wire location by driving pip location + PipId drv; + for (auto &bn : wd.bound_nets) + if (bn.second.second != PipId()) { + drv = bn.second.second; + break; + } + if (drv == PipId()) + continue; + Loc l = ctx->getPipLocation(drv); + max_x = std::max(max_x, l.x); + max_y = std::max(max_y, l.y); + if (l.y >= int(hm_xy.size())) + hm_xy.resize(l.y + 1); + if (l.x >= int(hm_xy.at(l.y).size())) + hm_xy.at(l.y).resize(l.x + 1); + if (val > 0) + hm_xy.at(l.y).at(l.x) += val; + } + for (int y = 0; y <= max_y; y++) { + for (int x = 0; x <= max_x; x++) { + if (y >= int(hm_xy.size()) || x >= int(hm_xy.at(y).size())) + out << "0,"; + else + out << hm_xy.at(y).at(x) << ","; + } + out << std::endl; + } + } + void router_test() { setup_nets(); @@ -691,6 +731,12 @@ struct Router2 } route_queue.clear(); update_congestion(); +#if 1 + if (iter == 1 && ctx->debug) { + std::ofstream cong_map("cong_map_0.csv"); + write_heatmap(cong_map, true); + } +#endif if (overused_wires == 0) { // Try and actually bind nextpnr Arch API wires bind_and_check_all(); -- cgit v1.2.3 From 72f4721167c14024dc00a83f2d3c13380a34b6fe Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 19 Nov 2019 10:42:43 +0000 Subject: router2: Some simple partitioning Signed-off-by: David Shah --- common/router2.cc | 44 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 67c6dae2..d513a08c 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -710,10 +710,54 @@ struct Router2 } } + void partition_nets() + { + // Create a histogram of positions in X and Y positions + std::map cxs, cys; + for (auto &n : nets) { + if (n.cx != -1) + ++cxs[n.cx]; + if (n.cy != -1) + ++cys[n.cy]; + } + // 4-way split for now + int accum_x = 0, accum_y = 0; + int mid_x = 0, mid_y = 0; + int halfway = int(nets.size()) / 2; + for (auto &p : cxs) { + if (accum_x < halfway && (accum_x + p.second) >= halfway) + mid_x = p.first; + accum_x += p.second; + } + for (auto &p : cys) { + if (accum_y < halfway && (accum_y + p.second) >= halfway) + mid_y = p.first; + accum_y += p.second; + } + log_info("x splitpoint: %d\n", mid_x); + log_info("y splitpoint: %d\n", mid_y); + std::vector bins(5, 0); + for (auto &n : nets) { + if (n.bb.x0 < mid_x && n.bb.x1 < mid_x && n.bb.y0 < mid_y && n.bb.y1 < mid_y) + ++bins[0]; // TL + else if (n.bb.x0 >= mid_x && n.bb.x1 >= mid_x && n.bb.y0 < mid_y && n.bb.y1 < mid_y) + ++bins[1]; // TR + else if (n.bb.x0 < mid_x && n.bb.x1 < mid_x && n.bb.y0 >= mid_y && n.bb.y1 >= mid_y) + ++bins[2]; // BL + else if (n.bb.x0 >= mid_x && n.bb.x1 >= mid_x && n.bb.y0 >= mid_y && n.bb.y1 >= mid_y) + ++bins[3]; // BR + else + ++bins[4]; // cross-boundary + } + for (int i = 0; i < 5; i++) + log_info("bin %d N=%d\n", i, bins[i]); + } + void router_test() { setup_nets(); setup_wires(); + partition_nets(); curr_cong_weight = 0.5; hist_cong_weight = 1.0; ThreadContext st; -- cgit v1.2.3 From 39b75244dae48f417522fd902227574debf889cb Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 19 Nov 2019 12:21:40 +0000 Subject: router2: Working on multithreading Signed-off-by: David Shah --- common/router2.cc | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 59 insertions(+), 1 deletion(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index d513a08c..e1ed430c 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -31,6 +31,7 @@ #include #include #include +#include #include "log.h" #include "nextpnr.h" #include "util.h" @@ -212,6 +213,11 @@ struct Router2 }; struct ThreadContext { + // Nets to route + std::vector route_nets; + // Nets that failed routing + std::vector failed_nets; + std::priority_queue, QueuedWire::Greater> queue; std::unordered_map visited; // Special case where one net has multiple logical arcs to the same physical sink @@ -709,6 +715,7 @@ struct Router2 out << std::endl; } } + int mid_x = 0, mid_y = 0; void partition_nets() { @@ -722,7 +729,6 @@ struct Router2 } // 4-way split for now int accum_x = 0, accum_y = 0; - int mid_x = 0, mid_y = 0; int halfway = int(nets.size()) / 2; for (auto &p : cxs) { if (accum_x < halfway && (accum_x + p.second) >= halfway) @@ -753,6 +759,55 @@ struct Router2 log_info("bin %d N=%d\n", i, bins[i]); } + void router_thread(ThreadContext &t) + { + for (auto n : t.route_nets) { + bool result = route_net(t, n, true); + if (!result) + t.failed_nets.push_back(n); + } + } + + void do_route() + { + const int N = 4; + std::vector tcs(N + 1); + for (auto n : route_queue) { + auto &nd = nets.at(n); + auto ni = nets_by_udata.at(n); + int bin = N; + int le_x = mid_x - bb_margin_x; + int rs_x = mid_x + bb_margin_x; + int le_y = mid_y - bb_margin_y; + int rs_y = mid_y + bb_margin_y; + + if (nd.bb.x0 < le_x && nd.bb.x1 < le_x && nd.bb.y0 < le_y && nd.bb.y1 < le_y) + bin = 0; + else if (nd.bb.x0 >= rs_x && nd.bb.x1 >= rs_x && nd.bb.y0 < le_y && nd.bb.y1 < le_y) + bin = 1; + else if (nd.bb.x0 < le_x && nd.bb.x1 < le_x && nd.bb.y0 >= rs_y && nd.bb.y1 >= rs_y) + bin = 2; + else if (nd.bb.x0 >= rs_x && nd.bb.x1 >= rs_x && nd.bb.y0 >= rs_y && nd.bb.y1 >= rs_y) + bin = 3; + tcs.at(bin).route_nets.push_back(ni); + } + // Multithreaded part of routing + std::vector threads; + for (int i = 0; i < N; i++) { + threads.emplace_back([&]() { router_thread(tcs.at(i)); }); + } + for (int i = 0; i < N; i++) + threads.at(i).join(); + // Singlethreaded part of routing - nets that cross partitions + // or don't fit within bounding box + for (auto st_net : tcs.at(N).route_nets) + route_net(tcs.at(N), st_net, false); + // Failed nets + for (int i = 0; i < N; i++) + for (auto fail : tcs.at(i).failed_nets) + route_net(tcs.at(N), fail, false); + } + void router_test() { setup_nets(); @@ -768,11 +823,14 @@ struct Router2 do { ctx->sorted_shuffle(route_queue); +#if 0 for (size_t j = 0; j < route_queue.size(); j++) { route_net(st, nets_by_udata[route_queue[j]], false); if ((j % 1000) == 0 || j == (route_queue.size() - 1)) log(" routed %d/%d\n", int(j), int(route_queue.size())); } +#endif + do_route(); route_queue.clear(); update_congestion(); #if 1 -- cgit v1.2.3 From 3b28ba2f76c519145795b1b330fda5851d8f38ca Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 19 Nov 2019 12:28:44 +0000 Subject: router2: Debugging Signed-off-by: David Shah --- common/router2.cc | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index e1ed430c..1cb04f9f 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -791,10 +791,11 @@ struct Router2 bin = 3; tcs.at(bin).route_nets.push_back(ni); } + log_info("%d/%d nets not multi-threadable\n", int(tcs.at(N).route_nets.size()), int(route_queue.size())); // Multithreaded part of routing std::vector threads; for (int i = 0; i < N; i++) { - threads.emplace_back([&]() { router_thread(tcs.at(i)); }); + threads.emplace_back([this, &tcs, i]() { router_thread(tcs.at(i)); }); } for (int i = 0; i < N; i++) threads.at(i).join(); -- cgit v1.2.3 From ffd679cd368225cde6621efd78bea89a034cfc1c Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 19 Nov 2019 15:41:16 +0000 Subject: router2: Attempt to fix some stuck routing cases Signed-off-by: David Shah --- common/router2.cc | 35 ++++++++++++++++++++++++++--------- 1 file changed, 26 insertions(+), 9 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 1cb04f9f..0782c403 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -196,7 +196,7 @@ struct Router2 }; }; - int bb_margin_x = 4, bb_margin_y = 4; // number of units outside the bounding box we may go + int bb_margin_x = 2, bb_margin_y = 2; // number of units outside the bounding box we may go bool hit_test_pip(ArcBounds &bb, Loc l) { return l.x >= (bb.x0 - bb_margin_x) && l.x <= (bb.x1 + bb_margin_x) && l.y >= (bb.y0 - bb_margin_y) && @@ -218,6 +218,8 @@ struct Router2 // Nets that failed routing std::vector failed_nets; + 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 @@ -346,17 +348,9 @@ struct Router2 if (dst_wire == WireId()) ARC_LOG_ERR("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port), ctx->nameOf(usr.cell)); - // Case of arcs that were pre-routed strongly (e.g. clocks) - if (net->wires.count(dst_wire) && net->wires.at(dst_wire).strength > STRENGTH_STRONG) - return ARC_SUCCESS; - // Check if arc is already legally routed - if (check_arc_routing(net, i)) - return ARC_SUCCESS; // Check if arc was already done _in this iteration_ if (t.processed_sinks.count(dst_wire)) return ARC_SUCCESS; - // Ripup arc to start with - ripup_arc(net, i); if (!t.queue.empty()) { std::priority_queue, QueuedWire::Greater> new_queue; @@ -536,7 +530,22 @@ struct Router2 bool have_failures = false; t.processed_sinks.clear(); + t.route_arcs.clear(); for (size_t i = 0; i < net->users.size(); i++) { + // Ripup failed arcs to start with + // Check if arc is already legally routed + if (check_arc_routing(net, i)) + continue; + auto &usr = net->users.at(i); + WireId dst_wire = ctx->getNetinfoSinkWire(net, usr); + // Case of arcs that were pre-routed strongly (e.g. clocks) + if (net->wires.count(dst_wire) && net->wires.at(dst_wire).strength > STRENGTH_STRONG) + return ARC_SUCCESS; + // Ripup arc to start with + ripup_arc(net, i); + t.route_arcs.push_back(i); + } + for (auto i : t.route_arcs) { auto res1 = route_arc(t, net, i, is_mt, true); if (res1 == ARC_FATAL) return false; // Arc failed irrecoverably @@ -770,6 +779,14 @@ struct Router2 void do_route() { + // Don't multithread if fewer than 200 nets (heuristic) + if (route_queue.size() < 200) { + ThreadContext st; + for (size_t j = 0; j < route_queue.size(); j++) { + route_net(st, nets_by_udata[route_queue[j]], false); + } + return; + } const int N = 4; std::vector tcs(N + 1); for (auto n : route_queue) { -- cgit v1.2.3 From 363d664f273976e1d1e23bd272329dbff3c858ce Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 20 Nov 2019 11:46:14 +0000 Subject: router2: tweaks Signed-off-by: David Shah --- common/router2.cc | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 0782c403..fcd52bb3 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -196,7 +196,7 @@ struct Router2 }; }; - int bb_margin_x = 2, bb_margin_y = 2; // number of units outside the bounding box we may go + int bb_margin_x = 4, bb_margin_y = 4; // number of units outside the bounding box we may go bool hit_test_pip(ArcBounds &bb, Loc l) { return l.x >= (bb.x0 - bb_margin_x) && l.x <= (bb.x1 + bb_margin_x) && l.y >= (bb.y0 - bb_margin_y) && @@ -671,8 +671,10 @@ struct Router2 #endif // Ripup wires and pips used by the net in nextpnr's structures net_wires.clear(); - for (auto &w : net->wires) - net_wires.push_back(w.first); + for (auto &w : net->wires) { + if (w.second.strength <= STRENGTH_STRONG) + net_wires.push_back(w.first); + } for (auto w : net_wires) ctx->unbindWire(w); // Bind the arcs using the routes we have discovered -- cgit v1.2.3 From 59c554b50ad599cbfc6f832b6942075efe3a0dbe Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 20 Nov 2019 15:13:28 +0000 Subject: router2: Improve backwards routing of some cases Signed-off-by: David Shah --- common/router2.cc | 28 +++++++++++++++++++++++++++- 1 file changed, 27 insertions(+), 1 deletion(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index fcd52bb3..271595ad 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -374,8 +374,34 @@ struct Router2 t.backwards_queue.pop(); auto &cwd = wires.at(cursor); PipId cpip; - if (cwd.bound_nets.count(net->udata)) + if (cwd.bound_nets.count(net->udata)) { + // If we can tack onto existing routing; try that + // Only do this if the existing routing is uncontented; however + WireId cursor2 = cursor; + bool bwd_merge_fail = false; + while (wires.at(cursor2).bound_nets.count(net->udata)) { + if (wires.at(cursor2).bound_nets.size() > 1) { + bwd_merge_fail = true; + break; + } + PipId p = wires.at(cursor2).bound_nets.at(net->udata).second; + if (p == PipId()) + break; + cursor2 = ctx->getPipSrcWire(p); + } + if (!bwd_merge_fail && cursor2 == src_wire) { + // Found a path to merge to existing routing; backwards + cursor2 = cursor; + while (wires.at(cursor2).bound_nets.count(net->udata)) { + PipId p = wires.at(cursor2).bound_nets.at(net->udata).second; + if (p == PipId()) + break; + cursor2 = ctx->getPipSrcWire(p); + t.backwards_pip[cursor2] = p; + } + } cpip = cwd.bound_nets.at(net->udata).second; + } bool did_something = false; for (auto uh : ctx->getPipsUphill(cursor)) { did_something = true; -- cgit v1.2.3 From bbc9c9b0ba0a326856daabc30f0ca1fc8d6ddee0 Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 20 Nov 2019 16:01:53 +0000 Subject: router2: speedup Signed-off-by: David Shah --- common/router2.cc | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 271595ad..7e45c122 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -399,6 +399,7 @@ struct Router2 cursor2 = ctx->getPipSrcWire(p); t.backwards_pip[cursor2] = p; } + break; } cpip = cwd.bound_nets.at(net->udata).second; } @@ -494,7 +495,7 @@ struct Router2 next_score.cost = curr.score.cost + score_wire_for_arc(net, i, next, dh); next_score.delay = curr.score.delay + ctx->getPipDelay(dh).maxDelay() + ctx->getWireDelay(next).maxDelay(); - next_score.togo_cost = 1.5 * get_togo_cost(net, i, next, dst_wire); + 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())) { #if 0 ROUTE_LOG_DBG("exploring wire %s cost %f togo %f\n", ctx->nameOfWire(next), next_score.cost, -- cgit v1.2.3 From 50b120528a1744e64eeb6a886dc392793a4659ab Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 29 Nov 2019 11:37:04 +0000 Subject: router2: debugging some edge cases Signed-off-by: David Shah --- common/router2.cc | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 7e45c122..c992f274 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -155,7 +155,7 @@ struct Router2 } } - boost::container::flat_map wires; + std::unordered_map wires; void setup_wires() { // Set up per-wire structures, so that MT parts don't have to do any memory allocation @@ -458,6 +458,7 @@ struct Router2 int toexplore = 25000 * std::max(1, (ad.bb.x1 - ad.bb.x0) + (ad.bb.y1 - ad.bb.y0)); int iter = 0; + int explored = 1; while (!t.queue.empty() && (!is_bb || iter < toexplore)) { auto curr = t.queue.top(); t.queue.pop(); @@ -497,6 +498,7 @@ struct Router2 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())) { + ++explored; #if 0 ROUTE_LOG_DBG("exploring wire %s cost %f togo %f\n", ctx->nameOfWire(next), next_score.cost, next_score.togo_cost); @@ -505,25 +507,23 @@ struct Router2 t.queue.push(QueuedWire(next, dh, ctx->getPipLocation(dh), next_score, ctx->rng())); t.visited[next].score = next_score; t.visited[next].pip = dh; - if (next == dst_wire) - goto loop_done; + if (next == dst_wire) { + toexplore = std::min(toexplore, iter + 5); + } } } - if (false) { - loop_done: - break; - } } if (t.visited.count(dst_wire)) { - ROUTE_LOG_DBG(" Routed: "); + 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); bind_pip_internal(net, i, cursor_bwd, v.pip); if (ctx->debug) { auto &wd = wires.at(cursor_bwd); - ROUTE_LOG_DBG(" wire: %s (curr %d hist %f)\n", ctx->nameOfWire(cursor_bwd), - int(wd.bound_nets.size()) - 1, wd.hist_cong_cost); + ROUTE_LOG_DBG(" wire: %s (curr %d hist %f share %d)\n", ctx->nameOfWire(cursor_bwd), + int(wd.bound_nets.size()) - 1, wd.hist_cong_cost, + wd.bound_nets.count(net->udata) ? wd.bound_nets.at(net->udata).first : 0); } if (v.pip == PipId()) { NPNR_ASSERT(cursor_bwd == src_wire); -- cgit v1.2.3 From 3d739b5916277357283da225d98255aaad85e70c Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 3 Dec 2019 13:44:16 +0000 Subject: router2: first pass at reserved wires Signed-off-by: David Shah --- common/router2.cc | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 65 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index c992f274..496a4bfc 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -62,12 +62,12 @@ struct Router2 { // net --> number of arcs; driving pip std::unordered_map> bound_nets; - // Which net is bound in the Arch API - int arch_bound_net = -1; // 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; }; float present_wire_cost(const PerWireData &w, int net_uid) @@ -165,7 +165,6 @@ struct Router2 NetInfo *bound = ctx->getBoundWireNet(wire); if (bound != nullptr) { wires[wire].bound_nets[bound->udata] = std::make_pair(1, bound->wires.at(wire).pip); - wires[wire].arch_bound_net = bound->udata; if (bound->wires.at(wire).strength > STRENGTH_STRONG) wires[wire].unavailable = true; } @@ -332,6 +331,64 @@ struct Router2 return (cursor == src_wire); } + // Returns true if a wire contains no source ports or driving pips + bool is_wire_undriveable(WireId wire) + { + for (auto bp : ctx->getWireBelPins(wire)) + if (ctx->getBelPinType(bp.bel, bp.pin) != PORT_IN) + return false; + for (auto p : ctx->getPipsUphill(wire)) + return false; + return true; + } + + // Find all the wires that must be used to route a given arc + void reserve_wires_for_arc(NetInfo *net, size_t i) + { + // This is slightly tricky, because of the possibility of "diamonds" + // eg /--C--\\ + // sink ----B----D--... + // we need to discover that D is a reserved wire; despite the branch and choice of B/C + WireId src = ctx->getNetinfoSourceWire(net); + WireId sink = ctx->getNetinfoSinkWire(net, net->users.at(i)); + if (sink == WireId()) + return; + std::unordered_set rsv; + WireId cursor = sink; + bool done = false; + while (!done) { + auto &wd = wires.at(cursor); + wd.reserved_net = net->udata; + if (cursor == src) + break; + WireId next_cursor; + for (auto uh : ctx->getPipsUphill(cursor)) { + WireId w = ctx->getPipSrcWire(uh); + if (is_wire_undriveable(w)) + continue; + if (next_cursor != WireId()) { + done = true; + break; + } + next_cursor = w; + } + if (next_cursor == WireId()) + break; + cursor = next_cursor; + } + } + + void find_all_reserved_wires() + { + for (auto net : nets_by_udata) { + WireId src = ctx->getNetinfoSourceWire(net); + if (src == WireId()) + continue; + for (size_t i = 0; i < net->users.size(); i++) + reserve_wires_for_arc(net, i); + } + } + ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, size_t i, bool is_mt, bool is_bb = true) { @@ -416,6 +473,8 @@ struct Router2 auto &wd = wires.at(next); if (wd.unavailable) continue; + if (wd.reserved_net != -1 && wd.reserved_net != net->udata) + continue; 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); @@ -490,6 +549,8 @@ struct Router2 auto &nwd = wires.at(next); if (nwd.unavailable) continue; + if (nwd.reserved_net != -1 && nwd.reserved_net != net->udata) + continue; if (nwd.bound_nets.count(net->udata) && nwd.bound_nets.at(net->udata).second != dh) continue; WireScore next_score; @@ -859,6 +920,7 @@ struct Router2 { setup_nets(); setup_wires(); + find_all_reserved_wires(); partition_nets(); curr_cong_weight = 0.5; hist_cong_weight = 1.0; -- cgit v1.2.3 From 17256c680a669faab618905555bf6721cfd943c1 Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 3 Dec 2019 14:07:24 +0000 Subject: router2: debugging Signed-off-by: David Shah --- common/router2.cc | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 496a4bfc..7724f581 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -356,8 +356,11 @@ struct Router2 std::unordered_set rsv; WireId cursor = sink; bool done = false; + log("resevering wires for arc %d of net %s\n", int(i), ctx->nameOf(net)); while (!done) { auto &wd = wires.at(cursor); + if (ctx->debug) + log(" %s\n", ctx->nameOfWire(cursor)); wd.reserved_net = net->udata; if (cursor == src) break; @@ -648,7 +651,9 @@ struct Router2 auto res2 = route_arc(t, net, i, is_mt, false); // If this also fails, no choice but to give up if (res2 != ARC_SUCCESS) - log_error("Failed to route arc %d of net '%s'.\n", int(i), ctx->nameOf(net)); + log_error("Failed to route arc %d of net '%s', from %s to %s.\n", int(i), ctx->nameOf(net), + ctx->nameOfWire(ctx->getNetinfoSourceWire(net)), + ctx->nameOfWire(ctx->getNetinfoSinkWire(net, net->users.at(i)))); } } } -- cgit v1.2.3 From 37543ad00364c9a575c21f450c96fdbc3492c042 Mon Sep 17 00:00:00 2001 From: David Shah Date: Thu, 5 Dec 2019 15:17:18 +0000 Subject: router2: debugging Signed-off-by: David Shah --- common/placer1.cc | 7 ++++++- common/router2.cc | 8 ++++++-- 2 files changed, 12 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/placer1.cc b/common/placer1.cc index 6683ddf7..96424957 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -609,9 +609,10 @@ class SAPlacer std::vector> dest_bels; double delta = 0; moveChange.reset(this); +#if 0 if (ctx->debug) log_info("finding cells for chain swap %s\n", cell->name.c_str(ctx)); - +#endif Loc baseLoc = ctx->getBelLocation(cell->bel); discover_chain(baseLoc, cell, cell_rel); Loc newBaseLoc = ctx->getBelLocation(newBase); @@ -634,8 +635,10 @@ class SAPlacer return false; dest_bels.emplace_back(std::make_pair(cr.first, targetBel)); } +#if 0 if (ctx->debug) log_info("trying chain swap %s\n", cell->name.c_str(ctx)); +#endif // for (const auto &db : dest_bels) { BelId oldBel = swap_cell_bels(db.first, db.second); @@ -661,8 +664,10 @@ class SAPlacer // SA acceptance criterea if (delta < 0 || (temp > 1e-9 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { n_accept++; +#if 0 if (ctx->debug) log_info("accepted chain swap %s\n", cell->name.c_str(ctx)); +#endif } else { goto swap_fail; } diff --git a/common/router2.cc b/common/router2.cc index 7724f581..5f6d7f78 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -521,6 +521,9 @@ struct Router2 int toexplore = 25000 * std::max(1, (ad.bb.x1 - ad.bb.x0) + (ad.bb.y1 - ad.bb.y0)); int iter = 0; int explored = 1; + bool debug_arc = /*usr.cell->type.str(ctx).find("RAMB") != std::string::npos && (usr.port == + ctx->id("ADDRATIEHIGH0") || usr.port == ctx->id("ADDRARDADDRL0"))*/ + false; while (!t.queue.empty() && (!is_bb || iter < toexplore)) { auto curr = t.queue.top(); t.queue.pop(); @@ -546,8 +549,9 @@ struct Router2 #endif // Evaluate score of next wire WireId next = ctx->getPipDstWire(dh); -#if 0 - ROUTE_LOG_DBG(" src wire %s\n", ctx->nameOfWire(next)); +#if 1 + if (debug_arc) + ROUTE_LOG_DBG(" src wire %s\n", ctx->nameOfWire(next)); #endif auto &nwd = wires.at(next); if (nwd.unavailable) -- cgit v1.2.3 From a1c703729cf4bf51752f188f63d5f0969d9f544b Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 10 Dec 2019 10:39:55 +0000 Subject: router2: reduce memory footprint Signed-off-by: David Shah --- common/router2.cc | 49 ++++++++++++++++++++++++++++--------------------- 1 file changed, 28 insertions(+), 21 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 5f6d7f78..533cee33 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -44,14 +44,16 @@ struct Router2 struct PerArcData { - std::unordered_map wires; + WireId sink_wire; ArcBounds bb; + bool routed = false; }; // As we allow overlap at first; the nextpnr bind functions can't be used // as the primary relation between arcs and wires/pips struct PerNetData { + WireId src_wire; std::vector arcs; ArcBounds bb; // Coordinates of the center of the net, used for the weight-to-average @@ -123,6 +125,7 @@ struct Router2 for (size_t j = 0; j < ni->users.size(); j++) { auto &usr = ni->users.at(j); WireId src_wire = ctx->getNetinfoSourceWire(ni), dst_wire = ctx->getNetinfoSinkWire(ni, usr); + nets.at(i).src_wire = src_wire; if (ni->driver.cell == nullptr) src_wire = dst_wire; if (src_wire == WireId()) @@ -131,6 +134,7 @@ struct Router2 if (dst_wire == WireId()) log_error("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port), ctx->nameOf(usr.cell)); + nets.at(i).arcs.at(j).sink_wire = dst_wire; // Set bounding box for this arc nets.at(i).arcs.at(j).bb = ctx->getRouteBoundingBox(src_wire, dst_wire); // Expand net bounding box to include this arc @@ -259,26 +263,31 @@ struct Router2 } else { NPNR_ASSERT(b.second == pip); } - nets.at(net->udata).arcs.at(user).wires[wire] = pip; } - void unbind_pip_internal(NetInfo *net, size_t user, WireId wire, bool dont_touch_arc = false) + void unbind_pip_internal(NetInfo *net, size_t user, WireId wire) { - auto &b = wires.at(wire).bound_nets[net->udata]; + auto &b = wires.at(wire).bound_nets.at(net->udata); --b.first; if (b.first == 0) { wires.at(wire).bound_nets.erase(net->udata); } - if (!dont_touch_arc) - nets.at(net->udata).arcs.at(user).wires.erase(wire); } void ripup_arc(NetInfo *net, size_t user) { auto &ad = nets.at(net->udata).arcs.at(user); - for (auto &wire : ad.wires) - unbind_pip_internal(net, user, wire.first, true); - ad.wires.clear(); + if (!ad.routed) + return; + WireId src = nets.at(net->udata).src_wire; + WireId cursor = ad.sink_wire; + while (cursor != src) { + auto &wd = wires.at(cursor); + PipId pip = wd.bound_nets.at(net->udata).second; + unbind_pip_internal(net, user, cursor); + cursor = ctx->getPipSrcWire(pip); + } + ad.routed = false; } float score_wire_for_arc(NetInfo *net, size_t user, WireId wire, PipId pip) @@ -316,14 +325,13 @@ struct Router2 bool check_arc_routing(NetInfo *net, size_t usr) { auto &ad = nets.at(net->udata).arcs.at(usr); - WireId src_wire = ctx->getNetinfoSourceWire(net); - WireId dst_wire = ctx->getNetinfoSinkWire(net, net->users.at(usr)); - WireId cursor = dst_wire; - while (ad.wires.count(cursor)) { + WireId src_wire = nets.at(net->udata).src_wire; + WireId cursor = ad.sink_wire; + while (wires.at(cursor).bound_nets.count(net->udata)) { auto &wd = wires.at(cursor); if (wd.bound_nets.size() != 1) return false; - auto &uh = ad.wires.at(cursor); + auto &uh = wd.bound_nets.at(net->udata).second; if (uh == PipId()) break; cursor = ctx->getPipSrcWire(uh); @@ -502,6 +510,7 @@ struct Router2 } } NPNR_ASSERT(cursor_fwd == dst_wire); + ad.routed = true; t.processed_sinks.insert(dst_wire); return ARC_SUCCESS; } @@ -602,6 +611,7 @@ struct Router2 cursor_bwd = ctx->getPipSrcWire(v.pip); } t.processed_sinks.insert(dst_wire); + ad.routed = true; return ARC_SUCCESS; } else { return ARC_RETRY_WITHOUT_BB; @@ -709,7 +719,7 @@ struct Router2 if (dst == WireId() || ctx->getBoundWireNet(dst) == net) return true; // Skip routes where there is no routing (special cases) - if (ad.wires.empty()) + if (!ad.routed) return true; WireId cursor = dst; @@ -725,16 +735,13 @@ struct Router2 break; } } - if (!ad.wires.count(cursor)) { + auto &wd = wires.at(cursor); + if (!wd.bound_nets.count(net->udata)) { log("Failure details:\n"); log(" Cursor: %s\n", ctx->nameOfWire(cursor)); - log(" route backtrace: \n"); - for (auto w : ad.wires) - log(" %s: %s (src: %s)\n", ctx->nameOfWire(w.first), ctx->nameOfPip(w.second), - ctx->nameOfWire(ctx->getPipSrcWire(w.second))); log_error("Internal error; incomplete route tree for arc %d of net %s.\n", usr_idx, ctx->nameOf(net)); } - auto &p = ad.wires.at(cursor); + auto &p = wd.bound_nets.at(net->udata).second; if (!ctx->checkPipAvail(p)) { success = false; break; -- cgit v1.2.3 From 3b6d9c952a45292c93de19040868c2c2ae562f26 Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 10 Dec 2019 11:31:08 +0000 Subject: router2: special case improvement Signed-off-by: David Shah --- common/router2.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 533cee33..5f3ebeea 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -434,7 +434,7 @@ struct Router2 // This could also be used to speed up forwards routing by a hybrid // bidirectional approach int backwards_iter = 0; - int backwards_limit = 10; + 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) { -- cgit v1.2.3 From 900fe98f0da27fa4902dfc9494d575010889ef91 Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 10 Dec 2019 12:45:38 +0000 Subject: router2: reduce bias cost factor Signed-off-by: David Shah --- common/router2.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 5f3ebeea..228cf7f0 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -304,7 +304,7 @@ struct Router2 source_uses = wd.bound_nets.at(net->udata).first; if (pip != PipId()) { Loc pl = ctx->getPipLocation(pip); - bias_cost = 0.5f * (base_cost / int(net->users.size())) * + bias_cost = 0.25f * (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; -- cgit v1.2.3 From 72367e6cfd3f36768288d6a5b03e670351ea8f8c Mon Sep 17 00:00:00 2001 From: David Shah Date: Thu, 2 Jan 2020 14:06:57 +0000 Subject: router2: Improvements Signed-off-by: David Shah --- common/router1.cc | 2 +- common/router2.cc | 29 +++++++++++++++++------------ common/router2.h | 2 +- 3 files changed, 19 insertions(+), 14 deletions(-) (limited to 'common') diff --git a/common/router1.cc b/common/router1.cc index a89d870d..4aa867c0 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -813,7 +813,7 @@ bool router1(Context *ctx, const Router1Cfg &cfg) std::chrono::duration(rend - rstart).count()); log_info("Routing complete.\n"); ctx->yield(); - log_info("Route time %.02fs\n", std::chrono::duration(rend - rstart).count()); + log_info("Router1 time %.02fs\n", std::chrono::duration(rend - rstart).count()); #ifndef NDEBUG router.check(); diff --git a/common/router2.cc b/common/router2.cc index 228cf7f0..88e9746e 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -28,6 +28,7 @@ #include #include +#include #include #include #include @@ -353,10 +354,6 @@ struct Router2 // Find all the wires that must be used to route a given arc void reserve_wires_for_arc(NetInfo *net, size_t i) { - // This is slightly tricky, because of the possibility of "diamonds" - // eg /--C--\\ - // sink ----B----D--... - // we need to discover that D is a reserved wire; despite the branch and choice of B/C WireId src = ctx->getNetinfoSourceWire(net); WireId sink = ctx->getNetinfoSinkWire(net, net->users.at(i)); if (sink == WireId()) @@ -364,7 +361,8 @@ struct Router2 std::unordered_set rsv; WireId cursor = sink; bool done = false; - log("resevering wires for arc %d of net %s\n", int(i), ctx->nameOf(net)); + if (ctx->debug) + log("resevering wires for arc %d of net %s\n", int(i), ctx->nameOf(net)); while (!done) { auto &wd = wires.at(cursor); if (ctx->debug) @@ -855,8 +853,10 @@ struct Router2 mid_y = p.first; accum_y += p.second; } - log_info("x splitpoint: %d\n", mid_x); - log_info("y splitpoint: %d\n", mid_y); + if (ctx->verbose) { + log_info(" x splitpoint: %d\n", mid_x); + log_info(" y splitpoint: %d\n", mid_y); + } std::vector bins(5, 0); for (auto &n : nets) { if (n.bb.x0 < mid_x && n.bb.x1 < mid_x && n.bb.y0 < mid_y && n.bb.y1 < mid_y) @@ -870,8 +870,9 @@ struct Router2 else ++bins[4]; // cross-boundary } - for (int i = 0; i < 5; i++) - log_info("bin %d N=%d\n", i, bins[i]); + if (ctx->verbose) + for (int i = 0; i < 5; i++) + log_info(" bin %d N=%d\n", i, bins[i]); } void router_thread(ThreadContext &t) @@ -914,7 +915,8 @@ struct Router2 bin = 3; tcs.at(bin).route_nets.push_back(ni); } - log_info("%d/%d nets not multi-threadable\n", int(tcs.at(N).route_nets.size()), int(route_queue.size())); + if (ctx->verbose) + log_info("%d/%d nets not multi-threadable\n", int(tcs.at(N).route_nets.size()), int(route_queue.size())); // Multithreaded part of routing std::vector threads; for (int i = 0; i < N; i++) { @@ -958,7 +960,7 @@ struct Router2 do_route(); route_queue.clear(); update_congestion(); -#if 1 +#if 0 if (iter == 1 && ctx->debug) { std::ofstream cong_map("cong_map_0.csv"); write_heatmap(cong_map, true); @@ -979,11 +981,14 @@ struct Router2 }; } // namespace -void router2_test(Context *ctx) +void router2(Context *ctx) { Router2 rt; rt.ctx = ctx; + auto rstart = std::chrono::high_resolution_clock::now(); rt.router_test(); + auto rend = std::chrono::high_resolution_clock::now(); + log_info("Router2 time %.02fs\n", std::chrono::duration(rend - rstart).count()); } NEXTPNR_NAMESPACE_END \ No newline at end of file diff --git a/common/router2.h b/common/router2.h index da750af5..e1f850b9 100644 --- a/common/router2.h +++ b/common/router2.h @@ -21,6 +21,6 @@ NEXTPNR_NAMESPACE_BEGIN -void router2_test(Context *ctx); +void router2(Context *ctx); NEXTPNR_NAMESPACE_END \ No newline at end of file -- cgit v1.2.3 From 7ac43e5f0039a07dd95c7377426d926e6705790a Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 14 Jan 2020 13:35:18 +0000 Subject: router2: Profile nets by route time Signed-off-by: David Shah --- common/router2.cc | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 88e9746e..d190904f 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -39,6 +39,8 @@ NEXTPNR_NAMESPACE_BEGIN +#define RUNTIME_PROFILE + namespace { struct Router2 { @@ -59,6 +61,7 @@ struct Router2 ArcBounds bb; // Coordinates of the center of the net, used for the weight-to-average int cx, cy, hpwl; + int total_route_us = 0; }; struct PerWireData @@ -627,6 +630,10 @@ struct Router2 ROUTE_LOG_DBG("Routing net '%s'...\n", ctx->nameOf(net)); +#ifdef RUNTIME_PROFILE + auto rstart = std::chrono::high_resolution_clock::now(); +#endif + // Nothing to do if net is undriven if (net->driver.cell == nullptr) return true; @@ -669,6 +676,11 @@ struct Router2 } } } +#ifdef RUNTIME_PROFILE + auto rend = std::chrono::high_resolution_clock::now(); + nets.at(net->udata).total_route_us += + (std::chrono::duration_cast(rend - rstart).count()); +#endif return !have_failures; } #undef ROUTE_LOG_DBG @@ -977,6 +989,18 @@ struct Router2 ++iter; curr_cong_weight *= 2; } while (!failed_nets.empty()); +#ifdef RUNTIME_PROFILE + std::vector> nets_by_runtime; + for (auto &n : nets_by_udata) { + nets_by_runtime.emplace_back(nets.at(n->udata).total_route_us, n->name); + } + std::sort(nets_by_runtime.begin(), nets_by_runtime.end(), std::greater>()); + log_info("1000 slowest nets by runtime:\n"); + for (int i = 0; i < std::min(int(nets_by_runtime.size()), 1000); i++) { + log(" %80s %6d %.1fms\n", nets_by_runtime.at(i).second.c_str(ctx), + int(ctx->nets.at(nets_by_runtime.at(i).second)->users.size()), nets_by_runtime.at(i).first / 1000.0); + } +#endif } }; } // namespace -- cgit v1.2.3 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') 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 From 3b043432f540a30f16c32f16c1f8ffb05932bddb Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 14 Jan 2020 15:28:44 +0000 Subject: router2: Flatten wire structure Signed-off-by: David Shah --- common/router2.cc | 167 ++++++++++++++++++++++++++++-------------------------- 1 file changed, 88 insertions(+), 79 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index f7962ae8..05734bec 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -74,6 +74,8 @@ struct Router2 struct PerWireData { + // nextpnr + WireId w; // net --> number of arcs; driving pip boost::container::flat_map> bound_nets; // Historical congestion cost @@ -170,30 +172,37 @@ struct Router2 } } - std::unordered_map wires; + std::unordered_map wire_to_idx; + std::vector flat_wires; + + PerWireData &wire_data(WireId w) { return flat_wires[wire_to_idx.at(w)]; } + void setup_wires() { // Set up per-wire structures, so that MT parts don't have to do any memory allocation // This is possibly quite wasteful and not cache-optimal; further consideration necessary for (auto wire : ctx->getWires()) { - wires[wire]; + PerWireData pwd; + pwd.w = wire; NetInfo *bound = ctx->getBoundWireNet(wire); if (bound != nullptr) { - wires[wire].bound_nets[bound->udata] = std::make_pair(1, bound->wires.at(wire).pip); + pwd.bound_nets[bound->udata] = std::make_pair(1, bound->wires.at(wire).pip); if (bound->wires.at(wire).strength > STRENGTH_STRONG) - wires[wire].unavailable = true; + pwd.unavailable = true; } + wire_to_idx[wire] = int(flat_wires.size()); + flat_wires.push_back(pwd); } } struct QueuedWire { - explicit QueuedWire(WireId wire = WireId(), PipId pip = PipId(), Loc loc = Loc(), WireScore score = WireScore{}, + explicit QueuedWire(int wire = -1, PipId pip = PipId(), Loc loc = Loc(), WireScore score = WireScore{}, int randtag = 0) : wire(wire), pip(pip), loc(loc), score(score), randtag(randtag){}; - WireId wire; + int wire; PipId pip; Loc loc; WireScore score; @@ -233,9 +242,9 @@ struct Router2 std::unordered_set processed_sinks; // Backwards routing - std::queue backwards_queue; + std::queue backwards_queue; - std::vector dirty_wires; + std::vector dirty_wires; }; enum ArcRouteResult @@ -259,9 +268,9 @@ struct Router2 log(__VA_ARGS__); \ } while (0) - void bind_pip_internal(NetInfo *net, size_t user, WireId wire, PipId pip) + void bind_pip_internal(NetInfo *net, size_t user, int wire, PipId pip) { - auto &b = wires.at(wire).bound_nets[net->udata]; + auto &b = flat_wires.at(wire).bound_nets[net->udata]; ++b.first; if (b.first == 1) { b.second = pip; @@ -272,10 +281,10 @@ struct Router2 void unbind_pip_internal(NetInfo *net, size_t user, WireId wire) { - auto &b = wires.at(wire).bound_nets.at(net->udata); + auto &b = wire_data(wire).bound_nets.at(net->udata); --b.first; if (b.first == 0) { - wires.at(wire).bound_nets.erase(net->udata); + wire_data(wire).bound_nets.erase(net->udata); } } @@ -287,7 +296,7 @@ struct Router2 WireId src = nets.at(net->udata).src_wire; WireId cursor = ad.sink_wire; while (cursor != src) { - auto &wd = wires.at(cursor); + auto &wd = wire_data(cursor); PipId pip = wd.bound_nets.at(net->udata).second; unbind_pip_internal(net, user, cursor); cursor = ctx->getPipSrcWire(pip); @@ -297,7 +306,7 @@ struct Router2 float score_wire_for_arc(NetInfo *net, size_t user, WireId wire, PipId pip) { - auto &wd = wires.at(wire); + auto &wd = wire_data(wire); auto &nd = nets.at(net->udata); float base_cost = ctx->getDelayNS(ctx->getPipDelay(pip).maxDelay() + ctx->getWireDelay(wire).maxDelay() + ctx->getDelayEpsilon()); @@ -315,16 +324,14 @@ struct Router2 return base_cost * hist_cost * present_cost / (1 + source_uses) + bias_cost; } - float get_togo_cost(NetInfo *net, size_t user, WireId wire, WireId sink) + float get_togo_cost(NetInfo *net, size_t user, int wire, WireId sink) { - auto &wd = wires.at(wire); + auto &wd = flat_wires[wire]; int source_uses = 0; if (wd.bound_nets.count(net->udata)) source_uses = wd.bound_nets.at(net->udata).first; // FIXME: timing/wirelength balance? - float ipin_cost = ctx->getDelayNS(ctx->getWireDelay(sink).maxDelay() + ctx->getDelayEpsilon()); - return std::max(0.0f, ctx->getDelayNS(ctx->estimateDelay(wire, sink)) - ipin_cost) / (1 + source_uses) + - ipin_cost; + return ctx->getDelayNS(ctx->estimateDelay(wd.w, sink)) / (1 + source_uses); } bool check_arc_routing(NetInfo *net, size_t usr) @@ -332,8 +339,8 @@ struct Router2 auto &ad = nets.at(net->udata).arcs.at(usr); WireId src_wire = nets.at(net->udata).src_wire; WireId cursor = ad.sink_wire; - while (wires.at(cursor).bound_nets.count(net->udata)) { - auto &wd = wires.at(cursor); + while (wire_data(cursor).bound_nets.count(net->udata)) { + auto &wd = wire_data(cursor); if (wd.bound_nets.size() != 1) return false; auto &uh = wd.bound_nets.at(net->udata).second; @@ -368,7 +375,7 @@ struct Router2 if (ctx->debug) log("resevering wires for arc %d of net %s\n", int(i), ctx->nameOf(net)); while (!done) { - auto &wd = wires.at(cursor); + auto &wd = wire_data(cursor); if (ctx->debug) log(" %s\n", ctx->nameOfWire(cursor)); wd.reserved_net = net->udata; @@ -405,17 +412,17 @@ 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(); + flat_wires[w].visit.visited = false; + flat_wires[w].visit.dirty = false; + flat_wires[w].visit.pip = PipId(); + flat_wires[w].visit.score = WireScore(); } t.dirty_wires.clear(); } - void set_visited(ThreadContext &t, WireId wire, PipId pip, WireScore score) + void set_visited(ThreadContext &t, int wire, PipId pip, WireScore score) { - auto &v = wires.at(wire).visit; + auto &v = flat_wires.at(wire).visit; if (!v.dirty) t.dirty_wires.push_back(wire); v.dirty = true; @@ -423,7 +430,7 @@ struct Router2 v.pip = pip; v.score = score; } - bool was_visited(WireId wire) { return wires.at(wire).visit.visited; } + bool was_visited(int wire) { return flat_wires.at(wire).visit.visited; } ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, size_t i, bool is_mt, bool is_bb = true) { @@ -434,13 +441,14 @@ struct Router2 ROUTE_LOG_DBG("Routing arc %d of net '%s' (%d, %d) -> (%d, %d)\n", int(i), ctx->nameOf(net), ad.bb.x0, ad.bb.y0, ad.bb.x1, ad.bb.y1); WireId src_wire = ctx->getNetinfoSourceWire(net), dst_wire = ctx->getNetinfoSinkWire(net, usr); - if (src_wire == WireId()) ARC_LOG_ERR("No wire found for port %s on source cell %s.\n", ctx->nameOf(net->driver.port), ctx->nameOf(net->driver.cell)); if (dst_wire == WireId()) ARC_LOG_ERR("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port), ctx->nameOf(usr.cell)); + int src_wire_idx = wire_to_idx.at(src_wire); + int dst_wire_idx = wire_to_idx.at(dst_wire); // Check if arc was already done _in this iteration_ if (t.processed_sinks.count(dst_wire)) return ARC_SUCCESS; @@ -450,7 +458,7 @@ struct Router2 t.queue.swap(new_queue); } if (!t.backwards_queue.empty()) { - std::queue new_queue; + std::queue new_queue; t.backwards_queue.swap(new_queue); } // First try strongly iteration-limited routing backwards BFS @@ -460,35 +468,35 @@ struct Router2 // bidirectional approach int backwards_iter = 0; int backwards_limit = ctx->getBelGlobalBuf(net->driver.cell->bel) ? 20000 : 15; - t.backwards_queue.push(dst_wire); + t.backwards_queue.push(wire_to_idx.at(dst_wire)); while (!t.backwards_queue.empty() && backwards_iter < backwards_limit) { - WireId cursor = t.backwards_queue.front(); + int cursor = t.backwards_queue.front(); t.backwards_queue.pop(); - auto &cwd = wires.at(cursor); + auto &cwd = flat_wires[cursor]; PipId cpip; if (cwd.bound_nets.count(net->udata)) { // If we can tack onto existing routing; try that // Only do this if the existing routing is uncontented; however - WireId cursor2 = cursor; + int cursor2 = cursor; bool bwd_merge_fail = false; - while (wires.at(cursor2).bound_nets.count(net->udata)) { - if (wires.at(cursor2).bound_nets.size() > 1) { + while (flat_wires.at(cursor2).bound_nets.count(net->udata)) { + if (flat_wires.at(cursor2).bound_nets.size() > 1) { bwd_merge_fail = true; break; } - PipId p = wires.at(cursor2).bound_nets.at(net->udata).second; + PipId p = flat_wires.at(cursor2).bound_nets.at(net->udata).second; if (p == PipId()) break; - cursor2 = ctx->getPipSrcWire(p); + cursor2 = wire_to_idx.at(ctx->getPipSrcWire(p)); } - if (!bwd_merge_fail && cursor2 == src_wire) { + if (!bwd_merge_fail && cursor2 == src_wire_idx) { // Found a path to merge to existing routing; backwards cursor2 = cursor; - while (wires.at(cursor2).bound_nets.count(net->udata)) { - PipId p = wires.at(cursor2).bound_nets.at(net->udata).second; + while (flat_wires.at(cursor2).bound_nets.count(net->udata)) { + PipId p = flat_wires.at(cursor2).bound_nets.at(net->udata).second; if (p == PipId()) break; - cursor2 = ctx->getPipSrcWire(p); + cursor2 = wire_to_idx.at(ctx->getPipSrcWire(p)); set_visited(t, cursor2, p, WireScore()); } break; @@ -496,16 +504,16 @@ struct Router2 cpip = cwd.bound_nets.at(net->udata).second; } bool did_something = false; - for (auto uh : ctx->getPipsUphill(cursor)) { + for (auto uh : ctx->getPipsUphill(flat_wires[cursor].w)) { did_something = true; if (!ctx->checkPipAvail(uh) && ctx->getBoundPipNet(uh) != net) continue; if (cpip != PipId() && cpip != uh) continue; // don't allow multiple pips driving a wire with a net - WireId next = ctx->getPipSrcWire(uh); + int next = wire_to_idx.at(ctx->getPipSrcWire(uh)); if (was_visited(next)) continue; // skip wires that have already been visited - auto &wd = wires.at(next); + auto &wd = flat_wires[next]; if (wd.unavailable) continue; if (wd.reserved_net != -1 && wd.reserved_net != net->udata) @@ -519,21 +527,21 @@ struct Router2 ++backwards_iter; } // Check if backwards routing succeeded in reaching source - if (was_visited(src_wire)) { + if (was_visited(src_wire_idx)) { ROUTE_LOG_DBG(" Routed (backwards): "); - WireId cursor_fwd = src_wire; - bind_pip_internal(net, i, src_wire, PipId()); + int cursor_fwd = src_wire_idx; + bind_pip_internal(net, i, src_wire_idx, PipId()); while (was_visited(cursor_fwd)) { - auto &v = wires.at(cursor_fwd).visit; - cursor_fwd = ctx->getPipDstWire(v.pip); + auto &v = flat_wires.at(cursor_fwd).visit; + cursor_fwd = wire_to_idx.at(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), + auto &wd = flat_wires.at(cursor_fwd); + ROUTE_LOG_DBG(" wire: %s (curr %d hist %f)\n", ctx->nameOfWire(wd.w), int(wd.bound_nets.size()) - 1, wd.hist_cong_cost); } } - NPNR_ASSERT(cursor_fwd == dst_wire); + NPNR_ASSERT(cursor_fwd == dst_wire_idx); ad.routed = true; t.processed_sinks.insert(dst_wire); reset_wires(t); @@ -545,11 +553,11 @@ struct Router2 WireScore base_score; base_score.cost = 0; base_score.delay = ctx->getWireDelay(src_wire).maxDelay(); - base_score.togo_cost = get_togo_cost(net, i, src_wire, dst_wire); + base_score.togo_cost = get_togo_cost(net, i, src_wire_idx, dst_wire); // Add source wire to queue - t.queue.push(QueuedWire(src_wire, PipId(), Loc(), base_score)); - set_visited(t, src_wire, PipId(), base_score); + t.queue.push(QueuedWire(src_wire_idx, PipId(), Loc(), base_score)); + set_visited(t, src_wire_idx, 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,13 +567,14 @@ struct Router2 false; while (!t.queue.empty() && (!is_bb || iter < toexplore)) { auto curr = t.queue.top(); + auto &d = flat_wires.at(curr.wire); t.queue.pop(); ++iter; #if 0 ROUTE_LOG_DBG("current wire %s\n", ctx->nameOfWire(curr.wire)); #endif // Explore all pips downhill of cursor - for (auto dh : ctx->getPipsDownhill(curr.wire)) { + for (auto dh : ctx->getPipsDownhill(d.w)) { // Skip pips outside of box in bounding-box mode #if 0 ROUTE_LOG_DBG("trying pip %s\n", ctx->nameOfPip(dh)); @@ -582,13 +591,14 @@ struct Router2 #endif // Evaluate score of next wire WireId next = ctx->getPipDstWire(dh); - if (was_visited(next)) + int next_idx = wire_to_idx.at(next); + if (was_visited(next_idx)) continue; #if 1 if (debug_arc) ROUTE_LOG_DBG(" src wire %s\n", ctx->nameOfWire(next)); #endif - auto &nwd = wires.at(next); + auto &nwd = flat_wires.at(next_idx); if (nwd.unavailable) continue; if (nwd.reserved_net != -1 && nwd.reserved_net != net->udata) @@ -599,8 +609,8 @@ struct Router2 next_score.cost = curr.score.cost + score_wire_for_arc(net, i, next, dh); 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); - const auto &v = wires.at(next).visit; + next_score.togo_cost = 1.75 * get_togo_cost(net, i, next_idx, dst_wire); + const auto &v = nwd.visit; if (!v.visited || (v.score.total() > next_score.total())) { ++explored; #if 0 @@ -608,33 +618,33 @@ struct Router2 next_score.togo_cost); #endif // Add wire to queue if it meets criteria - t.queue.push(QueuedWire(next, dh, ctx->getPipLocation(dh), next_score, ctx->rng())); - set_visited(t, next, dh, next_score); + t.queue.push(QueuedWire(next_idx, dh, ctx->getPipLocation(dh), next_score, ctx->rng())); + set_visited(t, next_idx, dh, next_score); if (next == dst_wire) { toexplore = std::min(toexplore, iter + 5); } } } } - if (was_visited(dst_wire)) { + if (was_visited(dst_wire_idx)) { ROUTE_LOG_DBG(" Routed (explored %d wires): ", explored); - WireId cursor_bwd = dst_wire; + int cursor_bwd = dst_wire_idx; while (was_visited(cursor_bwd)) { - auto &v = wires.at(cursor_bwd).visit; + auto &v = flat_wires.at(cursor_bwd).visit; bind_pip_internal(net, i, cursor_bwd, v.pip); if (ctx->debug) { - auto &wd = wires.at(cursor_bwd); - ROUTE_LOG_DBG(" wire: %s (curr %d hist %f share %d)\n", ctx->nameOfWire(cursor_bwd), + auto &wd = flat_wires.at(cursor_bwd); + ROUTE_LOG_DBG(" wire: %s (curr %d hist %f share %d)\n", ctx->nameOfWire(wd.w), int(wd.bound_nets.size()) - 1, wd.hist_cong_cost, wd.bound_nets.count(net->udata) ? wd.bound_nets.at(net->udata).first : 0); } if (v.pip == PipId()) { - NPNR_ASSERT(cursor_bwd == src_wire); + NPNR_ASSERT(cursor_bwd == src_wire_idx); break; } ROUTE_LOG_DBG(" pip: %s (%d, %d)\n", ctx->nameOfPip(v.pip), ctx->getPipLocation(v.pip).x, ctx->getPipLocation(v.pip).y); - cursor_bwd = ctx->getPipSrcWire(v.pip); + cursor_bwd = wire_to_idx.at(ctx->getPipSrcWire(v.pip)); } t.processed_sinks.insert(dst_wire); ad.routed = true; @@ -724,14 +734,14 @@ struct Router2 overused_wires = 0; total_wire_use = 0; failed_nets.clear(); - for (auto &wire : wires) { - total_wire_use += int(wire.second.bound_nets.size()); - int overuse = int(wire.second.bound_nets.size()) - 1; + for (auto &wire : flat_wires) { + total_wire_use += int(wire.bound_nets.size()); + int overuse = int(wire.bound_nets.size()) - 1; if (overuse > 0) { - wire.second.hist_cong_cost += overuse * hist_cong_weight; + wire.hist_cong_cost += overuse * hist_cong_weight; total_overuse += overuse; overused_wires += 1; - for (auto &bound : wire.second.bound_nets) + for (auto &bound : wire.bound_nets) failed_nets.insert(bound.first); } } @@ -772,7 +782,7 @@ struct Router2 break; } } - auto &wd = wires.at(cursor); + auto &wd = wire_data(cursor); if (!wd.bound_nets.count(net->udata)) { log("Failure details:\n"); log(" Cursor: %s\n", ctx->nameOfWire(cursor)); @@ -833,8 +843,7 @@ struct Router2 { std::vector> hm_xy; int max_x = 0, max_y = 0; - for (auto &w : wires) { - auto &wd = w.second; + for (auto &wd : flat_wires) { int val = int(wd.bound_nets.size()) - (congestion ? 1 : 0); if (wd.bound_nets.empty()) continue; -- cgit v1.2.3 From c27e7780d178241e611e4335d37e9ff31c28a85c Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 14 Jan 2020 15:36:42 +0000 Subject: router2: Multi-thread in more cases Signed-off-by: David Shah --- common/router2.cc | 38 ++++++++++++++++++++++++++++++++------ 1 file changed, 32 insertions(+), 6 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 05734bec..480b7a09 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -942,7 +942,8 @@ struct Router2 } return; } - const int N = 4; + const int Nq = 4, Nv = 2, Nh = 2; + const int N = Nq + Nv + Nh; std::vector tcs(N + 1); for (auto n : route_queue) { auto &nd = nets.at(n); @@ -952,7 +953,7 @@ struct Router2 int rs_x = mid_x + bb_margin_x; int le_y = mid_y - bb_margin_y; int rs_y = mid_y + bb_margin_y; - + // Quadrants if (nd.bb.x0 < le_x && nd.bb.x1 < le_x && nd.bb.y0 < le_y && nd.bb.y1 < le_y) bin = 0; else if (nd.bb.x0 >= rs_x && nd.bb.x1 >= rs_x && nd.bb.y0 < le_y && nd.bb.y1 < le_y) @@ -961,17 +962,42 @@ struct Router2 bin = 2; else if (nd.bb.x0 >= rs_x && nd.bb.x1 >= rs_x && nd.bb.y0 >= rs_y && nd.bb.y1 >= rs_y) bin = 3; + // Vertical split + else if (nd.bb.y0 < le_y && nd.bb.y1 < le_y) + bin = Nq + 0; + else if (nd.bb.y0 >= rs_y && nd.bb.y1 >= rs_y) + bin = Nq + 1; + // Horizontal split + else if (nd.bb.x0 < le_x && nd.bb.x1 < le_x) + bin = Nq + Nv + 0; + else if (nd.bb.x0 >= rs_x && nd.bb.x1 >= rs_x) + bin = Nq + Nv + 1; tcs.at(bin).route_nets.push_back(ni); } if (ctx->verbose) log_info("%d/%d nets not multi-threadable\n", int(tcs.at(N).route_nets.size()), int(route_queue.size())); - // Multithreaded part of routing + // Multithreaded part of routing - quadrants std::vector threads; - for (int i = 0; i < N; i++) { + for (int i = 0; i < Nq; i++) { threads.emplace_back([this, &tcs, i]() { router_thread(tcs.at(i)); }); } - for (int i = 0; i < N; i++) - threads.at(i).join(); + for (auto &t : threads) + t.join(); + threads.clear(); + // Vertical splits + for (int i = Nq; i < Nq + Nv; i++) { + threads.emplace_back([this, &tcs, i]() { router_thread(tcs.at(i)); }); + } + for (auto &t : threads) + t.join(); + threads.clear(); + // Horizontal splits + for (int i = Nq + Nv; i < Nq + Nv + Nh; i++) { + threads.emplace_back([this, &tcs, i]() { router_thread(tcs.at(i)); }); + } + for (auto &t : threads) + t.join(); + threads.clear(); // Singlethreaded part of routing - nets that cross partitions // or don't fit within bounding box for (auto st_net : tcs.at(N).route_nets) -- cgit v1.2.3 From f82e133c7c93b4589b2149631e6b72185148ada9 Mon Sep 17 00:00:00 2001 From: David Shah Date: Thu, 16 Jan 2020 11:35:24 +0000 Subject: router2: Fix case of undriven unsunk arcs Signed-off-by: David Shah --- common/router2.cc | 2 ++ 1 file changed, 2 insertions(+) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 480b7a09..3dad4583 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -141,6 +141,8 @@ struct Router2 nets.at(i).src_wire = src_wire; if (ni->driver.cell == nullptr) src_wire = dst_wire; + if (ni->driver.cell == nullptr && dst_wire == WireId()) + continue; if (src_wire == WireId()) log_error("No wire found for port %s on source cell %s.\n", ctx->nameOf(ni->driver.port), ctx->nameOf(ni->driver.cell)); -- cgit v1.2.3 From ad1cc12df1aa13c1618d85c07805a4987e0e041f Mon Sep 17 00:00:00 2001 From: David Shah Date: Mon, 3 Feb 2020 11:38:15 +0000 Subject: router2: Make magic numbers configurable Signed-off-by: David Shah --- common/router2.cc | 92 ++++++++++++++++++++++++++++++++----------------------- common/router2.h | 32 ++++++++++++++++++- 2 files changed, 85 insertions(+), 39 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 3dad4583..5ed007c3 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -26,6 +26,7 @@ * */ +#include "router2.h" #include #include #include @@ -39,8 +40,6 @@ NEXTPNR_NAMESPACE_BEGIN -#define RUNTIME_PROFILE - namespace { struct Router2 { @@ -105,6 +104,9 @@ struct Router2 } Context *ctx; + Router2Cfg cfg; + + Router2(Context *ctx, const Router2Cfg &cfg) : ctx(ctx), cfg(cfg) {} // Use 'udata' for fast net lookups and indexing std::vector nets_by_udata; @@ -221,11 +223,10 @@ struct Router2 }; }; - int bb_margin_x = 4, bb_margin_y = 4; // number of units outside the bounding box we may go bool hit_test_pip(ArcBounds &bb, Loc l) { - return l.x >= (bb.x0 - bb_margin_x) && l.x <= (bb.x1 + bb_margin_x) && l.y >= (bb.y0 - bb_margin_y) && - l.y <= (bb.y1 + bb_margin_y); + return l.x >= (bb.x0 - cfg.bb_margin_x) && l.x <= (bb.x1 + cfg.bb_margin_x) && + l.y >= (bb.y0 - cfg.bb_margin_y) && l.y <= (bb.y1 + cfg.bb_margin_y); } double curr_cong_weight, hist_cong_weight, estimate_weight; @@ -320,7 +321,7 @@ struct Router2 source_uses = wd.bound_nets.at(net->udata).first; if (pip != PipId()) { Loc pl = ctx->getPipLocation(pip); - bias_cost = 0.25f * (base_cost / int(net->users.size())) * + 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; @@ -333,7 +334,7 @@ struct Router2 if (wd.bound_nets.count(net->udata)) source_uses = wd.bound_nets.at(net->udata).first; // FIXME: timing/wirelength balance? - return ctx->getDelayNS(ctx->estimateDelay(wd.w, sink)) / (1 + source_uses); + return (ctx->getDelayNS(ctx->estimateDelay(wd.w, sink)) / (1 + source_uses)) + cfg.ipin_cost_adder; } bool check_arc_routing(NetInfo *net, size_t usr) @@ -469,7 +470,8 @@ struct Router2 // This could also be used to speed up forwards routing by a hybrid // bidirectional approach int backwards_iter = 0; - int backwards_limit = ctx->getBelGlobalBuf(net->driver.cell->bel) ? 20000 : 15; + int backwards_limit = + ctx->getBelGlobalBuf(net->driver.cell->bel) ? cfg.global_backwards_max_iter : cfg.backwards_max_iter; t.backwards_queue.push(wire_to_idx.at(dst_wire)); while (!t.backwards_queue.empty() && backwards_iter < backwards_limit) { int cursor = t.backwards_queue.front(); @@ -611,7 +613,7 @@ struct Router2 next_score.cost = curr.score.cost + score_wire_for_arc(net, i, next, dh); 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_idx, dst_wire); + next_score.togo_cost = cfg.estimate_weight * get_togo_cost(net, i, next_idx, dst_wire); const auto &v = nwd.visit; if (!v.visited || (v.score.total() > next_score.total())) { ++explored; @@ -669,9 +671,7 @@ struct Router2 ROUTE_LOG_DBG("Routing net '%s'...\n", ctx->nameOf(net)); -#ifdef RUNTIME_PROFILE auto rstart = std::chrono::high_resolution_clock::now(); -#endif // Nothing to do if net is undriven if (net->driver.cell == nullptr) @@ -715,11 +715,11 @@ struct Router2 } } } -#ifdef RUNTIME_PROFILE - auto rend = std::chrono::high_resolution_clock::now(); - nets.at(net->udata).total_route_us += - (std::chrono::duration_cast(rend - rstart).count()); -#endif + if (cfg.perf_profile) { + auto rend = std::chrono::high_resolution_clock::now(); + nets.at(net->udata).total_route_us += + (std::chrono::duration_cast(rend - rstart).count()); + } return !have_failures; } #undef ROUTE_LOG_DBG @@ -951,10 +951,10 @@ struct Router2 auto &nd = nets.at(n); auto ni = nets_by_udata.at(n); int bin = N; - int le_x = mid_x - bb_margin_x; - int rs_x = mid_x + bb_margin_x; - int le_y = mid_y - bb_margin_y; - int rs_y = mid_y + bb_margin_y; + int le_x = mid_x - cfg.bb_margin_x; + int rs_x = mid_x + cfg.bb_margin_x; + int le_y = mid_y - cfg.bb_margin_y; + int rs_y = mid_y + cfg.bb_margin_y; // Quadrants if (nd.bb.x0 < le_x && nd.bb.x1 < le_x && nd.bb.y0 < le_y && nd.bb.y1 < le_y) bin = 0; @@ -1010,14 +1010,14 @@ struct Router2 route_net(tcs.at(N), fail, false); } - void router_test() + void operator()() { setup_nets(); setup_wires(); find_all_reserved_wires(); partition_nets(); - curr_cong_weight = 0.5; - hist_cong_weight = 1.0; + curr_cong_weight = cfg.init_curr_cong_weight; + hist_cong_weight = cfg.hist_cong_weight; ThreadContext st; int iter = 1; @@ -1051,32 +1051,48 @@ struct Router2 log_info("iter=%d wires=%d overused=%d overuse=%d archfail=%s\n", iter, total_wire_use, overused_wires, total_overuse, overused_wires > 0 ? "NA" : std::to_string(arch_fail).c_str()); ++iter; - curr_cong_weight *= 2; + curr_cong_weight *= cfg.curr_cong_mult; } while (!failed_nets.empty()); -#ifdef RUNTIME_PROFILE - std::vector> nets_by_runtime; - for (auto &n : nets_by_udata) { - nets_by_runtime.emplace_back(nets.at(n->udata).total_route_us, n->name); - } - std::sort(nets_by_runtime.begin(), nets_by_runtime.end(), std::greater>()); - log_info("1000 slowest nets by runtime:\n"); - for (int i = 0; i < std::min(int(nets_by_runtime.size()), 1000); i++) { - log(" %80s %6d %.1fms\n", nets_by_runtime.at(i).second.c_str(ctx), - int(ctx->nets.at(nets_by_runtime.at(i).second)->users.size()), nets_by_runtime.at(i).first / 1000.0); + if (cfg.perf_profile) { + std::vector> nets_by_runtime; + for (auto &n : nets_by_udata) { + nets_by_runtime.emplace_back(nets.at(n->udata).total_route_us, n->name); + } + std::sort(nets_by_runtime.begin(), nets_by_runtime.end(), std::greater>()); + log_info("1000 slowest nets by runtime:\n"); + for (int i = 0; i < std::min(int(nets_by_runtime.size()), 1000); i++) { + log(" %80s %6d %.1fms\n", nets_by_runtime.at(i).second.c_str(ctx), + int(ctx->nets.at(nets_by_runtime.at(i).second)->users.size()), + nets_by_runtime.at(i).first / 1000.0); + } } -#endif } }; } // namespace -void router2(Context *ctx) +void router2(Context *ctx, const Router2Cfg &cfg) { - Router2 rt; + Router2 rt(ctx, cfg); rt.ctx = ctx; auto rstart = std::chrono::high_resolution_clock::now(); - rt.router_test(); + rt(); auto rend = std::chrono::high_resolution_clock::now(); log_info("Router2 time %.02fs\n", std::chrono::duration(rend - rstart).count()); } +Router2Cfg::Router2Cfg(Context *ctx) +{ + backwards_max_iter = ctx->setting("router2/bwdMaxIter", 20); + global_backwards_max_iter = ctx->setting("router2/glbBwdMaxIter", 200); + bb_margin_x = ctx->setting("router2/bbMargin/x", 3); + bb_margin_y = ctx->setting("router2/bbMargin/y", 3); + ipin_cost_adder = ctx->setting("router2/ipinCostAdder", 0.0f); + bias_cost_factor = ctx->setting("router2/biasCostFactor", 0.25f); + init_curr_cong_weight = ctx->setting("router2/initCurrCongWeight", 0.5f); + hist_cong_weight = ctx->setting("router2/histCongWeight", 1.0f); + curr_cong_mult = ctx->setting("router2/currCongWeightMult", 2.0f); + estimate_weight = ctx->setting("router2/estimateWeight", 1.75f); + perf_profile = ctx->setting("router2/perfProfile", false); +} + NEXTPNR_NAMESPACE_END \ No newline at end of file diff --git a/common/router2.h b/common/router2.h index e1f850b9..fb11f92d 100644 --- a/common/router2.h +++ b/common/router2.h @@ -21,6 +21,36 @@ NEXTPNR_NAMESPACE_BEGIN -void router2(Context *ctx); +struct Router2Cfg +{ + Router2Cfg(Context *ctx); + + // Maximum iterations for backwards routing attempt + int backwards_max_iter; + // Maximum iterations for backwards routing attempt for global nets + int global_backwards_max_iter; + // Padding added to bounding boxes to account for imperfect routing, + // congestion, etc + int bb_margin_x, bb_margin_y; + // Cost factor added to input pin wires; effectively reduces the + // benefit of sharing interconnect + float ipin_cost_adder; + // Cost factor for "bias" towards center location of net + float bias_cost_factor; + // Starting current and historical congestion cost factor + float init_curr_cong_weight, hist_cong_weight; + // Current congestion cost multiplier + float curr_cong_mult; + + // Weight given to delay estimate in A*. Higher values + // mean faster and more directed routing, at the risk + // of choosing a less congestion/delay-optimal route + float estimate_weight; + + // Print additional performance profiling information + bool perf_profile = false; +}; + +void router2(Context *ctx, const Router2Cfg &cfg); NEXTPNR_NAMESPACE_END \ No newline at end of file -- cgit v1.2.3 From 7123209324c93297efab6c2b2fc92286196be3fb Mon Sep 17 00:00:00 2001 From: David Shah Date: Mon, 3 Feb 2020 11:54:38 +0000 Subject: Allow selection of router algorithm Signed-off-by: David Shah --- common/command.cc | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) (limited to 'common') diff --git a/common/command.cc b/common/command.cc index 3866caca..f652ce67 100644 --- a/common/command.cc +++ b/common/command.cc @@ -132,6 +132,12 @@ po::options_description CommandHandler::getGeneralOptions() "; default: " + Arch::defaultPlacer) .c_str()); + general.add_options()( + "router", po::value(), + std::string("router algorithm to use; available: " + boost::algorithm::join(Arch::availableRouters, ", ") + + "; default: " + Arch::defaultPlacer) + .c_str()); + general.add_options()("slack_redist_iter", po::value(), "number of iterations between slack redistribution"); general.add_options()("cstrweight", po::value(), "placer weighting for relative constraint satisfaction"); general.add_options()("starttemp", po::value(), "placer SA start temperature"); @@ -214,6 +220,15 @@ void CommandHandler::setupContext(Context *ctx) ctx->settings[ctx->id("placer")] = placer; } + if (vm.count("router")) { + std::string router = vm["router"].as(); + if (std::find(Arch::availableRouters.begin(), Arch::availableRouters.end(), router) == + Arch::availableRouters.end()) + log_error("Router algorithm '%s' is not supported (available options: %s)\n", router.c_str(), + boost::algorithm::join(Arch::availableRouters, ", ").c_str()); + ctx->settings[ctx->id("router")] = router; + } + if (vm.count("cstrweight")) { ctx->settings[ctx->id("placer1/constraintWeight")] = std::to_string(vm["cstrweight"].as()); } @@ -244,6 +259,8 @@ void CommandHandler::setupContext(Context *ctx) ctx->settings[ctx->id("auto_freq")] = false; if (ctx->settings.find(ctx->id("placer")) == ctx->settings.end()) ctx->settings[ctx->id("placer")] = Arch::defaultPlacer; + if (ctx->settings.find(ctx->id("router")) == ctx->settings.end()) + ctx->settings[ctx->id("router")] = Arch::defaultRouter; ctx->settings[ctx->id("arch.name")] = std::string(ctx->archId().c_str(ctx)); ctx->settings[ctx->id("arch.type")] = std::string(ctx->archArgsToId(ctx->archArgs()).c_str(ctx)); -- cgit v1.2.3 From a8206ed170589dee3ae83cc6af0a8d936d7639b7 Mon Sep 17 00:00:00 2001 From: David Shah Date: Mon, 3 Feb 2020 13:33:20 +0000 Subject: router2: Add a simple timing heuristic Signed-off-by: David Shah --- common/router2.cc | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 5ed007c3..11fa2d68 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -36,6 +36,7 @@ #include #include "log.h" #include "nextpnr.h" +#include "timing.h" #include "util.h" NEXTPNR_NAMESPACE_BEGIN @@ -61,6 +62,7 @@ struct Router2 // Coordinates of the center of the net, used for the weight-to-average int cx, cy, hpwl; int total_route_us = 0; + float max_crit = 0; }; struct WireScore @@ -111,6 +113,10 @@ struct Router2 // Use 'udata' for fast net lookups and indexing std::vector nets_by_udata; std::vector nets; + + // Criticality data from timing analysis + NetCriticalityMap net_crit; + void setup_nets() { // Populate per-net and per-arc structures at start of routing @@ -1024,8 +1030,29 @@ struct Router2 for (size_t i = 0; i < nets_by_udata.size(); i++) route_queue.push_back(i); + bool timing_driven = ctx->setting("timing_driven"); + do { ctx->sorted_shuffle(route_queue); + + if (timing_driven && (int(route_queue.size()) > (int(nets_by_udata.size()) / 50))) { + // Heuristic: reduce runtime by skipping STA in the case of a "long tail" of a few + // congested nodes + get_criticalities(ctx, &net_crit); + for (auto n : route_queue) { + IdString name = nets_by_udata.at(n)->name; + auto fnd = net_crit.find(name); + auto &net = nets.at(n); + net.max_crit = 0; + if (fnd == net_crit.end()) + continue; + for (auto c : fnd->second.criticality) + net.max_crit = std::max(net.max_crit, c); + } + std::stable_sort(route_queue.begin(), route_queue.end(), + [&](int na, int nb) { return nets.at(na).max_crit > nets.at(nb).max_crit; }); + } + #if 0 for (size_t j = 0; j < route_queue.size(); j++) { route_net(st, nets_by_udata[route_queue[j]], false); -- cgit v1.2.3 From 2248e07b662bb99bbe053e485c5c4d8d10cf234b Mon Sep 17 00:00:00 2001 From: David Shah Date: Mon, 3 Feb 2020 13:46:05 +0000 Subject: router2: Improve flow and log output Signed-off-by: David Shah --- common/router2.cc | 17 ++++++++++++----- 1 file changed, 12 insertions(+), 5 deletions(-) (limited to 'common') diff --git a/common/router2.cc b/common/router2.cc index 11fa2d68..00760c78 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -36,6 +36,7 @@ #include #include "log.h" #include "nextpnr.h" +#include "router1.h" #include "timing.h" #include "util.h" @@ -1018,6 +1019,9 @@ struct Router2 void operator()() { + log_info("Running router2...\n"); + log_info("Setting up routing resources...\n"); + auto rstart = std::chrono::high_resolution_clock::now(); setup_nets(); setup_wires(); find_all_reserved_wires(); @@ -1031,7 +1035,7 @@ struct Router2 route_queue.push_back(i); bool timing_driven = ctx->setting("timing_driven"); - + log_info("Running main router loop...\n"); do { ctx->sorted_shuffle(route_queue); @@ -1075,7 +1079,7 @@ struct Router2 } for (auto cn : failed_nets) route_queue.push_back(cn); - log_info("iter=%d wires=%d overused=%d overuse=%d archfail=%s\n", iter, total_wire_use, overused_wires, + log_info(" iter=%d wires=%d overused=%d overuse=%d archfail=%s\n", iter, total_wire_use, overused_wires, total_overuse, overused_wires > 0 ? "NA" : std::to_string(arch_fail).c_str()); ++iter; curr_cong_weight *= cfg.curr_cong_mult; @@ -1093,6 +1097,12 @@ struct Router2 nets_by_runtime.at(i).first / 1000.0); } } + auto rend = std::chrono::high_resolution_clock::now(); + log_info("Router2 time %.02fs\n", std::chrono::duration(rend - rstart).count()); + + log_info("Running router1 to check that route is legal...\n"); + + router1(ctx, Router1Cfg(ctx)); } }; } // namespace @@ -1101,10 +1111,7 @@ void router2(Context *ctx, const Router2Cfg &cfg) { Router2 rt(ctx, cfg); rt.ctx = ctx; - auto rstart = std::chrono::high_resolution_clock::now(); rt(); - auto rend = std::chrono::high_resolution_clock::now(); - log_info("Router2 time %.02fs\n", std::chrono::duration(rend - rstart).count()); } Router2Cfg::Router2Cfg(Context *ctx) -- cgit v1.2.3