/* * nextpnr -- Next Generation Place and Route * * Copyright (C) 2018 Clifford Wolf * Copyright (C) 2018 David Shah * * Simulated annealing implementation based on arachne-pnr * Copyright (C) 2015-2018 Cotton Seed * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. * */ #include "placer1.h" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include "log.h" #include "place_common.h" #include "timing.h" #include "util.h" namespace std { template <> struct hash> { std::size_t operator()(const std::pair &idp) const noexcept { std::size_t seed = 0; boost::hash_combine(seed, hash()(idp.first)); boost::hash_combine(seed, hash()(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) { int num_bel_types = 0; for (auto bel : ctx->getBels()) { IdString type = ctx->getBelType(bel); if (bel_types.find(type) == bel_types.end()) { bel_types[type] = std::tuple(num_bel_types++, 1); } else { std::get<1>(bel_types.at(type))++; } } for (auto bel : ctx->getBels()) { Loc loc = ctx->getBelLocation(bel); IdString type = ctx->getBelType(bel); int type_idx = std::get<0>(bel_types.at(type)); int type_cnt = std::get<1>(bel_types.at(type)); if (type_cnt < cfg.minBelsForGridPick) loc.x = loc.y = 0; if (int(fast_bels.size()) < type_idx + 1) fast_bels.resize(type_idx + 1); if (int(fast_bels.at(type_idx).size()) < (loc.x + 1)) fast_bels.at(type_idx).resize(loc.x + 1); if (int(fast_bels.at(type_idx).at(loc.x).size()) < (loc.y + 1)) fast_bels.at(type_idx).at(loc.x).resize(loc.y + 1); max_x = std::max(max_x, loc.x); max_y = std::max(max_y, loc.y); fast_bels.at(type_idx).at(loc.x).at(loc.y).push_back(bel); } diameter = std::max(max_x, max_y) + 1; 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 ®ion : sorted(ctx->region)) { Region *r = region.second; BoundingBox bb; if (r->constr_bels) { bb.x0 = std::numeric_limits::max(); bb.x1 = std::numeric_limits::min(); bb.y0 = std::numeric_limits::max(); bb.y1 = std::numeric_limits::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() { for (auto &net : ctx->nets) net.second->udata = old_udata[net.second->udata]; } bool place(bool refine = false) { log_break(); ctx->lock(); size_t placed_cells = 0; std::vector autoplaced; std::vector 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)); } 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++; } } 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 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) 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(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"); } auto saplace_start = std::chrono::high_resolution_clock::now(); // 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; temp = refine ? 1e-7 : cfg.startTemp; // Main simulated annealing loop for (int iter = 1;; iter++) { n_move = n_accept = 0; improved = false; if (iter % 5 == 0 || iter == 1) 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 for (auto cell : autoplaced) { // Find another random Bel for this cell BelId try_bel = random_bel_for_cell(cell); // If valid, try and swap to a new position and see if // the new position is valid/worthwhile 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_wirelen_cost < min_wirelen) { min_wirelen = curr_wirelen_cost; improved = true; } // Heuristic to improve placement on the 8k if (improved) n_no_progress = 0; else n_no_progress++; 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; } double Raccept = double(n_accept) / double(n_move); int M = std::max(max_x, max_y) + 1; 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_wirelen_cost < 0.95 * avg_wirelen && curr_wirelen_cost > 0) { avg_wirelen = 0.8 * avg_wirelen + 0.2 * curr_wirelen_cost; } else { double diam_next = diameter * (1.0 - 0.44 + Raccept); diameter = std::max(1, std::min(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 { temp *= 0.8; } } // Once cooled below legalise threshold, run legalisation and start requiring // legal moves only 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 && 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 = std::min(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 && cfg.budgetBased) assign_budget(ctx, true /* quiet */); } require_legal = false; } 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_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(); } auto saplace_end = std::chrono::high_resolution_clock::now(); log_info("SA placement time %.02fs\n", std::chrono::duration(saplace_end - saplace_start).count()); // Final post-pacement validitiy check ctx->yield(); for (auto bel : ctx->getBels()) { CellInfo *cell = ctx->getBoundBelCell(bel); if (!ctx->isBelLocationValid(bel)) { std::string cell_text = "no cell"; if (cell != nullptr) cell_text = std::string("cell '") + ctx->nameOf(cell) + "'"; if (ctx->force) { log_warning("post-placement validity check failed for Bel '%s' " "(%s)\n", ctx->getBelName(bel).c_str(ctx), cell_text.c_str()); } else { log_error("post-placement validity check failed for Bel '%s' " "(%s)\n", ctx->getBelName(bel).c_str(ctx), cell_text.c_str()); } } } for (auto cell : sorted(ctx->cells)) if (get_constraints_distance(ctx, cell.second) != 0) log_error("constraint satisfaction check failed for cell '%s' at Bel '%s'\n", cell.first.c_str(ctx), ctx->getBelName(cell.second->bel).c_str(ctx)); timing_analysis(ctx); ctx->unlock(); return true; } private: // Initial random placement void place_initial(CellInfo *cell) { bool all_placed = false; int iters = 25; while (!all_placed) { BelId best_bel = BelId(); uint64_t best_score = std::numeric_limits::max(), best_ripup_score = std::numeric_limits::max(); CellInfo *ripup_target = nullptr; BelId ripup_bel = BelId(); if (cell->bel != BelId()) { ctx->unbindBel(cell->bel); } IdString targetType = cell->type; auto proc_bel = [&](BelId bel) { if (ctx->getBelType(bel) == targetType && ctx->isValidBelForCell(cell, bel)) { if (ctx->checkBelAvail(bel)) { uint64_t score = ctx->rng64(); if (score <= best_score) { best_score = score; best_bel = bel; } } else { uint64_t score = ctx->rng64(); CellInfo *bound_cell = ctx->getBoundBelCell(bel); if (score <= best_ripup_score && bound_cell->belStrength < STRENGTH_STRONG) { best_ripup_score = score; ripup_target = bound_cell; ripup_bel = bel; } } } }; 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)); --iters; ctx->unbindBel(ripup_target->bel); best_bel = ripup_bel; } else { all_placed = true; } ctx->bindBel(best_bel, cell, STRENGTH_WEAK); // Back annotate location cell->attrs[ctx->id("BEL")] = ctx->getBelName(cell->bel).str(ctx); cell = ripup_target; } } // Attempt a SA position swap, return true on success or false on failure bool try_swap_position(CellInfo *cell, BelId newBel) { 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 (!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); double delta = 0; ctx->unbindBel(oldBel); if (other_cell != nullptr) { ctx->unbindBel(newBel); } ctx->bindBel(newBel, cell, STRENGTH_WEAK); if (other_cell != nullptr) { ctx->bindBel(oldBel, other_cell, STRENGTH_WEAK); } add_move_cell(moveChange, cell, oldBel); if (other_cell != nullptr) { add_move_cell(moveChange, other_cell, newBel); } if (!ctx->isBelLocationValid(newBel) || ((other_cell != nullptr && !ctx->isBelLocationValid(oldBel)))) { ctx->unbindBel(newBel); if (other_cell != nullptr) ctx->unbindBel(oldBel); goto swap_fail; } // Recalculate metrics for all nets touched by the peturbation compute_cost_changes(moveChange); new_dist = get_constraints_distance(ctx, cell); if (other_cell != nullptr) new_dist += get_constraints_distance(ctx, other_cell); 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; n_move++; // SA acceptance criterea if (delta < 0 || (temp > 1e-8 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { n_accept++; } else { if (other_cell != nullptr) ctx->unbindBel(oldBel); ctx->unbindBel(newBel); goto swap_fail; } 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); } 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> &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> cell_rel; std::unordered_set cells; std::vector> moves_made; std::vector> 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)); // 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, 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 * 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) nx = ny = 0; if (nx >= int(fast_bels.at(beltype_idx).size())) continue; if (ny >= int(fast_bels.at(beltype_idx).at(nx).size())) continue; const auto &fb = fast_bels.at(beltype_idx).at(nx).at(ny); 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 bounds_changed_nets_x, bounds_changed_nets_y; std::vector> changed_arcs; std::vector already_bounds_changed_x, already_bounds_changed_y; std::vector> already_changed_arcs; std::vector new_net_bounds; std::vector, 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 net_bounds; // Map net arcs to their timing cost (criticality * delay ns) std::vector> net_arc_tcost; // Fast lookup for cell port to net user index std::unordered_map 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; 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> bel_types; std::unordered_map region_bounds; std::vector>>> fast_bels; std::unordered_set locked_bels; std::vector net_by_udata; std::vector old_udata; bool require_legal = true; const int legalise_dia = 4; Placer1Cfg cfg; }; Placer1Cfg::Placer1Cfg(Context *ctx) : Settings(ctx) { constraintWeight = get("placer1/constraintWeight", 10); minBelsForGridPick = get("placer1/minBelsForGridPick", 64); budgetBased = get("placer1/budgetBased", false); startTemp = get("placer1/startTemp", 1); timingFanoutThresh = std::numeric_limits::max(); } bool placer1(Context *ctx, Placer1Cfg cfg) { try { SAPlacer placer(ctx, cfg); placer.place(); 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; } } 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