placer1: Add routeability optimisation (off by default)

Signed-off-by: David Shah <dave@ds0.me>

2 files changed, 89 insertions, 3 deletions

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<double>(last_timing_cost, epsilon)) +
                 (1 - lambda) * (double(moveChange.wirelen_delta) / std::max<double>(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<double>(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<std::pair<CellInfo *, BelId>> moves_made;
         std::vector<std::pair<CellInfo *, BelId>> 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<double>(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<std::vector<std::unordered_map<IdString, int>>> nets_by_tile;
+    void setup_nets_by_tile()
+    {
+        total_net_share = 0;
+        nets_by_tile.resize(max_x + 1, std::vector<std::unordered_map<IdString, int>>(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<BoundingBox> net_bounds;
@@ -1144,6 +1229,7 @@ class SAPlacer
 Placer1Cfg::Placer1Cfg(Context *ctx)
 {
     constraintWeight = ctx->setting<float>("placer1/constraintWeight", 10);
+    netShareWeight = ctx->setting<float>("placer1/netShareWeight", 0);
     minBelsForGridPick = ctx->setting<int>("placer1/minBelsForGridPick", 64);
     budgetBased = ctx->setting<bool>("placer1/budgetBased", false);
     startTemp = ctx->setting<float>("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;