From 27a79a3a4f464f2d038f66737d78aaa2fb6f2703 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 21 Jul 2018 01:55:20 -0700 Subject: Update comment --- common/timing.cc | 118 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 118 insertions(+) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 3a48935f..479dba26 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -22,6 +22,7 @@ #include #include #include "log.h" +#include "util.h" NEXTPNR_NAMESPACE_BEGIN @@ -114,4 +115,121 @@ void assign_budget(Context *ctx) log_info("Checksum: 0x%08x\n", ctx->checksum()); } +typedef std::unordered_map updates_t; +typedef std::unordered_map delays_t; + +static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, delay_t slack, const delays_t& delays, updates_t& updates); + +// Follow a path, returning budget to annotate +static delay_t follow_user_port_update(Context *ctx, PortRef &user, int path_length, delay_t slack, const delays_t& delays, updates_t& updates) +{ + 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; + } else { + // Default to the path ending here, if no further paths found + value = slack / path_length; + // Follow outputs of the user + for (auto& port : user.cell->ports) { + if (port.second.type == PORT_OUT) { + delay_t comb_delay; + // Look up delay through this path + bool is_path = ctx->getCellDelay(user.cell, user.port, port.first, comb_delay); + if (is_path) { + NetInfo *net = port.second.net; + if (net) { + delay_t path_budget = follow_net_update(ctx, net, path_length, slack - comb_delay, delays, updates); + value = std::min(value, path_budget); + } + } + } + } + } + + auto ret = updates.emplace(&user.cell->ports.at(user.port), value); + if (!ret.second && value < ret.first->second) { + ret.first->second = value; + } + return value; +} + +static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, delay_t slack, const delays_t& delays,updates_t& updates) +{ + delay_t net_budget = slack / (path_length + 1); + for (auto& usr : net->users) { + net_budget = std::min(net_budget, follow_user_port_update(ctx, usr, path_length + 1, slack - get_or_default(delays, &usr.cell->ports.at(usr.port), 0.), delays, updates)); + } + return net_budget; +} + +void update_budget(Context *ctx) +{ + delays_t delays; + updates_t updates; + + // Compute the delay for every pin on every net + for (auto &n : ctx->nets) { + auto net = n.second.get(); + + int driver_x, driver_y; + bool driver_gb; + CellInfo *driver_cell = net->driver.cell; + if (!driver_cell) + continue; + if (driver_cell->bel == BelId()) + continue; + ctx->estimatePosition(driver_cell->bel, driver_x, driver_y, driver_gb); + WireId drv_wire = ctx->getWireBelPin(driver_cell->bel, ctx->portPinFromId(net->driver.port)); + if (driver_gb) + continue; + for (auto& load : net->users) { + if (load.cell == nullptr) + continue; + CellInfo *load_cell = load.cell; + if (load_cell->bel == BelId()) + continue; + WireId user_wire = ctx->getWireBelPin(load_cell->bel, ctx->portPinFromId(load.port)); + delay_t raw_wl = ctx->estimateDelay(drv_wire, user_wire); + delays.emplace(&load_cell->ports.at(load.port), raw_wl); + } + } + + // Go through all clocked drivers and distribute the available path slack evenly into every budget + 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()) { + if (port.second.net) + follow_net_update(ctx, port.second.net, 0, delay_t(1.0e12 / ctx->target_freq) - get_or_default(delays, &port.second, 0.), delays, updates); + } + } + } + } + + // Update the budgets + for (auto &net : ctx->nets) { + for (auto& user : net.second->users) { + auto pi = &user.cell->ports.at(user.port); + auto it = updates.find(pi); + if (it == updates.end()) continue; + user.budget = delays.at(pi) + it->second; + + // Post-update check +// if (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)); +// if (ctx->verbose) +// 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)); + } + } +} + NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From f89115c3e31012859a0981d6bccc8290d35b2d96 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 21 Jul 2018 01:55:46 -0700 Subject: Add update_budget() to timing.h header --- common/timing.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'common') diff --git a/common/timing.h b/common/timing.h index 025e4a76..b5574392 100644 --- a/common/timing.h +++ b/common/timing.h @@ -27,6 +27,8 @@ NEXTPNR_NAMESPACE_BEGIN // Assign "budget" values for all user ports in the design void assign_budget(Context *ctx); +void update_budget(Context *ctx); + NEXTPNR_NAMESPACE_END #endif -- cgit v1.2.3 From 3eecccc6f7f8c36994e9227adfc8ab1067ea287f Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 21 Jul 2018 01:59:16 -0700 Subject: Avoid hysteresis preventing placer from stopping --- common/placer1.cc | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-) (limited to 'common') diff --git a/common/placer1.cc b/common/placer1.cc index 74a11040..be20c072 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -145,6 +145,7 @@ class SAPlacer } int n_no_progress = 0; + wirelen_t min_metric = curr_metric; double avg_metric = curr_metric; temp = 10000; @@ -169,6 +170,12 @@ class SAPlacer try_swap_position(cell, try_bel); } } + + if (curr_metric < min_metric) { + min_metric = curr_metric; + improved = true; + } + // Heuristic to improve placement on the 8k if (improved) n_no_progress = 0; @@ -222,6 +229,9 @@ class SAPlacer ctx->shuffle(autoplaced); assign_budget(ctx); } + else { + update_budget(ctx); + } // Recalculate total metric entirely to avoid rounding errors // accumulating over time @@ -365,8 +375,8 @@ 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; + //if (delta < 2) + // improved = true; } else { if (other != IdString()) ctx->unbindBel(oldBel); -- cgit v1.2.3 From 1cd5c9dac8452ee8d8f51931dcff028245898618 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 21 Jul 2018 01:55:20 -0700 Subject: Update comment --- common/timing.cc | 118 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 118 insertions(+) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 3a48935f..479dba26 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -22,6 +22,7 @@ #include #include #include "log.h" +#include "util.h" NEXTPNR_NAMESPACE_BEGIN @@ -114,4 +115,121 @@ void assign_budget(Context *ctx) log_info("Checksum: 0x%08x\n", ctx->checksum()); } +typedef std::unordered_map updates_t; +typedef std::unordered_map delays_t; + +static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, delay_t slack, const delays_t& delays, updates_t& updates); + +// Follow a path, returning budget to annotate +static delay_t follow_user_port_update(Context *ctx, PortRef &user, int path_length, delay_t slack, const delays_t& delays, updates_t& updates) +{ + 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; + } else { + // Default to the path ending here, if no further paths found + value = slack / path_length; + // Follow outputs of the user + for (auto& port : user.cell->ports) { + if (port.second.type == PORT_OUT) { + delay_t comb_delay; + // Look up delay through this path + bool is_path = ctx->getCellDelay(user.cell, user.port, port.first, comb_delay); + if (is_path) { + NetInfo *net = port.second.net; + if (net) { + delay_t path_budget = follow_net_update(ctx, net, path_length, slack - comb_delay, delays, updates); + value = std::min(value, path_budget); + } + } + } + } + } + + auto ret = updates.emplace(&user.cell->ports.at(user.port), value); + if (!ret.second && value < ret.first->second) { + ret.first->second = value; + } + return value; +} + +static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, delay_t slack, const delays_t& delays,updates_t& updates) +{ + delay_t net_budget = slack / (path_length + 1); + for (auto& usr : net->users) { + net_budget = std::min(net_budget, follow_user_port_update(ctx, usr, path_length + 1, slack - get_or_default(delays, &usr.cell->ports.at(usr.port), 0.), delays, updates)); + } + return net_budget; +} + +void update_budget(Context *ctx) +{ + delays_t delays; + updates_t updates; + + // Compute the delay for every pin on every net + for (auto &n : ctx->nets) { + auto net = n.second.get(); + + int driver_x, driver_y; + bool driver_gb; + CellInfo *driver_cell = net->driver.cell; + if (!driver_cell) + continue; + if (driver_cell->bel == BelId()) + continue; + ctx->estimatePosition(driver_cell->bel, driver_x, driver_y, driver_gb); + WireId drv_wire = ctx->getWireBelPin(driver_cell->bel, ctx->portPinFromId(net->driver.port)); + if (driver_gb) + continue; + for (auto& load : net->users) { + if (load.cell == nullptr) + continue; + CellInfo *load_cell = load.cell; + if (load_cell->bel == BelId()) + continue; + WireId user_wire = ctx->getWireBelPin(load_cell->bel, ctx->portPinFromId(load.port)); + delay_t raw_wl = ctx->estimateDelay(drv_wire, user_wire); + delays.emplace(&load_cell->ports.at(load.port), raw_wl); + } + } + + // Go through all clocked drivers and distribute the available path slack evenly into every budget + 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()) { + if (port.second.net) + follow_net_update(ctx, port.second.net, 0, delay_t(1.0e12 / ctx->target_freq) - get_or_default(delays, &port.second, 0.), delays, updates); + } + } + } + } + + // Update the budgets + for (auto &net : ctx->nets) { + for (auto& user : net.second->users) { + auto pi = &user.cell->ports.at(user.port); + auto it = updates.find(pi); + if (it == updates.end()) continue; + user.budget = delays.at(pi) + it->second; + + // Post-update check +// if (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)); +// if (ctx->verbose) +// 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)); + } + } +} + NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From 241418dc250ba863add1ecddc0543bd00c915c0b Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 21 Jul 2018 01:55:46 -0700 Subject: Add update_budget() to timing.h header --- common/timing.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'common') diff --git a/common/timing.h b/common/timing.h index 025e4a76..b5574392 100644 --- a/common/timing.h +++ b/common/timing.h @@ -27,6 +27,8 @@ NEXTPNR_NAMESPACE_BEGIN // Assign "budget" values for all user ports in the design void assign_budget(Context *ctx); +void update_budget(Context *ctx); + NEXTPNR_NAMESPACE_END #endif -- cgit v1.2.3 From d23cdd6c06a37ef32740ee910aba6704a8a46292 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 21 Jul 2018 01:59:16 -0700 Subject: Avoid hysteresis preventing placer from stopping --- common/placer1.cc | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-) (limited to 'common') diff --git a/common/placer1.cc b/common/placer1.cc index 74a11040..be20c072 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -145,6 +145,7 @@ class SAPlacer } int n_no_progress = 0; + wirelen_t min_metric = curr_metric; double avg_metric = curr_metric; temp = 10000; @@ -169,6 +170,12 @@ class SAPlacer try_swap_position(cell, try_bel); } } + + if (curr_metric < min_metric) { + min_metric = curr_metric; + improved = true; + } + // Heuristic to improve placement on the 8k if (improved) n_no_progress = 0; @@ -222,6 +229,9 @@ class SAPlacer ctx->shuffle(autoplaced); assign_budget(ctx); } + else { + update_budget(ctx); + } // Recalculate total metric entirely to avoid rounding errors // accumulating over time @@ -365,8 +375,8 @@ 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; + //if (delta < 2) + // improved = true; } else { if (other != IdString()) ctx->unbindBel(oldBel); -- cgit v1.2.3 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') 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 b2452f4646bd828a34ce9efe8ad0fb0772723a90 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 21 Jul 2018 19:33:42 +0200 Subject: HACK: set carry budgets to zero --- common/timing.cc | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 479dba26..26f6530e 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -216,7 +216,10 @@ void update_budget(Context *ctx) auto it = updates.find(pi); if (it == updates.end()) continue; user.budget = delays.at(pi) + it->second; - + // HACK HACK HACK + if (net.second->driver.port == ctx->id("COUT")) + user.budget = 0; + // HACK HACK HACK // Post-update check // if (user.budget < 0) // log_warning("port %s.%s, connected to net '%s', has negative " -- cgit v1.2.3 From e44dc25f098194c970d1a516fbaa0a5e911a50e1 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 21 Jul 2018 12:47:09 -0700 Subject: Uncomment out negative slack messages during update_budget(), make verbose --- common/timing.cc | 22 ++++++++++++---------- 1 file changed, 12 insertions(+), 10 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 5f744621..6b4a8b64 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -223,16 +223,18 @@ void update_budget(Context *ctx) // HACK HACK HACK // Post-update check -// if (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)); -// if (ctx->verbose) -// 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)); + if (ctx->verbose) { + if (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)); + } } } } -- cgit v1.2.3 From 926c186ec78efb086364a05ba7e83e68fa116301 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 21 Jul 2018 13:05:09 -0700 Subject: Add Arch::getBudgetOverride() to eliminate hack for COUT --- common/timing.cc | 8 ++------ 1 file changed, 2 insertions(+), 6 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 6b4a8b64..9723550b 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -215,12 +215,8 @@ void update_budget(Context *ctx) auto pi = &user.cell->ports.at(user.port); auto it = updates.find(pi); if (it == updates.end()) continue; - user.budget = delays.at(pi) + it->second; - - // HACK HACK HACK - if (net.second->driver.port == ctx->id("COUT")) - user.budget = 0; - // HACK HACK HACK + auto budget = delays.at(pi) + it->second; + user.budget = ctx->getBudgetOverride(net.second->driver, budget); // Post-update check if (ctx->verbose) { -- 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 ++++++++++++++++++++-- common/timing.cc | 4 ++-- common/timing.h | 2 +- 3 files changed, 23 insertions(+), 5 deletions(-) (limited to 'common') 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); diff --git a/common/timing.cc b/common/timing.cc index 9723550b..0e84dded 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -164,7 +164,7 @@ static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, de return net_budget; } -void update_budget(Context *ctx) +void update_budget(Context *ctx, std::function delay_fn) { delays_t delays; updates_t updates; @@ -191,7 +191,7 @@ void update_budget(Context *ctx) if (load_cell->bel == BelId()) continue; WireId user_wire = ctx->getWireBelPin(load_cell->bel, ctx->portPinFromId(load.port)); - delay_t raw_wl = ctx->estimateDelay(drv_wire, user_wire); + delay_t raw_wl = delay_fn(ctx, drv_wire, user_wire); delays.emplace(&load_cell->ports.at(load.port), raw_wl); } } diff --git a/common/timing.h b/common/timing.h index b5574392..8c098963 100644 --- a/common/timing.h +++ b/common/timing.h @@ -27,7 +27,7 @@ NEXTPNR_NAMESPACE_BEGIN // Assign "budget" values for all user ports in the design void assign_budget(Context *ctx); -void update_budget(Context *ctx); +void update_budget(Context *ctx, std::function delay_fn=&Context::estimateDelay); NEXTPNR_NAMESPACE_END -- 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') 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 ++++---------------------------- common/timing.cc | 61 +++++++++++++++++++------------------------------------ common/timing.h | 2 +- 3 files changed, 26 insertions(+), 73 deletions(-) (limited to 'common') 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); diff --git a/common/timing.cc b/common/timing.cc index 0e84dded..dd0bf52a 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -116,12 +116,11 @@ void assign_budget(Context *ctx) } typedef std::unordered_map updates_t; -typedef std::unordered_map delays_t; -static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, delay_t slack, const delays_t& delays, updates_t& updates); +static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, delay_t slack, updates_t& updates); // Follow a path, returning budget to annotate -static delay_t follow_user_port_update(Context *ctx, PortRef &user, int path_length, delay_t slack, const delays_t& delays, updates_t& updates) +static delay_t follow_user_port_update(Context *ctx, PortRef &user, int path_length, delay_t slack, updates_t& updates) { delay_t value; if (ctx->getPortClock(user.cell, user.port) != IdString()) { @@ -140,7 +139,7 @@ static delay_t follow_user_port_update(Context *ctx, PortRef &user, int path_len if (is_path) { NetInfo *net = port.second.net; if (net) { - delay_t path_budget = follow_net_update(ctx, net, path_length, slack - comb_delay, delays, updates); + delay_t path_budget = follow_net_update(ctx, net, path_length, slack - comb_delay, updates); value = std::min(value, path_budget); } } @@ -155,55 +154,36 @@ static delay_t follow_user_port_update(Context *ctx, PortRef &user, int path_len return value; } -static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, delay_t slack, const delays_t& delays,updates_t& updates) +static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, delay_t slack, updates_t& updates) { delay_t net_budget = slack / (path_length + 1); - for (auto& usr : net->users) { - net_budget = std::min(net_budget, follow_user_port_update(ctx, usr, path_length + 1, slack - get_or_default(delays, &usr.cell->ports.at(usr.port), 0.), delays, updates)); + for (size_t i = 0; i < net->users.size(); ++i) { + auto& usr = net->users[i]; + net_budget = std::min(net_budget, follow_user_port_update(ctx, usr, path_length + 1, slack - ctx->getNetinfoRouteDelay(net, i), updates)); } return net_budget; } -void update_budget(Context *ctx, std::function delay_fn) +void update_budget(Context *ctx) { - delays_t delays; updates_t updates; - // Compute the delay for every pin on every net - for (auto &n : ctx->nets) { - auto net = n.second.get(); - - int driver_x, driver_y; - bool driver_gb; - CellInfo *driver_cell = net->driver.cell; - if (!driver_cell) - continue; - if (driver_cell->bel == BelId()) - continue; - ctx->estimatePosition(driver_cell->bel, driver_x, driver_y, driver_gb); - WireId drv_wire = ctx->getWireBelPin(driver_cell->bel, ctx->portPinFromId(net->driver.port)); - if (driver_gb) - continue; - for (auto& load : net->users) { - if (load.cell == nullptr) - continue; - CellInfo *load_cell = load.cell; - if (load_cell->bel == BelId()) - continue; - WireId user_wire = ctx->getWireBelPin(load_cell->bel, ctx->portPinFromId(load.port)); - delay_t raw_wl = delay_fn(ctx, drv_wire, user_wire); - delays.emplace(&load_cell->ports.at(load.port), raw_wl); - } - } - // Go through all clocked drivers and distribute the available path slack evenly into every budget 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()) { - if (port.second.net) - follow_net_update(ctx, port.second.net, 0, delay_t(1.0e12 / ctx->target_freq) - get_or_default(delays, &port.second, 0.), delays, updates); + auto net = port.second.net; + if (net) { + delay_t delay = 0; + if (port.second.name != net->driver.port) { + const auto& users = net->users; + auto it = std::find_if(users.begin(), users.end(), [&port](const PortRef& pr) { return pr.port == port.second.name; }); + delay = ctx->getNetinfoRouteDelay(net, std::distance(users.begin(), it)); + } + follow_net_update(ctx, net, 0, delay_t(1.0e12 / ctx->target_freq - delay), updates); + } } } } @@ -211,11 +191,12 @@ void update_budget(Context *ctx, std::function // Update the budgets for (auto &net : ctx->nets) { - for (auto& user : net.second->users) { + 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; - auto budget = delays.at(pi) + it->second; + auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i) + it->second; user.budget = ctx->getBudgetOverride(net.second->driver, budget); // Post-update check diff --git a/common/timing.h b/common/timing.h index 8c098963..b5574392 100644 --- a/common/timing.h +++ b/common/timing.h @@ -27,7 +27,7 @@ NEXTPNR_NAMESPACE_BEGIN // Assign "budget" values for all user ports in the design void assign_budget(Context *ctx); -void update_budget(Context *ctx, std::function delay_fn=&Context::estimateDelay); +void update_budget(Context *ctx); NEXTPNR_NAMESPACE_END -- 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 +- common/timing.cc | 14 +++----------- 2 files changed, 4 insertions(+), 12 deletions(-) (limited to 'common') 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); diff --git a/common/timing.cc b/common/timing.cc index dd0bf52a..53b2f132 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -174,16 +174,8 @@ void update_budget(Context *ctx) if (port.second.type == PORT_OUT) { IdString clock_domain = ctx->getPortClock(cell.second.get(), port.first); if (clock_domain != IdString()) { - auto net = port.second.net; - if (net) { - delay_t delay = 0; - if (port.second.name != net->driver.port) { - const auto& users = net->users; - auto it = std::find_if(users.begin(), users.end(), [&port](const PortRef& pr) { return pr.port == port.second.name; }); - delay = ctx->getNetinfoRouteDelay(net, std::distance(users.begin(), it)); - } - follow_net_update(ctx, net, 0, delay_t(1.0e12 / ctx->target_freq - delay), updates); - } + if (port.second.net) + follow_net_update(ctx, port.second.net, 0, delay_t(1.0e12 / ctx->target_freq), updates); } } } @@ -192,7 +184,7 @@ void update_budget(Context *ctx) // 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& user = net.second->users[i]; auto pi = &user.cell->ports.at(user.port); auto it = updates.find(pi); if (it == updates.end()) continue; -- cgit v1.2.3 From 7b4c5594edc9d91996da194b880458b415f5c143 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Tue, 24 Jul 2018 09:20:07 -0700 Subject: Refactor new code and existing code --- common/timing.cc | 86 ++++++++++++++++---------------------------------------- 1 file changed, 25 insertions(+), 61 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 53b2f132..ae164d20 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -26,10 +26,12 @@ NEXTPNR_NAMESPACE_BEGIN -static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack); +typedef std::unordered_map UpdateMap; + +static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap &updates); // 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 value; if (ctx->getPortClock(user.cell, user.port) != IdString()) { @@ -48,7 +50,7 @@ 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); value = std::min(value, path_budget); } } @@ -56,23 +58,26 @@ static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, de } } - if (value < user.budget) { - user.budget = value; + auto ret = updates.emplace(&user.cell->ports.at(user.port), value); + if (!ret.second && value < ret.first->second) { + ret.first->second = value; } 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 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)); + net_budget = std::min(net_budget, follow_user_port(ctx, usr, path_length + 1, slack, updates)); } return net_budget; } void assign_budget(Context *ctx) { + UpdateMap updates; + log_break(); log_info("Annotating ports with timing budgets\n"); // Clear delays to a very high value first @@ -90,15 +95,23 @@ void assign_budget(Context *ctx) if (clock_domain != IdString()) { delay_t slack = delay_t(1.0e12 / ctx->target_freq); // TODO: clock constraints if (port.second.net) - follow_net(ctx, port.second.net, 0, slack); + follow_net(ctx, port.second.net, 0, slack, updates); } } } } - // Post-allocation check + // Update the budgets for (auto &net : ctx->nets) { - for (auto user : net.second->users) { + 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; + auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i) + it->second; + user.budget = ctx->getBudgetOverride(net.second->driver, budget); + + // Post-update check if (user.budget < 0) log_warning("port %s.%s, connected to net '%s', has negative " "timing budget of %fns\n", @@ -115,58 +128,9 @@ void assign_budget(Context *ctx) log_info("Checksum: 0x%08x\n", ctx->checksum()); } -typedef std::unordered_map updates_t; - -static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, delay_t slack, updates_t& updates); - -// Follow a path, returning budget to annotate -static delay_t follow_user_port_update(Context *ctx, PortRef &user, int path_length, delay_t slack, updates_t& updates) -{ - 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; - } else { - // Default to the path ending here, if no further paths found - value = slack / path_length; - // Follow outputs of the user - for (auto& port : user.cell->ports) { - if (port.second.type == PORT_OUT) { - delay_t comb_delay; - // Look up delay through this path - bool is_path = ctx->getCellDelay(user.cell, user.port, port.first, comb_delay); - if (is_path) { - NetInfo *net = port.second.net; - if (net) { - delay_t path_budget = follow_net_update(ctx, net, path_length, slack - comb_delay, updates); - value = std::min(value, path_budget); - } - } - } - } - } - - auto ret = updates.emplace(&user.cell->ports.at(user.port), value); - if (!ret.second && value < ret.first->second) { - ret.first->second = value; - } - return value; -} - -static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, delay_t slack, updates_t& updates) -{ - delay_t net_budget = slack / (path_length + 1); - for (size_t i = 0; i < net->users.size(); ++i) { - auto& usr = net->users[i]; - net_budget = std::min(net_budget, follow_user_port_update(ctx, usr, path_length + 1, slack - ctx->getNetinfoRouteDelay(net, i), updates)); - } - return net_budget; -} - void update_budget(Context *ctx) { - updates_t updates; + UpdateMap updates; // Go through all clocked drivers and distribute the available path slack evenly into every budget for (auto &cell : ctx->cells) { @@ -175,7 +139,7 @@ void update_budget(Context *ctx) IdString clock_domain = ctx->getPortClock(cell.second.get(), port.first); if (clock_domain != IdString()) { if (port.second.net) - follow_net_update(ctx, port.second.net, 0, delay_t(1.0e12 / ctx->target_freq), updates); + follow_net(ctx, port.second.net, 0, delay_t(1.0e12 / ctx->target_freq), updates); } } } -- cgit v1.2.3 From 4920cf18fa1128758dac2ffd12bf88d194863f17 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Tue, 24 Jul 2018 09:21:52 -0700 Subject: improved is only set if we get a better metric, remove commented code --- common/placer1.cc | 2 -- 1 file changed, 2 deletions(-) (limited to 'common') diff --git a/common/placer1.cc b/common/placer1.cc index 461fc4e8..77e33f5b 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -387,8 +387,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); -- cgit v1.2.3 From a69745060ef416f1e91545be110034a18ae012bd Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Tue, 24 Jul 2018 22:39:51 -0700 Subject: Also subtract net delay from slack --- common/timing.cc | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 814b0426..0a895c0b 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -68,8 +68,9 @@ static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, de static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap &updates) { 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, updates)); + for (unsigned i = 0; i < net->users.size(); ++i) { + auto &usr = net->users[i]; + net_budget = std::min(net_budget, follow_user_port(ctx, usr, path_length + 1, slack - ctx->getNetinfoRouteDelay(net, i), updates)); } return net_budget; } @@ -141,8 +142,12 @@ void update_budget(Context *ctx) 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 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, delay_t(1.0e12 / ctx->target_freq), updates); + follow_net(ctx, port.second.net, 0, slack, updates); } } } -- cgit v1.2.3 From c71212d0e148b0b2ee136a951f5d707cc8822bda Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Tue, 24 Jul 2018 23:19:24 -0700 Subject: If --freq not set, attempt to find max by adjusting budget so min path slack == 0 --- common/nextpnr.h | 1 + common/timing.cc | 37 ++++++++++++++++++++++++++++--------- 2 files changed, 29 insertions(+), 9 deletions(-) (limited to 'common') diff --git a/common/nextpnr.h b/common/nextpnr.h index 4a1aaac1..b96a60cf 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -466,6 +466,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/timing.cc b/common/timing.cc index 0a895c0b..be8e86fb 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -28,16 +28,17 @@ NEXTPNR_NAMESPACE_BEGIN typedef std::unordered_map UpdateMap; -static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap &updates); +static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap &updates, delay_t &min_slack); // Follow a path, returning budget to annotate -static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, delay_t slack, UpdateMap &updates) +static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, delay_t slack, UpdateMap &updates, delay_t &min_slack) { 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; + min_slack = std::min(min_slack, value); } else { // Default to the path ending here, if no further paths found value = slack / path_length; @@ -50,7 +51,7 @@ 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, updates); + delay_t path_budget = follow_net(ctx, net, path_length, slack - comb_delay, updates, min_slack); value = std::min(value, path_budget); } } @@ -65,12 +66,12 @@ static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, de return value; } -static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap &updates) +static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap &updates, delay_t &min_slack) { delay_t net_budget = slack / (path_length + 1); for (unsigned i = 0; i < net->users.size(); ++i) { auto &usr = net->users[i]; - net_budget = std::min(net_budget, follow_user_port(ctx, usr, path_length + 1, slack - ctx->getNetinfoRouteDelay(net, i), updates)); + net_budget = std::min(net_budget, follow_user_port(ctx, usr, path_length + 1, slack - ctx->getNetinfoRouteDelay(net, i), updates, min_slack)); } return net_budget; } @@ -78,6 +79,7 @@ static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t s void assign_budget(Context *ctx) { UpdateMap updates; + delay_t min_slack = delay_t(1.0e12 / ctx->target_freq); log_break(); log_info("Annotating ports with timing budgets\n"); @@ -88,6 +90,7 @@ void assign_budget(Context *ctx) usr.budget = default_slack; } } + min_slack = default_slack; // Go through all clocked drivers and set up paths for (auto &cell : ctx->cells) { for (auto port : cell.second->ports) { @@ -98,13 +101,21 @@ void assign_budget(Context *ctx) 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, updates); + if (port.second.net) { + log_break(); + follow_net(ctx, port.second.net, 0, slack, updates, min_slack); + } } } } } + if (!ctx->user_freq) { + ctx->target_freq = delay_t(1e12 / (default_slack - min_slack)); + if (ctx->verbose) + log_info("minimum slack for this assign = %d, target Fmax for next update = %f\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) { @@ -135,6 +146,8 @@ void assign_budget(Context *ctx) void update_budget(Context *ctx) { UpdateMap updates; + delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); + delay_t min_slack = delay_t(1.0e12 / ctx->target_freq); // Go through all clocked drivers and distribute the available path slack evenly into every budget for (auto &cell : ctx->cells) { @@ -142,17 +155,23 @@ void update_budget(Context *ctx) 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, updates); + follow_net(ctx, port.second.net, 0, slack, updates, min_slack); } } } } + if (!ctx->user_freq) { + ctx->target_freq = delay_t(1e12 / (default_slack - min_slack)); + if (ctx->verbose) + log_info("minimum slack for this update = %d, target Fmax for next update = %f\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) { -- cgit v1.2.3 From 1fa738bd881f2951465586ae20f81f33743db73f Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Tue, 24 Jul 2018 23:34:59 -0700 Subject: With no user frequency set, use 1.05 * current_Fmax --- common/timing.cc | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index be8e86fb..2c467961 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -111,7 +111,7 @@ void assign_budget(Context *ctx) } if (!ctx->user_freq) { - ctx->target_freq = delay_t(1e12 / (default_slack - min_slack)); + ctx->target_freq = 1e12 / (default_slack - min_slack); if (ctx->verbose) log_info("minimum slack for this assign = %d, target Fmax for next update = %f\n", min_slack, ctx->target_freq/1e6); } @@ -127,7 +127,7 @@ void assign_budget(Context *ctx) user.budget = ctx->getBudgetOverride(net.second->driver, budget); // Post-update check - if (user.budget < 0) + 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), @@ -167,7 +167,7 @@ void update_budget(Context *ctx) } if (!ctx->user_freq) { - ctx->target_freq = delay_t(1e12 / (default_slack - min_slack)); + ctx->target_freq = 1.05 * (1e12 / (default_slack - min_slack)); if (ctx->verbose) log_info("minimum slack for this update = %d, target Fmax for next update = %f\n", min_slack, ctx->target_freq/1e6); } @@ -184,7 +184,7 @@ void update_budget(Context *ctx) // Post-update check if (ctx->verbose) { - if (user.budget < 0) + 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), -- 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/placer1.cc | 1 + common/router1.cc | 1 + common/timing.cc | 76 +++++++++++++++++++++++++++++-------------------------- common/timing.h | 3 +++ 4 files changed, 45 insertions(+), 36 deletions(-) (limited to 'common') diff --git a/common/placer1.cc b/common/placer1.cc index 30f0057c..d38cdd4b 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -276,6 +276,7 @@ class SAPlacer } } } + log_info("estimated Fmax = %.2f MHz\n", compute_fmax(ctx) / 1e6); ctx->unlock(); return true; } 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 diff --git a/common/timing.cc b/common/timing.cc index 2c467961..784952f8 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -76,40 +76,51 @@ static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t s return net_budget; } -void assign_budget(Context *ctx) +static UpdateMap compute_min_slack(Context *ctx, delay_t &min_slack) { UpdateMap updates; - delay_t min_slack = delay_t(1.0e12 / ctx->target_freq); - - 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; - } - } - min_slack = default_slack; - // Go through all clocked drivers and set up paths + + // 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) { - log_break(); + if (port.second.net) follow_net(ctx, port.second.net, 0, slack, updates, min_slack); - } } } } } + return updates; +} + +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 &usr : net.second->users) { + usr.budget = default_slack; + } + } + + delay_t min_slack = default_slack; + auto updates = compute_min_slack(ctx, min_slack); + + // If user has not specified a frequency, adjust the target frequency + // to be equivalent to the critical path if (!ctx->user_freq) { ctx->target_freq = 1e12 / (default_slack - min_slack); if (ctx->verbose) @@ -145,27 +156,12 @@ void assign_budget(Context *ctx) void update_budget(Context *ctx) { - UpdateMap updates; delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); - delay_t min_slack = delay_t(1.0e12 / ctx->target_freq); - - // Go through all clocked drivers and distribute the available path slack evenly into every budget - 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 = 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, updates, min_slack); - } - } - } - } + delay_t min_slack = default_slack; + auto updates = compute_min_slack(ctx, min_slack); + // If user has not specified a frequency, adjust the target frequency + // to be +5% higher than the current critical path if (!ctx->user_freq) { ctx->target_freq = 1.05 * (1e12 / (default_slack - min_slack)); if (ctx->verbose) @@ -199,4 +195,12 @@ void update_budget(Context *ctx) } } +float compute_fmax(Context *ctx) +{ + delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); + delay_t min_slack = default_slack; + compute_min_slack(ctx, min_slack); + return 1e12 / (default_slack - min_slack); +} + NEXTPNR_NAMESPACE_END diff --git a/common/timing.h b/common/timing.h index b5574392..22aa40c7 100644 --- a/common/timing.h +++ b/common/timing.h @@ -27,8 +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); +float compute_fmax(Context *ctx); + NEXTPNR_NAMESPACE_END #endif -- cgit v1.2.3 From 9d489e819863e431de3db58221f0d6fbe3387412 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Wed, 25 Jul 2018 18:34:14 -0700 Subject: Retry clangformat --- common/placer1.cc | 3 +-- common/timing.cc | 37 +++++++++++++++++++++++-------------- 2 files changed, 24 insertions(+), 16 deletions(-) (limited to 'common') diff --git a/common/placer1.cc b/common/placer1.cc index d38cdd4b..12bf470f 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -239,8 +239,7 @@ class SAPlacer diameter *= post_legalise_dia_scale; ctx->shuffle(autoplaced); assign_budget(ctx); - } - else { + } else { update_budget(ctx); } diff --git a/common/timing.cc b/common/timing.cc index 784952f8..1da7efba 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -26,12 +26,14 @@ NEXTPNR_NAMESPACE_BEGIN -typedef std::unordered_map UpdateMap; +typedef std::unordered_map UpdateMap; -static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap &updates, delay_t &min_slack); +static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap &updates, + delay_t &min_slack); // Follow a path, returning budget to annotate -static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, delay_t slack, UpdateMap &updates, delay_t &min_slack) +static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, delay_t slack, UpdateMap &updates, + delay_t &min_slack) { delay_t value; if (ctx->getPortClock(user.cell, user.port) != IdString()) { @@ -66,12 +68,15 @@ static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, de return value; } -static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap &updates, delay_t &min_slack) +static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap &updates, + delay_t &min_slack) { delay_t net_budget = slack / (path_length + 1); for (unsigned i = 0; i < net->users.size(); ++i) { auto &usr = net->users[i]; - net_budget = std::min(net_budget, follow_user_port(ctx, usr, path_length + 1, slack - ctx->getNetinfoRouteDelay(net, i), updates, min_slack)); + net_budget = + std::min(net_budget, follow_user_port(ctx, usr, path_length + 1, + slack - ctx->getNetinfoRouteDelay(net, i), updates, min_slack)); } return net_budget; } @@ -81,7 +86,7 @@ static UpdateMap compute_min_slack(Context *ctx, delay_t &min_slack) UpdateMap updates; delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); - // Go through all clocked drivers and distribute the available 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) { @@ -119,21 +124,23 @@ void assign_budget(Context *ctx) delay_t min_slack = default_slack; auto updates = compute_min_slack(ctx, min_slack); - // If user has not specified a frequency, adjust the target frequency + // If user has not specified a frequency, adjust the target frequency // to be equivalent to the critical path 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 = %f\n", min_slack, ctx->target_freq/1e6); + log_info("minimum slack for this assign = %d, target Fmax for next update = %f\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 &user = net.second->users[i]; auto pi = &user.cell->ports.at(user.port); auto it = updates.find(pi); - if (it == updates.end()) continue; + if (it == updates.end()) + continue; auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i) + it->second; user.budget = ctx->getBudgetOverride(net.second->driver, budget); @@ -160,21 +167,23 @@ void update_budget(Context *ctx) delay_t min_slack = default_slack; auto updates = compute_min_slack(ctx, min_slack); - // If user has not specified a frequency, adjust the target frequency + // If user has not specified a frequency, adjust the target frequency // to be +5% higher than the current critical path if (!ctx->user_freq) { ctx->target_freq = 1.05 * (1e12 / (default_slack - min_slack)); if (ctx->verbose) - log_info("minimum slack for this update = %d, target Fmax for next update = %f\n", min_slack, ctx->target_freq/1e6); + log_info("minimum slack for this update = %d, target Fmax for next update = %f\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 &user = net.second->users[i]; auto pi = &user.cell->ports.at(user.port); auto it = updates.find(pi); - if (it == updates.end()) continue; + if (it == updates.end()) + continue; auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i) + it->second; user.budget = ctx->getBudgetOverride(net.second->driver, budget); -- 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/placer1.cc | 2 +- common/router1.cc | 2 +- common/timing.cc | 104 ++++++++++++++++++++++++++++++++++++++---------------- common/timing.h | 2 +- 4 files changed, 76 insertions(+), 34 deletions(-) (limited to 'common') diff --git a/common/placer1.cc b/common/placer1.cc index 12bf470f..264f1eba 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -275,7 +275,7 @@ class SAPlacer } } } - log_info("estimated Fmax = %.2f MHz\n", compute_fmax(ctx) / 1e6); + compute_fmax(ctx, true /* print_fmax */); ctx->unlock(); return true; } 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 diff --git a/common/timing.cc b/common/timing.cc index 1da7efba..1887b03d 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -27,20 +27,24 @@ NEXTPNR_NAMESPACE_BEGIN typedef std::unordered_map UpdateMap; +typedef std::list PortRefList; -static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap &updates, - delay_t &min_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); // Follow a path, returning budget to annotate -static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, delay_t slack, UpdateMap &updates, - delay_t &min_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; - min_slack = std::min(min_slack, value); + 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; @@ -53,7 +57,7 @@ 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, updates, min_slack); + 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); } } @@ -61,30 +65,35 @@ static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, de } } - auto ret = updates.emplace(&user.cell->ports.at(user.port), value); - if (!ret.second && value < ret.first->second) { - ret.first->second = 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, UpdateMap &updates, - delay_t &min_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 (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)); + slack - ctx->getNetinfoRouteDelay(net, i), updates, min_slack, current_path, crit_path)); + if (crit_path) current_path->pop_back(); } return net_budget; } -static UpdateMap compute_min_slack(Context *ctx, delay_t &min_slack) +static delay_t compute_min_slack(Context *ctx, UpdateMap *updates, PortRefList *crit_path) { - UpdateMap updates; delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); + 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 --- @@ -99,18 +108,17 @@ static UpdateMap compute_min_slack(Context *ctx, delay_t &min_slack) 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, updates, min_slack); + follow_net(ctx, port.second.net, 0, slack, updates, min_slack, ¤t_path, crit_path); } } } } - return updates; + 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 @@ -121,15 +129,15 @@ void assign_budget(Context *ctx) } } - delay_t min_slack = default_slack; - auto updates = compute_min_slack(ctx, min_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 critical path + // 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 = %f\n", min_slack, + log_info("minimum slack for this assign = %d, target Fmax for next update = %.2f MHz\n", min_slack, ctx->target_freq / 1e6); } @@ -163,16 +171,18 @@ void assign_budget(Context *ctx) void update_budget(Context *ctx) { + UpdateMap updates; delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); - delay_t min_slack = default_slack; - auto updates = compute_min_slack(ctx, min_slack); + delay_t min_slack = compute_min_slack(ctx, &updates, nullptr); - // If user has not specified a frequency, adjust the target frequency - // to be +5% higher than the current critical path + // If user has not specified a frequency, adjust the frequency dynamically: if (!ctx->user_freq) { - ctx->target_freq = 1.05 * (1e12 / (default_slack - min_slack)); + 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 = %f\n", min_slack, + log_info("minimum slack for this update = %d, target Fmax for next update = %.2f MHz\n", min_slack, ctx->target_freq / 1e6); } @@ -204,12 +214,44 @@ void update_budget(Context *ctx) } } -float compute_fmax(Context *ctx) +void compute_fmax(Context *ctx, bool print_fmax, bool print_path) { delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); - delay_t min_slack = default_slack; - compute_min_slack(ctx, min_slack); - return 1e12 / (default_slack - min_slack); + 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:\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 (s)\n", comb_delay, total, driver_cell->name.c_str(ctx), driver.port.c_str(ctx)); + delay_t net_delay = ctx->getNetinfoRouteDelay(net, i); + net_delay = ctx->getBudgetOverride(driver, net_delay); + total += net_delay; + log_info("%4d %4d Net %s\n", net_delay, total, net->name.c_str(ctx)); + 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 22aa40c7..ed48c137 100644 --- a/common/timing.h +++ b/common/timing.h @@ -30,7 +30,7 @@ void assign_budget(Context *ctx); // Evenly redistribute the total path slack amongst all sinks on each path void update_budget(Context *ctx); -float compute_fmax(Context *ctx); +void compute_fmax(Context *ctx, bool print_fmax=false, bool print_path=false); NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From 8f930d683bd58f21554832f19529b567fa0e8fa2 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Wed, 25 Jul 2018 22:31:47 -0700 Subject: Print budget of net and its driver/sink locations too --- common/timing.cc | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 1887b03d..7977bcd2 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -222,7 +222,7 @@ void compute_fmax(Context *ctx, bool print_fmax, bool print_path) if (print_path) { delay_t total = 0; log_break(); - log_info("Critical path:\n"); + 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); @@ -240,11 +240,12 @@ void compute_fmax(Context *ctx, bool print_fmax, bool print_path) delay_t comb_delay; ctx->getCellDelay(sink_cell, last_port, driver.port, comb_delay); total += comb_delay; - log_info("%4d %4d Source %s.%s (s)\n", comb_delay, total, driver_cell->name.c_str(ctx), driver.port.c_str(ctx)); + 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); - net_delay = ctx->getBudgetOverride(driver, net_delay); total += net_delay; - log_info("%4d %4d Net %s\n", net_delay, total, net->name.c_str(ctx)); + 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; } -- cgit v1.2.3 From e5d3821955cebfb2f3b2a10f97f2eea0dc9ecec3 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Wed, 25 Jul 2018 22:32:07 -0700 Subject: clangformat --- common/timing.cc | 45 ++++++++++++++++++++++++++------------------- common/timing.h | 2 +- 2 files changed, 27 insertions(+), 20 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 7977bcd2..f919cf1b 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -30,11 +30,11 @@ typedef std::unordered_map UpdateMap; typedef std::list 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); + 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, UpdateMap *updates, - delay_t &min_slack, PortRefList *current_path, PortRefList* crit_path) + delay_t &min_slack, PortRefList *current_path, PortRefList *crit_path) { delay_t value; if (ctx->getPortClock(user.cell, user.port) != IdString()) { @@ -43,7 +43,8 @@ static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, de value = slack / path_length; if (slack < min_slack) { min_slack = slack; - if (crit_path) *crit_path = *current_path; + if (crit_path) + *crit_path = *current_path; } } else { // Default to the path ending here, if no further paths found @@ -57,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, updates, min_slack, current_path, crit_path); + 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); } } @@ -79,11 +81,13 @@ static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t s delay_t net_budget = slack / (path_length + 1); 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(); + 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; } @@ -224,35 +228,38 @@ void compute_fmax(Context *ctx, bool print_fmax, bool print_path) 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 &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 &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; + 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)); + 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("%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)); + 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 ed48c137..a1e12ab3 100644 --- a/common/timing.h +++ b/common/timing.h @@ -30,7 +30,7 @@ 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); +void compute_fmax(Context *ctx, bool print_fmax = false, bool print_path = false); NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From f45e688354c13f38bda3ba4064587880a25980fe Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Wed, 25 Jul 2018 23:10:26 -0700 Subject: Do not use budget override anymore, and subtract not add! --- common/timing.cc | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index f919cf1b..cefe36f0 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -153,8 +153,7 @@ void assign_budget(Context *ctx) auto it = updates.find(pi); if (it == updates.end()) continue; - auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i) + it->second; - user.budget = ctx->getBudgetOverride(net.second->driver, budget); + user.budget = ctx->getNetinfoRouteDelay(net.second.get(), i) - it->second; // Post-update check if (ctx->user_freq && user.budget < 0) @@ -198,8 +197,7 @@ void update_budget(Context *ctx) auto it = updates.find(pi); if (it == updates.end()) continue; - auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i) + it->second; - user.budget = ctx->getBudgetOverride(net.second->driver, budget); + user.budget = ctx->getNetinfoRouteDelay(net.second.get(), i) + it->second; // Post-update check if (ctx->verbose) { -- cgit v1.2.3 From 5622dc04448cadf6ea162b7d54e3d26301b2b05b Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Thu, 26 Jul 2018 21:35:02 -0700 Subject: Fix budget realloc --- common/timing.cc | 11 ++++------- 1 file changed, 4 insertions(+), 7 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index cefe36f0..5534b1c8 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -180,10 +180,7 @@ void update_budget(Context *ctx) // 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); + ctx->target_freq = 1e12 / (default_slack - 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); @@ -197,7 +194,7 @@ void update_budget(Context *ctx) auto it = updates.find(pi); if (it == updates.end()) continue; - user.budget = ctx->getNetinfoRouteDelay(net.second.get(), i) + it->second; + user.budget = ctx->getNetinfoRouteDelay(net.second.get(), i) - it->second; // Post-update check if (ctx->verbose) { @@ -236,8 +233,8 @@ void compute_fmax(Context *ctx, bool print_fmax, bool print_path) auto net = port.net; unsigned i = 0; for (auto &usr : net->users) - if (&usr == sink) - break; + if (&usr == sink) break; + else ++i; auto &driver = net->driver; auto driver_cell = driver.cell; delay_t comb_delay; -- cgit v1.2.3 From 21d46fb633383909609a9f8adbb543ae6e7ed70c Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Thu, 26 Jul 2018 21:35:37 -0700 Subject: Move target_freq update after budget update --- common/timing.cc | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 5534b1c8..7f28ef75 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -175,17 +175,8 @@ void assign_budget(Context *ctx) 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) { - ctx->target_freq = 1e12 / (default_slack - 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) { @@ -211,6 +202,15 @@ void update_budget(Context *ctx) } } } + + // If user has not specified a frequency, adjust the frequency dynamically: + if (!ctx->user_freq) { + delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); + ctx->target_freq = 1e12 / (default_slack - 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); + } } void compute_fmax(Context *ctx, bool print_fmax, bool print_path) -- cgit v1.2.3 From 69ef533db35e67198ba7051cfd8920e73d960912 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Thu, 26 Jul 2018 22:32:24 -0700 Subject: Re-add getBudgetOverride() but also account for path length of overridden --- common/timing.cc | 24 ++++++++++++++++++------ 1 file changed, 18 insertions(+), 6 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 7f28ef75..2873f017 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -83,8 +83,15 @@ static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t s auto &usr = net->users[i]; if (crit_path) current_path->push_back(&usr); + // If budget override is less than existing budget, then do not increment path length + int pl = path_length + 1; + auto budget = ctx->getBudgetOverride(net, i, net_budget); + if (budget < net_budget) { + net_budget = budget; + pl = std::max(1, path_length); + } net_budget = std::min(net_budget, - follow_user_port(ctx, usr, path_length + 1, slack - ctx->getNetinfoRouteDelay(net, i), + follow_user_port(ctx, usr, pl, slack - ctx->getNetinfoRouteDelay(net, i), updates, min_slack, current_path, crit_path)); if (crit_path) current_path->pop_back(); @@ -136,10 +143,13 @@ void assign_budget(Context *ctx) 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 user has not specified a frequency, adjust the target frequency dynamically + // TODO(eddieh): Tune these factors if (!ctx->user_freq) { - ctx->target_freq = 1e12 / (default_slack - min_slack); + if (min_slack < 0) + ctx->target_freq = 1e12 / (default_slack - 0.95 * min_slack); + else + ctx->target_freq = 1e12 / (default_slack - 1.2 * 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); @@ -153,7 +163,8 @@ void assign_budget(Context *ctx) auto it = updates.find(pi); if (it == updates.end()) continue; - user.budget = ctx->getNetinfoRouteDelay(net.second.get(), i) - it->second; + auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i) - it->second; + user.budget = ctx->getBudgetOverride(net.second.get(), i, budget); // Post-update check if (ctx->user_freq && user.budget < 0) @@ -185,7 +196,8 @@ void update_budget(Context *ctx) auto it = updates.find(pi); if (it == updates.end()) continue; - user.budget = ctx->getNetinfoRouteDelay(net.second.get(), i) - it->second; + auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i) - it->second; + user.budget = ctx->getBudgetOverride(net.second.get(), i, budget); // Post-update check if (ctx->verbose) { -- cgit v1.2.3 From 4c40541484f0f0b571e1c7e4604c39c74dd5c93d Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Thu, 26 Jul 2018 22:49:08 -0700 Subject: Even if there is no updates, set budget to current delay --- common/timing.cc | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 2873f017..afaddbdf 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -193,10 +193,10 @@ void update_budget(Context *ctx) 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 budget = ctx->getNetinfoRouteDelay(net.second.get(), i); auto it = updates.find(pi); - if (it == updates.end()) - continue; - auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i) - it->second; + if (it != updates.end()) + budget -= it->second; user.budget = ctx->getBudgetOverride(net.second.get(), i, budget); // Post-update check -- cgit v1.2.3 From 0bbe309a260dc690a27e882c52f12437a119b4b1 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Fri, 27 Jul 2018 19:52:58 -0700 Subject: Fix sign of slack redistribution again --- common/timing.cc | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index afaddbdf..f720b772 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -160,10 +160,10 @@ void assign_budget(Context *ctx) 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 budget = ctx->getNetinfoRouteDelay(net.second.get(), i); auto it = updates.find(pi); - if (it == updates.end()) - continue; - auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i) - it->second; + if (it != updates.end()) + budget += it->second; user.budget = ctx->getBudgetOverride(net.second.get(), i, budget); // Post-update check @@ -196,7 +196,7 @@ void update_budget(Context *ctx) auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i); auto it = updates.find(pi); if (it != updates.end()) - budget -= it->second; + budget += it->second; user.budget = ctx->getBudgetOverride(net.second.get(), i, budget); // Post-update check -- cgit v1.2.3 From 0be236ce05c90a5853b3285e0556737f663999c3 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Fri, 27 Jul 2018 23:46:05 -0700 Subject: Fix auto Fmax overconstraining during update_budget() --- common/timing.cc | 34 +++++++++++++++++++--------------- 1 file changed, 19 insertions(+), 15 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index f720b772..e0ddd2aa 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -143,18 +143,6 @@ void assign_budget(Context *ctx) UpdateMap updates; delay_t min_slack = compute_min_slack(ctx, &updates, nullptr); - // If user has not specified a frequency, adjust the target frequency dynamically - // TODO(eddieh): Tune these factors - if (!ctx->user_freq) { - if (min_slack < 0) - ctx->target_freq = 1e12 / (default_slack - 0.95 * min_slack); - else - ctx->target_freq = 1e12 / (default_slack - 1.2 * 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) { @@ -180,6 +168,18 @@ void assign_budget(Context *ctx) } } + // If user has not specified a frequency, adjust the target frequency dynamically + // TODO(eddieh): Tune these factors + if (!ctx->user_freq) { + if (min_slack < 0) + ctx->target_freq = 1e12 / (default_slack - 0.95 * min_slack); + else + ctx->target_freq = 1e12 / (default_slack - 1.2 * 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); + } + log_info("Checksum: 0x%08x\n", ctx->checksum()); } @@ -215,12 +215,16 @@ void update_budget(Context *ctx) } } - // If user has not specified a frequency, adjust the frequency dynamically: + // If user has not specified a frequency, adjust the target frequency dynamically + // TODO(eddieh): Tune these factors if (!ctx->user_freq) { delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); - ctx->target_freq = 1e12 / (default_slack - min_slack); + if (min_slack < 0) + ctx->target_freq = 1e12 / (default_slack - 0.95 * min_slack); + else + ctx->target_freq = 1e12 / (default_slack - 1.2 * min_slack); if (ctx->verbose) - log_info("minimum slack for this update = %d, target Fmax for next update = %.2f MHz\n", min_slack, + log_info("minimum slack for this assign = %d, target Fmax for next update = %.2f MHz\n", min_slack, ctx->target_freq / 1e6); } } -- 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/placer1.cc | 2 +- common/router1.cc | 2 +- common/timing.cc | 62 +++++++++++++++++-------------------------------------- common/timing.h | 4 +++- 4 files changed, 24 insertions(+), 46 deletions(-) (limited to 'common') diff --git a/common/placer1.cc b/common/placer1.cc index 264f1eba..99ae6765 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -275,7 +275,7 @@ class SAPlacer } } } - compute_fmax(ctx, true /* print_fmax */); + timing_analysis(ctx, true /* print_fmax */); ctx->unlock(); return true; } 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) { diff --git a/common/timing.cc b/common/timing.cc index e0ddd2aa..20cfd1b5 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -26,14 +26,13 @@ NEXTPNR_NAMESPACE_BEGIN -typedef std::unordered_map UpdateMap; typedef std::list PortRefList; -static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap *updates, +static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, bool update, 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, UpdateMap *updates, +static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, delay_t slack, bool update, delay_t &min_slack, PortRefList *current_path, PortRefList *crit_path) { delay_t value; @@ -58,7 +57,7 @@ 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, updates, min_slack, + delay_t path_budget = follow_net(ctx, net, path_length, slack - comb_delay, update, min_slack, current_path, crit_path); value = std::min(value, path_budget); } @@ -66,16 +65,10 @@ static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, de } } } - - 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, UpdateMap *updates, +static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, bool update, delay_t &min_slack, PortRefList *current_path, PortRefList *crit_path) { delay_t net_budget = slack / (path_length + 1); @@ -92,14 +85,16 @@ static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t s } net_budget = std::min(net_budget, follow_user_port(ctx, usr, pl, slack - ctx->getNetinfoRouteDelay(net, i), - updates, min_slack, current_path, crit_path)); + update, min_slack, current_path, crit_path)); + if (update) + usr.budget = std::min(usr.budget, net_budget); if (crit_path) current_path->pop_back(); } return net_budget; } -static delay_t compute_min_slack(Context *ctx, UpdateMap *updates, PortRefList *crit_path) +static delay_t walk_paths(Context *ctx, bool update, PortRefList *crit_path) { delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); delay_t min_slack = default_slack; @@ -119,7 +114,7 @@ static delay_t compute_min_slack(Context *ctx, UpdateMap *updates, PortRefList * 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, updates, min_slack, ¤t_path, crit_path); + follow_net(ctx, port.second.net, 0, slack, update, min_slack, ¤t_path, crit_path); } } } @@ -140,20 +135,10 @@ void assign_budget(Context *ctx) } } - UpdateMap updates; - delay_t min_slack = compute_min_slack(ctx, &updates, nullptr); + delay_t min_slack = walk_paths(ctx, true, nullptr); - // 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 budget = ctx->getNetinfoRouteDelay(net.second.get(), i); - auto it = updates.find(pi); - if (it != updates.end()) - budget += it->second; - user.budget = ctx->getBudgetOverride(net.second.get(), i, budget); - + for (auto &user : net.second->users) { // Post-update check if (ctx->user_freq && user.budget < 0) log_warning("port %s.%s, connected to net '%s', has negative " @@ -185,22 +170,12 @@ void assign_budget(Context *ctx) void update_budget(Context *ctx) { - UpdateMap updates; - delay_t min_slack = compute_min_slack(ctx, &updates, nullptr); + delay_t min_slack = walk_paths(ctx, true, nullptr); - // 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 budget = ctx->getNetinfoRouteDelay(net.second.get(), i); - auto it = updates.find(pi); - if (it != updates.end()) - budget += it->second; - user.budget = ctx->getBudgetOverride(net.second.get(), i, budget); - - // Post-update check - if (ctx->verbose) { + if (ctx->verbose) { + for (auto &net : ctx->nets) { + for (auto &user : net.second->users) { + // 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", @@ -229,11 +204,11 @@ void update_budget(Context *ctx) } } -void compute_fmax(Context *ctx, bool print_fmax, bool print_path) +delay_t timing_analysis(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); + delay_t min_slack = walk_paths(ctx, false, &crit_path); if (print_path) { delay_t total = 0; log_break(); @@ -271,6 +246,7 @@ void compute_fmax(Context *ctx, bool print_fmax, bool print_path) } if (print_fmax) log_info("estimated Fmax = %.2f MHz\n", 1e6 / (default_slack - min_slack)); + return min_slack; } NEXTPNR_NAMESPACE_END diff --git a/common/timing.h b/common/timing.h index a1e12ab3..de4f7bbe 100644 --- a/common/timing.h +++ b/common/timing.h @@ -30,7 +30,9 @@ 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); +// Perform timing analysis and return the minimum path slack, +// optionally, print out the fmax and critical path +delay_t timing_analysis(Context *ctx, bool print_fmax = false, bool print_path = false); NEXTPNR_NAMESPACE_END -- 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/placer1.cc | 2 +- common/router1.cc | 2 +- common/timing.cc | 57 ++++++++++++++----------------------------------------- common/timing.h | 5 +---- 4 files changed, 17 insertions(+), 49 deletions(-) (limited to 'common') diff --git a/common/placer1.cc b/common/placer1.cc index d0771e5c..c677a22a 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -237,7 +237,7 @@ class SAPlacer ctx->shuffle(autoplaced); assign_budget(ctx); } else { - update_budget(ctx); + assign_budget(ctx, true /* quiet */); } // Recalculate total metric entirely to avoid rounding errors 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); diff --git a/common/timing.cc b/common/timing.cc index 20cfd1b5..5a9d8c02 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -83,11 +83,12 @@ static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t s net_budget = budget; pl = std::max(1, path_length); } + auto delay = ctx->getNetinfoRouteDelay(net, i); net_budget = std::min(net_budget, - follow_user_port(ctx, usr, pl, slack - ctx->getNetinfoRouteDelay(net, i), + follow_user_port(ctx, usr, pl, slack - delay, update, min_slack, current_path, crit_path)); if (update) - usr.budget = std::min(usr.budget, net_budget); + usr.budget = std::min(usr.budget, delay + net_budget); if (crit_path) current_path->pop_back(); } @@ -123,10 +124,13 @@ static delay_t walk_paths(Context *ctx, bool update, PortRefList *crit_path) return min_slack; } -void assign_budget(Context *ctx) +void assign_budget(Context *ctx, bool quiet) { - log_break(); - log_info("Annotating ports with timing budgets\n"); + if (!quiet) { + 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) { @@ -137,42 +141,7 @@ void assign_budget(Context *ctx) delay_t min_slack = walk_paths(ctx, true, nullptr); - for (auto &net : ctx->nets) { - for (auto &user : net.second->users) { - // 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), - ctx->getDelayNS(user.budget)); - if (ctx->verbose) - 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)); - } - } - - // If user has not specified a frequency, adjust the target frequency dynamically - // TODO(eddieh): Tune these factors - if (!ctx->user_freq) { - if (min_slack < 0) - ctx->target_freq = 1e12 / (default_slack - 0.95 * min_slack); - else - ctx->target_freq = 1e12 / (default_slack - 1.2 * 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); - } - - log_info("Checksum: 0x%08x\n", ctx->checksum()); -} - -void update_budget(Context *ctx) -{ - delay_t min_slack = walk_paths(ctx, true, nullptr); - - if (ctx->verbose) { + if (!quiet || ctx->verbose) { for (auto &net : ctx->nets) { for (auto &user : net.second->users) { // Post-update check @@ -181,7 +150,7 @@ void update_budget(Context *ctx) "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 + else if (ctx->verbose) 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), @@ -193,7 +162,6 @@ void update_budget(Context *ctx) // If user has not specified a frequency, adjust the target frequency dynamically // TODO(eddieh): Tune these factors if (!ctx->user_freq) { - delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); if (min_slack < 0) ctx->target_freq = 1e12 / (default_slack - 0.95 * min_slack); else @@ -202,6 +170,9 @@ void update_budget(Context *ctx) log_info("minimum slack for this assign = %d, target Fmax for next update = %.2f MHz\n", min_slack, ctx->target_freq / 1e6); } + + if (!quiet) + log_info("Checksum: 0x%08x\n", ctx->checksum()); } delay_t timing_analysis(Context *ctx, bool print_fmax, bool print_path) diff --git a/common/timing.h b/common/timing.h index de4f7bbe..d0159d5c 100644 --- a/common/timing.h +++ b/common/timing.h @@ -24,11 +24,8 @@ 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 assign_budget(Context *ctx, bool quiet = false); // Perform timing analysis and return the minimum path slack, // optionally, print out the fmax and critical path -- cgit v1.2.3 From beabb429b0be91c597cb2a9f7726a159a6f40b32 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 28 Jul 2018 14:11:43 -0700 Subject: clangformat --- common/timing.cc | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index 5a9d8c02..c6e2b037 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -28,8 +28,8 @@ NEXTPNR_NAMESPACE_BEGIN typedef std::list PortRefList; -static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, bool update, - delay_t &min_slack, PortRefList *current_path, PortRefList *crit_path); +static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, bool update, 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, bool update, @@ -68,8 +68,8 @@ static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, de return value; } -static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, bool update, - delay_t &min_slack, PortRefList *current_path, PortRefList *crit_path) +static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, bool update, delay_t &min_slack, + PortRefList *current_path, PortRefList *crit_path) { delay_t net_budget = slack / (path_length + 1); for (unsigned i = 0; i < net->users.size(); ++i) { @@ -84,9 +84,8 @@ static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t s pl = std::max(1, path_length); } auto delay = ctx->getNetinfoRouteDelay(net, i); - net_budget = std::min(net_budget, - follow_user_port(ctx, usr, pl, slack - delay, - update, min_slack, current_path, crit_path)); + net_budget = std::min( + net_budget, follow_user_port(ctx, usr, pl, slack - delay, update, min_slack, current_path, crit_path)); if (update) usr.budget = std::min(usr.budget, delay + net_budget); if (crit_path) @@ -195,8 +194,10 @@ delay_t timing_analysis(Context *ctx, bool print_fmax, bool print_path) auto net = port.net; unsigned i = 0; for (auto &usr : net->users) - if (&usr == sink) break; - else ++i; + if (&usr == sink) + break; + else + ++i; auto &driver = net->driver; auto driver_cell = driver.cell; delay_t comb_delay; -- cgit v1.2.3 From 52cc146a67346f8a797d1ea133c7757a7330992d Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sat, 28 Jul 2018 22:57:37 -0700 Subject: Keep things simple by not overconstraining Fmax --- common/timing.cc | 9 +++------ 1 file changed, 3 insertions(+), 6 deletions(-) (limited to 'common') diff --git a/common/timing.cc b/common/timing.cc index c6e2b037..c9e1cabd 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -158,13 +158,10 @@ void assign_budget(Context *ctx, bool quiet) } } - // If user has not specified a frequency, adjust the target frequency dynamically - // TODO(eddieh): Tune these factors + // If user has not specified a frequency, dynamically adjust the target + // frequency to be the current maximum if (!ctx->user_freq) { - if (min_slack < 0) - ctx->target_freq = 1e12 / (default_slack - 0.95 * min_slack); - else - ctx->target_freq = 1e12 / (default_slack - 1.2 * min_slack); + ctx->target_freq = 1e12 / (default_slack - 1.2 * 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); -- cgit v1.2.3