From e314ea761abd8f55b3341f733c01d13ce2d4fae5 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Sun, 5 Aug 2018 22:38:54 -0700 Subject: WIP for new assign_budget() using topographical ordering --- common/timing.cc | 171 +++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 165 insertions(+), 6 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index d37a0f59..23fbd9f9 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -23,6 +23,7 @@ #include #include "log.h" #include "util.h" +#include NEXTPNR_NAMESPACE_BEGIN @@ -38,6 +39,14 @@ struct Timing PortRefVector *crit_path; DelayFrequency *slack_histogram; + struct TimingData { + TimingData() : max_arrival(), max_path_length(), min_remaining_budget() {} + TimingData(delay_t max_arrival) : max_arrival(max_arrival), max_path_length(), min_remaining_budget() {} + delay_t max_arrival; + unsigned max_path_length = 0; + delay_t min_remaining_budget; + }; + Timing(Context *ctx, bool update, PortRefVector *crit_path = nullptr, DelayFrequency *slack_histogram = nullptr) : ctx(ctx), update(update), min_slack(1.0e12 / ctx->target_freq), crit_path(crit_path), slack_histogram(slack_histogram) @@ -53,8 +62,8 @@ struct Timing // If budget override is less than existing budget, then do not increment // path length int pl = path_length + 1; - auto budget = ctx->getBudgetOverride(net, usr, net_budget); - if (budget < net_budget) { + auto budget = net_budget; + if (ctx->getBudgetOverride(net, usr, budget) && budget < net_budget) { net_budget = budget; pl = std::max(1, path_length); } @@ -109,16 +118,17 @@ struct Timing delay_t walk_paths() { - delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); + const auto clk_period = delay_t(1.0e12 / ctx->target_freq); // Go through all clocked drivers and distribute the available path // slack evenly into the budget of every sink on the path +#if 0 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 slack = clk_period; // TODO: clock constraints DelayInfo clkToQ; if (ctx->getCellDelay(cell.second.get(), clock_domain, port.first, clkToQ)) slack -= clkToQ.maxDelay(); @@ -128,16 +138,165 @@ struct Timing } } } + +#else + std::vector topographical_order; + std::unordered_map port_fanin; + std::unordered_map net_data; + + std::vector input_ports; + std::vector output_ports; + for (auto &cell : ctx->cells) { + input_ports.clear(); + output_ports.clear(); + bool is_io = cell.second->type == ctx->id_sb_io; + for (auto& port : cell.second->ports) { + if (!port.second.net) continue; + if (port.second.type == PORT_OUT) + output_ports.push_back(&port.second); + else + input_ports.push_back(port.first); + } + + for (auto o : output_ports) { + IdString clock_domain = ctx->getPortClock(cell.second.get(), o->name); + if (clock_domain != IdString()) { + DelayInfo clkToQ; + ctx->getCellDelay(cell.second.get(), clock_domain, o->name, clkToQ); + topographical_order.emplace_back(o->net); + net_data.emplace(o->net, TimingData{ clkToQ.maxDelay() }); + } + else { + if (is_io) { + topographical_order.emplace_back(o->net); + net_data.emplace(o->net, TimingData{}); + } + for (auto i : input_ports) { + DelayInfo comb_delay; + bool is_path = ctx->getCellDelay(cell.second.get(), i, o->name, comb_delay); + if (is_path) + port_fanin[o]++; + } + } + } + } + + std::deque queue(topographical_order.begin(), topographical_order.end()); + + while (!queue.empty()) { + const auto net = queue.front(); + queue.pop_front(); + + for (auto &usr : net->users) { + if (ctx->getPortClock(usr.cell, usr.port) != IdString()) { + } else { + // Follow outputs of the user + for (auto& port : usr.cell->ports) { + if (port.second.type == PORT_OUT && port.second.net) { + DelayInfo comb_delay; + bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay); + if (is_path) { + auto it = port_fanin.find(&port.second); + NPNR_ASSERT(it != port_fanin.end()); + if (--it->second == 0) { + topographical_order.emplace_back(port.second.net); + queue.emplace_back(port.second.net); + port_fanin.erase(it); + } + } + } + } + } + } + } + + // Find the maximum arrival time and max path length for each net + for (auto net : topographical_order) { + auto &nd = net_data.at(net); + const auto net_arrival = nd.max_arrival; + const auto net_length_plus_one = nd.max_path_length + 1; + nd.min_remaining_budget = clk_period; + for (auto &usr : net->users) { + if (ctx->getPortClock(usr.cell, usr.port) != IdString()) { + } else { + auto net_delay = ctx->getNetinfoRouteDelay(net, usr); + delay_t budget; + auto budget_override = ctx->getBudgetOverride(net, usr, budget); + auto usr_arrival = net_arrival + net_delay; + // Follow outputs of the user + for (auto port : usr.cell->ports) { + if (port.second.type == PORT_OUT && port.second.net) { + DelayInfo comb_delay; + // Look up delay through this path + bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay); + if (is_path) { + auto& data = net_data[port.second.net]; + auto& arrival = data.max_arrival; + arrival = std::max(arrival, usr_arrival + comb_delay.maxDelay()); + if (!budget_override) { + auto& path_length = data.max_path_length; + path_length = std::max(path_length, net_length_plus_one); + } + } + } + } + } + } + } + + for (auto net : boost::adaptors::reverse(topographical_order)) { + auto &nd = net_data.at(net); + const delay_t net_length_plus_one = nd.max_path_length + 1; + auto& net_min_remaining_budget = nd.min_remaining_budget; + for (auto &usr : net->users) { + const auto net_delay = ctx->getNetinfoRouteDelay(net, usr); + auto budget_override = ctx->getBudgetOverride(net, usr, usr.budget); + if (ctx->getPortClock(usr.cell, usr.port) != IdString()) { + const auto net_arrival = nd.max_arrival; + auto path_budget = clk_period - (net_arrival + net_delay); + auto budget_share = path_budget / net_length_plus_one; + if (budget_override) + budget_share = 0; + else + usr.budget = std::min(usr.budget, net_delay + budget_share); + net_min_remaining_budget = std::min(net_min_remaining_budget, path_budget - budget_share); + + min_slack = std::min(min_slack, path_budget); + if (slack_histogram) { + int slack_ps = ctx->getDelayNS(path_budget) * 1000; + (*slack_histogram)[slack_ps]++; + } + } else { + // Follow outputs of the user + for (auto port : usr.cell->ports) { + if (port.second.type == PORT_OUT && port.second.net) { + DelayInfo comb_delay; + // Look up delay through this path + bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay); + if (is_path) { + auto path_budget = net_data.at(port.second.net).min_remaining_budget; + auto budget_share = path_budget / net_length_plus_one; + if (budget_override) + budget_share = 0; + else + usr.budget = std::min(usr.budget, net_delay + budget_share); + net_min_remaining_budget = std::min(net_min_remaining_budget, path_budget - budget_share); + } + } + } + } + } + } +#endif return min_slack; } void assign_budget() { // 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; + usr.budget = std::numeric_limits::max(); } } -- cgit v1.2.3