From 7daa8524c8ab8c9ff5400d5074b80573b0d39a14 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Wed, 11 Jul 2018 18:15:08 +0200 Subject: Add ctx->place() API Signed-off-by: Clifford Wolf --- common/place_sa.cc | 450 ----------------------------------------------------- common/place_sa.h | 30 ---- common/placer1.cc | 450 +++++++++++++++++++++++++++++++++++++++++++++++++++++ common/placer1.h | 30 ++++ 4 files changed, 480 insertions(+), 480 deletions(-) delete mode 100644 common/place_sa.cc delete mode 100644 common/place_sa.h create mode 100644 common/placer1.cc create mode 100644 common/placer1.h (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc deleted file mode 100644 index ab161c57..00000000 --- a/common/place_sa.cc +++ /dev/null @@ -1,450 +0,0 @@ -/* - * 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 "place_sa.h" -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include "log.h" -#include "place_common.h" -#include "place_legaliser.h" -#include "timing.h" -#include "util.h" -NEXTPNR_NAMESPACE_BEGIN - -class SAPlacer -{ - public: - SAPlacer(Context *ctx) : ctx(ctx) - { - int num_bel_types = 0; - for (auto bel : ctx->getBels()) { - int x, y; - bool gb; - ctx->estimatePosition(bel, x, y, gb); - BelType type = ctx->getBelType(bel); - int type_idx; - if (bel_types.find(type) == bel_types.end()) { - type_idx = num_bel_types++; - bel_types[type] = type_idx; - } else { - type_idx = bel_types.at(type); - } - if (int(fast_bels.size()) < type_idx + 1) - fast_bels.resize(type_idx + 1); - if (int(fast_bels.at(type_idx).size()) < (x + 1)) - fast_bels.at(type_idx).resize(x + 1); - if (int(fast_bels.at(type_idx).at(x).size()) < (y + 1)) - fast_bels.at(type_idx).at(x).resize(y + 1); - max_x = std::max(max_x, x); - max_y = std::max(max_y, y); - fast_bels.at(type_idx).at(x).at(y).push_back(bel); - } - diameter = std::max(max_x, max_y) + 1; - } - - bool place() - { - log_break(); - - 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)); - } - - BelType bel_type = ctx->getBelType(bel); - if (bel_type != ctx->belTypeFromId(cell->type)) { - log_error("Bel \'%s\' of type \'%s\' does not match cell " - "\'%s\' of type \'%s\'", - loc_name.c_str(), ctx->belTypeToId(bel_type).c_str(ctx), cell->name.c_str(ctx), - cell->type.c_str(ctx)); - } - - ctx->bindBel(bel, cell->name, 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)); - - // Sort to-place cells for deterministic initial placement - std::vector autoplaced; - 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); - - // 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())); - - log_info("Running simulated annealing placer.\n"); - - // Calculate wirelength after initial placement - curr_wirelength = 0; - curr_tns = 0; - for (auto &net : ctx->nets) { - wirelen_t wl = get_net_wirelength(ctx, net.second.get(), curr_tns); - wirelengths[net.first] = wl; - curr_wirelength += wl; - } - - int n_no_progress = 0; - double avg_wirelength = curr_wirelength; - temp = 10000; - - // 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, wire length = " - "%.0f, est tns = %.02fns\n", - iter, temp, double(curr_wirelength), curr_tns); - - 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); - } - } - // Heuristic to improve placement on the 8k - if (improved) - n_no_progress = 0; - else - n_no_progress++; - - if (temp <= 1e-3 && n_no_progress >= 5) { - if (iter % 5 != 0) - log_info(" at iteration #%d: temp = %f, wire length = %f\n", iter, temp, double(curr_wirelength)); - break; - } - - double Raccept = double(n_accept) / double(n_move); - - int M = std::max(max_x, max_y) + 1; - - double upper = 0.6, lower = 0.4; - - if (curr_wirelength < 0.95 * avg_wirelength) { - avg_wirelength = 0.8 * avg_wirelength + 0.2 * curr_wirelength; - } else { - if (Raccept >= 0.8) { - temp *= 0.7; - } else if (Raccept > upper) { - if (diameter < M) - diameter++; - else - temp *= 0.9; - } else if (Raccept > lower) { - temp *= 0.95; - } else { - // Raccept < 0.3 - if (diameter > 1) - diameter--; - else - temp *= 0.8; - } - } - // Once cooled below legalise threshold, run legalisation and start requiring - // legal moves only - if (temp < legalise_temp && !require_legal) { - legalise_design(ctx); - require_legal = true; - autoplaced.clear(); - for (auto cell : sorted(ctx->cells)) { - if (cell.second->belStrength < STRENGTH_STRONG) - autoplaced.push_back(cell.second); - } - temp = post_legalise_temp; - diameter *= post_legalise_dia_scale; - ctx->shuffle(autoplaced); - assign_budget(ctx); - } - - // Recalculate total wirelength entirely to avoid rounding errors - // accumulating over time - curr_wirelength = 0; - curr_tns = 0; - for (auto &net : ctx->nets) { - wirelen_t wl = get_net_wirelength(ctx, net.second.get(), curr_tns); - wirelengths[net.first] = wl; - curr_wirelength += wl; - } - } - // Final post-pacement validitiy check - for (auto bel : ctx->getBels()) { - IdString cell = ctx->getBoundBelCell(bel); - if (!ctx->isBelLocationValid(bel)) { - std::string cell_text = "no cell"; - if (cell != IdString()) - cell_text = std::string("cell '") + cell.str(ctx) + "'"; - 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()); - } - } - } - 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); - } - BelType targetType = ctx->belTypeFromId(cell->type); - for (auto bel : ctx->getBels()) { - if (ctx->getBelType(bel) == targetType && (ctx->isValidBelForCell(cell, bel) || !require_legal)) { - 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(); - if (score <= best_ripup_score) { - best_ripup_score = score; - ripup_target = ctx->cells.at(ctx->getBoundBelCell(bel)).get(); - ripup_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->name, 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 std::unordered_set update; - static std::vector> new_lengths; - new_lengths.clear(); - update.clear(); - BelId oldBel = cell->bel; - IdString other = ctx->getBoundBelCell(newBel); - CellInfo *other_cell = nullptr; - if (other != IdString()) { - other_cell = ctx->cells[other].get(); - if (other_cell->belStrength > STRENGTH_WEAK) - return false; - } - wirelen_t new_wirelength = 0, delta; - ctx->unbindBel(oldBel); - if (other != IdString()) { - ctx->unbindBel(newBel); - } - - for (const auto &port : cell->ports) - if (port.second.net != nullptr) - update.insert(port.second.net); - - if (other != IdString()) { - for (const auto &port : other_cell->ports) - if (port.second.net != nullptr) - update.insert(port.second.net); - } - - ctx->bindBel(newBel, cell->name, STRENGTH_WEAK); - - if (other != IdString()) { - ctx->bindBel(oldBel, other_cell->name, STRENGTH_WEAK); - } - if (require_legal) { - if (!ctx->isBelLocationValid(newBel) || ((other != IdString() && !ctx->isBelLocationValid(oldBel)))) { - ctx->unbindBel(newBel); - if (other != IdString()) - ctx->unbindBel(oldBel); - goto swap_fail; - } - } - - new_wirelength = curr_wirelength; - - // Recalculate wirelengths for all nets touched by the peturbation - for (auto net : update) { - new_wirelength -= wirelengths.at(net->name); - float temp_tns = 0; - wirelen_t net_new_wl = get_net_wirelength(ctx, net, temp_tns); - new_wirelength += net_new_wl; - new_lengths.push_back(std::make_pair(net->name, net_new_wl)); - } - delta = new_wirelength - curr_wirelength; - n_move++; - // SA acceptance criterea - if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { - n_accept++; - if (delta < 2) - improved = true; - } else { - if (other != IdString()) - ctx->unbindBel(oldBel); - ctx->unbindBel(newBel); - goto swap_fail; - } - curr_wirelength = new_wirelength; - for (auto new_wl : new_lengths) - wirelengths.at(new_wl.first) = new_wl.second; - - return true; - swap_fail: - ctx->bindBel(oldBel, cell->name, STRENGTH_WEAK); - if (other != IdString()) { - ctx->bindBel(newBel, other, STRENGTH_WEAK); - } - return false; - } - - // Find a random Bel of the correct type for a cell, within the specified - // diameter - BelId random_bel_for_cell(CellInfo *cell) - { - BelType targetType = ctx->belTypeFromId(cell->type); - int x, y; - bool gb; - ctx->estimatePosition(cell->bel, x, y, gb); - while (true) { - int nx = ctx->rng(2 * diameter + 1) + std::max(x - diameter, 0); - int ny = ctx->rng(2 * diameter + 1) + std::max(y - diameter, 0); - int beltype_idx = bel_types.at(targetType); - 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 (locked_bels.find(bel) != locked_bels.end()) - continue; - return bel; - } - } - - Context *ctx; - std::unordered_map wirelengths; - wirelen_t curr_wirelength = std::numeric_limits::max(); - float curr_tns = 0; - float temp = 1000; - bool improved = false; - int n_move, n_accept; - int diameter = 35, max_x = 1, max_y = 1; - std::unordered_map bel_types; - std::vector>>> fast_bels; - std::unordered_set locked_bels; - bool require_legal = false; - const float legalise_temp = 1; - const float post_legalise_temp = 20; - const float post_legalise_dia_scale = 2; -}; - -bool place_design_sa(Context *ctx) -{ - try { - SAPlacer placer(ctx); - placer.place(); - log_info("Checksum: 0x%08x\n", ctx->checksum()); -#ifndef NDEBUG - ctx->check(); -#endif - return true; - } catch (log_execution_error_exception) { -#ifndef NDEBUG - ctx->check(); -#endif - return false; - } -} - -NEXTPNR_NAMESPACE_END diff --git a/common/place_sa.h b/common/place_sa.h deleted file mode 100644 index 1fd8c712..00000000 --- a/common/place_sa.h +++ /dev/null @@ -1,30 +0,0 @@ -/* - * nextpnr -- Next Generation Place and Route - * - * Copyright (C) 2018 Clifford Wolf - * - * 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. - * - */ -#ifndef PLACE_H -#define PLACE_H - -#include "nextpnr.h" - -NEXTPNR_NAMESPACE_BEGIN - -extern bool place_design_sa(Context *ctx); - -NEXTPNR_NAMESPACE_END - -#endif // PLACE_H diff --git a/common/placer1.cc b/common/placer1.cc new file mode 100644 index 00000000..53295a91 --- /dev/null +++ b/common/placer1.cc @@ -0,0 +1,450 @@ +/* + * 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 "log.h" +#include "place_common.h" +#include "place_legaliser.h" +#include "timing.h" +#include "util.h" +NEXTPNR_NAMESPACE_BEGIN + +class SAPlacer +{ + public: + SAPlacer(Context *ctx) : ctx(ctx) + { + int num_bel_types = 0; + for (auto bel : ctx->getBels()) { + int x, y; + bool gb; + ctx->estimatePosition(bel, x, y, gb); + BelType type = ctx->getBelType(bel); + int type_idx; + if (bel_types.find(type) == bel_types.end()) { + type_idx = num_bel_types++; + bel_types[type] = type_idx; + } else { + type_idx = bel_types.at(type); + } + if (int(fast_bels.size()) < type_idx + 1) + fast_bels.resize(type_idx + 1); + if (int(fast_bels.at(type_idx).size()) < (x + 1)) + fast_bels.at(type_idx).resize(x + 1); + if (int(fast_bels.at(type_idx).at(x).size()) < (y + 1)) + fast_bels.at(type_idx).at(x).resize(y + 1); + max_x = std::max(max_x, x); + max_y = std::max(max_y, y); + fast_bels.at(type_idx).at(x).at(y).push_back(bel); + } + diameter = std::max(max_x, max_y) + 1; + } + + bool place() + { + log_break(); + + 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)); + } + + BelType bel_type = ctx->getBelType(bel); + if (bel_type != ctx->belTypeFromId(cell->type)) { + log_error("Bel \'%s\' of type \'%s\' does not match cell " + "\'%s\' of type \'%s\'", + loc_name.c_str(), ctx->belTypeToId(bel_type).c_str(ctx), cell->name.c_str(ctx), + cell->type.c_str(ctx)); + } + + ctx->bindBel(bel, cell->name, 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)); + + // Sort to-place cells for deterministic initial placement + std::vector autoplaced; + 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); + + // 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())); + + log_info("Running simulated annealing placer.\n"); + + // Calculate wirelength after initial placement + curr_wirelength = 0; + curr_tns = 0; + for (auto &net : ctx->nets) { + wirelen_t wl = get_net_wirelength(ctx, net.second.get(), curr_tns); + wirelengths[net.first] = wl; + curr_wirelength += wl; + } + + int n_no_progress = 0; + double avg_wirelength = curr_wirelength; + temp = 10000; + + // 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, wire length = " + "%.0f, est tns = %.02fns\n", + iter, temp, double(curr_wirelength), curr_tns); + + 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); + } + } + // Heuristic to improve placement on the 8k + if (improved) + n_no_progress = 0; + else + n_no_progress++; + + if (temp <= 1e-3 && n_no_progress >= 5) { + if (iter % 5 != 0) + log_info(" at iteration #%d: temp = %f, wire length = %f\n", iter, temp, double(curr_wirelength)); + break; + } + + double Raccept = double(n_accept) / double(n_move); + + int M = std::max(max_x, max_y) + 1; + + double upper = 0.6, lower = 0.4; + + if (curr_wirelength < 0.95 * avg_wirelength) { + avg_wirelength = 0.8 * avg_wirelength + 0.2 * curr_wirelength; + } else { + if (Raccept >= 0.8) { + temp *= 0.7; + } else if (Raccept > upper) { + if (diameter < M) + diameter++; + else + temp *= 0.9; + } else if (Raccept > lower) { + temp *= 0.95; + } else { + // Raccept < 0.3 + if (diameter > 1) + diameter--; + else + temp *= 0.8; + } + } + // Once cooled below legalise threshold, run legalisation and start requiring + // legal moves only + if (temp < legalise_temp && !require_legal) { + legalise_design(ctx); + require_legal = true; + autoplaced.clear(); + for (auto cell : sorted(ctx->cells)) { + if (cell.second->belStrength < STRENGTH_STRONG) + autoplaced.push_back(cell.second); + } + temp = post_legalise_temp; + diameter *= post_legalise_dia_scale; + ctx->shuffle(autoplaced); + assign_budget(ctx); + } + + // Recalculate total wirelength entirely to avoid rounding errors + // accumulating over time + curr_wirelength = 0; + curr_tns = 0; + for (auto &net : ctx->nets) { + wirelen_t wl = get_net_wirelength(ctx, net.second.get(), curr_tns); + wirelengths[net.first] = wl; + curr_wirelength += wl; + } + } + // Final post-pacement validitiy check + for (auto bel : ctx->getBels()) { + IdString cell = ctx->getBoundBelCell(bel); + if (!ctx->isBelLocationValid(bel)) { + std::string cell_text = "no cell"; + if (cell != IdString()) + cell_text = std::string("cell '") + cell.str(ctx) + "'"; + 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()); + } + } + } + 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); + } + BelType targetType = ctx->belTypeFromId(cell->type); + for (auto bel : ctx->getBels()) { + if (ctx->getBelType(bel) == targetType && (ctx->isValidBelForCell(cell, bel) || !require_legal)) { + 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(); + if (score <= best_ripup_score) { + best_ripup_score = score; + ripup_target = ctx->cells.at(ctx->getBoundBelCell(bel)).get(); + ripup_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->name, 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 std::unordered_set update; + static std::vector> new_lengths; + new_lengths.clear(); + update.clear(); + BelId oldBel = cell->bel; + IdString other = ctx->getBoundBelCell(newBel); + CellInfo *other_cell = nullptr; + if (other != IdString()) { + other_cell = ctx->cells[other].get(); + if (other_cell->belStrength > STRENGTH_WEAK) + return false; + } + wirelen_t new_wirelength = 0, delta; + ctx->unbindBel(oldBel); + if (other != IdString()) { + ctx->unbindBel(newBel); + } + + for (const auto &port : cell->ports) + if (port.second.net != nullptr) + update.insert(port.second.net); + + if (other != IdString()) { + for (const auto &port : other_cell->ports) + if (port.second.net != nullptr) + update.insert(port.second.net); + } + + ctx->bindBel(newBel, cell->name, STRENGTH_WEAK); + + if (other != IdString()) { + ctx->bindBel(oldBel, other_cell->name, STRENGTH_WEAK); + } + if (require_legal) { + if (!ctx->isBelLocationValid(newBel) || ((other != IdString() && !ctx->isBelLocationValid(oldBel)))) { + ctx->unbindBel(newBel); + if (other != IdString()) + ctx->unbindBel(oldBel); + goto swap_fail; + } + } + + new_wirelength = curr_wirelength; + + // Recalculate wirelengths for all nets touched by the peturbation + for (auto net : update) { + new_wirelength -= wirelengths.at(net->name); + float temp_tns = 0; + wirelen_t net_new_wl = get_net_wirelength(ctx, net, temp_tns); + new_wirelength += net_new_wl; + new_lengths.push_back(std::make_pair(net->name, net_new_wl)); + } + delta = new_wirelength - curr_wirelength; + n_move++; + // SA acceptance criterea + if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { + n_accept++; + if (delta < 2) + improved = true; + } else { + if (other != IdString()) + ctx->unbindBel(oldBel); + ctx->unbindBel(newBel); + goto swap_fail; + } + curr_wirelength = new_wirelength; + for (auto new_wl : new_lengths) + wirelengths.at(new_wl.first) = new_wl.second; + + return true; + swap_fail: + ctx->bindBel(oldBel, cell->name, STRENGTH_WEAK); + if (other != IdString()) { + ctx->bindBel(newBel, other, STRENGTH_WEAK); + } + return false; + } + + // Find a random Bel of the correct type for a cell, within the specified + // diameter + BelId random_bel_for_cell(CellInfo *cell) + { + BelType targetType = ctx->belTypeFromId(cell->type); + int x, y; + bool gb; + ctx->estimatePosition(cell->bel, x, y, gb); + while (true) { + int nx = ctx->rng(2 * diameter + 1) + std::max(x - diameter, 0); + int ny = ctx->rng(2 * diameter + 1) + std::max(y - diameter, 0); + int beltype_idx = bel_types.at(targetType); + 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 (locked_bels.find(bel) != locked_bels.end()) + continue; + return bel; + } + } + + Context *ctx; + std::unordered_map wirelengths; + wirelen_t curr_wirelength = std::numeric_limits::max(); + float curr_tns = 0; + float temp = 1000; + bool improved = false; + int n_move, n_accept; + int diameter = 35, max_x = 1, max_y = 1; + std::unordered_map bel_types; + std::vector>>> fast_bels; + std::unordered_set locked_bels; + bool require_legal = false; + const float legalise_temp = 1; + const float post_legalise_temp = 20; + const float post_legalise_dia_scale = 2; +}; + +bool placer1(Context *ctx) +{ + try { + SAPlacer placer(ctx); + placer.place(); + log_info("Checksum: 0x%08x\n", ctx->checksum()); +#ifndef NDEBUG + ctx->check(); +#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 new file mode 100644 index 00000000..477fae56 --- /dev/null +++ b/common/placer1.h @@ -0,0 +1,30 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Clifford Wolf + * + * 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. + * + */ +#ifndef PLACE_H +#define PLACE_H + +#include "nextpnr.h" + +NEXTPNR_NAMESPACE_BEGIN + +extern bool placer1(Context *ctx); + +NEXTPNR_NAMESPACE_END + +#endif // PLACE_H -- cgit v1.2.3