aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorgatecat <gatecat@ds0.me>2022-04-19 19:09:29 +0100
committerGitHub <noreply@github.com>2022-04-19 19:09:29 +0100
commitb8f9f2daa2942395f15e33bcf6700e6f67667675 (patch)
tree39853fb89ccf67652ea2073fe82d0b5ac2135d21
parentd76a6093ae68d094d6fbf4f1f2c4e7f69f0818d2 (diff)
parent19cade3b3b84ac7bfa07aa9eb8f47866dcd52d4e (diff)
downloadnextpnr-b8f9f2daa2942395f15e33bcf6700e6f67667675.tar.gz
nextpnr-b8f9f2daa2942395f15e33bcf6700e6f67667675.tar.bz2
nextpnr-b8f9f2daa2942395f15e33bcf6700e6f67667675.zip
Merge pull request #977 from YosysHQ/gatecat/prefine-tileswap
prefine: Do full-tile swaps, too
-rw-r--r--common/place/detail_place_core.cc2
-rw-r--r--common/place/parallel_refine.cc99
2 files changed, 100 insertions, 1 deletions
diff --git a/common/place/detail_place_core.cc b/common/place/detail_place_core.cc
index bb383639..7e629f24 100644
--- a/common/place/detail_place_core.cc
+++ b/common/place/detail_place_core.cc
@@ -348,7 +348,7 @@ void DetailPlacerThreadState::compute_changes_for_cell(CellInfo *cell, BelId old
if (new_pos > b1) {
// Further out than current upper bound
b1 = new_pos;
- n1 = new_pos;
+ n1 = 1;
if (change == NO_CHANGE) {
change = CELL_MOVED_OUTWARDS;
axis.bounds_changed_nets.push_back(idx);
diff --git a/common/place/parallel_refine.cc b/common/place/parallel_refine.cc
index a2de5b13..de71b8e0 100644
--- a/common/place/parallel_refine.cc
+++ b/common/place/parallel_refine.cc
@@ -39,6 +39,8 @@ struct GlobalState : DetailPlacerState
{
explicit GlobalState(Context *ctx, ParallelRefineCfg cfg) : DetailPlacerState(ctx, this->cfg), cfg(cfg){};
+ dict<ClusterId, std::vector<CellInfo *>> cluster2cells;
+
ParallelRefineCfg cfg;
double temperature = 1e-7;
int radius = 3;
@@ -52,6 +54,8 @@ struct ThreadState : DetailPlacerThreadState
GlobalState &g;
int n_move = 0, n_accept = 0;
+ dict<std::pair<int, int>, std::vector<CellInfo *>> tile2cell;
+
bool accept_move()
{
static constexpr double epsilon = 1e-20;
@@ -218,6 +222,97 @@ struct ThreadState : DetailPlacerThreadState
}
}
+ bool cluster_inside_tile(ClusterId cluster, int x, int y)
+ {
+ for (auto &c : g.cluster2cells.at(cluster)) {
+ Loc l = ctx->getBelLocation(c->bel);
+ if (l.x != x || l.y != y)
+ return false;
+ }
+ return true;
+ }
+
+ bool do_tile_swap(int x, int y, int xn, int yn)
+ {
+ if (xn < p.x0 || xn > p.x1)
+ return false;
+ if (yn < p.y0 || yn > p.y1)
+ return false;
+ if ((x == xn) && (y == yn))
+ return false;
+
+ NPNR_ASSERT(moved_cells.empty());
+
+ auto move_tile = [&](int sx, int sy, int dx, int dy) -> bool {
+ for (auto c : tile2cell[std::make_pair(sx, sy)]) {
+ if (c->belStrength > STRENGTH_STRONG ||
+ ((c->cluster != ClusterId()) && !cluster_inside_tile(c->cluster, sx, sy)))
+ return false; // check clusters before we start moving stuff
+ }
+ for (auto c : tile2cell[std::make_pair(sx, sy)]) {
+ Loc l = ctx->getBelLocation(c->bel);
+ l.x = dx;
+ l.y = dy;
+ BelId new_bel = ctx->getBelByLocation(l);
+ if (new_bel == BelId() || !ctx->isValidBelForCellType(c->type, new_bel))
+ return false;
+ if (!add_to_move(c, c->bel, new_bel))
+ return false;
+ }
+ return true;
+ };
+
+ if (!move_tile(x, y, xn, yn))
+ goto fail;
+ if (!move_tile(xn, yn, x, y))
+ goto fail;
+
+ compute_total_change();
+ // SA acceptance criteria
+ if (!accept_move()) {
+ // SA fail
+ goto fail;
+ }
+ // Check validity rules
+ if (!bind_move())
+ goto fail;
+ if (!check_validity())
+ goto fail;
+ // Accepted!
+ commit_move();
+ reset_move_state();
+ std::swap(tile2cell[std::make_pair(x, y)], tile2cell[std::make_pair(xn, yn)]);
+ return true;
+ fail:
+ revert_move();
+ reset_move_state();
+ return false;
+ }
+
+ void do_tile_swaps()
+ {
+ tile2cell.clear();
+ for (auto c : p.cells) {
+ auto loc = ctx->getBelLocation(c->bel);
+ tile2cell[std::make_pair(loc.x, loc.y)].push_back(c);
+ }
+ std::vector<std::pair<int, int>> tiles;
+ for (auto &t : tile2cell)
+ tiles.push_back(t.first);
+ rng.shuffle(tiles);
+ for (auto &t : tiles) {
+ int x = t.first, y = t.second;
+ int lx = std::max(x - g.radius, p.x0), rx = std::min(x + g.radius, p.x1);
+ int by = std::max(y - g.radius, p.y0), ty = std::min(y + g.radius, p.y1);
+ int xn = lx + ctx->rng((rx - lx) + 1);
+ int yn = by + ctx->rng((ty - by) + 1);
+ ++n_move;
+ if (do_tile_swap(x, y, xn, yn)) {
+ ++n_accept;
+ }
+ }
+ }
+
void run_iter()
{
setup_initial_state();
@@ -246,6 +341,8 @@ struct ThreadState : DetailPlacerThreadState
++n_accept;
}
}
+ if ((m % 2) == 0)
+ do_tile_swaps();
}
}
};
@@ -295,6 +392,8 @@ struct ParallelRefine
for (auto &cell : ctx->cells) {
IdString cell_type = cell.second->type;
cell_types_in_use.insert(cell_type);
+ if (cell.second->cluster != ClusterId())
+ g.cluster2cells[cell.second->cluster].push_back(cell.second.get());
}
for (auto cell_type : cell_types_in_use) {