diff options
author | Keith Rothman <537074+litghost@users.noreply.github.com> | 2021-01-28 15:40:26 -0800 |
---|---|---|
committer | Keith Rothman <537074+litghost@users.noreply.github.com> | 2021-02-02 07:34:56 -0800 |
commit | 2285c8dbbdbc5b7e718fa849952c560bef69a8fc (patch) | |
tree | 0bfeaff2dd647b0139e19ca97c50d374f4c45fa7 /common | |
parent | efc98c517eb1d2eb4a8ecc2ae82e770aaa1a0edd (diff) | |
download | nextpnr-2285c8dbbdbc5b7e718fa849952c560bef69a8fc.tar.gz nextpnr-2285c8dbbdbc5b7e718fa849952c560bef69a8fc.tar.bz2 nextpnr-2285c8dbbdbc5b7e718fa849952c560bef69a8fc.zip |
Initial refactoring of placer API.
Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com>
Diffstat (limited to 'common')
-rw-r--r-- | common/fast_bels.h | 105 | ||||
-rw-r--r-- | common/place_common.cc | 4 | ||||
-rw-r--r-- | common/placer1.cc | 47 | ||||
-rw-r--r-- | common/placer_heap.cc | 46 | ||||
-rw-r--r-- | common/timing_opt.cc | 2 |
5 files changed, 136 insertions, 68 deletions
diff --git a/common/fast_bels.h b/common/fast_bels.h new file mode 100644 index 00000000..1b769baf --- /dev/null +++ b/common/fast_bels.h @@ -0,0 +1,105 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Clifford Wolf <clifford@symbioticeda.com> + * Copyright (C) 2018 David Shah <david@symbioticeda.com> + * + * 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. + * + */ + +#pragma once + +#include "nextpnr.h" +#include <cstddef> + +NEXTPNR_NAMESPACE_BEGIN + +// FastBels is a lookup class that provides a fast lookup for finding BELs +// that support a given cell type. +struct FastBels { + struct CellTypeData { + size_t cell_type_index; + size_t number_of_possible_bels; + }; + + FastBels(Context *ctx, int minBelsForGridPick) : ctx(ctx), minBelsForGridPick(minBelsForGridPick) {} + + void addCellType(IdString cell_type) { + auto iter = cell_types.find(cell_type); + if(iter != cell_types.end()) { + // This cell type has already been added to the fast BEL lookup. + return; + } + + size_t type_idx = cell_types.size(); + auto &cell_type_data = cell_types[cell_type]; + cell_type_data.cell_type_index = type_idx; + + fast_bels.resize(type_idx + 1); + auto &bel_data = fast_bels.at(type_idx); + + for (auto bel : ctx->getBels()) { + if(!ctx->isValidBelForCellType(cell_type, bel)) { + continue; + } + + cell_type_data.number_of_possible_bels += 1; + } + + for (auto bel : ctx->getBels()) { + if(!ctx->checkBelAvail(bel)) { + continue; + } + + Loc loc = ctx->getBelLocation(bel); + if (minBelsForGridPick >= 0 && cell_type_data.number_of_possible_bels < minBelsForGridPick) { + loc.x = loc.y = 0; + } + + if (int(bel_data.size()) < (loc.x + 1)) { + bel_data.resize(loc.x + 1); + } + + if (int(bel_data.at(loc.x).size()) < (loc.y + 1)) { + bel_data.at(loc.x).resize(loc.y + 1); + } + + bel_data.at(loc.x).at(loc.y).push_back(bel); + } + } + + typedef std::vector<std::vector<std::vector<BelId>>> FastBelsData; + + size_t getBelsForCellType(IdString cell_type, FastBelsData **data) { + auto iter = cell_types.find(cell_type); + if(iter == cell_types.end()) { + addCellType(cell_type); + iter = cell_types.find(cell_type); + NPNR_ASSERT(iter != cell_types.end()); + } + + auto cell_type_data = iter->second; + + *data = &fast_bels.at(cell_type_data.cell_type_index); + return cell_type_data.number_of_possible_bels; + } + + Context *ctx; + int minBelsForGridPick; + + std::unordered_map<IdString, CellTypeData> cell_types; + std::vector<FastBelsData> fast_bels; +}; + +NEXTPNR_NAMESPACE_END diff --git a/common/place_common.cc b/common/place_common.cc index cb9799b5..fb973e2c 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -118,7 +118,7 @@ bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality) } IdString targetType = cell->type; for (auto bel : ctx->getBels()) { - if (ctx->getBelType(bel) == targetType && (!require_legality || ctx->isValidBelForCell(cell, bel))) { + if (ctx->isValidBelForCellType(targetType, bel) && (!require_legality || ctx->isValidBelForCell(cell, bel))) { if (ctx->checkBelAvail(bel)) { wirelen_t wirelen = get_cell_metric_at_bel(ctx, cell, bel, MetricType::COST); if (iters >= 4) @@ -229,7 +229,7 @@ class ConstraintLegaliseWorker if (locBel == BelId()) { return false; } - if (ctx->getBelType(locBel) != cell->type) { + if (!ctx->isValidBelForCellType(cell->type, locBel)) { return false; } if (!ctx->checkBelAvail(locBel)) { diff --git a/common/placer1.cc b/common/placer1.cc index 49f556f7..e2c3dd22 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -43,6 +43,7 @@ #include "place_common.h" #include "timing.h" #include "util.h" +#include "fast_bels.h" namespace std { template <> struct hash<std::pair<NEXTPNR_NAMESPACE_PREFIX IdString, std::size_t>> @@ -75,33 +76,12 @@ class SAPlacer }; public: - SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), cfg(cfg) + SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), fast_bels(ctx, cfg.minBelsForGridPick), 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<int, int>(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; @@ -170,13 +150,14 @@ class SAPlacer loc_name.c_str(), cell->name.c_str(ctx)); } - IdString bel_type = ctx->getBelType(bel); - if (bel_type != cell->type) { + if (!ctx->isValidBelForCellType(cell->type, bel)) { + IdString bel_type = ctx->getBelType(bel); 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)) { + IdString bel_type = ctx->getBelType(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)); @@ -452,7 +433,7 @@ class SAPlacer IdString targetType = cell->type; auto proc_bel = [&](BelId bel) { - if (ctx->getBelType(bel) == targetType && ctx->isValidBelForCell(cell, bel)) { + if (ctx->isValidBelForCellType(targetType, bel) && ctx->isValidBelForCell(cell, bel)) { if (ctx->checkBelAvail(bel)) { uint64_t score = ctx->rng64(); if (score <= best_score) { @@ -651,7 +632,7 @@ class SAPlacer BelId targetBel = ctx->getBelByLocation(targetLoc); if (targetBel == BelId()) return false; - if (ctx->getBelType(targetBel) != cell->type) + if (!ctx->isValidBelForCellType(cell->type, targetBel)) 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 @@ -733,15 +714,15 @@ class SAPlacer 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) + FastBels::FastBelsData *bel_data; + auto type_cnt = fast_bels.getBelsForCellType(targetType, &bel_data); + if (cfg.minBelsForGridPick >= 0 && type_cnt < cfg.minBelsForGridPick) nx = ny = 0; - if (nx >= int(fast_bels.at(beltype_idx).size())) + if (nx >= int(bel_data->size())) continue; - if (ny >= int(fast_bels.at(beltype_idx).at(nx).size())) + if (ny >= int(bel_data->at(nx).size())) continue; - const auto &fb = fast_bels.at(beltype_idx).at(nx).at(ny); + const auto &fb = bel_data->at(nx).at(ny); if (fb.size() == 0) continue; BelId bel = fb.at(ctx->rng(int(fb.size()))); @@ -1217,7 +1198,7 @@ class SAPlacer 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; + FastBels fast_bels; std::unordered_set<BelId> locked_bels; std::vector<NetInfo *> net_by_udata; std::vector<decltype(NetInfo::udata)> old_udata; diff --git a/common/placer_heap.cc b/common/placer_heap.cc index f10d4139..4f71577f 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -318,7 +318,7 @@ class HeAPPlacer PlacerHeapCfg cfg; int max_x = 0, max_y = 0; - std::vector<std::vector<std::vector<std::vector<BelId>>>> fast_bels; + FastBels fast_bels; std::unordered_map<IdString, std::tuple<int, int>> bel_types; // For fast handling of heterogeneity during initial placement without full legalisation, @@ -384,13 +384,14 @@ class HeAPPlacer loc_name.c_str(), cell->name.c_str(ctx)); } - IdString bel_type = ctx->getBelType(bel); - if (bel_type != cell->type) { + if (!ctx->isValidBelForCellType(cell->type, bel)) { + IdString bel_type = ctx->getBelType(bel); 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)) { + IdString bel_type = ctx->getBelType(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)); @@ -413,31 +414,12 @@ class HeAPPlacer // Construct the fast_bels, nearest_row_with_bel and nearest_col_with_bel void build_fast_bels() { - - 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<int, int>(num_bel_types++, 1); - } else { - std::get<1>(bel_types.at(type))++; - } - } for (auto bel : ctx->getBels()) { if (!ctx->checkBelAvail(bel)) continue; Loc loc = ctx->getBelLocation(bel); - IdString type = ctx->getBelType(bel); - int type_idx = std::get<0>(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()) < (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); } nearest_row_with_bel.resize(num_bel_types, std::vector<int>(max_y + 1, -1)); @@ -814,8 +796,8 @@ class HeAPPlacer if (ci->bel != BelId()) continue; // log_info(" Legalising %s (%s)\n", top.second.c_str(ctx), ci->type.c_str(ctx)); - int bt = std::get<0>(bel_types.at(ci->type)); - auto &fb = fast_bels.at(bt); + FastBels::FastBelsData *fb; + fast_bels.getBelsForCellType(ci->type, &fb); int radius = 0; int iter = 0; int iter_at_radius = 0; @@ -864,13 +846,13 @@ class HeAPPlacer while (radius < std::max(max_x, max_y)) { for (int x = std::max(0, cell_locs.at(ci->name).x - radius); x <= std::min(max_x, cell_locs.at(ci->name).x + radius); x++) { - if (x >= int(fb.size())) + if (x >= int(fb->size())) break; for (int y = std::max(0, cell_locs.at(ci->name).y - radius); y <= std::min(max_y, cell_locs.at(ci->name).y + radius); y++) { - if (y >= int(fb.at(x).size())) + if (y >= int(fb->at(x).size())) break; - if (fb.at(x).at(y).size() > 0) + if (fb->at(x).at(y).size() > 0) goto notempty; } } @@ -888,11 +870,11 @@ class HeAPPlacer // ny = nearest_row_with_bel.at(bt).at(ny); // nx = nearest_col_with_bel.at(bt).at(nx); - if (nx >= int(fb.size())) + if (nx >= int(fb->size())) continue; - if (ny >= int(fb.at(nx).size())) + if (ny >= int(fb->at(nx).size())) continue; - if (fb.at(nx).at(ny).empty()) + if (fb->at(nx).at(ny).empty()) continue; int need_to_explore = 2 * radius; @@ -912,7 +894,7 @@ class HeAPPlacer } if (ci->constr_children.empty() && !ci->constr_abs_z) { - for (auto sz : fb.at(nx).at(ny)) { + for (auto sz : fb->at(nx).at(ny)) { if (ci->region != nullptr && ci->region->constr_bels && !ci->region->bels.count(sz)) continue; if (ctx->checkBelAvail(sz) || (radius > ripup_radius || ctx->rng(20000) < 10)) { @@ -962,7 +944,7 @@ class HeAPPlacer } } } else { - for (auto sz : fb.at(nx).at(ny)) { + for (auto sz : fb->at(nx).at(ny)) { Loc loc = ctx->getBelLocation(sz); if (ci->constr_abs_z && loc.z != ci->constr_z) continue; diff --git a/common/timing_opt.cc b/common/timing_opt.cc index eae15fb2..025084b7 100644 --- a/common/timing_opt.cc +++ b/common/timing_opt.cc @@ -215,7 +215,7 @@ class TimingOptimiser std::vector<BelId> free_bels_at_loc; std::vector<BelId> bound_bels_at_loc; for (auto bel : ctx->getBelsByTile(curr_loc.x + dx, curr_loc.y + dy)) { - if (ctx->getBelType(bel) != cell->type) + if (!ctx->isValidBelForCellType(cell->type, bel)) continue; CellInfo *bound = ctx->getBoundBelCell(bel); if (bound == nullptr) { |