diff options
Diffstat (limited to 'common/placer1.cc')
| -rw-r--r-- | common/placer1.cc | 787 |
1 files changed, 613 insertions, 174 deletions
diff --git a/common/placer1.cc b/common/placer1.cc index 5b72602f..98251627 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,32 @@ #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 + { + int x0 = 0, x1 = 0, y0 = 0, y1 = 0; + bool is_inside_inc(int x, int y) const { return x >= x0 && x <= x1 && y >= y0 && y <= y1; } + bool touches_bounds(int x, int y) const { return x == x0 || x == x1 || y == y0 || y == y1; } + wirelen_t hpwl() const { return wirelen_t((x1 - x0) + (y1 - y0)); } + }; + public: SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), cfg(cfg) { @@ -78,13 +101,44 @@ 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()); + moveChange.already_bounds_changed.resize(ctx->nets.size()); + moveChange.already_changed_arcs.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()); + moveChange.already_changed_arcs.at(n).resize(net.second->users.size()); net.second->udata = n++; + net_by_udata.push_back(net.second.get()); + } + for (auto ®ion : 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 +147,121 @@ 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())); - - for (auto cell : autoplaced) { - place_initial(cell); - placed_cells++; - if ((placed_cells - constr_placed_cells) % 500 == 0) + 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) + 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(); + 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 +269,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 +283,17 @@ 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 (curr_metric < min_metric) { - min_metric = curr_metric; + if (curr_wirelen_cost < min_wirelen) { + min_wirelen = curr_wirelen_cost; improved = true; } @@ -218,9 +303,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 +314,64 @@ 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 && curr_metric > 0) { - 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(); // 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 +423,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 +442,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 +474,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(); + 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 +513,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 +532,148 @@ 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(); + 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)); + } + 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; + add_move_cell(moveChange, mm.first, mm.second); + if (bound != nullptr) + add_move_cell(moveChange, bound, mm.first->bel); + } + 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 +686,262 @@ 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; + + for (auto user : net->users) { + if (user.cell->bel == BelId()) + continue; + Loc uloc = ctx->getBelLocation(user.cell->bel); + bb.x0 = std::min(bb.x0, uloc.x); + bb.x1 = std::max(bb.x1, uloc.x); + bb.y0 = std::min(bb.y0, uloc.y); + bb.y1 = std::max(bb.y1, uloc.y); + } + + 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 + { + std::vector<decltype(NetInfo::udata)> bounds_changed_nets; + std::vector<std::pair<decltype(NetInfo::udata), size_t>> changed_arcs; + + std::vector<bool> already_bounds_changed; + std::vector<std::vector<bool>> already_changed_arcs; + + std::vector<std::pair<decltype(NetInfo::udata), 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 reset() + { + for (auto bc : bounds_changed_nets) + already_bounds_changed[bc] = false; + for (const auto &tc : changed_arcs) + already_changed_arcs[tc.first][tc.second] = false; + bounds_changed_nets.clear(); + changed_arcs.clear(); + new_net_bounds.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; + const BoundingBox &curr_bounds = net_bounds[pn->udata]; + // If the old location was at the edge of the bounds, or the new location exceeds the bounds, + // an update is needed + if (curr_bounds.touches_bounds(old_loc.x, old_loc.y) || !curr_bounds.is_inside_inc(curr_loc.x, curr_loc.y)) + if (!mc.already_bounds_changed[pn->udata]) { + mc.bounds_changed_nets.push_back(pn->udata); + mc.already_bounds_changed[pn->udata] = true; + } + 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) { + wirelen_t old_hpwl = net_bounds.at(bc).hpwl(); + auto bounds = get_net_bounds(net_by_udata.at(bc)); + md.new_net_bounds.emplace_back(std::make_pair(bc, bounds)); + md.wirelen_delta += (bounds.hpwl() - old_hpwl); + md.already_bounds_changed[bc] = false; + } + 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.new_net_bounds) + net_bounds[bc.first] = bc.second; + 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 +964,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 |