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 From 3f5c0373a5eb77cf4cd40f1d280452bfbe6f42f8 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 6 Aug 2018 12:03:58 -0700 Subject: Consider clocked cells with COUT, consider constant nets --- common/timing.cc | 58 +++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 38 insertions(+), 20 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index 72093183..12a4940a 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -155,7 +155,7 @@ struct Timing for (auto &cell : ctx->cells) { input_ports.clear(); output_ports.clear(); - bool is_io = cell.second->type == ctx->id_sb_io; + bool is_io = cell.second->type == ctx->id_sb_io; // HACK HACK HACK for (auto& port : cell.second->ports) { if (!port.second.net) continue; if (port.second.type == PORT_OUT) @@ -187,28 +187,41 @@ struct Timing } } + auto it = ctx->nets.find(ctx->id("$PACKER_VCC_NET")); + if (it != ctx->nets.end()) { + topographical_order.emplace_back(it->second.get()); + net_data.emplace(it->second.get(), TimingData{}); + } + it = ctx->nets.find(ctx->id("$PACKER_GND_NET")); + if (it != ctx->nets.end()) { + topographical_order.emplace_back(it->second.get()); + net_data.emplace(it->second.get(), TimingData{}); + } + std::deque queue(topographical_order.begin(), topographical_order.end()); while (!queue.empty()) { const auto net = queue.front(); queue.pop_front(); + DelayInfo clkToQ; 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); - } + auto clock_domain = ctx->getPortClock(usr.cell, usr.port); + // Follow outputs of the user + for (auto& port : usr.cell->ports) { + if (port.second.type == PORT_OUT && port.second.net) { + // Skip if this is a clocked output + if (clock_domain != IdString() && ctx->getCellDelay(usr.cell, clock_domain, port.first, clkToQ)) + continue; + 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); } } } @@ -216,6 +229,9 @@ struct Timing } } + NPNR_ASSERT(port_fanin.empty()); + port_fanin.clear(); + // Find the maximum arrival time and max path length for each net for (auto net : topographical_order) { auto &nd = net_data.at(net); @@ -225,7 +241,7 @@ struct Timing for (auto &usr : net->users) { if (ctx->getPortClock(usr.cell, usr.port) != IdString()) { } else { - auto net_delay = ctx->getNetinfoRouteDelay(net, usr); + auto net_delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t(); auto budget_override = ctx->getBudgetOverride(net, usr, net_delay); auto usr_arrival = net_arrival + net_delay; // Follow outputs of the user @@ -254,13 +270,14 @@ struct Timing 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 net_delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t(); auto budget_override = ctx->getBudgetOverride(net, usr, net_delay); 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 = budget_override ? 0 : path_budget / net_length_plus_one; - usr.budget = std::min(usr.budget, net_delay + budget_share); + if (update) + 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); @@ -278,7 +295,8 @@ struct Timing if (is_path) { auto path_budget = net_data.at(port.second.net).min_remaining_budget; auto budget_share = budget_override ? 0 : path_budget / net_length_plus_one; - usr.budget = std::min(usr.budget, net_delay + budget_share); + if (update) + usr.budget = std::min(usr.budget, net_delay + budget_share); net_min_remaining_budget = std::min(net_min_remaining_budget, path_budget - budget_share); } } -- cgit v1.2.3 From daedf732911bc6d149e7c6db14f4fd976c79bbac Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 6 Aug 2018 12:12:03 -0700 Subject: Use new Arch::isIOCell() function in Timing --- common/timing.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index 12a4940a..eb3cdc55 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -155,7 +155,7 @@ struct Timing for (auto &cell : ctx->cells) { input_ports.clear(); output_ports.clear(); - bool is_io = cell.second->type == ctx->id_sb_io; // HACK HACK HACK + bool is_io = ctx->isIOCell(cell.second.get()); for (auto& port : cell.second->ports) { if (!port.second.net) continue; if (port.second.type == PORT_OUT) -- cgit v1.2.3 From 519b755acb9155caef0346fd478a6bc02ef9ae8d Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 6 Aug 2018 13:12:24 -0700 Subject: Add comments --- common/timing.cc | 54 +++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 43 insertions(+), 11 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index 11383cee..49e8a5ef 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -127,9 +127,9 @@ struct Timing { const auto clk_period = delay_t(1.0e12 / ctx->target_freq); +#if 0 // 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) { @@ -147,16 +147,20 @@ struct Timing } #else + // First, compute the topographical order of nets to walk through + // the circuit, assuming it is a _acyclic_ graph + // TODO: Handle the case where it is cyclic, e.g. combinatorial loops std::vector topographical_order; - std::unordered_map port_fanin; std::unordered_map net_data; + // In lieu of deleting edges from the graph, simply count + // the number of fanins to each output port + std::unordered_map port_fanin; std::vector input_ports; std::vector output_ports; for (auto &cell : ctx->cells) { input_ports.clear(); output_ports.clear(); - bool is_io = ctx->isIOCell(cell.second.get()); for (auto& port : cell.second->ports) { if (!port.second.net) continue; if (port.second.type == PORT_OUT) @@ -165,8 +169,11 @@ struct Timing input_ports.push_back(port.first); } + bool is_io = ctx->isIOCell(cell.second.get()); for (auto o : output_ports) { IdString clock_domain = ctx->getPortClock(cell.second.get(), o->name); + // If output port is influenced by a clock (e.g. FF output) + // then add it to the ordering as a timing start-point if (clock_domain != IdString()) { DelayInfo clkToQ; ctx->getCellDelay(cell.second.get(), clock_domain, o->name, clkToQ); @@ -174,10 +181,14 @@ struct Timing net_data.emplace(o->net, TimingData{ clkToQ.maxDelay() }); } else { + // Also add I/O cells too if (is_io) { topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{}); } + // Otherwise, for all driven input ports on this cell, + // if a timing arch exists between the input and + // the current output port, increment fanin counter for (auto i : input_ports) { DelayInfo comb_delay; bool is_path = ctx->getCellDelay(cell.second.get(), i, o->name, comb_delay); @@ -188,6 +199,7 @@ struct Timing } } + // If these constant nets exist, add them to the topographical ordering too auto it = ctx->nets.find(ctx->id("$PACKER_VCC_NET")); if (it != ctx->nets.end()) { topographical_order.emplace_back(it->second.get()); @@ -201,6 +213,8 @@ struct Timing std::deque queue(topographical_order.begin(), topographical_order.end()); + // Now walk the design, from the start points identified previously, building + // up a topographical order while (!queue.empty()) { const auto net = queue.front(); queue.pop_front(); @@ -208,15 +222,16 @@ struct Timing DelayInfo clkToQ; for (auto &usr : net->users) { auto clock_domain = ctx->getPortClock(usr.cell, usr.port); - // Follow outputs of the user for (auto& port : usr.cell->ports) { if (port.second.type == PORT_OUT && port.second.net) { - // Skip if this is a clocked output + // Skip if this is a clocked output (but allow non-clocked ones) if (clock_domain != IdString() && ctx->getCellDelay(usr.cell, clock_domain, port.first, clkToQ)) continue; DelayInfo comb_delay; bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay); if (is_path) { + // Decrement the fanin count, and only add to topographical + // order if all its fanins have already been visited auto it = port_fanin.find(&port.second); NPNR_ASSERT(it != port_fanin.end()); if (--it->second == 0) { @@ -230,10 +245,25 @@ struct Timing } } +#if 0 + // Sanity check to ensure that all ports where fanins were recorded + // were indeed visited + log_info("port_fanin = %d\n", port_fanin.size()); + for (auto i : port_fanin) { + log_info("%s %s.%s has %d fanins left\n", i.first->net->name.c_str(ctx),i.first->net->driver.cell->name.c_str(ctx), i.first->name.c_str(ctx), i.second); + auto cell = i.first->net->driver.cell; + for (auto& port : cell->ports) { + if (!port.second.net) continue; + if (port.second.type == PORT_IN) + log_info(" %s connected to %s\n", port.second.name.c_str(ctx), port.second.net->name.c_str(ctx)); + } + } NPNR_ASSERT(port_fanin.empty()); +#endif port_fanin.clear(); - // Find the maximum arrival time and max path length for each net + // Go forwards topographically to 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; @@ -245,7 +275,7 @@ struct Timing auto net_delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t(); auto budget_override = ctx->getBudgetOverride(net, usr, net_delay); auto usr_arrival = net_arrival + net_delay; - // Follow outputs of the user + // Iterate over all output ports on the same cell as the sink for (auto port : usr.cell->ports) { if (port.second.type == PORT_OUT && port.second.net) { DelayInfo comb_delay; @@ -255,7 +285,8 @@ struct Timing auto& data = net_data[port.second.net]; auto& arrival = data.max_arrival; arrival = std::max(arrival, usr_arrival + comb_delay.maxDelay()); - if (!budget_override) { + if (!budget_override) { // Do not increment path length if budget overriden + // since it doesn't require a share of the slack auto& path_length = data.max_path_length; path_length = std::max(path_length, net_length_plus_one); } @@ -266,6 +297,8 @@ struct Timing } } + // Now go backwards topographically to determine the minimum path slack, + // and to distribute all path slack evenly between all nets on the path 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; @@ -287,11 +320,10 @@ struct Timing (*slack_histogram)[slack_ps]++; } } else { - // Follow outputs of the user - for (auto port : usr.cell->ports) { + // Iterate over all output ports on the same cell as the sink + for (const 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; -- cgit v1.2.3 From 06584f2e74bff6bf5a179e7f4a0dbebda7ef6caf Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 6 Aug 2018 14:14:41 -0700 Subject: Compute critical path report --- common/timing.cc | 51 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 49 insertions(+), 2 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index 49e8a5ef..8fe5cd49 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -145,7 +145,6 @@ struct Timing } } } - #else // First, compute the topographical order of nets to walk through // the circuit, assuming it is a _acyclic_ graph @@ -297,6 +296,8 @@ struct Timing } } + const NetInfo* crit_net = nullptr; + // Now go backwards topographically to determine the minimum path slack, // and to distribute all path slack evenly between all nets on the path for (auto net : boost::adaptors::reverse(topographical_order)) { @@ -314,7 +315,14 @@ struct Timing 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 (path_budget < min_slack) { + min_slack = path_budget; + if (crit_path) { + crit_path->clear(); + crit_path->push_back(&usr); + crit_net = net; + } + } if (slack_histogram) { int slack_ps = ctx->getDelayNS(path_budget) * 1000; (*slack_histogram)[slack_ps]++; @@ -337,6 +345,45 @@ struct Timing } } } + + if (crit_path) { + // Walk backwards from the most critical net + while (crit_net) { + const PortInfo* crit_ipin = nullptr; + delay_t max_arrival = std::numeric_limits::min(); + + // Look at all input ports on its driving cell + for (const auto& port : crit_net->driver.cell->ports) { + if (port.second.type == PORT_IN && port.second.net) { + DelayInfo comb_delay; + bool is_path = ctx->getCellDelay(crit_net->driver.cell, port.first, crit_net->driver.port, comb_delay); + if (is_path) { + // If input port is influenced by a clock, skip + if (ctx->getPortClock(crit_net->driver.cell, port.first) != IdString()) + continue; + + // And find the fanin net with the latest arrival time + const auto net_arrival = net_data.at(port.second.net).max_arrival; + if (net_arrival > max_arrival) { + max_arrival = net_arrival; + crit_ipin = &port.second; + } + } + } + } + + if (!crit_ipin) break; + + for (auto &usr : crit_ipin->net->users) { + if (usr.cell->name == crit_net->driver.cell->name && usr.port == crit_ipin->name) { + crit_path->push_back(&usr); + break; + } + } + crit_net = crit_ipin->net; + } + std::reverse(crit_path->begin(), crit_path->end()); + } #endif return min_slack; } -- cgit v1.2.3 From f3e46df7095582b23ffcd4726e1b33cd77df6ba0 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 6 Aug 2018 16:09:17 -0700 Subject: Remove old timing code --- common/timing.cc | 88 -------------------------------------------------------- 1 file changed, 88 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index 8fe5cd49..b1be8dad 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -37,7 +37,6 @@ struct Timing bool net_delays; bool update; delay_t min_slack; - PortRefVector current_path; PortRefVector *crit_path; DelayFrequency *slack_histogram; @@ -56,96 +55,10 @@ struct Timing { } - delay_t follow_net(NetInfo *net, int path_length, delay_t slack) - { - const delay_t default_budget = slack / (path_length + 1); - delay_t net_budget = default_budget; - for (auto &usr : net->users) { - auto delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t(); - if (crit_path) - current_path.push_back(&usr); - // If budget override exists, use that value and do not increment path_length - auto budget = default_budget; - if (ctx->getBudgetOverride(net, usr, budget)) { - if (update) - usr.budget = std::min(usr.budget, budget); - budget = follow_user_port(usr, path_length, slack - budget); - net_budget = std::min(net_budget, budget); - } - else { - budget = follow_user_port(usr, path_length + 1, slack - delay); - net_budget = std::min(net_budget, budget); - if (update) - usr.budget = std::min(usr.budget, delay + budget); - } - if (crit_path) - current_path.pop_back(); - } - return net_budget; - } - - // Follow a path, returning budget to annotate - delay_t follow_user_port(PortRef &user, int path_length, delay_t 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; - if (slack < min_slack) { - min_slack = slack; - if (crit_path) - *crit_path = current_path; - } - if (slack_histogram) { - int slack_ps = ctx->getDelayNS(slack) * 1000; - (*slack_histogram)[slack_ps]++; - } - } 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) { - DelayInfo 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(net, path_length, slack - comb_delay.maxDelay()); - value = std::min(value, path_budget); - } - } - } - } - } - return value; - } - delay_t walk_paths() { const auto clk_period = delay_t(1.0e12 / ctx->target_freq); -#if 0 - // Go through all clocked drivers and distribute the available path - // slack evenly into the budget of every sink on the path - 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 = clk_period; // TODO: clock constraints - DelayInfo clkToQ; - if (ctx->getCellDelay(cell.second.get(), clock_domain, port.first, clkToQ)) - slack -= clkToQ.maxDelay(); - if (port.second.net) - follow_net(port.second.net, 0, slack); - } - } - } - } -#else // First, compute the topographical order of nets to walk through // the circuit, assuming it is a _acyclic_ graph // TODO: Handle the case where it is cyclic, e.g. combinatorial loops @@ -384,7 +297,6 @@ struct Timing } std::reverse(crit_path->begin(), crit_path->end()); } -#endif return min_slack; } -- cgit v1.2.3 From 483f8631068086d7f0bdf10f60205567e03d943e Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 6 Aug 2018 17:20:29 -0700 Subject: Also add PLL outputs as timing startpoints --- common/timing.cc | 18 +++--------------- 1 file changed, 3 insertions(+), 15 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index b1be8dad..3a4f0f9c 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -61,7 +61,7 @@ struct Timing // First, compute the topographical order of nets to walk through // the circuit, assuming it is a _acyclic_ graph - // TODO: Handle the case where it is cyclic, e.g. combinatorial loops + // TODO(eddieh): Handle the case where it is cyclic, e.g. combinatorial loops std::vector topographical_order; std::unordered_map net_data; // In lieu of deleting edges from the graph, simply count @@ -94,7 +94,8 @@ struct Timing } else { // Also add I/O cells too - if (is_io) { + // TODO(eddieh): More generic way of detecting PLLs + if (is_io || cell.second->type == ctx->id("ICESTORM_PLL")) { topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{}); } @@ -157,22 +158,9 @@ struct Timing } } -#if 0 // Sanity check to ensure that all ports where fanins were recorded // were indeed visited - log_info("port_fanin = %d\n", port_fanin.size()); - for (auto i : port_fanin) { - log_info("%s %s.%s has %d fanins left\n", i.first->net->name.c_str(ctx),i.first->net->driver.cell->name.c_str(ctx), i.first->name.c_str(ctx), i.second); - auto cell = i.first->net->driver.cell; - for (auto& port : cell->ports) { - if (!port.second.net) continue; - if (port.second.type == PORT_IN) - log_info(" %s connected to %s\n", port.second.name.c_str(ctx), port.second.net->name.c_str(ctx)); - } - } NPNR_ASSERT(port_fanin.empty()); -#endif - port_fanin.clear(); // Go forwards topographically to find the maximum arrival time // and max path length for each net -- cgit v1.2.3 From f44a5fb904e6e52e8383e8f13d9b3f4ab9d7ce48 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 6 Aug 2018 17:35:23 -0700 Subject: clangformat --- common/timing.cc | 65 +++++++++++++++++++++++++++++++------------------------- 1 file changed, 36 insertions(+), 29 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index 3a4f0f9c..e524cd19 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -20,11 +20,11 @@ #include "timing.h" #include +#include #include #include #include "log.h" #include "util.h" -#include NEXTPNR_NAMESPACE_BEGIN @@ -40,7 +40,8 @@ struct Timing PortRefVector *crit_path; DelayFrequency *slack_histogram; - struct TimingData { + 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; @@ -61,20 +62,22 @@ struct Timing // First, compute the topographical order of nets to walk through // the circuit, assuming it is a _acyclic_ graph - // TODO(eddieh): Handle the case where it is cyclic, e.g. combinatorial loops - std::vector topographical_order; - std::unordered_map net_data; + // TODO(eddieh): Handle the case where it is cyclic, e.g. combinatorial + // loops + std::vector topographical_order; + std::unordered_map net_data; // In lieu of deleting edges from the graph, simply count // the number of fanins to each output port - std::unordered_map port_fanin; + std::unordered_map port_fanin; std::vector input_ports; - std::vector output_ports; + std::vector output_ports; for (auto &cell : ctx->cells) { input_ports.clear(); output_ports.clear(); - for (auto& port : cell.second->ports) { - if (!port.second.net) continue; + for (auto &port : cell.second->ports) { + if (!port.second.net) + continue; if (port.second.type == PORT_OUT) output_ports.push_back(&port.second); else @@ -90,11 +93,10 @@ struct Timing 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 { + net_data.emplace(o->net, TimingData{clkToQ.maxDelay()}); + } else { // Also add I/O cells too - // TODO(eddieh): More generic way of detecting PLLs + // TODO(eddieh): More generic way of detecting PLLs if (is_io || cell.second->type == ctx->id("ICESTORM_PLL")) { topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{}); @@ -124,9 +126,10 @@ struct Timing net_data.emplace(it->second.get(), TimingData{}); } - std::deque queue(topographical_order.begin(), topographical_order.end()); + std::deque queue(topographical_order.begin(), topographical_order.end()); - // Now walk the design, from the start points identified previously, building + // Now walk the design, from the start points identified previously, + // building // up a topographical order while (!queue.empty()) { const auto net = queue.front(); @@ -135,7 +138,7 @@ struct Timing DelayInfo clkToQ; for (auto &usr : net->users) { auto clock_domain = ctx->getPortClock(usr.cell, usr.port); - for (auto& port : usr.cell->ports) { + for (auto &port : usr.cell->ports) { if (port.second.type == PORT_OUT && port.second.net) { // Skip if this is a clocked output (but allow non-clocked ones) if (clock_domain != IdString() && ctx->getCellDelay(usr.cell, clock_domain, port.first, clkToQ)) @@ -182,12 +185,13 @@ struct Timing // 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; + auto &data = net_data[port.second.net]; + auto &arrival = data.max_arrival; arrival = std::max(arrival, usr_arrival + comb_delay.maxDelay()); - if (!budget_override) { // Do not increment path length if budget overriden - // since it doesn't require a share of the slack - auto& path_length = data.max_path_length; + if (!budget_override) { // Do not increment path length if + // budget overriden + // since it doesn't require a share of the slack + auto &path_length = data.max_path_length; path_length = std::max(path_length, net_length_plus_one); } } @@ -197,14 +201,14 @@ struct Timing } } - const NetInfo* crit_net = nullptr; + const NetInfo *crit_net = nullptr; // Now go backwards topographically to determine the minimum path slack, // and to distribute all path slack evenly between all nets on the path 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; + auto &net_min_remaining_budget = nd.min_remaining_budget; for (auto &usr : net->users) { auto net_delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t(); auto budget_override = ctx->getBudgetOverride(net, usr, net_delay); @@ -230,7 +234,7 @@ struct Timing } } else { // Iterate over all output ports on the same cell as the sink - for (const auto& port : usr.cell->ports) { + for (const 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); @@ -239,7 +243,8 @@ struct Timing auto budget_share = budget_override ? 0 : path_budget / net_length_plus_one; if (update) usr.budget = std::min(usr.budget, net_delay + budget_share); - net_min_remaining_budget = std::min(net_min_remaining_budget, path_budget - budget_share); + net_min_remaining_budget = + std::min(net_min_remaining_budget, path_budget - budget_share); } } } @@ -250,14 +255,15 @@ struct Timing if (crit_path) { // Walk backwards from the most critical net while (crit_net) { - const PortInfo* crit_ipin = nullptr; + const PortInfo *crit_ipin = nullptr; delay_t max_arrival = std::numeric_limits::min(); // Look at all input ports on its driving cell - for (const auto& port : crit_net->driver.cell->ports) { + for (const auto &port : crit_net->driver.cell->ports) { if (port.second.type == PORT_IN && port.second.net) { DelayInfo comb_delay; - bool is_path = ctx->getCellDelay(crit_net->driver.cell, port.first, crit_net->driver.port, comb_delay); + bool is_path = + ctx->getCellDelay(crit_net->driver.cell, port.first, crit_net->driver.port, comb_delay); if (is_path) { // If input port is influenced by a clock, skip if (ctx->getPortClock(crit_net->driver.cell, port.first) != IdString()) @@ -273,7 +279,8 @@ struct Timing } } - if (!crit_ipin) break; + if (!crit_ipin) + break; for (auto &usr : crit_ipin->net->users) { if (usr.cell->name == crit_net->driver.cell->name && usr.port == crit_ipin->name) { -- cgit v1.2.3 From 676500b83fade3c2bc422a20f503ee1987cdb00f Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 6 Aug 2018 17:42:44 -0700 Subject: Do less work if update flag is false --- common/timing.cc | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index e524cd19..bb3f680d 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -215,10 +215,11 @@ struct Timing 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 = budget_override ? 0 : path_budget / net_length_plus_one; - if (update) + if (update) { + auto budget_share = budget_override ? 0 : path_budget / net_length_plus_one; usr.budget = std::min(usr.budget, net_delay + budget_share); - net_min_remaining_budget = std::min(net_min_remaining_budget, path_budget - budget_share); + net_min_remaining_budget = std::min(net_min_remaining_budget, path_budget - budget_share); + } if (path_budget < min_slack) { min_slack = path_budget; @@ -232,7 +233,7 @@ struct Timing int slack_ps = ctx->getDelayNS(path_budget) * 1000; (*slack_histogram)[slack_ps]++; } - } else { + } else if (update) { // Iterate over all output ports on the same cell as the sink for (const auto &port : usr.cell->ports) { if (port.second.type == PORT_OUT && port.second.net) { @@ -241,8 +242,7 @@ struct Timing if (is_path) { auto path_budget = net_data.at(port.second.net).min_remaining_budget; auto budget_share = budget_override ? 0 : path_budget / net_length_plus_one; - if (update) - usr.budget = std::min(usr.budget, net_delay + budget_share); + usr.budget = std::min(usr.budget, net_delay + budget_share); net_min_remaining_budget = std::min(net_min_remaining_budget, path_budget - budget_share); } -- cgit v1.2.3 From a1d626469f46d112c2dfea680beb30ebdebc65fe Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Mon, 6 Aug 2018 19:53:42 -0700 Subject: Cleanup nesting --- common/timing.cc | 118 +++++++++++++++++++++++++++---------------------------- 1 file changed, 59 insertions(+), 59 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index bb3f680d..841f8e92 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -139,23 +139,23 @@ struct Timing for (auto &usr : net->users) { auto clock_domain = ctx->getPortClock(usr.cell, usr.port); for (auto &port : usr.cell->ports) { - if (port.second.type == PORT_OUT && port.second.net) { - // Skip if this is a clocked output (but allow non-clocked ones) - if (clock_domain != IdString() && ctx->getCellDelay(usr.cell, clock_domain, port.first, clkToQ)) - continue; - DelayInfo comb_delay; - bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay); - if (is_path) { - // Decrement the fanin count, and only add to topographical - // order if all its fanins have already been visited - 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); - } - } + if (port.second.type != PORT_OUT || !port.second.net) + continue; + // Skip if this is a clocked output (but allow non-clocked ones) + if (clock_domain != IdString() && ctx->getCellDelay(usr.cell, clock_domain, port.first, clkToQ)) + continue; + DelayInfo comb_delay; + bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay); + if (!is_path) + continue; + // Decrement the fanin count, and only add to topographical + // order if all its fanins have already been visited + 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); } } } @@ -180,21 +180,21 @@ struct Timing auto usr_arrival = net_arrival + net_delay; // Iterate over all output ports on the same cell as the sink 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) { // Do not increment path length if - // budget overriden - // since it doesn't require a share of the slack - auto &path_length = data.max_path_length; - path_length = std::max(path_length, net_length_plus_one); - } - } + if (port.second.type != PORT_OUT || !port.second.net) + continue; + 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) + continue; + auto &data = net_data[port.second.net]; + auto &arrival = data.max_arrival; + arrival = std::max(arrival, usr_arrival + comb_delay.maxDelay()); + if (!budget_override) { // Do not increment path length if + // budget overriden + // since it doesn't require a share of the slack + auto &path_length = data.max_path_length; + path_length = std::max(path_length, net_length_plus_one); } } } @@ -236,17 +236,16 @@ struct Timing } else if (update) { // Iterate over all output ports on the same cell as the sink for (const 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 path_budget = net_data.at(port.second.net).min_remaining_budget; - auto budget_share = budget_override ? 0 : path_budget / net_length_plus_one; - usr.budget = std::min(usr.budget, net_delay + budget_share); - net_min_remaining_budget = - std::min(net_min_remaining_budget, path_budget - budget_share); - } - } + if (port.second.type != PORT_OUT || !port.second.net) + continue; + DelayInfo comb_delay; + bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay); + if (!is_path) + continue; + auto path_budget = net_data.at(port.second.net).min_remaining_budget; + auto budget_share = budget_override ? 0 : path_budget / net_length_plus_one; + usr.budget = std::min(usr.budget, net_delay + budget_share); + net_min_remaining_budget = std::min(net_min_remaining_budget, path_budget - budget_share); } } } @@ -260,28 +259,29 @@ struct Timing // Look at all input ports on its driving cell for (const auto &port : crit_net->driver.cell->ports) { - if (port.second.type == PORT_IN && port.second.net) { - DelayInfo comb_delay; - bool is_path = - ctx->getCellDelay(crit_net->driver.cell, port.first, crit_net->driver.port, comb_delay); - if (is_path) { - // If input port is influenced by a clock, skip - if (ctx->getPortClock(crit_net->driver.cell, port.first) != IdString()) - continue; - - // And find the fanin net with the latest arrival time - const auto net_arrival = net_data.at(port.second.net).max_arrival; - if (net_arrival > max_arrival) { - max_arrival = net_arrival; - crit_ipin = &port.second; - } - } + if (port.second.type != PORT_IN || !port.second.net) + continue; + DelayInfo comb_delay; + bool is_path = + ctx->getCellDelay(crit_net->driver.cell, port.first, crit_net->driver.port, comb_delay); + if (!is_path) + continue; + // If input port is influenced by a clock, skip + if (ctx->getPortClock(crit_net->driver.cell, port.first) != IdString()) + continue; + + // And find the fanin net with the latest arrival time + const auto net_arrival = net_data.at(port.second.net).max_arrival; + if (net_arrival > max_arrival) { + max_arrival = net_arrival; + crit_ipin = &port.second; } } if (!crit_ipin) break; + // Now convert PortInfo* into a PortRef* for (auto &usr : crit_ipin->net->users) { if (usr.cell->name == crit_net->driver.cell->name && usr.port == crit_ipin->name) { crit_path->push_back(&usr); -- cgit v1.2.3 From d8b383003194f45cae8486905e50575d792a4640 Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 8 Aug 2018 14:58:43 +0200 Subject: timing: Update to new use API (currently broken) Signed-off-by: David Shah --- common/timing.cc | 32 +++++++++++++++++++++----------- 1 file changed, 21 insertions(+), 11 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index 841f8e92..15a4d126 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -84,20 +84,20 @@ struct Timing input_ports.push_back(port.first); } - bool is_io = ctx->isIOCell(cell.second.get()); for (auto o : output_ports) { - IdString clock_domain = ctx->getPortClock(cell.second.get(), o->name); + IdString clockPort; + TimingPortClass portClass = ctx->getPortTimingClass(cell.second.get(), o->name, clockPort); // If output port is influenced by a clock (e.g. FF output) // then add it to the ordering as a timing start-point - if (clock_domain != IdString()) { + if (portClass == TMG_REGISTER_OUTPUT) { DelayInfo clkToQ; - ctx->getCellDelay(cell.second.get(), clock_domain, o->name, clkToQ); + ctx->getCellDelay(cell.second.get(), clockPort, o->name, clkToQ); topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{clkToQ.maxDelay()}); } else { // Also add I/O cells too // TODO(eddieh): More generic way of detecting PLLs - if (is_io || cell.second->type == ctx->id("ICESTORM_PLL")) { + if (portClass == TMG_STARTPOINT || portClass == TMG_IGNORE) { // IGNORE: ???? topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{}); } @@ -137,12 +137,13 @@ struct Timing DelayInfo clkToQ; for (auto &usr : net->users) { - auto clock_domain = ctx->getPortClock(usr.cell, usr.port); + IdString clockPort; + TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, usr.port, clockPort); for (auto &port : usr.cell->ports) { if (port.second.type != PORT_OUT || !port.second.net) continue; // Skip if this is a clocked output (but allow non-clocked ones) - if (clock_domain != IdString() && ctx->getCellDelay(usr.cell, clock_domain, port.first, clkToQ)) + if (portClass == TMG_REGISTER_OUTPUT || portClass == TMG_ENDPOINT || portClass == TMG_IGNORE) continue; DelayInfo comb_delay; bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay); @@ -173,7 +174,9 @@ struct Timing 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()) { + IdString clockPort; + TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, usr.port, clockPort); + if (portClass == TMG_REGISTER_INPUT || portClass == TMG_ENDPOINT || portClass == TMG_IGNORE) { } else { auto net_delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t(); auto budget_override = ctx->getBudgetOverride(net, usr, net_delay); @@ -212,7 +215,9 @@ struct Timing for (auto &usr : net->users) { auto net_delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t(); auto budget_override = ctx->getBudgetOverride(net, usr, net_delay); - if (ctx->getPortClock(usr.cell, usr.port) != IdString()) { + IdString associatedClock; + TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, usr.port, associatedClock); + if (portClass == TMG_REGISTER_INPUT || portClass == TMG_ENDPOINT) { const auto net_arrival = nd.max_arrival; auto path_budget = clk_period - (net_arrival + net_delay); if (update) { @@ -267,7 +272,10 @@ struct Timing if (!is_path) continue; // If input port is influenced by a clock, skip - if (ctx->getPortClock(crit_net->driver.cell, port.first) != IdString()) + IdString portClock; + TimingPortClass portClass = ctx->getPortTimingClass(crit_net->driver.cell, port.first, portClock); + if (portClass == TMG_REGISTER_INPUT || portClass == TMG_CLOCK_INPUT || portClass == TMG_ENDPOINT || + portClass == TMG_IGNORE) continue; // And find the fanin net with the latest arrival time @@ -373,7 +381,9 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_path) 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); + + IdString last_port; + ctx->getPortTimingClass(front_driver.cell, front_driver.port, last_port); for (auto sink : crit_path) { auto sink_cell = sink->cell; auto &port = sink_cell->ports.at(sink->port); -- cgit v1.2.3 From d173ddba367f7082f122df75dffb59577afaf0b4 Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 8 Aug 2018 15:07:41 +0200 Subject: timing: Debugging implementation of new timing API Signed-off-by: David Shah --- common/timing.cc | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index 15a4d126..0028fd21 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -96,8 +96,8 @@ struct Timing net_data.emplace(o->net, TimingData{clkToQ.maxDelay()}); } else { // Also add I/O cells too - // TODO(eddieh): More generic way of detecting PLLs - if (portClass == TMG_STARTPOINT || portClass == TMG_IGNORE) { // IGNORE: ???? + // TODO: how to process ignore here + if (portClass == TMG_STARTPOINT || portClass == TMG_IGNORE) { topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{}); } @@ -138,12 +138,17 @@ struct Timing DelayInfo clkToQ; for (auto &usr : net->users) { IdString clockPort; - TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, usr.port, clockPort); + TimingPortClass usrClass = ctx->getPortTimingClass(usr.cell, usr.port, clockPort); + if (usrClass == TMG_IGNORE || usrClass == TMG_CLOCK_INPUT) + continue; for (auto &port : usr.cell->ports) { if (port.second.type != PORT_OUT || !port.second.net) continue; + TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, port.first, clockPort); + // Skip if this is a clocked output (but allow non-clocked ones) - if (portClass == TMG_REGISTER_OUTPUT || portClass == TMG_ENDPOINT || portClass == TMG_IGNORE) + if (portClass == TMG_REGISTER_OUTPUT || portClass == TMG_STARTPOINT || portClass == TMG_IGNORE || + portClass == TMG_GEN_CLOCK) continue; DelayInfo comb_delay; bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay); -- cgit v1.2.3 From fca01f5447d8ca0ba2e0075cb214f3a19933e6c1 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Wed, 8 Aug 2018 07:49:07 -0700 Subject: Also include TMG_GEN_CLOCK as a timing startpoint --- common/timing.cc | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index 0028fd21..fae9ca53 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -95,14 +95,13 @@ struct Timing topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{clkToQ.maxDelay()}); } else { - // Also add I/O cells too // TODO: how to process ignore here - if (portClass == TMG_STARTPOINT || portClass == TMG_IGNORE) { + if (portClass == TMG_STARTPOINT || portClass == TMG_GEN_CLOCK || portClass == TMG_IGNORE) { topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{}); } // Otherwise, for all driven input ports on this cell, - // if a timing arch exists between the input and + // if a timing arc exists between the input and // the current output port, increment fanin counter for (auto i : input_ports) { DelayInfo comb_delay; -- cgit v1.2.3 From 936b52eafc6da47fdd9c5e56d2e5ae667f000944 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Wed, 8 Aug 2018 08:01:24 -0700 Subject: Unfurl comments for clangformat --- common/timing.cc | 40 ++++++++++++---------------------------- 1 file changed, 12 insertions(+), 28 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index fae9ca53..47091c27 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -60,14 +60,11 @@ struct Timing { const auto clk_period = delay_t(1.0e12 / ctx->target_freq); - // First, compute the topographical order of nets to walk through - // the circuit, assuming it is a _acyclic_ graph - // TODO(eddieh): Handle the case where it is cyclic, e.g. combinatorial - // loops + // First, compute the topographical order of nets to walk through the circuit, assuming it is a _acyclic_ graph + // TODO(eddieh): Handle the case where it is cyclic, e.g. combinatorial loops std::vector topographical_order; std::unordered_map net_data; - // In lieu of deleting edges from the graph, simply count - // the number of fanins to each output port + // In lieu of deleting edges from the graph, simply count the number of fanins to each output port std::unordered_map port_fanin; std::vector input_ports; @@ -87,8 +84,7 @@ struct Timing for (auto o : output_ports) { IdString clockPort; TimingPortClass portClass = ctx->getPortTimingClass(cell.second.get(), o->name, clockPort); - // If output port is influenced by a clock (e.g. FF output) - // then add it to the ordering as a timing start-point + // If output port is influenced by a clock (e.g. FF output) then add it to the ordering as a timing start-point if (portClass == TMG_REGISTER_OUTPUT) { DelayInfo clkToQ; ctx->getCellDelay(cell.second.get(), clockPort, o->name, clkToQ); @@ -100,9 +96,7 @@ struct Timing topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{}); } - // Otherwise, for all driven input ports on this cell, - // if a timing arc exists between the input and - // the current output port, increment fanin counter + // Otherwise, for all driven input ports on this cell, if a timing arc exists between the input and the current output port, increment fanin counter for (auto i : input_ports) { DelayInfo comb_delay; bool is_path = ctx->getCellDelay(cell.second.get(), i, o->name, comb_delay); @@ -127,9 +121,7 @@ struct Timing std::deque queue(topographical_order.begin(), topographical_order.end()); - // Now walk the design, from the start points identified previously, - // building - // up a topographical order + // Now walk the design, from the start points identified previously, building up a topographical order while (!queue.empty()) { const auto net = queue.front(); queue.pop_front(); @@ -153,8 +145,7 @@ struct Timing bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay); if (!is_path) continue; - // Decrement the fanin count, and only add to topographical - // order if all its fanins have already been visited + // Decrement the fanin count, and only add to topographical order if all its fanins have already been visited auto it = port_fanin.find(&port.second); NPNR_ASSERT(it != port_fanin.end()); if (--it->second == 0) { @@ -166,12 +157,10 @@ struct Timing } } - // Sanity check to ensure that all ports where fanins were recorded - // were indeed visited + // Sanity check to ensure that all ports where fanins were recorded were indeed visited NPNR_ASSERT(port_fanin.empty()); - // Go forwards topographically to find the maximum arrival time - // and max path length for each net + // Go forwards topographically to 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; @@ -197,9 +186,7 @@ struct Timing auto &data = net_data[port.second.net]; auto &arrival = data.max_arrival; arrival = std::max(arrival, usr_arrival + comb_delay.maxDelay()); - if (!budget_override) { // Do not increment path length if - // budget overriden - // since it doesn't require a share of the slack + if (!budget_override) { // Do not increment path length if budget overriden since it doesn't require a share of the slack auto &path_length = data.max_path_length; path_length = std::max(path_length, net_length_plus_one); } @@ -210,8 +197,7 @@ struct Timing const NetInfo *crit_net = nullptr; - // Now go backwards topographically to determine the minimum path slack, - // and to distribute all path slack evenly between all nets on the path + // Now go backwards topographically to determine the minimum path slack, and to distribute all path slack evenly between all nets on the path 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; @@ -348,9 +334,7 @@ void assign_budget(Context *ctx, bool quiet) } } - // For slack redistribution, if user has not specified a frequency - // dynamically adjust the target frequency to be the currently - // achieved maximum + // For slack redistribution, if user has not specified a frequency dynamically adjust the target frequency to be the currently achieved maximum if (ctx->auto_freq && ctx->slack_redist_iter > 0) { delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); ctx->target_freq = 1e12 / (default_slack - timing.min_slack); -- cgit v1.2.3 From 90e3db324eb016b6c5ae4168db6ac00f65c2af4e Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 8 Aug 2018 17:07:20 +0200 Subject: clangformat Signed-off-by: David Shah --- common/timing.cc | 18 ++++++++++++------ 1 file changed, 12 insertions(+), 6 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index 47091c27..a3b5235a 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -84,7 +84,8 @@ struct Timing for (auto o : output_ports) { IdString clockPort; TimingPortClass portClass = ctx->getPortTimingClass(cell.second.get(), o->name, clockPort); - // If output port is influenced by a clock (e.g. FF output) then add it to the ordering as a timing start-point + // If output port is influenced by a clock (e.g. FF output) then add it to the ordering as a timing + // start-point if (portClass == TMG_REGISTER_OUTPUT) { DelayInfo clkToQ; ctx->getCellDelay(cell.second.get(), clockPort, o->name, clkToQ); @@ -96,7 +97,8 @@ struct Timing topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{}); } - // Otherwise, for all driven input ports on this cell, if a timing arc exists between the input and the current output port, increment fanin counter + // Otherwise, for all driven input ports on this cell, if a timing arc exists between the input and + // the current output port, increment fanin counter for (auto i : input_ports) { DelayInfo comb_delay; bool is_path = ctx->getCellDelay(cell.second.get(), i, o->name, comb_delay); @@ -145,7 +147,8 @@ struct Timing bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay); if (!is_path) continue; - // Decrement the fanin count, and only add to topographical order if all its fanins have already been visited + // Decrement the fanin count, and only add to topographical order if all its fanins have already + // been visited auto it = port_fanin.find(&port.second); NPNR_ASSERT(it != port_fanin.end()); if (--it->second == 0) { @@ -186,7 +189,8 @@ struct Timing auto &data = net_data[port.second.net]; auto &arrival = data.max_arrival; arrival = std::max(arrival, usr_arrival + comb_delay.maxDelay()); - if (!budget_override) { // Do not increment path length if budget overriden since it doesn't require a share of the slack + if (!budget_override) { // Do not increment path length if budget overriden since it doesn't + // require a share of the slack auto &path_length = data.max_path_length; path_length = std::max(path_length, net_length_plus_one); } @@ -197,7 +201,8 @@ struct Timing const NetInfo *crit_net = nullptr; - // Now go backwards topographically to determine the minimum path slack, and to distribute all path slack evenly between all nets on the path + // Now go backwards topographically to determine the minimum path slack, and to distribute all path slack evenly + // between all nets on the path 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; @@ -334,7 +339,8 @@ void assign_budget(Context *ctx, bool quiet) } } - // For slack redistribution, if user has not specified a frequency dynamically adjust the target frequency to be the currently achieved maximum + // For slack redistribution, if user has not specified a frequency dynamically adjust the target frequency to be the + // currently achieved maximum if (ctx->auto_freq && ctx->slack_redist_iter > 0) { delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); ctx->target_freq = 1e12 / (default_slack - timing.min_slack); -- cgit v1.2.3 From 91023d2a0e6c4d15b640f9c913565b8298f0a19c Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Wed, 8 Aug 2018 08:31:08 -0700 Subject: Leave comment behind about removing false paths --- common/timing.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index a3b5235a..c1be083d 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -92,7 +92,7 @@ struct Timing topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{clkToQ.maxDelay()}); } else { - // TODO: how to process ignore here + // TODO(eddieh): Generated clocks and ignored ports are currently added into the ordering as if it was a regular timing start point in order to enable the full topographical order to be computed, however these false nets (and their downstream paths) should not be in the final ordering if (portClass == TMG_STARTPOINT || portClass == TMG_GEN_CLOCK || portClass == TMG_IGNORE) { topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{}); -- cgit v1.2.3 From 03575a2a7a07dd4798bf7acde6bd49258c2ec236 Mon Sep 17 00:00:00 2001 From: Eddie Hung Date: Wed, 8 Aug 2018 08:32:17 -0700 Subject: One more breadcrumb --- common/timing.cc | 1 + 1 file changed, 1 insertion(+) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index c1be083d..3c430739 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -110,6 +110,7 @@ struct Timing } // If these constant nets exist, add them to the topographical ordering too + // TODO(eddieh): Also false paths and should be removed from ordering auto it = ctx->nets.find(ctx->id("$PACKER_VCC_NET")); if (it != ctx->nets.end()) { topographical_order.emplace_back(it->second.get()); -- cgit v1.2.3 From 8e593fb47147ca7b4cd73d3cafc789d520871cb4 Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 8 Aug 2018 17:54:25 +0200 Subject: timing: Update to use getDelayNS Signed-off-by: David Shah --- common/timing.cc | 25 ++++++++++++++----------- 1 file changed, 14 insertions(+), 11 deletions(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index 3c430739..601311a8 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -92,7 +92,9 @@ struct Timing topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{clkToQ.maxDelay()}); } else { - // TODO(eddieh): Generated clocks and ignored ports are currently added into the ordering as if it was a regular timing start point in order to enable the full topographical order to be computed, however these false nets (and their downstream paths) should not be in the final ordering + // TODO(eddieh): Generated clocks and ignored ports are currently added into the ordering as if it + // was a regular timing start point in order to enable the full topographical order to be computed, + // however these false nets (and their downstream paths) should not be in the final ordering if (portClass == TMG_STARTPOINT || portClass == TMG_GEN_CLOCK || portClass == TMG_IGNORE) { topographical_order.emplace_back(o->net); net_data.emplace(o->net, TimingData{}); @@ -343,12 +345,12 @@ void assign_budget(Context *ctx, bool quiet) // For slack redistribution, if user has not specified a frequency dynamically adjust the target frequency to be the // currently achieved maximum if (ctx->auto_freq && ctx->slack_redist_iter > 0) { - delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); - ctx->target_freq = 1e12 / (default_slack - timing.min_slack); + delay_t default_slack = delay_t((1.0e9 / ctx->getDelayNS(1)) / ctx->target_freq); + ctx->target_freq = 1.0e9 / ctx->getDelayNS(default_slack - timing.min_slack); if (ctx->verbose) - log_info("minimum slack for this assign = %d, target Fmax for next " + log_info("minimum slack for this assign = %.2f ns, target Fmax for next " "update = %.2f MHz\n", - timing.min_slack, ctx->target_freq / 1e6); + ctx->getDelayNS(timing.min_slack), ctx->target_freq / 1e6); } if (!quiet) @@ -388,14 +390,15 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_path) DelayInfo comb_delay; ctx->getCellDelay(sink_cell, last_port, driver.port, comb_delay); total += comb_delay.maxDelay(); - log_info("%4d %4d Source %s.%s\n", comb_delay.maxDelay(), total, driver_cell->name.c_str(ctx), - driver.port.c_str(ctx)); + log_info("%4.1f %4.1f Source %s.%s\n", ctx->getDelayNS(comb_delay.maxDelay()), ctx->getDelayNS(total), + driver_cell->name.c_str(ctx), driver.port.c_str(ctx)); auto net_delay = ctx->getNetinfoRouteDelay(net, *sink); 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("%4.1f %4.1f Net %s budget %f ns (%d,%d) -> (%d,%d)\n", ctx->getDelayNS(net_delay), + ctx->getDelayNS(total), net->name.c_str(ctx), ctx->getDelayNS(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; } @@ -403,8 +406,8 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_path) } } - delay_t default_slack = delay_t(1.0e12 / ctx->target_freq); - log_info("estimated Fmax = %.2f MHz\n", 1e6 / (default_slack - min_slack)); + delay_t default_slack = delay_t((1.0e9 / ctx->getDelayNS(1)) / ctx->target_freq); + log_info("estimated Fmax = %.2f MHz\n", 1e3 / ctx->getDelayNS(default_slack - min_slack)); if (print_histogram && slack_histogram.size() > 0) { constexpr unsigned num_bins = 20; -- cgit v1.2.3 From 3e11ba8afb332909ee40760a222b2d2b56bc3232 Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 8 Aug 2018 17:55:54 +0200 Subject: timing: Remove unused variable Signed-off-by: David Shah --- common/timing.cc | 1 - 1 file changed, 1 deletion(-) (limited to 'common/timing.cc') diff --git a/common/timing.cc b/common/timing.cc index 601311a8..aadd8381 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -131,7 +131,6 @@ struct Timing const auto net = queue.front(); queue.pop_front(); - DelayInfo clkToQ; for (auto &usr : net->users) { IdString clockPort; TimingPortClass usrClass = ctx->getPortTimingClass(usr.cell, usr.port, clockPort); -- cgit v1.2.3