aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--common/timing.cc171
-rw-r--r--ecp5/arch.cc2
-rw-r--r--ecp5/arch.h2
-rw-r--r--generic/arch.cc2
-rw-r--r--generic/arch.h2
-rw-r--r--ice40/arch.cc10
-rw-r--r--ice40/arch.h2
7 files changed, 176 insertions, 15 deletions
diff --git a/common/timing.cc b/common/timing.cc
index ae5783cd..69fdd29f 100644
--- a/common/timing.cc
+++ b/common/timing.cc
@@ -23,6 +23,7 @@
#include <utility>
#include "log.h"
#include "util.h"
+#include <boost/range/adaptor/reversed.hpp>
NEXTPNR_NAMESPACE_BEGIN
@@ -39,6 +40,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 net_delays, bool update, PortRefVector *crit_path = nullptr,
DelayFrequency *slack_histogram = nullptr)
: ctx(ctx), net_delays(net_delays), update(update), min_slack(1.0e12 / ctx->target_freq),
@@ -55,8 +64,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);
}
@@ -111,16 +120,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();
@@ -130,16 +140,165 @@ struct Timing
}
}
}
+
+#else
+ std::vector<NetInfo*> topographical_order;
+ std::unordered_map<const PortInfo*, unsigned> port_fanin;
+ std::unordered_map<const NetInfo*, TimingData> net_data;
+
+ std::vector<IdString> input_ports;
+ std::vector<const PortInfo*> 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<NetInfo*> 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<delay_t>::max();
}
}
diff --git a/ecp5/arch.cc b/ecp5/arch.cc
index d72b0085..d2d62241 100644
--- a/ecp5/arch.cc
+++ b/ecp5/arch.cc
@@ -422,7 +422,7 @@ delay_t Arch::predictDelay(const NetInfo *net_info, const PortRef &sink) const
return 200 * (abs(driver_loc.x - sink_loc.x) + abs(driver_loc.y - sink_loc.y));
}
-delay_t Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t budget) const { return budget; }
+bool Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t &budget) const { return false; }
// -----------------------------------------------------------------------
diff --git a/ecp5/arch.h b/ecp5/arch.h
index 74f0c4e1..e00e111a 100644
--- a/ecp5/arch.h
+++ b/ecp5/arch.h
@@ -805,7 +805,7 @@ struct Arch : BaseCtx
delay_t getRipupDelayPenalty() const { return 200; }
float getDelayNS(delay_t v) const { return v * 0.001; }
uint32_t getDelayChecksum(delay_t v) const { return v; }
- delay_t getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t budget) const;
+ bool getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t &budget) const;
// -------------------------------------------------
diff --git a/generic/arch.cc b/generic/arch.cc
index 7e65d411..0fa93da8 100644
--- a/generic/arch.cc
+++ b/generic/arch.cc
@@ -408,7 +408,7 @@ delay_t Arch::predictDelay(const NetInfo *net_info, const PortRef &sink) const
return (dx + dy) * grid_distance_to_delay;
}
-delay_t Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t budget) const { return budget; }
+bool Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t &budget) const { return false; }
// ---------------------------------------------------------------
diff --git a/generic/arch.h b/generic/arch.h
index a5b3470f..59fe8d05 100644
--- a/generic/arch.h
+++ b/generic/arch.h
@@ -200,7 +200,7 @@ struct Arch : BaseCtx
delay_t getRipupDelayPenalty() const { return 1.0; }
float getDelayNS(delay_t v) const { return v; }
uint32_t getDelayChecksum(delay_t v) const { return 0; }
- delay_t getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t budget) const;
+ bool getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t &budget) const;
bool pack() { return true; }
bool place();
diff --git a/ice40/arch.cc b/ice40/arch.cc
index 0b168383..b8bb13ea 100644
--- a/ice40/arch.cc
+++ b/ice40/arch.cc
@@ -637,17 +637,19 @@ std::vector<GroupId> Arch::getGroupGroups(GroupId group) const
// -----------------------------------------------------------------------
-delay_t Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t budget) const
+bool Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t &budget) const
{
const auto &driver = net_info->driver;
if (driver.port == id_cout) {
auto driver_loc = getBelLocation(driver.cell->bel);
auto sink_loc = getBelLocation(sink.cell->bel);
if (driver_loc.y == sink_loc.y)
- return 0;
- return 250;
+ budget = 0;
+ else
+ budget = 190;
+ return true;
}
- return budget;
+ return false;
}
// -----------------------------------------------------------------------
diff --git a/ice40/arch.h b/ice40/arch.h
index 236f73f1..328950df 100644
--- a/ice40/arch.h
+++ b/ice40/arch.h
@@ -766,7 +766,7 @@ struct Arch : BaseCtx
delay_t getRipupDelayPenalty() const { return 200; }
float getDelayNS(delay_t v) const { return v * 0.001; }
uint32_t getDelayChecksum(delay_t v) const { return v; }
- delay_t getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t budget) const;
+ bool getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t &budget) const;
// -------------------------------------------------
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-27 09:58:13 +0000