diff options
| -rw-r--r-- | common/nextpnr.h | 1 | ||||
| -rw-r--r-- | common/placer1.cc | 11 | ||||
| -rw-r--r-- | common/router1.cc | 4 | ||||
| -rw-r--r-- | common/timing.cc | 189 | ||||
| -rw-r--r-- | common/timing.h | 5 | ||||
| -rw-r--r-- | ecp5/main.cc | 6 | ||||
| -rw-r--r-- | ice40/main.cc | 6 |
7 files changed, 195 insertions, 27 deletions
diff --git a/common/nextpnr.h b/common/nextpnr.h index 5e32d5b6..c4c05ae0 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -470,6 +470,7 @@ struct Context : Arch, DeterministicRNG bool force = false; bool timing_driven = true; float target_freq = 12e6; + bool user_freq = false; Context(ArchArgs args) : Arch(args) {} diff --git a/common/placer1.cc b/common/placer1.cc index 4659da11..264f1eba 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -155,6 +155,7 @@ class SAPlacer ctx->unlock(); int n_no_progress = 0; + wirelen_t min_metric = curr_metric; double avg_metric = curr_metric; temp = 10000; @@ -180,6 +181,11 @@ class SAPlacer } } + if (curr_metric < min_metric) { + min_metric = curr_metric; + improved = true; + } + // Heuristic to improve placement on the 8k if (improved) n_no_progress = 0; @@ -233,6 +239,8 @@ class SAPlacer diameter *= post_legalise_dia_scale; ctx->shuffle(autoplaced); assign_budget(ctx); + } else { + update_budget(ctx); } // Recalculate total metric entirely to avoid rounding errors @@ -267,6 +275,7 @@ class SAPlacer } } } + compute_fmax(ctx, true /* print_fmax */); ctx->unlock(); return true; } @@ -382,8 +391,6 @@ class SAPlacer // SA acceptance criterea if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { n_accept++; - if (delta < 2) - improved = true; } else { if (other != IdString()) ctx->unbindBel(oldBel); diff --git a/common/router1.cc b/common/router1.cc index 8a05236f..2ae54245 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -22,6 +22,7 @@ #include "log.h" #include "router1.h" +#include "timing.h" namespace { @@ -615,6 +616,8 @@ bool router1(Context *ctx) if (ctx->verbose || iterCnt == 1) log_info("routing queue contains %d jobs.\n", int(jobQueue.size())); + update_budget(ctx); + bool printNets = ctx->verbose && (jobQueue.size() < 10); while (!jobQueue.empty()) { @@ -811,6 +814,7 @@ bool router1(Context *ctx) #ifndef NDEBUG ctx->check(); #endif + compute_fmax(ctx, true /* print_fmax */, true /* print_path */); ctx->unlock(); return true; } catch (log_execution_error_exception) { diff --git a/common/timing.cc b/common/timing.cc index d91dea20..cefe36f0 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -22,19 +22,30 @@ #include <unordered_map> #include <utility> #include "log.h" +#include "util.h" NEXTPNR_NAMESPACE_BEGIN -static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack); +typedef std::unordered_map<const PortInfo *, delay_t> UpdateMap; +typedef std::list<const PortRef *> PortRefList; + +static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap *updates, + delay_t &min_slack, PortRefList *current_path, PortRefList *crit_path); // Follow a path, returning budget to annotate -static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, delay_t slack) +static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, delay_t slack, UpdateMap *updates, + delay_t &min_slack, PortRefList *current_path, PortRefList *crit_path) { delay_t value; if (ctx->getPortClock(user.cell, user.port) != IdString()) { // At the end of a timing path (arguably, should check setup time // here too) value = slack / path_length; + if (slack < min_slack) { + min_slack = slack; + if (crit_path) + *crit_path = *current_path; + } } else { // Default to the path ending here, if no further paths found value = slack / path_length; @@ -47,7 +58,8 @@ static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, de if (is_path) { NetInfo *net = port.second.net; if (net) { - delay_t path_budget = follow_net(ctx, net, path_length, slack - comb_delay); + delay_t path_budget = follow_net(ctx, net, path_length, slack - comb_delay, updates, min_slack, + current_path, crit_path); value = std::min(value, path_budget); } } @@ -55,53 +67,96 @@ static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, de } } - if (value < user.budget) { - user.budget = value; + if (updates) { + auto ret = updates->emplace(&user.cell->ports.at(user.port), value); + if (!ret.second) + ret.first->second = std::min(value, ret.first->second); } return value; } -static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack) +static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap *updates, + delay_t &min_slack, PortRefList *current_path, PortRefList *crit_path) { delay_t net_budget = slack / (path_length + 1); - for (auto &usr : net->users) { - net_budget = std::min(net_budget, follow_user_port(ctx, usr, path_length + 1, slack)); + for (unsigned i = 0; i < net->users.size(); ++i) { + auto &usr = net->users[i]; + if (crit_path) + current_path->push_back(&usr); + net_budget = std::min(net_budget, + follow_user_port(ctx, usr, path_length + 1, slack - ctx->getNetinfoRouteDelay(net, i), + updates, min_slack, current_path, crit_path)); + if (crit_path) + current_path->pop_back(); } return net_budget; } -void assign_budget(Context *ctx) +static delay_t compute_min_slack(Context *ctx, UpdateMap *updates, PortRefList *crit_path) { - log_break(); - log_info("Annotating ports with timing budgets\n"); - // Clear delays to a very high value first delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); - for (auto &net : ctx->nets) { - for (auto &usr : net.second->users) { - usr.budget = default_slack; - } - } - // Go through all clocked drivers and set up paths + delay_t min_slack = default_slack; + + PortRefList current_path; + + // Go through all clocked drivers and distribute the available path + // slack evenly into the budget of every sink on the path --- + // record this value into the UpdateMap for (auto &cell : ctx->cells) { for (auto port : cell.second->ports) { if (port.second.type == PORT_OUT) { IdString clock_domain = ctx->getPortClock(cell.second.get(), port.first); if (clock_domain != IdString()) { - delay_t slack = delay_t(1.0e12 / ctx->target_freq); // TODO: clock constraints + delay_t slack = default_slack; // TODO: clock constraints delay_t clkToQ; if (ctx->getCellDelay(cell.second.get(), clock_domain, port.first, clkToQ)) slack -= clkToQ; if (port.second.net) - follow_net(ctx, port.second.net, 0, slack); + follow_net(ctx, port.second.net, 0, slack, updates, min_slack, ¤t_path, crit_path); } } } } - // Post-allocation check + return min_slack; +} + +void assign_budget(Context *ctx) +{ + log_break(); + log_info("Annotating ports with timing budgets\n"); + // Clear delays to a very high value first + delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); for (auto &net : ctx->nets) { - for (auto user : net.second->users) { - if (user.budget < 0) + for (auto &usr : net.second->users) { + usr.budget = default_slack; + } + } + + UpdateMap updates; + delay_t min_slack = compute_min_slack(ctx, &updates, nullptr); + + // If user has not specified a frequency, adjust the target frequency + // to be equivalent to the estimate Fmax + if (!ctx->user_freq) { + ctx->target_freq = 1e12 / (default_slack - min_slack); + if (ctx->verbose) + log_info("minimum slack for this assign = %d, target Fmax for next update = %.2f MHz\n", min_slack, + ctx->target_freq / 1e6); + } + + // Update the budgets + for (auto &net : ctx->nets) { + for (size_t i = 0; i < net.second->users.size(); ++i) { + auto &user = net.second->users[i]; + auto pi = &user.cell->ports.at(user.port); + auto it = updates.find(pi); + if (it == updates.end()) + continue; + user.budget = ctx->getNetinfoRouteDelay(net.second.get(), i) - it->second; + + // Post-update check + if (ctx->user_freq && user.budget < 0) log_warning("port %s.%s, connected to net '%s', has negative " "timing budget of %fns\n", user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx), @@ -117,4 +172,92 @@ void assign_budget(Context *ctx) log_info("Checksum: 0x%08x\n", ctx->checksum()); } +void update_budget(Context *ctx) +{ + UpdateMap updates; + delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); + delay_t min_slack = compute_min_slack(ctx, &updates, nullptr); + + // If user has not specified a frequency, adjust the frequency dynamically: + if (!ctx->user_freq) { + if (min_slack < 0) + ctx->target_freq = 1e12 / (default_slack - 0.99 * min_slack); + else + ctx->target_freq = 1e12 / (default_slack - 1.05 * min_slack); + if (ctx->verbose) + log_info("minimum slack for this update = %d, target Fmax for next update = %.2f MHz\n", min_slack, + ctx->target_freq / 1e6); + } + + // Update the budgets + for (auto &net : ctx->nets) { + for (size_t i = 0; i < net.second->users.size(); ++i) { + auto &user = net.second->users[i]; + auto pi = &user.cell->ports.at(user.port); + auto it = updates.find(pi); + if (it == updates.end()) + continue; + user.budget = ctx->getNetinfoRouteDelay(net.second.get(), i) + it->second; + + // Post-update check + if (ctx->verbose) { + if (ctx->user_freq && user.budget < 0) + log_warning("port %s.%s, connected to net '%s', has negative " + "timing budget of %fns\n", + user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx), + ctx->getDelayNS(user.budget)); + else + log_info("port %s.%s, connected to net '%s', has " + "timing budget of %fns\n", + user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx), + ctx->getDelayNS(user.budget)); + } + } + } +} + +void compute_fmax(Context *ctx, bool print_fmax, bool print_path) +{ + delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); + PortRefList crit_path; + delay_t min_slack = compute_min_slack(ctx, nullptr, &crit_path); + if (print_path) { + delay_t total = 0; + log_break(); + log_info("Critical path report:\n"); + log_info("curr total\n"); + auto &front = crit_path.front(); + auto &front_port = front->cell->ports.at(front->port); + auto &front_driver = front_port.net->driver; + auto last_port = ctx->getPortClock(front_driver.cell, front_driver.port); + for (auto sink : crit_path) { + auto sink_cell = sink->cell; + auto &port = sink_cell->ports.at(sink->port); + auto net = port.net; + unsigned i = 0; + for (auto &usr : net->users) + if (&usr == sink) + break; + auto &driver = net->driver; + auto driver_cell = driver.cell; + delay_t comb_delay; + ctx->getCellDelay(sink_cell, last_port, driver.port, comb_delay); + total += comb_delay; + log_info("%4d %4d Source %s.%s\n", comb_delay, total, driver_cell->name.c_str(ctx), + driver.port.c_str(ctx)); + delay_t net_delay = ctx->getNetinfoRouteDelay(net, i); + total += net_delay; + auto driver_loc = ctx->getBelLocation(driver_cell->bel); + auto sink_loc = ctx->getBelLocation(sink_cell->bel); + log_info("%4d %4d Net %s budget %d (%d,%d) -> (%d,%d)\n", net_delay, total, net->name.c_str(ctx), + sink->budget, driver_loc.x, driver_loc.y, sink_loc.x, sink_loc.y); + log_info(" Sink %s.%s\n", sink_cell->name.c_str(ctx), sink->port.c_str(ctx)); + last_port = sink->port; + } + log_break(); + } + if (print_fmax) + log_info("estimated Fmax = %.2f MHz\n", 1e6 / (default_slack - min_slack)); +} + NEXTPNR_NAMESPACE_END diff --git a/common/timing.h b/common/timing.h index 025e4a76..a1e12ab3 100644 --- a/common/timing.h +++ b/common/timing.h @@ -27,6 +27,11 @@ NEXTPNR_NAMESPACE_BEGIN // Assign "budget" values for all user ports in the design void assign_budget(Context *ctx); +// Evenly redistribute the total path slack amongst all sinks on each path +void update_budget(Context *ctx); + +void compute_fmax(Context *ctx, bool print_fmax = false, bool print_path = false); + NEXTPNR_NAMESPACE_END #endif diff --git a/ecp5/main.cc b/ecp5/main.cc index f2db74d7..9f683a7b 100644 --- a/ecp5/main.cc +++ b/ecp5/main.cc @@ -167,8 +167,12 @@ int main(int argc, char *argv[]) if (!ctx->pack() && !ctx->force) log_error("Packing design failed.\n"); - if (vm.count("freq")) + if (vm.count("freq")) { ctx->target_freq = vm["freq"].as<double>() * 1e6; + ctx->user_freq = true; + } else { + log_warning("Target frequency not specified. Will optimise for max frequency.\n"); + } assign_budget(ctx.get()); ctx->check(); print_utilisation(ctx.get()); diff --git a/ice40/main.cc b/ice40/main.cc index 32815b26..865eea9e 100644 --- a/ice40/main.cc +++ b/ice40/main.cc @@ -363,8 +363,12 @@ int main(int argc, char *argv[]) } } - if (vm.count("freq")) + if (vm.count("freq")) { ctx->target_freq = vm["freq"].as<double>() * 1e6; + ctx->user_freq = true; + } else { + log_warning("Target frequency not specified. Will optimise for max frequency.\n"); + } ctx->timing_driven = true; if (vm.count("no-tmdriv")) |