aboutsummaryrefslogtreecommitdiffstats
path: root/common/placer1.cc
diff options
context:
space:
mode:
Diffstat (limited to 'common/placer1.cc')
-rw-r--r--common/placer1.cc981
1 files changed, 808 insertions, 173 deletions
diff --git a/common/placer1.cc b/common/placer1.cc
index cec37847..a8ddd8a6 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -24,6 +24,7 @@
#include "placer1.h"
#include <algorithm>
#include <boost/lexical_cast.hpp>
+#include <boost/range/adaptor/reversed.hpp>
#include <chrono>
#include <cmath>
#include <iostream>
@@ -43,10 +44,33 @@
#include "timing.h"
#include "util.h"
+namespace std {
+template <> struct hash<std::pair<NEXTPNR_NAMESPACE_PREFIX IdString, std::size_t>>
+{
+ std::size_t operator()(const std::pair<NEXTPNR_NAMESPACE_PREFIX IdString, std::size_t> &idp) const noexcept
+ {
+ std::size_t seed = 0;
+ boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(idp.first));
+ boost::hash_combine(seed, hash<std::size_t>()(idp.second));
+ return seed;
+ }
+};
+} // namespace std
+
NEXTPNR_NAMESPACE_BEGIN
class SAPlacer
{
+ private:
+ struct BoundingBox
+ {
+ // Actual bounding box
+ int x0 = 0, x1 = 0, y0 = 0, y1 = 0;
+ // Number of cells at each extremity
+ int nx0 = 0, nx1 = 0, ny0 = 0, ny1 = 0;
+ wirelen_t hpwl() const { return wirelen_t((x1 - x0) + (y1 - y0)); }
+ };
+
public:
SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), cfg(cfg)
{
@@ -78,13 +102,41 @@ class SAPlacer
}
diameter = std::max(max_x, max_y) + 1;
- costs.resize(ctx->nets.size());
+ net_bounds.resize(ctx->nets.size());
+ net_arc_tcost.resize(ctx->nets.size());
old_udata.reserve(ctx->nets.size());
+ net_by_udata.reserve(ctx->nets.size());
decltype(NetInfo::udata) n = 0;
for (auto &net : ctx->nets) {
old_udata.emplace_back(net.second->udata);
+ net_arc_tcost.at(n).resize(net.second->users.size());
net.second->udata = n++;
+ net_by_udata.push_back(net.second.get());
}
+ for (auto &region : sorted(ctx->region)) {
+ Region *r = region.second;
+ BoundingBox bb;
+ if (r->constr_bels) {
+ bb.x0 = std::numeric_limits<int>::max();
+ bb.x1 = std::numeric_limits<int>::min();
+ bb.y0 = std::numeric_limits<int>::max();
+ bb.y1 = std::numeric_limits<int>::min();
+ for (auto bel : r->bels) {
+ Loc loc = ctx->getBelLocation(bel);
+ bb.x0 = std::min(bb.x0, loc.x);
+ bb.x1 = std::max(bb.x1, loc.x);
+ bb.y0 = std::min(bb.y0, loc.y);
+ bb.y1 = std::max(bb.y1, loc.y);
+ }
+ } else {
+ bb.x0 = 0;
+ bb.y0 = 0;
+ bb.x1 = max_x;
+ bb.y1 = max_y;
+ }
+ region_bounds[r->name] = bb;
+ }
+ build_port_index();
}
~SAPlacer()
@@ -93,97 +145,122 @@ class SAPlacer
net.second->udata = old_udata[net.second->udata];
}
- bool place()
+ bool place(bool refine = false)
{
log_break();
ctx->lock();
size_t placed_cells = 0;
- // Initial constraints placer
- for (auto &cell_entry : ctx->cells) {
- CellInfo *cell = cell_entry.second.get();
- auto loc = cell->attrs.find(ctx->id("BEL"));
- if (loc != cell->attrs.end()) {
- std::string loc_name = loc->second;
- BelId bel = ctx->getBelByName(ctx->id(loc_name));
- if (bel == BelId()) {
- log_error("No Bel named \'%s\' located for "
- "this chip (processing BEL attribute on \'%s\')\n",
- loc_name.c_str(), cell->name.c_str(ctx));
- }
+ std::vector<CellInfo *> autoplaced;
+ std::vector<CellInfo *> chain_basis;
+ if (!refine) {
+ // Initial constraints placer
+ for (auto &cell_entry : ctx->cells) {
+ CellInfo *cell = cell_entry.second.get();
+ auto loc = cell->attrs.find(ctx->id("BEL"));
+ if (loc != cell->attrs.end()) {
+ std::string loc_name = loc->second;
+ BelId bel = ctx->getBelByName(ctx->id(loc_name));
+ if (bel == BelId()) {
+ log_error("No Bel named \'%s\' located for "
+ "this chip (processing BEL attribute on \'%s\')\n",
+ loc_name.c_str(), cell->name.c_str(ctx));
+ }
- IdString bel_type = ctx->getBelType(bel);
- if (bel_type != cell->type) {
- log_error("Bel \'%s\' of type \'%s\' does not match cell "
- "\'%s\' of type \'%s\'\n",
- loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
- }
- if (!ctx->isValidBelForCell(cell, bel)) {
- log_error("Bel \'%s\' of type \'%s\' is not valid for cell "
- "\'%s\' of type \'%s\'\n",
- loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
- }
+ IdString bel_type = ctx->getBelType(bel);
+ if (bel_type != cell->type) {
+ log_error("Bel \'%s\' of type \'%s\' does not match cell "
+ "\'%s\' of type \'%s\'\n",
+ loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
+ }
+ if (!ctx->isValidBelForCell(cell, bel)) {
+ log_error("Bel \'%s\' of type \'%s\' is not valid for cell "
+ "\'%s\' of type \'%s\'\n",
+ loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
+ }
- auto bound_cell = ctx->getBoundBelCell(bel);
- if (bound_cell) {
- log_error("Cell \'%s\' cannot be bound to bel \'%s\' since it is already bound to cell \'%s\'\n",
- cell->name.c_str(ctx), loc_name.c_str(), bound_cell->name.c_str(ctx));
- }
+ auto bound_cell = ctx->getBoundBelCell(bel);
+ if (bound_cell) {
+ log_error(
+ "Cell \'%s\' cannot be bound to bel \'%s\' since it is already bound to cell \'%s\'\n",
+ cell->name.c_str(ctx), loc_name.c_str(), bound_cell->name.c_str(ctx));
+ }
- ctx->bindBel(bel, cell, STRENGTH_USER);
- locked_bels.insert(bel);
- placed_cells++;
+ ctx->bindBel(bel, cell, STRENGTH_USER);
+ locked_bels.insert(bel);
+ placed_cells++;
+ }
}
- }
- int constr_placed_cells = placed_cells;
- log_info("Placed %d cells based on constraints.\n", int(placed_cells));
- ctx->yield();
+ int constr_placed_cells = placed_cells;
+ log_info("Placed %d cells based on constraints.\n", int(placed_cells));
+ ctx->yield();
- // Sort to-place cells for deterministic initial placement
- std::vector<CellInfo *> autoplaced;
- for (auto &cell : ctx->cells) {
- CellInfo *ci = cell.second.get();
- if (ci->bel == BelId()) {
- autoplaced.push_back(cell.second.get());
+ // Sort to-place cells for deterministic initial placement
+
+ for (auto &cell : ctx->cells) {
+ CellInfo *ci = cell.second.get();
+ if (ci->bel == BelId()) {
+ autoplaced.push_back(cell.second.get());
+ }
}
- }
- std::sort(autoplaced.begin(), autoplaced.end(), [](CellInfo *a, CellInfo *b) { return a->name < b->name; });
- ctx->shuffle(autoplaced);
- auto iplace_start = std::chrono::high_resolution_clock::now();
- // Place cells randomly initially
- log_info("Creating initial placement for remaining %d cells.\n", int(autoplaced.size()));
+ std::sort(autoplaced.begin(), autoplaced.end(), [](CellInfo *a, CellInfo *b) { return a->name < b->name; });
+ ctx->shuffle(autoplaced);
+ auto iplace_start = std::chrono::high_resolution_clock::now();
+ // Place cells randomly initially
+ log_info("Creating initial placement for remaining %d cells.\n", int(autoplaced.size()));
- for (auto cell : autoplaced) {
- place_initial(cell);
- placed_cells++;
- if ((placed_cells - constr_placed_cells) % 500 == 0)
+ for (auto cell : autoplaced) {
+ place_initial(cell);
+ placed_cells++;
+ if ((placed_cells - constr_placed_cells) % 500 == 0)
+ log_info(" initial placement placed %d/%d cells\n", int(placed_cells - constr_placed_cells),
+ int(autoplaced.size()));
+ }
+ if ((placed_cells - constr_placed_cells) % 500 != 0)
log_info(" initial placement placed %d/%d cells\n", int(placed_cells - constr_placed_cells),
int(autoplaced.size()));
+ if (cfg.budgetBased && ctx->slack_redist_iter > 0)
+ assign_budget(ctx);
+ ctx->yield();
+ auto iplace_end = std::chrono::high_resolution_clock::now();
+ log_info("Initial placement time %.02fs\n",
+ std::chrono::duration<float>(iplace_end - iplace_start).count());
+ log_info("Running simulated annealing placer.\n");
+ } else {
+ for (auto &cell : ctx->cells) {
+ CellInfo *ci = cell.second.get();
+ if (ci->belStrength > STRENGTH_STRONG)
+ continue;
+ else if (ci->constr_parent != nullptr)
+ continue;
+ else if (!ci->constr_children.empty() || ci->constr_z != ci->UNCONSTR)
+ chain_basis.push_back(ci);
+ else
+ autoplaced.push_back(ci);
+ }
+ require_legal = false;
+ diameter = 3;
+ log_info("Running simulated annealing placer for refinement.\n");
}
- if ((placed_cells - constr_placed_cells) % 500 != 0)
- log_info(" initial placement placed %d/%d cells\n", int(placed_cells - constr_placed_cells),
- int(autoplaced.size()));
- if (ctx->slack_redist_iter > 0)
- assign_budget(ctx);
- ctx->yield();
- auto iplace_end = std::chrono::high_resolution_clock::now();
- log_info("Initial placement time %.02fs\n", std::chrono::duration<float>(iplace_end - iplace_start).count());
auto saplace_start = std::chrono::high_resolution_clock::now();
- log_info("Running simulated annealing placer.\n");
- // Calculate metric after initial placement
- curr_metric = 0;
- curr_tns = 0;
- for (auto &net : ctx->nets) {
- wirelen_t wl = get_net_metric(ctx, net.second.get(), MetricType::COST, curr_tns);
- costs[net.second->udata] = CostChange{wl, -1};
- curr_metric += wl;
- }
+ // Invoke timing analysis to obtain criticalities
+ if (!cfg.budgetBased)
+ get_criticalities(ctx, &net_crit);
+
+ // Calculate costs after initial placement
+ setup_costs();
+ moveChange.init(this);
+ curr_wirelen_cost = total_wirelen_cost();
+ curr_timing_cost = total_timing_cost();
+ last_wirelen_cost = curr_wirelen_cost;
+ last_timing_cost = curr_timing_cost;
+
+ wirelen_t avg_wirelen = curr_wirelen_cost;
+ wirelen_t min_wirelen = curr_wirelen_cost;
int n_no_progress = 0;
- wirelen_t min_metric = curr_metric;
- double avg_metric = curr_metric;
- temp = 10000;
+ temp = refine ? 1e-7 : cfg.startTemp;
// Main simulated annealing loop
for (int iter = 1;; iter++) {
@@ -191,9 +268,9 @@ class SAPlacer
improved = false;
if (iter % 5 == 0 || iter == 1)
- log_info(" at iteration #%d: temp = %f, cost = "
- "%.0f, est tns = %.02fns\n",
- iter, temp, double(curr_metric), curr_tns);
+ log_info(" at iteration #%d: temp = %f, timing cost = "
+ "%.0f, wirelen = %.0f\n",
+ iter, temp, double(curr_timing_cost), double(curr_wirelen_cost));
for (int m = 0; m < 15; ++m) {
// Loop through all automatically placed cells
@@ -205,10 +282,35 @@ class SAPlacer
if (try_bel != BelId() && try_bel != cell->bel)
try_swap_position(cell, try_bel);
}
+ // Also try swapping chains, if applicable
+ for (auto cb : chain_basis) {
+ Loc chain_base_loc = ctx->getBelLocation(cb->bel);
+ BelId try_base = random_bel_for_cell(cb, chain_base_loc.z);
+ if (try_base != BelId() && try_base != cb->bel)
+ try_swap_chain(cb, try_base);
+ }
+ }
+
+ if (ctx->debug) {
+ // Verify correctness of incremental wirelen updates
+ for (size_t i = 0; i < net_bounds.size(); i++) {
+ auto net = net_by_udata[i];
+ if (ignore_net(net))
+ continue;
+ auto &incr = net_bounds.at(i), gold = get_net_bounds(net);
+ NPNR_ASSERT(incr.x0 == gold.x0);
+ NPNR_ASSERT(incr.x1 == gold.x1);
+ NPNR_ASSERT(incr.y0 == gold.y0);
+ NPNR_ASSERT(incr.y1 == gold.y1);
+ NPNR_ASSERT(incr.nx0 == gold.nx0);
+ NPNR_ASSERT(incr.nx1 == gold.nx1);
+ NPNR_ASSERT(incr.ny0 == gold.ny0);
+ NPNR_ASSERT(incr.ny1 == gold.ny1);
+ }
}
- if (curr_metric < min_metric) {
- min_metric = curr_metric;
+ if (curr_wirelen_cost < min_wirelen) {
+ min_wirelen = curr_wirelen_cost;
improved = true;
}
@@ -218,9 +320,10 @@ class SAPlacer
else
n_no_progress++;
- if (temp <= 1e-3 && n_no_progress >= 5) {
- if (iter % 5 != 0)
- log_info(" at iteration #%d: temp = %f, cost = %f\n", iter, temp, double(curr_metric));
+ if (temp <= 1e-7 && n_no_progress >= (refine ? 1 : 5)) {
+ log_info(" at iteration #%d: temp = %f, timing cost = "
+ "%.0f, wirelen = %.0f \n",
+ iter, temp, double(curr_timing_cost), double(curr_wirelen_cost));
break;
}
@@ -228,61 +331,68 @@ class SAPlacer
int M = std::max(max_x, max_y) + 1;
- double upper = 0.6, lower = 0.4;
+ if (ctx->verbose)
+ log("iter #%d: temp = %f, timing cost = "
+ "%.0f, wirelen = %.0f, dia = %d, Ra = %.02f \n",
+ iter, temp, double(curr_timing_cost), double(curr_wirelen_cost), diameter, Raccept);
- if (curr_metric < 0.95 * avg_metric) {
- avg_metric = 0.8 * avg_metric + 0.2 * curr_metric;
+ if (curr_wirelen_cost < 0.95 * avg_wirelen && curr_wirelen_cost > 0) {
+ avg_wirelen = 0.8 * avg_wirelen + 0.2 * curr_wirelen_cost;
} else {
- if (Raccept >= 0.8) {
- temp *= 0.7;
- } else if (Raccept > upper) {
- if (diameter < M)
- diameter++;
- else
- temp *= 0.9;
- } else if (Raccept > lower) {
+ double diam_next = diameter * (1.0 - 0.44 + Raccept);
+ diameter = std::max<int>(1, std::min<int>(M, int(diam_next + 0.5)));
+ if (Raccept > 0.96) {
+ temp *= 0.5;
+ } else if (Raccept > 0.8) {
+ temp *= 0.9;
+ } else if (Raccept > 0.15 && diameter > 1) {
temp *= 0.95;
} else {
- // Raccept < 0.3
- if (diameter > 1)
- diameter--;
- else
- temp *= 0.8;
+ temp *= 0.8;
}
}
// Once cooled below legalise threshold, run legalisation and start requiring
// legal moves only
- if (temp < legalise_temp && require_legal) {
+ if (diameter < legalise_dia && require_legal) {
if (legalise_relative_constraints(ctx)) {
// Only increase temperature if something was moved
autoplaced.clear();
+ chain_basis.clear();
for (auto cell : sorted(ctx->cells)) {
- if (cell.second->belStrength < STRENGTH_STRONG)
+ if (cell.second->belStrength <= STRENGTH_STRONG && cell.second->constr_parent == nullptr &&
+ !cell.second->constr_children.empty())
+ chain_basis.push_back(cell.second);
+ else if (cell.second->belStrength < STRENGTH_STRONG)
autoplaced.push_back(cell.second);
}
- temp = post_legalise_temp;
- diameter *= post_legalise_dia_scale;
+ // temp = post_legalise_temp;
+ // diameter = std::min<int>(M, diameter * post_legalise_dia_scale);
ctx->shuffle(autoplaced);
// Legalisation is a big change so force a slack redistribution here
- if (ctx->slack_redist_iter > 0)
+ if (ctx->slack_redist_iter > 0 && cfg.budgetBased)
assign_budget(ctx, true /* quiet */);
}
require_legal = false;
- } else if (ctx->slack_redist_iter > 0 && iter % ctx->slack_redist_iter == 0) {
+ } else if (cfg.budgetBased && ctx->slack_redist_iter > 0 && iter % ctx->slack_redist_iter == 0) {
assign_budget(ctx, true /* quiet */);
}
+ // Invoke timing analysis to obtain criticalities
+ if (!cfg.budgetBased && ctx->timing_driven)
+ get_criticalities(ctx, &net_crit);
+ // Need to rebuild costs after criticalities change
+ setup_costs();
+ // Reset incremental bounds
+ moveChange.reset(this);
+ moveChange.new_net_bounds = net_bounds;
+
// Recalculate total metric entirely to avoid rounding errors
// accumulating over time
- curr_metric = 0;
- curr_tns = 0;
- for (auto &net : ctx->nets) {
- wirelen_t wl = get_net_metric(ctx, net.second.get(), MetricType::COST, curr_tns);
- costs[net.second->udata] = CostChange{wl, -1};
- curr_metric += wl;
- }
-
+ curr_wirelen_cost = total_wirelen_cost();
+ curr_timing_cost = total_timing_cost();
+ last_wirelen_cost = curr_wirelen_cost;
+ last_timing_cost = curr_timing_cost;
// Let the UI show visualization updates.
ctx->yield();
}
@@ -334,7 +444,8 @@ class SAPlacer
ctx->unbindBel(cell->bel);
}
IdString targetType = cell->type;
- for (auto bel : ctx->getBels()) {
+
+ auto proc_bel = [&](BelId bel) {
if (ctx->getBelType(bel) == targetType && ctx->isValidBelForCell(cell, bel)) {
if (ctx->checkBelAvail(bel)) {
uint64_t score = ctx->rng64();
@@ -352,7 +463,18 @@ class SAPlacer
}
}
}
+ };
+
+ if (cell->region != nullptr && cell->region->constr_bels) {
+ for (auto bel : cell->region->bels) {
+ proc_bel(bel);
+ }
+ } else {
+ for (auto bel : ctx->getBels()) {
+ proc_bel(bel);
+ }
}
+
if (best_bel == BelId()) {
if (iters == 0 || ripup_bel == BelId())
log_error("failed to place cell '%s' of type '%s'\n", cell->name.c_str(ctx), cell->type.c_str(ctx));
@@ -373,49 +495,38 @@ class SAPlacer
// Attempt a SA position swap, return true on success or false on failure
bool try_swap_position(CellInfo *cell, BelId newBel)
{
- static std::vector<NetInfo *> updates;
- updates.clear();
+ static const double epsilon = 1e-20;
+ moveChange.reset(this);
+ if (!require_legal && is_constrained(cell))
+ return false;
BelId oldBel = cell->bel;
CellInfo *other_cell = ctx->getBoundBelCell(newBel);
- if (other_cell != nullptr && other_cell->belStrength > STRENGTH_WEAK) {
+ if (!require_legal && other_cell != nullptr &&
+ (is_constrained(other_cell) || other_cell->belStrength > STRENGTH_WEAK)) {
return false;
}
int old_dist = get_constraints_distance(ctx, cell);
int new_dist;
if (other_cell != nullptr)
old_dist += get_constraints_distance(ctx, other_cell);
- wirelen_t new_metric = 0, delta;
+ double delta = 0;
ctx->unbindBel(oldBel);
if (other_cell != nullptr) {
ctx->unbindBel(newBel);
}
- for (const auto &port : cell->ports) {
- if (port.second.net != nullptr) {
- auto &cost = costs[port.second.net->udata];
- if (cost.new_cost == 0)
- continue;
- cost.new_cost = 0;
- updates.emplace_back(port.second.net);
- }
- }
+ ctx->bindBel(newBel, cell, STRENGTH_WEAK);
if (other_cell != nullptr) {
- for (const auto &port : other_cell->ports)
- if (port.second.net != nullptr) {
- auto &cost = costs[port.second.net->udata];
- if (cost.new_cost == 0)
- continue;
- cost.new_cost = 0;
- updates.emplace_back(port.second.net);
- }
+ ctx->bindBel(oldBel, other_cell, STRENGTH_WEAK);
}
- ctx->bindBel(newBel, cell, STRENGTH_WEAK);
+ add_move_cell(moveChange, cell, oldBel);
if (other_cell != nullptr) {
- ctx->bindBel(oldBel, other_cell, STRENGTH_WEAK);
+ add_move_cell(moveChange, other_cell, newBel);
}
+
if (!ctx->isBelLocationValid(newBel) || ((other_cell != nullptr && !ctx->isBelLocationValid(oldBel)))) {
ctx->unbindBel(newBel);
if (other_cell != nullptr)
@@ -423,26 +534,18 @@ class SAPlacer
goto swap_fail;
}
- new_metric = curr_metric;
-
// Recalculate metrics for all nets touched by the peturbation
- for (const auto &net : updates) {
- auto &c = costs[net->udata];
- new_metric -= c.curr_cost;
- float temp_tns = 0;
- wirelen_t net_new_wl = get_net_metric(ctx, net, MetricType::COST, temp_tns);
- new_metric += net_new_wl;
- c.new_cost = net_new_wl;
- }
+ compute_cost_changes(moveChange);
new_dist = get_constraints_distance(ctx, cell);
if (other_cell != nullptr)
new_dist += get_constraints_distance(ctx, other_cell);
- delta = new_metric - curr_metric;
- delta += (cfg.constraintWeight / temp) * (new_dist - old_dist);
+ 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;
n_move++;
// SA acceptance criterea
- if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) {
+ if (delta < 0 || (temp > 1e-8 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) {
n_accept++;
} else {
if (other_cell != nullptr)
@@ -450,32 +553,149 @@ class SAPlacer
ctx->unbindBel(newBel);
goto swap_fail;
}
- curr_metric = new_metric;
- for (const auto &net : updates) {
- auto &c = costs[net->udata];
- c = CostChange{c.new_cost, -1};
- }
-
+ commit_cost_changes(moveChange);
+#if 0
+ log_info("swap %s -> %s\n", cell->name.c_str(ctx), ctx->getBelName(newBel).c_str(ctx));
+ if (other_cell != nullptr)
+ log_info("swap %s -> %s\n", other_cell->name.c_str(ctx), ctx->getBelName(oldBel).c_str(ctx));
+#endif
return true;
swap_fail:
ctx->bindBel(oldBel, cell, STRENGTH_WEAK);
if (other_cell != nullptr) {
ctx->bindBel(newBel, other_cell, STRENGTH_WEAK);
}
- for (const auto &net : updates)
- costs[net->udata].new_cost = -1;
+ return false;
+ }
+
+ inline bool is_constrained(CellInfo *cell)
+ {
+ return cell->constr_parent != nullptr || !cell->constr_children.empty();
+ }
+
+ // Swap the Bel of a cell with another, return the original location
+ BelId swap_cell_bels(CellInfo *cell, BelId newBel)
+ {
+ BelId oldBel = cell->bel;
+#if 0
+ log_info("%s old: %s new: %s\n", cell->name.c_str(ctx), ctx->getBelName(cell->bel).c_str(ctx), ctx->getBelName(newBel).c_str(ctx));
+#endif
+ CellInfo *bound = ctx->getBoundBelCell(newBel);
+ if (bound != nullptr)
+ ctx->unbindBel(newBel);
+ ctx->unbindBel(oldBel);
+ ctx->bindBel(newBel, cell, is_constrained(cell) ? STRENGTH_STRONG : STRENGTH_WEAK);
+ if (bound != nullptr)
+ ctx->bindBel(oldBel, bound, is_constrained(bound) ? STRENGTH_STRONG : STRENGTH_WEAK);
+ return oldBel;
+ }
+
+ // Discover the relative positions of all cells in a chain
+ void discover_chain(Loc baseLoc, CellInfo *cell, std::vector<std::pair<CellInfo *, Loc>> &cell_rel)
+ {
+ Loc cellLoc = ctx->getBelLocation(cell->bel);
+ Loc rel{cellLoc.x - baseLoc.x, cellLoc.y - baseLoc.y, cellLoc.z};
+ cell_rel.emplace_back(std::make_pair(cell, rel));
+ for (auto child : cell->constr_children)
+ discover_chain(baseLoc, child, cell_rel);
+ }
+
+ // Attempt to swap a chain with a non-chain
+ bool try_swap_chain(CellInfo *cell, BelId newBase)
+ {
+ std::vector<std::pair<CellInfo *, Loc>> cell_rel;
+ std::unordered_set<IdString> cells;
+ std::vector<std::pair<CellInfo *, BelId>> moves_made;
+ std::vector<std::pair<CellInfo *, BelId>> dest_bels;
+ double delta = 0;
+ moveChange.reset(this);
+ if (ctx->debug)
+ log_info("finding cells for chain swap %s\n", cell->name.c_str(ctx));
+
+ Loc baseLoc = ctx->getBelLocation(cell->bel);
+ discover_chain(baseLoc, cell, cell_rel);
+ Loc newBaseLoc = ctx->getBelLocation(newBase);
+ NPNR_ASSERT(newBaseLoc.z == baseLoc.z);
+ for (const auto &cr : cell_rel)
+ cells.insert(cr.first->name);
+
+ for (const auto &cr : cell_rel) {
+ Loc targetLoc = {newBaseLoc.x + cr.second.x, newBaseLoc.y + cr.second.y, cr.second.z};
+ BelId targetBel = ctx->getBelByLocation(targetLoc);
+ if (targetBel == BelId())
+ return false;
+ if (ctx->getBelType(targetBel) != cell->type)
+ return false;
+ CellInfo *bound = ctx->getBoundBelCell(targetBel);
+ // We don't consider swapping chains with other chains, at least for the time being - unless it is
+ // part of this chain
+ if (bound != nullptr && !cells.count(bound->name) &&
+ (bound->belStrength >= STRENGTH_STRONG || is_constrained(bound)))
+ return false;
+ dest_bels.emplace_back(std::make_pair(cr.first, targetBel));
+ }
+ if (ctx->debug)
+ log_info("trying chain swap %s\n", cell->name.c_str(ctx));
+ // <cell, oldBel>
+ for (const auto &db : dest_bels) {
+ BelId oldBel = swap_cell_bels(db.first, db.second);
+ moves_made.emplace_back(std::make_pair(db.first, oldBel));
+ CellInfo *bound = ctx->getBoundBelCell(oldBel);
+ add_move_cell(moveChange, db.first, oldBel);
+ if (bound != nullptr)
+ add_move_cell(moveChange, bound, db.second);
+ }
+ for (const auto &mm : moves_made) {
+ if (!ctx->isBelLocationValid(mm.first->bel) || !check_cell_bel_region(mm.first, mm.first->bel))
+ goto swap_fail;
+ if (!ctx->isBelLocationValid(mm.second))
+ goto swap_fail;
+ CellInfo *bound = ctx->getBoundBelCell(mm.second);
+ if (bound && !check_cell_bel_region(bound, bound->bel))
+ goto swap_fail;
+ }
+ compute_cost_changes(moveChange);
+ delta = lambda * (moveChange.timing_delta / last_timing_cost) +
+ (1 - lambda) * (double(moveChange.wirelen_delta) / last_wirelen_cost);
+ n_move++;
+ // SA acceptance criterea
+ if (delta < 0 || (temp > 1e-9 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) {
+ n_accept++;
+ if (ctx->debug)
+ log_info("accepted chain swap %s\n", cell->name.c_str(ctx));
+ } else {
+ goto swap_fail;
+ }
+ commit_cost_changes(moveChange);
+ return true;
+ swap_fail:
+ for (const auto &entry : boost::adaptors::reverse(moves_made))
+ swap_cell_bels(entry.first, entry.second);
return false;
}
// Find a random Bel of the correct type for a cell, within the specified
// diameter
- BelId random_bel_for_cell(CellInfo *cell)
+ BelId random_bel_for_cell(CellInfo *cell, int force_z = -1)
{
IdString targetType = cell->type;
Loc curr_loc = ctx->getBelLocation(cell->bel);
+ int count = 0;
+
+ int dx = diameter, dy = diameter;
+ if (cell->region != nullptr && cell->region->constr_bels) {
+ dx = std::min(diameter, (region_bounds[cell->region->name].x1 - region_bounds[cell->region->name].x0) + 1);
+ dy = std::min(diameter, (region_bounds[cell->region->name].y1 - region_bounds[cell->region->name].y0) + 1);
+ // Clamp location to within bounds
+ curr_loc.x = std::max(region_bounds[cell->region->name].x0, curr_loc.x);
+ curr_loc.x = std::min(region_bounds[cell->region->name].x1, curr_loc.x);
+ curr_loc.y = std::max(region_bounds[cell->region->name].y0, curr_loc.y);
+ curr_loc.y = std::min(region_bounds[cell->region->name].y1, curr_loc.y);
+ }
+
while (true) {
- int nx = ctx->rng(2 * diameter + 1) + std::max(curr_loc.x - diameter, 0);
- int ny = ctx->rng(2 * diameter + 1) + std::max(curr_loc.y - diameter, 0);
+ int nx = ctx->rng(2 * dx + 1) + std::max(curr_loc.x - dx, 0);
+ int ny = ctx->rng(2 * dy + 1) + std::max(curr_loc.y - dy, 0);
int beltype_idx, beltype_cnt;
std::tie(beltype_idx, beltype_cnt) = bel_types.at(targetType);
if (beltype_cnt < cfg.minBelsForGridPick)
@@ -488,41 +708,436 @@ class SAPlacer
if (fb.size() == 0)
continue;
BelId bel = fb.at(ctx->rng(int(fb.size())));
+ if (force_z != -1) {
+ Loc loc = ctx->getBelLocation(bel);
+ if (loc.z != force_z)
+ continue;
+ }
+ if (!check_cell_bel_region(cell, bel))
+ continue;
if (locked_bels.find(bel) != locked_bels.end())
continue;
+ count++;
return bel;
}
}
+ // Return true if a net is to be entirely ignored
+ inline bool ignore_net(NetInfo *net)
+ {
+ return net->driver.cell == nullptr || net->driver.cell->bel == BelId() ||
+ ctx->getBelGlobalBuf(net->driver.cell->bel);
+ }
+
+ // Get the bounding box for a net
+ inline BoundingBox get_net_bounds(NetInfo *net)
+ {
+ BoundingBox bb;
+ NPNR_ASSERT(net->driver.cell != nullptr);
+ Loc dloc = ctx->getBelLocation(net->driver.cell->bel);
+ bb.x0 = dloc.x;
+ bb.x1 = dloc.x;
+ bb.y0 = dloc.y;
+ bb.y1 = dloc.y;
+ bb.nx0 = 1;
+ bb.nx1 = 1;
+ bb.ny0 = 1;
+ bb.ny1 = 1;
+ for (auto user : net->users) {
+ if (user.cell->bel == BelId())
+ continue;
+ Loc uloc = ctx->getBelLocation(user.cell->bel);
+ if (bb.x0 == uloc.x)
+ ++bb.nx0;
+ else if (uloc.x < bb.x0) {
+ bb.x0 = uloc.x;
+ bb.nx0 = 1;
+ }
+ if (bb.x1 == uloc.x)
+ ++bb.nx1;
+ else if (uloc.x > bb.x1) {
+ bb.x1 = uloc.x;
+ bb.nx1 = 1;
+ }
+ if (bb.y0 == uloc.y)
+ ++bb.ny0;
+ else if (uloc.y < bb.y0) {
+ bb.y0 = uloc.y;
+ bb.ny0 = 1;
+ }
+ if (bb.y1 == uloc.y)
+ ++bb.ny1;
+ else if (uloc.y > bb.y1) {
+ bb.y1 = uloc.y;
+ bb.ny1 = 1;
+ }
+ }
+
+ return bb;
+ }
+
+ // Get the timing cost for an arc of a net
+ inline double get_timing_cost(NetInfo *net, size_t user)
+ {
+ int cc;
+ if (net->driver.cell == nullptr)
+ return 0;
+ if (ctx->getPortTimingClass(net->driver.cell, net->driver.port, cc) == TMG_IGNORE)
+ return 0;
+ if (cfg.budgetBased) {
+ double delay = ctx->getDelayNS(ctx->predictDelay(net, net->users.at(user)));
+ return std::min(10.0, std::exp(delay - ctx->getDelayNS(net->users.at(user).budget) / 10));
+ } else {
+ auto crit = net_crit.find(net->name);
+ if (crit == net_crit.end() || crit->second.criticality.empty())
+ return 0;
+ double delay = ctx->getDelayNS(ctx->predictDelay(net, net->users.at(user)));
+ return delay * std::pow(crit->second.criticality.at(user), crit_exp);
+ }
+ }
+
+ // Set up the cost maps
+ void setup_costs()
+ {
+ for (auto net : sorted(ctx->nets)) {
+ NetInfo *ni = net.second;
+ if (ignore_net(ni))
+ continue;
+ net_bounds[ni->udata] = get_net_bounds(ni);
+ if (ctx->timing_driven && int(ni->users.size()) < cfg.timingFanoutThresh)
+ for (size_t i = 0; i < ni->users.size(); i++)
+ net_arc_tcost[ni->udata][i] = get_timing_cost(ni, i);
+ }
+ }
+
+ // Get the total wiring cost for the design
+ wirelen_t total_wirelen_cost()
+ {
+ wirelen_t cost = 0;
+ for (const auto &net : net_bounds)
+ cost += net.hpwl();
+ return cost;
+ }
+
+ // Get the total timing cost for the design
+ double total_timing_cost()
+ {
+ double cost = 0;
+ for (const auto &net : net_arc_tcost) {
+ for (auto arc_cost : net) {
+ cost += arc_cost;
+ }
+ }
+ return cost;
+ }
+
+ // Cost-change-related data for a move
+ struct MoveChangeData
+ {
+
+ enum BoundChangeType
+ {
+ NO_CHANGE,
+ CELL_MOVED_INWARDS,
+ CELL_MOVED_OUTWARDS,
+ FULL_RECOMPUTE
+ };
+
+ std::vector<decltype(NetInfo::udata)> bounds_changed_nets_x, bounds_changed_nets_y;
+ std::vector<std::pair<decltype(NetInfo::udata), size_t>> changed_arcs;
+
+ std::vector<BoundChangeType> already_bounds_changed_x, already_bounds_changed_y;
+ std::vector<std::vector<bool>> already_changed_arcs;
+
+ std::vector<BoundingBox> new_net_bounds;
+ std::vector<std::pair<std::pair<decltype(NetInfo::udata), size_t>, double>> new_arc_costs;
+
+ wirelen_t wirelen_delta = 0;
+ double timing_delta = 0;
+
+ void init(SAPlacer *p)
+ {
+ already_bounds_changed_x.resize(p->ctx->nets.size());
+ already_bounds_changed_y.resize(p->ctx->nets.size());
+ already_changed_arcs.resize(p->ctx->nets.size());
+ for (auto &net : p->ctx->nets) {
+ already_changed_arcs.at(net.second->udata).resize(net.second->users.size());
+ }
+ new_net_bounds = p->net_bounds;
+ }
+
+ void reset(SAPlacer *p)
+ {
+ for (auto bc : bounds_changed_nets_x) {
+ new_net_bounds[bc] = p->net_bounds[bc];
+ already_bounds_changed_x[bc] = NO_CHANGE;
+ }
+ for (auto bc : bounds_changed_nets_y) {
+ new_net_bounds[bc] = p->net_bounds[bc];
+ already_bounds_changed_y[bc] = NO_CHANGE;
+ }
+ for (const auto &tc : changed_arcs)
+ already_changed_arcs[tc.first][tc.second] = false;
+ bounds_changed_nets_x.clear();
+ bounds_changed_nets_y.clear();
+ changed_arcs.clear();
+ new_arc_costs.clear();
+ wirelen_delta = 0;
+ timing_delta = 0;
+ }
+
+ } moveChange;
+
+ void add_move_cell(MoveChangeData &mc, CellInfo *cell, BelId old_bel)
+ {
+ Loc curr_loc = ctx->getBelLocation(cell->bel);
+ Loc old_loc = ctx->getBelLocation(old_bel);
+ // Check net bounds
+ for (const auto &port : cell->ports) {
+ NetInfo *pn = port.second.net;
+ if (pn == nullptr)
+ continue;
+ if (ignore_net(pn))
+ continue;
+ BoundingBox &curr_bounds = mc.new_net_bounds[pn->udata];
+ // Incremental bounding box updates
+ // Note that everything other than full updates are applied immediately rather than being queued,
+ // so further updates to the same net in the same move are dealt with correctly.
+ // If a full update is already queued, this can be considered a no-op
+ if (mc.already_bounds_changed_x[pn->udata] != MoveChangeData::FULL_RECOMPUTE) {
+ // Bounds x0
+ if (curr_loc.x < curr_bounds.x0) {
+ // Further out than current bounds x0
+ curr_bounds.x0 = curr_loc.x;
+ curr_bounds.nx0 = 1;
+ if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE) {
+ // Checking already_bounds_changed_x ensures that each net is only added once
+ // to bounds_changed_nets, lest we add its HPWL change multiple times skewing the
+ // overall cost change
+ mc.already_bounds_changed_x[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS;
+ mc.bounds_changed_nets_x.push_back(pn->udata);
+ }
+ } else if (curr_loc.x == curr_bounds.x0 && old_loc.x > curr_bounds.x0) {
+ curr_bounds.nx0++;
+ if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE) {
+ mc.already_bounds_changed_x[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS;
+ mc.bounds_changed_nets_x.push_back(pn->udata);
+ }
+ } else if (old_loc.x == curr_bounds.x0 && curr_loc.x > curr_bounds.x0) {
+ if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE)
+ mc.bounds_changed_nets_x.push_back(pn->udata);
+ if (curr_bounds.nx0 == 1) {
+ mc.already_bounds_changed_x[pn->udata] = MoveChangeData::FULL_RECOMPUTE;
+ } else {
+ curr_bounds.nx0--;
+ if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE)
+ mc.already_bounds_changed_x[pn->udata] = MoveChangeData::CELL_MOVED_INWARDS;
+ }
+ }
+
+ // Bounds x1
+ if (curr_loc.x > curr_bounds.x1) {
+ // Further out than current bounds x1
+ curr_bounds.x1 = curr_loc.x;
+ curr_bounds.nx1 = 1;
+ if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE) {
+ // Checking already_bounds_changed_x ensures that each net is only added once
+ // to bounds_changed_nets, lest we add its HPWL change multiple times skewing the
+ // overall cost change
+ mc.already_bounds_changed_x[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS;
+ mc.bounds_changed_nets_x.push_back(pn->udata);
+ }
+ } else if (curr_loc.x == curr_bounds.x1 && old_loc.x < curr_bounds.x1) {
+ curr_bounds.nx1++;
+ if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE) {
+ mc.already_bounds_changed_x[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS;
+ mc.bounds_changed_nets_x.push_back(pn->udata);
+ }
+ } else if (old_loc.x == curr_bounds.x1 && curr_loc.x < curr_bounds.x1) {
+ if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE)
+ mc.bounds_changed_nets_x.push_back(pn->udata);
+ if (curr_bounds.nx1 == 1) {
+ mc.already_bounds_changed_x[pn->udata] = MoveChangeData::FULL_RECOMPUTE;
+ } else {
+ curr_bounds.nx1--;
+ if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE)
+ mc.already_bounds_changed_x[pn->udata] = MoveChangeData::CELL_MOVED_INWARDS;
+ }
+ }
+ }
+ if (mc.already_bounds_changed_y[pn->udata] != MoveChangeData::FULL_RECOMPUTE) {
+ // Bounds y0
+ if (curr_loc.y < curr_bounds.y0) {
+ // Further out than current bounds y0
+ curr_bounds.y0 = curr_loc.y;
+ curr_bounds.ny0 = 1;
+ if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE) {
+ mc.already_bounds_changed_y[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS;
+ mc.bounds_changed_nets_y.push_back(pn->udata);
+ }
+ } else if (curr_loc.y == curr_bounds.y0 && old_loc.y > curr_bounds.y0) {
+ curr_bounds.ny0++;
+ if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE) {
+ mc.already_bounds_changed_y[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS;
+ mc.bounds_changed_nets_y.push_back(pn->udata);
+ }
+ } else if (old_loc.y == curr_bounds.y0 && curr_loc.y > curr_bounds.y0) {
+ if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE)
+ mc.bounds_changed_nets_y.push_back(pn->udata);
+ if (curr_bounds.ny0 == 1) {
+ mc.already_bounds_changed_y[pn->udata] = MoveChangeData::FULL_RECOMPUTE;
+ } else {
+ curr_bounds.ny0--;
+ if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE)
+ mc.already_bounds_changed_y[pn->udata] = MoveChangeData::CELL_MOVED_INWARDS;
+ }
+ }
+
+ // Bounds y1
+ if (curr_loc.y > curr_bounds.y1) {
+ // Further out than current bounds y1
+ curr_bounds.y1 = curr_loc.y;
+ curr_bounds.ny1 = 1;
+ if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE) {
+ mc.already_bounds_changed_y[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS;
+ mc.bounds_changed_nets_y.push_back(pn->udata);
+ }
+ } else if (curr_loc.y == curr_bounds.y1 && old_loc.y < curr_bounds.y1) {
+ curr_bounds.ny1++;
+ if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE) {
+ mc.already_bounds_changed_y[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS;
+ mc.bounds_changed_nets_y.push_back(pn->udata);
+ }
+ } else if (old_loc.y == curr_bounds.y1 && curr_loc.y < curr_bounds.y1) {
+ if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE)
+ mc.bounds_changed_nets_y.push_back(pn->udata);
+ if (curr_bounds.ny1 == 1) {
+ mc.already_bounds_changed_y[pn->udata] = MoveChangeData::FULL_RECOMPUTE;
+ } else {
+ curr_bounds.ny1--;
+ if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE)
+ mc.already_bounds_changed_y[pn->udata] = MoveChangeData::CELL_MOVED_INWARDS;
+ }
+ }
+ }
+
+ if (ctx->timing_driven && int(pn->users.size()) < cfg.timingFanoutThresh) {
+ // Output ports - all arcs change timing
+ if (port.second.type == PORT_OUT) {
+ int cc;
+ TimingPortClass cls = ctx->getPortTimingClass(cell, port.first, cc);
+ if (cls != TMG_IGNORE)
+ for (size_t i = 0; i < pn->users.size(); i++)
+ if (!mc.already_changed_arcs[pn->udata][i]) {
+ mc.changed_arcs.emplace_back(std::make_pair(pn->udata, i));
+ mc.already_changed_arcs[pn->udata][i] = true;
+ }
+ } else if (port.second.type == PORT_IN) {
+ auto usr = fast_port_to_user.at(&port.second);
+ if (!mc.already_changed_arcs[pn->udata][usr]) {
+ mc.changed_arcs.emplace_back(std::make_pair(pn->udata, usr));
+ mc.already_changed_arcs[pn->udata][usr] = true;
+ }
+ }
+ }
+ }
+ }
+
+ void compute_cost_changes(MoveChangeData &md)
+ {
+ for (const auto &bc : md.bounds_changed_nets_x) {
+ if (md.already_bounds_changed_x[bc] == MoveChangeData::FULL_RECOMPUTE)
+ md.new_net_bounds[bc] = get_net_bounds(net_by_udata[bc]);
+ }
+ for (const auto &bc : md.bounds_changed_nets_y) {
+ if (md.already_bounds_changed_x[bc] != MoveChangeData::FULL_RECOMPUTE &&
+ md.already_bounds_changed_y[bc] == MoveChangeData::FULL_RECOMPUTE)
+ md.new_net_bounds[bc] = get_net_bounds(net_by_udata[bc]);
+ }
+
+ for (const auto &bc : md.bounds_changed_nets_x)
+ md.wirelen_delta += md.new_net_bounds[bc].hpwl() - net_bounds[bc].hpwl();
+ for (const auto &bc : md.bounds_changed_nets_y)
+ if (md.already_bounds_changed_x[bc] == MoveChangeData::NO_CHANGE)
+ md.wirelen_delta += md.new_net_bounds[bc].hpwl() - net_bounds[bc].hpwl();
+
+ if (ctx->timing_driven) {
+ for (const auto &tc : md.changed_arcs) {
+ double old_cost = net_arc_tcost.at(tc.first).at(tc.second);
+ double new_cost = get_timing_cost(net_by_udata.at(tc.first), tc.second);
+ md.new_arc_costs.emplace_back(std::make_pair(tc, new_cost));
+ md.timing_delta += (new_cost - old_cost);
+ md.already_changed_arcs[tc.first][tc.second] = false;
+ }
+ }
+ }
+
+ void commit_cost_changes(MoveChangeData &md)
+ {
+ for (const auto &bc : md.bounds_changed_nets_x)
+ net_bounds[bc] = md.new_net_bounds[bc];
+ for (const auto &bc : md.bounds_changed_nets_y)
+ net_bounds[bc] = md.new_net_bounds[bc];
+ for (const auto &tc : md.new_arc_costs)
+ net_arc_tcost[tc.first.first].at(tc.first.second) = tc.second;
+ curr_wirelen_cost += md.wirelen_delta;
+ curr_timing_cost += md.timing_delta;
+ }
+ // Build the cell port -> user index
+ void build_port_index()
+ {
+ for (auto net : sorted(ctx->nets)) {
+ NetInfo *ni = net.second;
+ for (size_t i = 0; i < ni->users.size(); i++) {
+ auto &usr = ni->users.at(i);
+ fast_port_to_user[&(usr.cell->ports.at(usr.port))] = i;
+ }
+ }
+ }
+
+ // Get the combined wirelen/timing metric
+ inline double curr_metric() { return lambda * curr_timing_cost + (1 - lambda) * curr_wirelen_cost; }
+
+ // Map nets to their bounding box (so we can skip recompute for moves that do not exceed the bounds
+ std::vector<BoundingBox> net_bounds;
+ // Map net arcs to their timing cost (criticality * delay ns)
+ std::vector<std::vector<double>> net_arc_tcost;
+
+ // Fast lookup for cell port to net user index
+ std::unordered_map<const PortInfo *, size_t> fast_port_to_user;
+
+ // Wirelength and timing cost at last and current iteration
+ wirelen_t last_wirelen_cost, curr_wirelen_cost;
+ double last_timing_cost, curr_timing_cost;
+
+ // Criticality data from timing analysis
+ NetCriticalityMap net_crit;
+
Context *ctx;
- wirelen_t curr_metric = std::numeric_limits<wirelen_t>::max();
- float curr_tns = 0;
- float temp = 1000;
+ float temp = 10;
+ float crit_exp = 8;
+ float lambda = 0.5;
bool improved = false;
int n_move, n_accept;
int diameter = 35, max_x = 1, max_y = 1;
std::unordered_map<IdString, std::tuple<int, int>> bel_types;
+ std::unordered_map<IdString, BoundingBox> region_bounds;
std::vector<std::vector<std::vector<std::vector<BelId>>>> fast_bels;
std::unordered_set<BelId> locked_bels;
+ std::vector<NetInfo *> net_by_udata;
+ std::vector<decltype(NetInfo::udata)> old_udata;
bool require_legal = true;
- const float legalise_temp = 1;
- const float post_legalise_temp = 10;
- const float post_legalise_dia_scale = 1.5;
+ const int legalise_dia = 4;
Placer1Cfg cfg;
-
- struct CostChange
- {
- wirelen_t curr_cost;
- wirelen_t new_cost;
- };
- std::vector<CostChange> costs;
- std::vector<decltype(NetInfo::udata)> old_udata;
};
Placer1Cfg::Placer1Cfg(Context *ctx) : Settings(ctx)
{
constraintWeight = get<float>("placer1/constraintWeight", 10);
minBelsForGridPick = get<int>("placer1/minBelsForGridPick", 64);
+ budgetBased = get<bool>("placer1/budgetBased", false);
+ startTemp = get<float>("placer1/startTemp", 1);
+ timingFanoutThresh = std::numeric_limits<int>::max();
}
bool placer1(Context *ctx, Placer1Cfg cfg)
@@ -545,4 +1160,24 @@ bool placer1(Context *ctx, Placer1Cfg cfg)
}
}
+bool placer1_refine(Context *ctx, Placer1Cfg cfg)
+{
+ try {
+ SAPlacer placer(ctx, cfg);
+ placer.place(true);
+ log_info("Checksum: 0x%08x\n", ctx->checksum());
+#ifndef NDEBUG
+ ctx->lock();
+ ctx->check();
+ ctx->unlock();
+#endif
+ return true;
+ } catch (log_execution_error_exception) {
+#ifndef NDEBUG
+ ctx->check();
+#endif
+ return false;
+ }
+}
+
NEXTPNR_NAMESPACE_END
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-22 04:24:43 +0000