From 693c34ad0646aac1bb766e783eb94d710f8ff72b Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 14:08:45 +0200 Subject: Improvements in router Signed-off-by: Clifford Wolf --- common/route.cc | 212 +++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 148 insertions(+), 64 deletions(-) (limited to 'common/route.cc') diff --git a/common/route.cc b/common/route.cc index 6a410397..cf87ebaa 100644 --- a/common/route.cc +++ b/common/route.cc @@ -23,6 +23,38 @@ #include "log.h" #include "route.h" +namespace std { +template <> +struct hash> +{ + std::size_t + operator()(const pair &arg) const noexcept + { + std::size_t seed = hash()(arg.first); + seed ^= hash()(arg.second) + + 0x9e3779b9 + (seed << 6) + (seed >> 2); + return seed; + } +}; + +template <> +struct hash< + pair> +{ + std::size_t + operator()(const pair &arg) const noexcept + { + std::size_t seed = hash()(arg.first); + seed ^= hash()(arg.second) + + 0x9e3779b9 + (seed << 6) + (seed >> 2); + return seed; + } +}; +} // namespace std + namespace { USING_NEXTPNR_NAMESPACE @@ -46,6 +78,12 @@ struct QueuedWire }; }; +struct RipupScoreboard +{ + std::unordered_map, int> wireScores; + std::unordered_map, int> pipScores; +}; + void ripup_net(Context *ctx, IdString net_name) { auto net_info = ctx->nets.at(net_name); @@ -62,7 +100,9 @@ void ripup_net(Context *ctx, IdString net_name) struct Router { Context *ctx; + RipupScoreboard scores; IdString net_name; + bool ripup; delay_t ripup_penalty; @@ -99,31 +139,41 @@ struct Router queue.pop(); for (auto pip : ctx->getPipsDownhill(qw.wire)) { - delay_t next_delay = qw.delay; - IdString ripupNet = net_name; + delay_t next_delay = + qw.delay + ctx->getPipDelay(pip).avgDelay(); + WireId next_wire = ctx->getPipDstWire(pip); + bool foundRipupNet = false; visitCnt++; - if (!ctx->checkPipAvail(pip)) { + if (!ctx->checkWireAvail(next_wire)) { if (!ripup) continue; - ripupNet = ctx->getPipNet(pip, true); - if (ripupNet == net_name) + IdString ripupWireNet = ctx->getWireNet(next_wire, true); + if (ripupWireNet == net_name || ripupWireNet == IdString()) continue; + auto it = scores.wireScores.find( + std::make_pair(ripupWireNet, next_wire)); + if (it != scores.wireScores.end()) + next_delay += it->second * ripup_penalty; + foundRipupNet = true; } - WireId next_wire = ctx->getPipDstWire(pip); - next_delay += ctx->getPipDelay(pip).avgDelay(); - - if (!ctx->checkWireAvail(next_wire)) { + if (!ctx->checkPipAvail(pip)) { if (!ripup) continue; - ripupNet = ctx->getWireNet(next_wire, true); - if (ripupNet == net_name) + IdString ripupPipNet = ctx->getPipNet(pip, true); + if (ripupPipNet == net_name || ripupPipNet == IdString()) continue; + auto it = scores.pipScores.find( + std::make_pair(ripupPipNet, pip)); + if (it != scores.pipScores.end()) + next_delay += it->second * ripup_penalty; + foundRipupNet = true; } - if (ripupNet != net_name) + if (foundRipupNet) next_delay += ripup_penalty; + assert(next_delay >= 0); if (visited.count(next_wire)) { @@ -131,7 +181,7 @@ struct Router next_delay + ctx->getDelayEpsilon()) continue; #if 0 // FIXME - if (ctx->verbose) + if (ctx->debug) log("Found better route to %s. Old vs new delay " "estimate: %.3f %.3f\n", ctx->getWireName(next_wire).c_str(), @@ -154,16 +204,17 @@ struct Router } } - Router(Context *ctx, WireId src_wire, WireId dst_wire, bool ripup = false, - delay_t ripup_penalty = 0) - : ctx(ctx), ripup(ripup), ripup_penalty(ripup_penalty) + Router(Context *ctx, RipupScoreboard &scores, WireId src_wire, + WireId dst_wire, bool ripup = false, delay_t ripup_penalty = 0) + : ctx(ctx), scores(scores), ripup(ripup), + ripup_penalty(ripup_penalty) { std::unordered_map src_wires; src_wires[src_wire] = 0; route(src_wires, dst_wire); routedOkay = visited.count(dst_wire); - if (ctx->verbose) { + if (ctx->debug) { log("Route (from destination to source):\n"); WireId cursor = dst_wire; @@ -180,17 +231,17 @@ struct Router } } - Router(Context *ctx, IdString net_name, bool ripup = false, - delay_t ripup_penalty = 0) - : ctx(ctx), net_name(net_name), ripup(ripup), + Router(Context *ctx, RipupScoreboard &scores, IdString net_name, + bool ripup = false, delay_t ripup_penalty = 0) + : ctx(ctx), scores(scores), net_name(net_name), ripup(ripup), ripup_penalty(ripup_penalty) { auto net_info = ctx->nets.at(net_name); - if (ctx->verbose) + if (ctx->debug) log("Routing net %s.\n", net_name.c_str(ctx)); - if (ctx->verbose) + if (ctx->debug) log(" Source: %s.%s.\n", net_info->driver.cell->name.c_str(ctx), net_info->driver.port.c_str(ctx)); @@ -201,7 +252,7 @@ struct Router net_info->driver.cell->name.c_str(ctx), net_info->driver.cell->type.c_str(ctx)); - if (ctx->verbose) + if (ctx->debug) log(" Source bel: %s\n", ctx->getBelName(src_bel).c_str(ctx)); IdString driver_port = net_info->driver.port; @@ -220,7 +271,7 @@ struct Router net_info->driver.cell->name.c_str(ctx), ctx->getBelName(src_bel).c_str(ctx)); - if (ctx->verbose) + if (ctx->debug) log(" Source wire: %s\n", ctx->getWireName(src_wire).c_str(ctx)); std::unordered_map src_wires; @@ -232,7 +283,7 @@ struct Router ctx->shuffle(users_array); for (auto &user_it : users_array) { - if (ctx->verbose) + if (ctx->debug) log(" Route to: %s.%s.\n", user_it.cell->name.c_str(ctx), user_it.port.c_str(ctx)); @@ -243,7 +294,7 @@ struct Router user_it.cell->name.c_str(ctx), user_it.cell->type.c_str(ctx)); - if (ctx->verbose) + if (ctx->debug) log(" Destination bel: %s\n", ctx->getBelName(dst_bel).c_str(ctx)); @@ -264,7 +315,7 @@ struct Router user_it.cell->name.c_str(ctx), ctx->getBelName(dst_bel).c_str(ctx)); - if (ctx->verbose) { + if (ctx->debug) { log(" Destination wire: %s\n", ctx->getWireName(dst_wire).c_str(ctx)); log(" Path delay estimate: %.2f\n", @@ -274,7 +325,7 @@ struct Router route(src_wires, dst_wire); if (visited.count(dst_wire) == 0) { - if (ctx->verbose) + if (ctx->debug) log("Failed to route %s -> %s.\n", ctx->getWireName(src_wire).c_str(ctx), ctx->getWireName(dst_wire).c_str(ctx)); @@ -287,18 +338,18 @@ struct Router return; } - if (ctx->verbose) + if (ctx->debug) log(" Final path delay: %.3f\n", ctx->getDelayNS(visited[dst_wire].delay)); maxDelay = fmaxf(maxDelay, visited[dst_wire].delay); - if (ctx->verbose) + if (ctx->debug) log(" Route (from destination to source):\n"); WireId cursor = dst_wire; while (1) { - if (ctx->verbose) + if (ctx->debug) log(" %8.3f %s\n", ctx->getDelayNS(visited[cursor].delay), ctx->getWireName(cursor).c_str(ctx)); @@ -306,22 +357,31 @@ struct Router if (src_wires.count(cursor)) break; - IdString conflicting_net = ctx->getWireNet(cursor, true); + IdString conflicting_wire_net = ctx->getWireNet(cursor, true); + IdString conflicting_pip_net = + ctx->getPipNet(visited[cursor].pip, true); - if (conflicting_net != IdString()) { + if (conflicting_wire_net != IdString()) { assert(ripup); - assert(conflicting_net != net_name); - ripup_net(ctx, conflicting_net); - rippedNets.insert(conflicting_net); + assert(conflicting_wire_net != net_name); + ripup_net(ctx, conflicting_wire_net); + rippedNets.insert(conflicting_wire_net); + scores.wireScores[std::make_pair(net_name, cursor)]++; + scores.wireScores[std::make_pair(conflicting_wire_net, + cursor)]++; } - conflicting_net = ctx->getPipNet(visited[cursor].pip, true); - - if (conflicting_net != IdString()) { + if (conflicting_pip_net != IdString()) { assert(ripup); - assert(conflicting_net != net_name); - ripup_net(ctx, conflicting_net); - rippedNets.insert(conflicting_net); + assert(conflicting_pip_net != net_name); + if (conflicting_wire_net != conflicting_pip_net) { + ripup_net(ctx, conflicting_pip_net); + rippedNets.insert(conflicting_pip_net); + } + scores.pipScores[std::make_pair(net_name, + visited[cursor].pip)]++; + scores.pipScores[std::make_pair(conflicting_pip_net, + visited[cursor].pip)]++; } net_info->wires[cursor] = visited[cursor].pip; @@ -343,7 +403,8 @@ NEXTPNR_NAMESPACE_BEGIN bool route_design(Context *ctx) { - delay_t ripup_penalty = 5; + delay_t ripup_penalty = ctx->getRipupDelayPenalty(); + RipupScoreboard scores; log_info("Routing..\n"); @@ -425,17 +486,23 @@ bool route_design(Context *ctx) while (!netsQueue.empty()) { if (iterCnt == 200) { - log_info("giving up after %d iterations.\n", iterCnt); + log_warning("giving up after %d iterations.\n", iterCnt); return false; } - log_info("-- %d --\n", ++iterCnt); + + iterCnt++; + if (ctx->verbose) + log_info("-- %d --\n", iterCnt); int visitCnt = 0, revisitCnt = 0, netCnt = 0; std::unordered_set ripupQueue; - log_info("routing queue contains %d nets.\n", int(netsQueue.size())); - bool printNets = netsQueue.size() < 10; + if (ctx->verbose || iterCnt == 1) + log_info("routing queue contains %d nets.\n", + int(netsQueue.size())); + + bool printNets = ctx->verbose && (netsQueue.size() < 10); std::vector netsArray(netsQueue.begin(), netsQueue.end()); ctx->sorted_shuffle(netsArray); @@ -446,7 +513,7 @@ bool route_design(Context *ctx) log_info(" routing net %s. (%d users)\n", net_name.c_str(ctx), int(ctx->nets.at(net_name)->users.size())); - Router router(ctx, net_name, false); + Router router(ctx, scores, net_name, false); netCnt++; visitCnt += router.visitCnt; @@ -459,23 +526,29 @@ bool route_design(Context *ctx) ripupQueue.insert(net_name); } - if (!printNets && netCnt % 100 == 0) + if ((ctx->verbose || iterCnt == 1) && !printNets && + (netCnt % 100 == 0)) log_info(" processed %d nets. (%d routed, %d failed)\n", netCnt, netCnt - int(ripupQueue.size()), int(ripupQueue.size())); } - if (netCnt % 100 != 0) + int normalRouteCnt = netCnt - int(ripupQueue.size()); + + if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0)) log_info(" processed %d nets. (%d routed, %d failed)\n", netCnt, - netCnt - int(ripupQueue.size()), int(ripupQueue.size())); - log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt); + normalRouteCnt, int(ripupQueue.size())); + + if (ctx->verbose) + log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt); if (!ripupQueue.empty()) { - log_info("failed to route %d nets. re-routing in ripup mode.\n", - int(ripupQueue.size())); + if (ctx->verbose || iterCnt == 1) + log_info("failed to route %d nets. re-routing in ripup mode.\n", + int(ripupQueue.size())); - printNets = ripupQueue.size() < 10; + printNets = ctx->verbose && (ripupQueue.size() < 10); visitCnt = 0; revisitCnt = 0; @@ -492,8 +565,7 @@ bool route_design(Context *ctx) net_name.c_str(ctx), int(ctx->nets.at(net_name)->users.size())); - Router router(ctx, net_name, true, - ripup_penalty * (iterCnt - 1)); + Router router(ctx, scores, net_name, true, ripup_penalty); netCnt++; visitCnt += router.visitCnt; @@ -521,22 +593,33 @@ bool route_design(Context *ctx) ripCnt += router.rippedNets.size(); - if (!printNets && netCnt % 100 == 0) + if ((ctx->verbose || iterCnt == 1) && !printNets && + (netCnt % 100 == 0)) log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt); } - if (netCnt % 100 != 0) + if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0)) log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt); - log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt); + if (ctx->verbose) + log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt); - if (!netsQueue.empty()) + if (ctx->verbose && !netsQueue.empty()) log_info(" ripped up %d previously routed nets. continue " "routing.\n", int(netsQueue.size())); } + + if (!ctx->verbose) + log_info("iteration %d: routed %d nets without ripup, routed %d " + "nets with ripup.\n", + iterCnt, normalRouteCnt, int(ripupQueue.size())); + + if (iterCnt == 8 || iterCnt == 16 || iterCnt == 32 || iterCnt == 64 || + iterCnt == 128) + ripup_penalty += ctx->getRipupDelayPenalty(); } log_info("routing complete after %d iterations.\n", iterCnt); @@ -546,7 +629,8 @@ bool route_design(Context *ctx) bool get_actual_route_delay(Context *ctx, WireId src_wire, WireId dst_wire, delay_t &delay) { - Router router(ctx, src_wire, dst_wire); + RipupScoreboard scores; + Router router(ctx, scores, src_wire, dst_wire); if (router.routedOkay) delay = router.visited.at(dst_wire).delay; return router.routedOkay; -- cgit v1.2.3 From 993f6ef7d31ceee5fc71a99fcec19b521694e4f3 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 14:09:50 +0200 Subject: Improve log messages, move many messages to verbose mode Signed-off-by: Clifford Wolf --- common/route.cc | 1 + 1 file changed, 1 insertion(+) (limited to 'common/route.cc') diff --git a/common/route.cc b/common/route.cc index cf87ebaa..bdb2f5b5 100644 --- a/common/route.cc +++ b/common/route.cc @@ -406,6 +406,7 @@ bool route_design(Context *ctx) delay_t ripup_penalty = ctx->getRipupDelayPenalty(); RipupScoreboard scores; + log_break(); log_info("Routing..\n"); std::unordered_set netsQueue; -- cgit v1.2.3 From 08020400b379a0c2d7069bbd62f43782d438598b Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 14:16:07 +0200 Subject: Fix build of "dummy" architexture Signed-off-by: Clifford Wolf --- common/route.cc | 44 ++++++++++++++++++-------------------------- 1 file changed, 18 insertions(+), 26 deletions(-) (limited to 'common/route.cc') diff --git a/common/route.cc b/common/route.cc index bdb2f5b5..bf11b7d2 100644 --- a/common/route.cc +++ b/common/route.cc @@ -23,41 +23,32 @@ #include "log.h" #include "route.h" -namespace std { -template <> -struct hash> +namespace { + +USING_NEXTPNR_NAMESPACE + +struct hash_id_wire { - std::size_t - operator()(const pair &arg) const noexcept + std::size_t operator()(const std::pair &arg) const + noexcept { - std::size_t seed = hash()(arg.first); - seed ^= hash()(arg.second) + - 0x9e3779b9 + (seed << 6) + (seed >> 2); + std::size_t seed = std::hash()(arg.first); + seed ^= std::hash()(arg.second) + 0x9e3779b9 + (seed << 6) + + (seed >> 2); return seed; } }; -template <> -struct hash< - pair> +struct hash_id_pip { - std::size_t - operator()(const pair &arg) const noexcept + std::size_t operator()(const std::pair &arg) const noexcept { - std::size_t seed = hash()(arg.first); - seed ^= hash()(arg.second) + - 0x9e3779b9 + (seed << 6) + (seed >> 2); + std::size_t seed = std::hash()(arg.first); + seed ^= std::hash()(arg.second) + 0x9e3779b9 + (seed << 6) + + (seed >> 2); return seed; } }; -} // namespace std - -namespace { - -USING_NEXTPNR_NAMESPACE struct QueuedWire { @@ -80,8 +71,9 @@ struct QueuedWire struct RipupScoreboard { - std::unordered_map, int> wireScores; - std::unordered_map, int> pipScores; + std::unordered_map, int, hash_id_wire> + wireScores; + std::unordered_map, int, hash_id_pip> pipScores; }; void ripup_net(Context *ctx, IdString net_name) -- cgit v1.2.3 From a29bfc788eba9f11f1e0cd3d62a32c3894cddf49 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 15:47:41 +0200 Subject: Add ctx->checksum(), slightly improve log messages Signed-off-by: Clifford Wolf --- common/route.cc | 2 ++ 1 file changed, 2 insertions(+) (limited to 'common/route.cc') diff --git a/common/route.cc b/common/route.cc index bf11b7d2..69a314d7 100644 --- a/common/route.cc +++ b/common/route.cc @@ -480,6 +480,7 @@ bool route_design(Context *ctx) while (!netsQueue.empty()) { if (iterCnt == 200) { log_warning("giving up after %d iterations.\n", iterCnt); + log_info("Checksum: 0x%08x\n", ctx->checksum()); return false; } @@ -616,6 +617,7 @@ bool route_design(Context *ctx) } log_info("routing complete after %d iterations.\n", iterCnt); + log_info("Checksum: 0x%08x\n", ctx->checksum()); return true; } -- cgit v1.2.3 From 8fac26c2b795865098b1ba16152cd1c510133f29 Mon Sep 17 00:00:00 2001 From: Miodrag Milanovic Date: Thu, 21 Jun 2018 17:56:45 +0200 Subject: Fixed return codes for packer, placer and router --- common/route.cc | 332 +++++++++++++++++++++++++++++--------------------------- 1 file changed, 171 insertions(+), 161 deletions(-) (limited to 'common/route.cc') diff --git a/common/route.cc b/common/route.cc index 69a314d7..e747f09c 100644 --- a/common/route.cc +++ b/common/route.cc @@ -395,230 +395,240 @@ NEXTPNR_NAMESPACE_BEGIN bool route_design(Context *ctx) { - delay_t ripup_penalty = ctx->getRipupDelayPenalty(); - RipupScoreboard scores; - - log_break(); - log_info("Routing..\n"); - - std::unordered_set netsQueue; - - for (auto &net_it : ctx->nets) { - auto net_name = net_it.first; - auto net_info = net_it.second; - - if (net_info->driver.cell == nullptr) - continue; + try { + delay_t ripup_penalty = ctx->getRipupDelayPenalty(); + RipupScoreboard scores; - if (!net_info->wires.empty()) - continue; - - netsQueue.insert(net_name); - } - - if (netsQueue.empty()) { - log_info("found no unrouted nets. no routing necessary.\n"); - return true; - } + log_break(); + log_info("Routing..\n"); - log_info("found %d unrouted nets. starting routing procedure.\n", - int(netsQueue.size())); + std::unordered_set netsQueue; - delay_t estimatedTotalDelay = 0.0; - int estimatedTotalDelayCnt = 0; + for (auto &net_it : ctx->nets) { + auto net_name = net_it.first; + auto net_info = net_it.second; - for (auto net_name : netsQueue) { - auto net_info = ctx->nets.at(net_name); + if (net_info->driver.cell == nullptr) + continue; - auto src_bel = net_info->driver.cell->bel; + if (!net_info->wires.empty()) + continue; - if (src_bel == BelId()) - continue; + netsQueue.insert(net_name); + } - IdString driver_port = net_info->driver.port; + if (netsQueue.empty()) { + log_info("found no unrouted nets. no routing necessary.\n"); + return true; + } - auto driver_port_it = net_info->driver.cell->pins.find(driver_port); - if (driver_port_it != net_info->driver.cell->pins.end()) - driver_port = driver_port_it->second; + log_info("found %d unrouted nets. starting routing procedure.\n", + int(netsQueue.size())); - auto src_wire = - ctx->getWireBelPin(src_bel, ctx->portPinFromId(driver_port)); + delay_t estimatedTotalDelay = 0.0; + int estimatedTotalDelayCnt = 0; - if (src_wire == WireId()) - continue; + for (auto net_name : netsQueue) { + auto net_info = ctx->nets.at(net_name); - for (auto &user_it : net_info->users) { - auto dst_bel = user_it.cell->bel; + auto src_bel = net_info->driver.cell->bel; - if (dst_bel == BelId()) + if (src_bel == BelId()) continue; - IdString user_port = user_it.port; - - auto user_port_it = user_it.cell->pins.find(user_port); + IdString driver_port = net_info->driver.port; - if (user_port_it != user_it.cell->pins.end()) - user_port = user_port_it->second; + auto driver_port_it = net_info->driver.cell->pins.find(driver_port); + if (driver_port_it != net_info->driver.cell->pins.end()) + driver_port = driver_port_it->second; - auto dst_wire = - ctx->getWireBelPin(dst_bel, ctx->portPinFromId(user_port)); + auto src_wire = ctx->getWireBelPin(src_bel, + ctx->portPinFromId(driver_port)); - if (dst_wire == WireId()) + if (src_wire == WireId()) continue; - estimatedTotalDelay += ctx->estimateDelay(src_wire, dst_wire); - estimatedTotalDelayCnt++; - } - } + for (auto &user_it : net_info->users) { + auto dst_bel = user_it.cell->bel; - log_info("estimated total wire delay: %.2f (avg %.2f)\n", - float(estimatedTotalDelay), - float(estimatedTotalDelay) / estimatedTotalDelayCnt); + if (dst_bel == BelId()) + continue; - int iterCnt = 0; + IdString user_port = user_it.port; - while (!netsQueue.empty()) { - if (iterCnt == 200) { - log_warning("giving up after %d iterations.\n", iterCnt); - log_info("Checksum: 0x%08x\n", ctx->checksum()); - return false; - } - - iterCnt++; - if (ctx->verbose) - log_info("-- %d --\n", iterCnt); - - int visitCnt = 0, revisitCnt = 0, netCnt = 0; + auto user_port_it = user_it.cell->pins.find(user_port); - std::unordered_set ripupQueue; + if (user_port_it != user_it.cell->pins.end()) + user_port = user_port_it->second; - if (ctx->verbose || iterCnt == 1) - log_info("routing queue contains %d nets.\n", - int(netsQueue.size())); + auto dst_wire = ctx->getWireBelPin( + dst_bel, ctx->portPinFromId(user_port)); - bool printNets = ctx->verbose && (netsQueue.size() < 10); + if (dst_wire == WireId()) + continue; - std::vector netsArray(netsQueue.begin(), netsQueue.end()); - ctx->sorted_shuffle(netsArray); - netsQueue.clear(); - - for (auto net_name : netsArray) { - if (printNets) - log_info(" routing net %s. (%d users)\n", net_name.c_str(ctx), - int(ctx->nets.at(net_name)->users.size())); + estimatedTotalDelay += ctx->estimateDelay(src_wire, dst_wire); + estimatedTotalDelayCnt++; + } + } - Router router(ctx, scores, net_name, false); + log_info("estimated total wire delay: %.2f (avg %.2f)\n", + float(estimatedTotalDelay), + float(estimatedTotalDelay) / estimatedTotalDelayCnt); - netCnt++; - visitCnt += router.visitCnt; - revisitCnt += router.revisitCnt; + int iterCnt = 0; - if (!router.routedOkay) { - if (printNets) - log_info(" failed to route to %s.\n", - ctx->getWireName(router.failedDest).c_str(ctx)); - ripupQueue.insert(net_name); + while (!netsQueue.empty()) { + if (iterCnt == 200) { + log_warning("giving up after %d iterations.\n", iterCnt); + log_info("Checksum: 0x%08x\n", ctx->checksum()); + return false; } - if ((ctx->verbose || iterCnt == 1) && !printNets && - (netCnt % 100 == 0)) - log_info(" processed %d nets. (%d routed, %d failed)\n", - netCnt, netCnt - int(ripupQueue.size()), - int(ripupQueue.size())); - } - - int normalRouteCnt = netCnt - int(ripupQueue.size()); + iterCnt++; + if (ctx->verbose) + log_info("-- %d --\n", iterCnt); - if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0)) - log_info(" processed %d nets. (%d routed, %d failed)\n", netCnt, - normalRouteCnt, int(ripupQueue.size())); + int visitCnt = 0, revisitCnt = 0, netCnt = 0; - if (ctx->verbose) - log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt); + std::unordered_set ripupQueue; - if (!ripupQueue.empty()) { if (ctx->verbose || iterCnt == 1) - log_info("failed to route %d nets. re-routing in ripup mode.\n", - int(ripupQueue.size())); - - printNets = ctx->verbose && (ripupQueue.size() < 10); + log_info("routing queue contains %d nets.\n", + int(netsQueue.size())); - visitCnt = 0; - revisitCnt = 0; - netCnt = 0; - int ripCnt = 0; + bool printNets = ctx->verbose && (netsQueue.size() < 10); - std::vector ripupArray(ripupQueue.begin(), - ripupQueue.end()); - ctx->sorted_shuffle(ripupArray); + std::vector netsArray(netsQueue.begin(), netsQueue.end()); + ctx->sorted_shuffle(netsArray); + netsQueue.clear(); - for (auto net_name : ripupArray) { + for (auto net_name : netsArray) { if (printNets) log_info(" routing net %s. (%d users)\n", net_name.c_str(ctx), int(ctx->nets.at(net_name)->users.size())); - Router router(ctx, scores, net_name, true, ripup_penalty); + Router router(ctx, scores, net_name, false); netCnt++; visitCnt += router.visitCnt; revisitCnt += router.revisitCnt; - if (!router.routedOkay) - log_error("Net %s is impossible to route.\n", - net_name.c_str(ctx)); - - for (auto it : router.rippedNets) - netsQueue.insert(it); - - if (printNets) { - if (router.rippedNets.size() < 10) { - log_info(" ripped up %d other nets:\n", - int(router.rippedNets.size())); - for (auto n : router.rippedNets) - log_info(" %s (%d users)\n", n.c_str(ctx), - int(ctx->nets.at(n)->users.size())); - } else { - log_info(" ripped up %d other nets.\n", - int(router.rippedNets.size())); - } + if (!router.routedOkay) { + if (printNets) + log_info( + " failed to route to %s.\n", + ctx->getWireName(router.failedDest).c_str(ctx)); + ripupQueue.insert(net_name); } - ripCnt += router.rippedNets.size(); - if ((ctx->verbose || iterCnt == 1) && !printNets && (netCnt % 100 == 0)) - log_info(" routed %d nets, ripped %d nets.\n", netCnt, - ripCnt); + log_info(" processed %d nets. (%d routed, %d failed)\n", + netCnt, netCnt - int(ripupQueue.size()), + int(ripupQueue.size())); } + int normalRouteCnt = netCnt - int(ripupQueue.size()); + if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0)) - log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt); + log_info(" processed %d nets. (%d routed, %d failed)\n", + netCnt, normalRouteCnt, int(ripupQueue.size())); if (ctx->verbose) log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", visitCnt, (100.0 * revisitCnt) / visitCnt); - if (ctx->verbose && !netsQueue.empty()) - log_info(" ripped up %d previously routed nets. continue " - "routing.\n", - int(netsQueue.size())); - } + if (!ripupQueue.empty()) { + if (ctx->verbose || iterCnt == 1) + log_info("failed to route %d nets. re-routing in ripup " + "mode.\n", + int(ripupQueue.size())); + + printNets = ctx->verbose && (ripupQueue.size() < 10); + + visitCnt = 0; + revisitCnt = 0; + netCnt = 0; + int ripCnt = 0; + + std::vector ripupArray(ripupQueue.begin(), + ripupQueue.end()); + ctx->sorted_shuffle(ripupArray); + + for (auto net_name : ripupArray) { + if (printNets) + log_info(" routing net %s. (%d users)\n", + net_name.c_str(ctx), + int(ctx->nets.at(net_name)->users.size())); + + Router router(ctx, scores, net_name, true, ripup_penalty); + + netCnt++; + visitCnt += router.visitCnt; + revisitCnt += router.revisitCnt; + + if (!router.routedOkay) + log_error("Net %s is impossible to route.\n", + net_name.c_str(ctx)); + + for (auto it : router.rippedNets) + netsQueue.insert(it); + + if (printNets) { + if (router.rippedNets.size() < 10) { + log_info(" ripped up %d other nets:\n", + int(router.rippedNets.size())); + for (auto n : router.rippedNets) + log_info(" %s (%d users)\n", n.c_str(ctx), + int(ctx->nets.at(n)->users.size())); + } else { + log_info(" ripped up %d other nets.\n", + int(router.rippedNets.size())); + } + } - if (!ctx->verbose) - log_info("iteration %d: routed %d nets without ripup, routed %d " - "nets with ripup.\n", - iterCnt, normalRouteCnt, int(ripupQueue.size())); + ripCnt += router.rippedNets.size(); - if (iterCnt == 8 || iterCnt == 16 || iterCnt == 32 || iterCnt == 64 || - iterCnt == 128) - ripup_penalty += ctx->getRipupDelayPenalty(); - } + if ((ctx->verbose || iterCnt == 1) && !printNets && + (netCnt % 100 == 0)) + log_info(" routed %d nets, ripped %d nets.\n", netCnt, + ripCnt); + } + + if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0)) + log_info(" routed %d nets, ripped %d nets.\n", netCnt, + ripCnt); - log_info("routing complete after %d iterations.\n", iterCnt); - log_info("Checksum: 0x%08x\n", ctx->checksum()); - return true; + if (ctx->verbose) + log_info(" routing pass visited %d PIPs (%.2f%% " + "revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt); + + if (ctx->verbose && !netsQueue.empty()) + log_info(" ripped up %d previously routed nets. continue " + "routing.\n", + int(netsQueue.size())); + } + + if (!ctx->verbose) + log_info( + "iteration %d: routed %d nets without ripup, routed %d " + "nets with ripup.\n", + iterCnt, normalRouteCnt, int(ripupQueue.size())); + + if (iterCnt == 8 || iterCnt == 16 || iterCnt == 32 || + iterCnt == 64 || iterCnt == 128) + ripup_penalty += ctx->getRipupDelayPenalty(); + } + + log_info("routing complete after %d iterations.\n", iterCnt); + log_info("Checksum: 0x%08x\n", ctx->checksum()); + return true; + } catch (log_execution_error_exception) { + return false; + } } bool get_actual_route_delay(Context *ctx, WireId src_wire, WireId dst_wire, -- cgit v1.2.3 From 38dc1cc5504961f666da32d7249532a23d5876ad Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 19:17:04 +0200 Subject: Work "overtime" to find better solutions in routing search algorithm Signed-off-by: Clifford Wolf --- common/route.cc | 32 +++++++++++++++++++++++--------- 1 file changed, 23 insertions(+), 9 deletions(-) (limited to 'common/route.cc') diff --git a/common/route.cc b/common/route.cc index 69a314d7..0c072c3a 100644 --- a/common/route.cc +++ b/common/route.cc @@ -100,7 +100,7 @@ struct Router std::unordered_set rippedNets; std::unordered_map visited; - int visitCnt = 0, revisitCnt = 0; + int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0; bool routedOkay = false; delay_t maxDelay = 0.0; WireId failedDest; @@ -126,16 +126,22 @@ struct Router visited[qw.wire] = qw; } - while (!queue.empty() && !visited.count(dst_wire)) { + int thisVisitCnt = 0; + int thisVisitCntLimit = 0; + + while (!queue.empty() && (thisVisitCntLimit == 0 || thisVisitCnt < thisVisitCntLimit)) { QueuedWire qw = queue.top(); queue.pop(); + if (thisVisitCntLimit == 0 && visited.count(dst_wire)) + thisVisitCntLimit = (thisVisitCnt*3)/2; + for (auto pip : ctx->getPipsDownhill(qw.wire)) { delay_t next_delay = qw.delay + ctx->getPipDelay(pip).avgDelay(); WireId next_wire = ctx->getPipDstWire(pip); bool foundRipupNet = false; - visitCnt++; + thisVisitCnt++; if (!ctx->checkWireAvail(next_wire)) { if (!ripup) @@ -180,7 +186,10 @@ struct Router ctx->getDelayNS(visited.at(next_wire).delay), ctx->getDelayNS(next_delay)); #endif - revisitCnt++; + if (thisVisitCntLimit == 0) + revisitCnt++; + else + overtimeRevisitCnt++; } QueuedWire next_qw; @@ -194,6 +203,8 @@ struct Router queue.push(next_qw); } } + + visitCnt += thisVisitCnt; } Router(Context *ctx, RipupScoreboard &scores, WireId src_wire, @@ -488,7 +499,7 @@ bool route_design(Context *ctx) if (ctx->verbose) log_info("-- %d --\n", iterCnt); - int visitCnt = 0, revisitCnt = 0, netCnt = 0; + int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0, netCnt = 0; std::unordered_set ripupQueue; @@ -512,6 +523,7 @@ bool route_design(Context *ctx) netCnt++; visitCnt += router.visitCnt; revisitCnt += router.revisitCnt; + overtimeRevisitCnt += router.overtimeRevisitCnt; if (!router.routedOkay) { if (printNets) @@ -534,8 +546,8 @@ bool route_design(Context *ctx) normalRouteCnt, int(ripupQueue.size())); if (ctx->verbose) - log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt); + log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt); if (!ripupQueue.empty()) { if (ctx->verbose || iterCnt == 1) @@ -546,6 +558,7 @@ bool route_design(Context *ctx) visitCnt = 0; revisitCnt = 0; + overtimeRevisitCnt = 0; netCnt = 0; int ripCnt = 0; @@ -564,6 +577,7 @@ bool route_design(Context *ctx) netCnt++; visitCnt += router.visitCnt; revisitCnt += router.revisitCnt; + overtimeRevisitCnt += router.overtimeRevisitCnt; if (!router.routedOkay) log_error("Net %s is impossible to route.\n", @@ -597,8 +611,8 @@ bool route_design(Context *ctx) log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt); if (ctx->verbose) - log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt); + log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt); if (ctx->verbose && !netsQueue.empty()) log_info(" ripped up %d previously routed nets. continue " -- cgit v1.2.3 From 2c98231f88cd145267048b32a5ce0e4deadc2716 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 19:36:20 +0200 Subject: Updates from clangformat Signed-off-by: Clifford Wolf --- common/route.cc | 20 +++++++++++++------- 1 file changed, 13 insertions(+), 7 deletions(-) (limited to 'common/route.cc') diff --git a/common/route.cc b/common/route.cc index e6697349..967f9aa1 100644 --- a/common/route.cc +++ b/common/route.cc @@ -129,12 +129,13 @@ struct Router int thisVisitCnt = 0; int thisVisitCntLimit = 0; - while (!queue.empty() && (thisVisitCntLimit == 0 || thisVisitCnt < thisVisitCntLimit)) { + while (!queue.empty() && + (thisVisitCntLimit == 0 || thisVisitCnt < thisVisitCntLimit)) { QueuedWire qw = queue.top(); queue.pop(); if (thisVisitCntLimit == 0 && visited.count(dst_wire)) - thisVisitCntLimit = (thisVisitCnt*3)/2; + thisVisitCntLimit = (thisVisitCnt * 3) / 2; for (auto pip : ctx->getPipsDownhill(qw.wire)) { delay_t next_delay = @@ -500,7 +501,8 @@ bool route_design(Context *ctx) if (ctx->verbose) log_info("-- %d --\n", iterCnt); - int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0, netCnt = 0; + int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0, + netCnt = 0; std::unordered_set ripupQueue; @@ -549,8 +551,10 @@ bool route_design(Context *ctx) netCnt, normalRouteCnt, int(ripupQueue.size())); if (ctx->verbose) - log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt); + log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime " + "revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt, + (100.0 * overtimeRevisitCnt) / visitCnt); if (!ripupQueue.empty()) { if (ctx->verbose || iterCnt == 1) @@ -616,8 +620,10 @@ bool route_design(Context *ctx) ripCnt); if (ctx->verbose) - log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt); + log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% " + "overtime revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt, + (100.0 * overtimeRevisitCnt) / visitCnt); if (ctx->verbose && !netsQueue.empty()) log_info(" ripped up %d previously routed nets. continue " -- cgit v1.2.3