From 2c7d2f9e0c850590f306139a4eaa9135b0f2a254 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 2 Feb 2020 16:01:40 +0000 Subject: placer1: Add routeability optimisation (off by default) Signed-off-by: David Shah --- common/placer1.cc | 90 +++++++++++++++++++++++++++++++++++++++++++++++++++++-- common/placer1.h | 2 +- 2 files changed, 89 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/placer1.cc b/common/placer1.cc index 9c1eaba4..1ba50e28 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -259,6 +259,9 @@ class SAPlacer last_wirelen_cost = curr_wirelen_cost; last_timing_cost = curr_timing_cost; + if (cfg.netShareWeight > 0) + setup_nets_by_tile(); + wirelen_t avg_wirelen = curr_wirelen_cost; wirelen_t min_wirelen = curr_wirelen_cost; @@ -513,6 +516,11 @@ class SAPlacer if (other_cell != nullptr) old_dist += get_constraints_distance(ctx, other_cell); double delta = 0; + + int net_delta_score = 0; + if (cfg.netShareWeight > 0) + net_delta_score += update_nets_by_tile(cell, ctx->getBelLocation(cell->bel), ctx->getBelLocation(newBel)); + ctx->unbindBel(oldBel); if (other_cell != nullptr) { ctx->unbindBel(newBel); @@ -522,6 +530,9 @@ class SAPlacer if (other_cell != nullptr) { ctx->bindBel(oldBel, other_cell, STRENGTH_WEAK); + if (cfg.netShareWeight > 0) + net_delta_score += + update_nets_by_tile(other_cell, ctx->getBelLocation(newBel), ctx->getBelLocation(oldBel)); } add_move_cell(moveChange, cell, oldBel); @@ -546,6 +557,8 @@ class SAPlacer delta = lambda * (moveChange.timing_delta / std::max(last_timing_cost, epsilon)) + (1 - lambda) * (double(moveChange.wirelen_delta) / std::max(last_wirelen_cost, epsilon)); delta += (cfg.constraintWeight / temp) * (new_dist - old_dist) / last_wirelen_cost; + if (cfg.netShareWeight > 0) + delta += -cfg.netShareWeight * (net_delta_score / std::max(total_net_share, epsilon)); n_move++; // SA acceptance criterea if (delta < 0 || (temp > 1e-8 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { @@ -567,7 +580,11 @@ class SAPlacer ctx->bindBel(oldBel, cell, STRENGTH_WEAK); if (other_cell != nullptr) { ctx->bindBel(newBel, other_cell, STRENGTH_WEAK); + if (cfg.netShareWeight > 0) + update_nets_by_tile(other_cell, ctx->getBelLocation(oldBel), ctx->getBelLocation(newBel)); } + if (cfg.netShareWeight > 0) + update_nets_by_tile(cell, ctx->getBelLocation(newBel), ctx->getBelLocation(oldBel)); return false; } @@ -588,8 +605,13 @@ class SAPlacer ctx->unbindBel(newBel); ctx->unbindBel(oldBel); ctx->bindBel(newBel, cell, is_constrained(cell) ? STRENGTH_STRONG : STRENGTH_WEAK); - if (bound != nullptr) + if (bound != nullptr) { ctx->bindBel(oldBel, bound, is_constrained(bound) ? STRENGTH_STRONG : STRENGTH_WEAK); + if (cfg.netShareWeight > 0) + update_nets_by_tile(bound, ctx->getBelLocation(newBel), ctx->getBelLocation(oldBel)); + } + if (cfg.netShareWeight > 0) + update_nets_by_tile(cell, ctx->getBelLocation(oldBel), ctx->getBelLocation(newBel)); return oldBel; } @@ -611,6 +633,7 @@ class SAPlacer std::vector> moves_made; std::vector> dest_bels; double delta = 0; + int orig_share_cost = total_net_share; moveChange.reset(this); #if 0 if (ctx->debug) @@ -663,6 +686,10 @@ class SAPlacer compute_cost_changes(moveChange); delta = lambda * (moveChange.timing_delta / last_timing_cost) + (1 - lambda) * (double(moveChange.wirelen_delta) / last_wirelen_cost); + if (cfg.netShareWeight > 0) { + delta += + cfg.netShareWeight * (orig_share_cost - total_net_share) / std::max(total_net_share, 1e-20); + } n_move++; // SA acceptance criterea if (delta < 0 || (temp > 1e-9 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { @@ -1105,8 +1132,66 @@ class SAPlacer } } + // Simple routeability driven placement + const int large_cell_thresh = 50; + int total_net_share = 0; + std::vector>> nets_by_tile; + void setup_nets_by_tile() + { + total_net_share = 0; + nets_by_tile.resize(max_x + 1, std::vector>(max_y + 1)); + for (auto cell : sorted(ctx->cells)) { + CellInfo *ci = cell.second; + if (int(ci->ports.size()) > large_cell_thresh) + continue; + Loc loc = ctx->getBelLocation(ci->bel); + auto &nbt = nets_by_tile.at(loc.x).at(loc.y); + for (const auto &port : ci->ports) { + if (port.second.net == nullptr) + continue; + if (port.second.net->driver.cell == nullptr || ctx->getBelGlobalBuf(port.second.net->driver.cell->bel)) + continue; + int &s = nbt[port.second.net->name]; + if (s > 0) + ++total_net_share; + ++s; + } + } + } + + int update_nets_by_tile(CellInfo *ci, Loc old_loc, Loc new_loc) + { + if (int(ci->ports.size()) > large_cell_thresh) + return 0; + int loss = 0, gain = 0; + auto &nbt_old = nets_by_tile.at(old_loc.x).at(old_loc.y); + auto &nbt_new = nets_by_tile.at(new_loc.x).at(new_loc.y); + + for (const auto &port : ci->ports) { + if (port.second.net == nullptr) + continue; + if (port.second.net->driver.cell == nullptr || ctx->getBelGlobalBuf(port.second.net->driver.cell->bel)) + continue; + int &o = nbt_old[port.second.net->name]; + --o; + NPNR_ASSERT(o >= 0); + if (o > 0) + ++loss; + int &n = nbt_new[port.second.net->name]; + if (n > 0) + ++gain; + ++n; + } + int delta = gain - loss; + total_net_share += delta; + return delta; + } + // Get the combined wirelen/timing metric - inline double curr_metric() { return lambda * curr_timing_cost + (1 - lambda) * curr_wirelen_cost; } + inline double curr_metric() + { + return lambda * curr_timing_cost + (1 - lambda) * curr_wirelen_cost - cfg.netShareWeight * total_net_share; + } // Map nets to their bounding box (so we can skip recompute for moves that do not exceed the bounds std::vector net_bounds; @@ -1144,6 +1229,7 @@ class SAPlacer Placer1Cfg::Placer1Cfg(Context *ctx) { constraintWeight = ctx->setting("placer1/constraintWeight", 10); + netShareWeight = ctx->setting("placer1/netShareWeight", 0); minBelsForGridPick = ctx->setting("placer1/minBelsForGridPick", 64); budgetBased = ctx->setting("placer1/budgetBased", false); startTemp = ctx->setting("placer1/startTemp", 1); diff --git a/common/placer1.h b/common/placer1.h index e803d592..cf66151c 100644 --- a/common/placer1.h +++ b/common/placer1.h @@ -27,7 +27,7 @@ NEXTPNR_NAMESPACE_BEGIN struct Placer1Cfg { Placer1Cfg(Context *ctx); - float constraintWeight; + float constraintWeight, netShareWeight; int minBelsForGridPick; bool budgetBased; float startTemp; -- cgit v1.2.3