From bbb140c6991f01838009a65c81399694fe8afe3f Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 21 Jul 2018 11:52:41 +0200 Subject: Quick hack to route nets with lowest budget first --- common/router1.cc | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-) (limited to 'common/router1.cc') diff --git a/common/router1.cc b/common/router1.cc index 94c7070e..50022169 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -402,6 +402,21 @@ struct Router NEXTPNR_NAMESPACE_BEGIN +static void prioritise_nets(Context *ctx, std::vector &netsArray) +{ + std::unordered_map netScores; + for (auto net_name : netsArray) { + delay_t score = std::numeric_limits::max(); + for (const auto &sink : ctx->nets.at(net_name)->users) { + if (sink.budget < score) + score = sink.budget; + } + netScores[net_name] = score; + } + std::sort(netsArray.begin(), netsArray.end(), + [&netScores](IdString a, IdString b) { return netScores[a] < netScores[b]; }); +} + bool router1(Context *ctx) { try { @@ -508,7 +523,7 @@ bool router1(Context *ctx) bool printNets = ctx->verbose && (netsQueue.size() < 10); std::vector netsArray(netsQueue.begin(), netsQueue.end()); - ctx->sorted_shuffle(netsArray); + prioritise_nets(ctx, netsArray); netsQueue.clear(); for (auto net_name : netsArray) { @@ -560,7 +575,7 @@ bool router1(Context *ctx) int ripCnt = 0; std::vector ripupArray(ripupQueue.begin(), ripupQueue.end()); - ctx->sorted_shuffle(ripupArray); + prioritise_nets(ctx, ripupArray); for (auto net_name : ripupArray) { if (printNets) -- cgit v1.2.3 From 5aa4cf2efbf34b89fba39495e66048a09c1d258c Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 21 Jul 2018 13:59:48 -0700 Subject: Call now-more-flexibile update_budget() during routing, but using any actual delays that we have --- common/router1.cc | 22 ++++++++++++++++++++-- 1 file changed, 20 insertions(+), 2 deletions(-) (limited to 'common/router1.cc') diff --git a/common/router1.cc b/common/router1.cc index 86fb1a44..767e10fd 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -22,6 +22,7 @@ #include "log.h" #include "router1.h" +#include "timing.h" namespace { @@ -730,8 +731,25 @@ bool router1(Context *ctx) std::unordered_set normalRouteNets, ripupQueue; - if (ctx->verbose || iterCnt == 1) - log_info("routing queue contains %d jobs.\n", int(jobQueue.size())); + if (iterCnt == 1) { + if (ctx->verbose) + log_info("routing queue contains %d jobs.\n", int(jobQueue.size())); + } else { + static auto actual_delay = [](Context *ctx, WireId src, WireId dst) { + delay_t total_delay = ctx->getWireDelay(dst).maxDelay(); + WireId last_wire = dst; + for (auto pip : ctx->getPipsDownhill(dst)) { + total_delay += ctx->getPipDelay(pip).maxDelay(); + WireId next_wire = ctx->getPipDstWire(pip); + total_delay += ctx->getWireDelay(next_wire).maxDelay(); + } + NPNR_ASSERT(last_wire != WireId()); + if (last_wire != src) + total_delay += ctx->estimateDelay(src, last_wire); + return total_delay; + }; + update_budget(ctx, actual_delay); + } bool printNets = ctx->verbose && (jobQueue.size() < 10); -- cgit v1.2.3 From e92698f32e3d6ff1ac8cfccc46c966114acb8433 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 21 Jul 2018 18:04:54 -0700 Subject: Fix delay function used for update_budget() --- common/router1.cc | 31 ++++++++++++++++++++++--------- 1 file changed, 22 insertions(+), 9 deletions(-) (limited to 'common/router1.cc') diff --git a/common/router1.cc b/common/router1.cc index 767e10fd..d6fcc611 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -736,16 +736,29 @@ bool router1(Context *ctx) log_info("routing queue contains %d jobs.\n", int(jobQueue.size())); } else { static auto actual_delay = [](Context *ctx, WireId src, WireId dst) { - delay_t total_delay = ctx->getWireDelay(dst).maxDelay(); - WireId last_wire = dst; - for (auto pip : ctx->getPipsDownhill(dst)) { - total_delay += ctx->getPipDelay(pip).maxDelay(); - WireId next_wire = ctx->getPipDstWire(pip); - total_delay += ctx->getWireDelay(next_wire).maxDelay(); + delay_t total_delay = 0; + WireId last = dst; + auto net_name = ctx->getBoundWireNet(src); + if (net_name != IdString()) { + auto net = ctx->nets.at(net_name).get(); + while (last != src) { + total_delay += ctx->getWireDelay(last).maxDelay(); + auto pip = net->wires.at(last).pip; + NPNR_ASSERT(ctx->getBoundPipNet(pip) == net_name); + total_delay += ctx->getPipDelay(pip).maxDelay(); + last = ctx->getPipSrcWire(pip); + if (ctx->getBoundWireNet(last) != net_name) { + log_warning("Wire %s bound to %s not %s!\n", ctx->getWireName(last).c_str(ctx), ctx->getBoundWireNet(last).c_str(ctx), net_name.c_str(ctx)); + break; + } + NPNR_ASSERT(ctx->getBoundWireNet(last) == net_name); + } + NPNR_ASSERT(last != WireId()); } - NPNR_ASSERT(last_wire != WireId()); - if (last_wire != src) - total_delay += ctx->estimateDelay(src, last_wire); + if (last != src) + total_delay += ctx->estimateDelay(src, last); + else + total_delay += ctx->getWireDelay(last).maxDelay(); return total_delay; }; update_budget(ctx, actual_delay); -- cgit v1.2.3 From ee2e6ed1c6c6f7fe13f7d20a2310626f445d8612 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 23 Jul 2018 18:58:57 -0700 Subject: Simplify and use Arch::getNetinfoRouteDelay() for update_budget() --- common/router1.cc | 36 ++++-------------------------------- 1 file changed, 4 insertions(+), 32 deletions(-) (limited to 'common/router1.cc') diff --git a/common/router1.cc b/common/router1.cc index 431770da..f4f0d75b 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -613,38 +613,10 @@ bool router1(Context *ctx) std::unordered_set normalRouteNets, ripupQueue; - if (iterCnt == 1) { - if (ctx->verbose) - log_info("routing queue contains %d jobs.\n", int(jobQueue.size())); - } else { - static auto actual_delay = [](Context *ctx, WireId src, WireId dst) { - delay_t total_delay = 0; - WireId last = dst; - auto net_name = ctx->getBoundWireNet(src); - if (net_name != IdString()) { - auto net = ctx->nets.at(net_name).get(); - while (last != src) { - total_delay += ctx->getWireDelay(last).maxDelay(); - auto pip = net->wires.at(last).pip; - NPNR_ASSERT(ctx->getBoundPipNet(pip) == net_name); - total_delay += ctx->getPipDelay(pip).maxDelay(); - last = ctx->getPipSrcWire(pip); - if (ctx->getBoundWireNet(last) != net_name) { - log_warning("Wire %s bound to %s not %s!\n", ctx->getWireName(last).c_str(ctx), ctx->getBoundWireNet(last).c_str(ctx), net_name.c_str(ctx)); - break; - } - NPNR_ASSERT(ctx->getBoundWireNet(last) == net_name); - } - NPNR_ASSERT(last != WireId()); - } - if (last != src) - total_delay += ctx->estimateDelay(src, last); - else - total_delay += ctx->getWireDelay(last).maxDelay(); - return total_delay; - }; - update_budget(ctx, actual_delay); - } + if (iterCnt == 1 && ctx->verbose) + log_info("routing queue contains %d jobs.\n", int(jobQueue.size())); + + update_budget(ctx); bool printNets = ctx->verbose && (jobQueue.size() < 10); -- cgit v1.2.3 From adc1a86648453b6bbc96ed6c3eb9d1ac0cdc0bbc Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 23 Jul 2018 19:25:00 -0700 Subject: Oops --- common/router1.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common/router1.cc') diff --git a/common/router1.cc b/common/router1.cc index f4f0d75b..dbf97af7 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -613,7 +613,7 @@ bool router1(Context *ctx) std::unordered_set normalRouteNets, ripupQueue; - if (iterCnt == 1 && ctx->verbose) + if (ctx->verbose || iterCnt == 1) log_info("routing queue contains %d jobs.\n", int(jobQueue.size())); update_budget(ctx); -- cgit v1.2.3 From 760a47779aca8aabbc11b4a769e987a1ce42ad0c Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Wed, 25 Jul 2018 18:21:39 -0700 Subject: Add compute_fmax() with refactoring, plus print out Fmax estimate post-place and post-route --- common/router1.cc | 1 + 1 file changed, 1 insertion(+) (limited to 'common/router1.cc') diff --git a/common/router1.cc b/common/router1.cc index dbf97af7..8664819f 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -815,6 +815,7 @@ bool router1(Context *ctx) ctx->check(); ctx->unlock(); #endif + log_info("estimated Fmax = %.2f MHz\n", compute_fmax(ctx) / 1e6); return true; } catch (log_execution_error_exception) { #ifndef NDEBUG -- cgit v1.2.3 From b211dded3fa21859227a24b2129a680306fc5a65 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Wed, 25 Jul 2018 22:10:26 -0700 Subject: Fix min_slack computation, and print out critical path after routing --- common/router1.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common/router1.cc') diff --git a/common/router1.cc b/common/router1.cc index 8664819f..dae8d8cb 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -815,7 +815,7 @@ bool router1(Context *ctx) ctx->check(); ctx->unlock(); #endif - log_info("estimated Fmax = %.2f MHz\n", compute_fmax(ctx) / 1e6); + compute_fmax(ctx, true /* print_fmax */, true /* print_path */); return true; } catch (log_execution_error_exception) { #ifndef NDEBUG -- cgit v1.2.3 From e0517caf1aeb520733edb49f13b4ef61923d41f1 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 28 Jul 2018 12:50:21 -0700 Subject: Refactor --- common/router1.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common/router1.cc') diff --git a/common/router1.cc b/common/router1.cc index 2ae54245..d1551363 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -814,7 +814,7 @@ bool router1(Context *ctx) #ifndef NDEBUG ctx->check(); #endif - compute_fmax(ctx, true /* print_fmax */, true /* print_path */); + timing_analysis(ctx, true /* print_fmax */, true /* print_path */); ctx->unlock(); return true; } catch (log_execution_error_exception) { -- cgit v1.2.3 From de6d0d20d7d8e4d79fe1f96bc44945326c230fc4 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 28 Jul 2018 14:10:48 -0700 Subject: Merge update_budget into assign_budget; update as we go along --- common/router1.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common/router1.cc') diff --git a/common/router1.cc b/common/router1.cc index d1551363..e18f27fb 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -616,7 +616,7 @@ bool router1(Context *ctx) if (ctx->verbose || iterCnt == 1) log_info("routing queue contains %d jobs.\n", int(jobQueue.size())); - update_budget(ctx); + assign_budget(ctx, true /* quiet */); bool printNets = ctx->verbose && (jobQueue.size() < 10); -- cgit v1.2.3