From f3d9b453876e02da94c0534d732a35a04e4e58f0 Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 23 Jan 2019 16:36:53 +0000 Subject: HeAP: Add SA-based iterative refinement after AP Signed-off-by: David Shah --- common/placer1.cc | 167 ++++++++++++++++++++++++++++++-------------------- common/placer1.h | 1 + common/placer_heap.cc | 62 ++++++++++++------- 3 files changed, 143 insertions(+), 87 deletions(-) diff --git a/common/placer1.cc b/common/placer1.cc index 767dbae6..ffa3aa75 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -147,85 +147,102 @@ 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 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)); - } + 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 - // Sort to-place cells for deterministic initial placement - std::vector autoplaced; - std::vector chain_basis; - for (auto &cell : ctx->cells) { - CellInfo *ci = cell.second.get(); - if (ci->bel == BelId()) { - autoplaced.push_back(cell.second.get()); + 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(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; } - 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()); auto saplace_start = std::chrono::high_resolution_clock::now(); - log_info("Running simulated annealing placer.\n"); // Invoke timing analysis to obtain criticalities if (!cfg.budgetBased) @@ -242,7 +259,7 @@ class SAPlacer wirelen_t min_wirelen = curr_wirelen_cost; int n_no_progress = 0; - temp = cfg.startTemp; + temp = refine ? 1e-8 : cfg.startTemp; // Main simulated annealing loop for (int iter = 1;; iter++) { @@ -284,7 +301,7 @@ class SAPlacer else n_no_progress++; - if (temp <= 1e-7 && n_no_progress >= 5) { + 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)); @@ -934,4 +951,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 diff --git a/common/placer1.h b/common/placer1.h index a0eabbb0..4c7c7339 100644 --- a/common/placer1.h +++ b/common/placer1.h @@ -35,6 +35,7 @@ struct Placer1Cfg : public Settings }; extern bool placer1(Context *ctx, Placer1Cfg cfg); +extern bool placer1_refine(Context *ctx, Placer1Cfg cfg); NEXTPNR_NAMESPACE_END diff --git a/common/placer_heap.cc b/common/placer_heap.cc index 3e98b937..7e8323ca 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -34,6 +34,7 @@ #include "nextpnr.h" #include "place_common.h" #include "placer_math.h" +#include "placer1.h" #include "util.h" NEXTPNR_NAMESPACE_BEGIN @@ -191,6 +192,9 @@ class HeAPPlacer ++iter; } ctx->unlock(); + + placer1_refine(ctx, Placer1Cfg(ctx)); + return true; } @@ -355,14 +359,17 @@ class HeAPPlacer // FIXME: Are there better approaches to the initial placement (e.g. greedy?) void seed_placement() { - std::unordered_map> available_bels; + std::unordered_map> available_bels; for (auto bel : ctx->getBels()) { if (!ctx->checkBelAvail(bel)) continue; available_bels[ctx->getBelType(bel)].push_back(bel); } - for (auto &ab : available_bels) - ctx->shuffle(ab.second); + for (auto &t : available_bels) { + std::random_shuffle(t.second.begin(), t.second.end(), [&](size_t n){ + return ctx->rng(int(n)); + }); + } for (auto cell : sorted(ctx->cells)) { CellInfo *ci = cell.second; if (ci->bel != BelId()) { @@ -372,23 +379,34 @@ class HeAPPlacer cell_locs[cell.first].locked = true; cell_locs[cell.first].global = ctx->getBelGlobalBuf(ci->bel); } else if (ci->constr_parent == nullptr) { - if (!available_bels.count(ci->type) || available_bels.at(ci->type).empty()) - log_error("Unable to place cell '%s', no Bels remaining of type '%s'\n", ci->name.c_str(ctx), - ci->type.c_str(ctx)); - BelId bel = available_bels.at(ci->type).back(); - available_bels.at(ci->type).pop_back(); - Loc loc = ctx->getBelLocation(bel); - cell_locs[cell.first].x = loc.x; - cell_locs[cell.first].y = loc.y; - cell_locs[cell.first].locked = false; - cell_locs[cell.first].global = ctx->getBelGlobalBuf(bel); - // FIXME - if (has_connectivity(cell.second) && cell.second->type != ctx->id("SB_IO")) { - place_cells.push_back(ci); - } else { - ctx->bindBel(bel, ci, STRENGTH_STRONG); - cell_locs[cell.first].locked = true; + bool placed = false; + while (!placed) { + if (!available_bels.count(ci->type) || available_bels.at(ci->type).empty()) + log_error("Unable to place cell '%s', no Bels remaining of type '%s'\n", ci->name.c_str(ctx), + ci->type.c_str(ctx)); + BelId bel = available_bels.at(ci->type).back(); + available_bels.at(ci->type).pop_back(); + Loc loc = ctx->getBelLocation(bel); + cell_locs[cell.first].x = loc.x; + cell_locs[cell.first].y = loc.y; + cell_locs[cell.first].locked = false; + cell_locs[cell.first].global = ctx->getBelGlobalBuf(bel); + // FIXME + if (has_connectivity(cell.second) && cell.second->type != ctx->id("SB_IO")) { + place_cells.push_back(ci); + placed = true; + } else { + if (ctx->isValidBelForCell(ci, bel)) { + ctx->bindBel(bel, ci, STRENGTH_STRONG); + cell_locs[cell.first].locked = true; + placed = true; + } else { + available_bels.at(ci->type).push_front(bel); + } + + } } + } } } @@ -728,8 +746,8 @@ class HeAPPlacer for (auto &r : regions) { if (merged_regions.count(r.id)) continue; - /*log_info("%s (%d, %d) |_> (%d, %d) %d/%d\n", beltype.c_str(ctx), r.x0, r.y0, r.x1, r.y1, r.cells, - r.bels);*/ + log_info("%s (%d, %d) |_> (%d, %d) %d/%d\n", beltype.c_str(ctx), r.x0, r.y0, r.x1, r.y1, r.cells, + r.bels); workqueue.emplace(r.id, false); //cut_region(r, false); } @@ -865,7 +883,7 @@ class HeAPPlacer auto process_location = [&](int x, int y) { // Merge with any overlapping regions - if (groups.at(x).at(y) != r.id) { + if (groups.at(x).at(y) == -1) { r.bels += bels_at(x, y); r.cells += occ_at(x, y); } -- cgit v1.2.3