diff options
Diffstat (limited to 'common/placer_heap.cc')
| -rw-r--r-- | common/placer_heap.cc | 358 |
1 files changed, 205 insertions, 153 deletions
diff --git a/common/placer_heap.cc b/common/placer_heap.cc index f10d4139..d149a5b0 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -44,12 +44,14 @@ #include <queue> #include <tuple> #include <unordered_map> +#include "fast_bels.h" #include "log.h" #include "nextpnr.h" #include "place_common.h" #include "placer1.h" #include "timing.h" #include "util.h" + NEXTPNR_NAMESPACE_BEGIN namespace { @@ -136,7 +138,10 @@ template <typename T> struct EquationSystem class HeAPPlacer { public: - HeAPPlacer(Context *ctx, PlacerHeapCfg cfg) : ctx(ctx), cfg(cfg) { Eigen::initParallel(); } + HeAPPlacer(Context *ctx, PlacerHeapCfg cfg) : ctx(ctx), cfg(cfg), fast_bels(ctx, /*check_bel_available=*/true, -1) + { + Eigen::initParallel(); + } bool place() { @@ -175,24 +180,26 @@ class HeAPPlacer std::vector<std::tuple<CellInfo *, BelId, PlaceStrength>> solution; - std::vector<std::unordered_set<IdString>> heap_runs; - std::unordered_set<IdString> all_celltypes; - std::unordered_map<IdString, int> ct_count; + std::vector<std::unordered_set<BelBucketId>> heap_runs; + std::unordered_set<BelBucketId> all_buckets; + std::unordered_map<BelBucketId, int> bucket_count; for (auto cell : place_cells) { - if (!all_celltypes.count(cell->type)) { - heap_runs.push_back(std::unordered_set<IdString>{cell->type}); - all_celltypes.insert(cell->type); + BelBucketId bucket = ctx->getBelBucketForCellType(cell->type); + if (!all_buckets.count(bucket)) { + heap_runs.push_back(std::unordered_set<BelBucketId>{bucket}); + all_buckets.insert(bucket); } - ct_count[cell->type]++; + bucket_count[bucket]++; } // If more than 98% of cells are one cell type, always solve all at once // Otherwise, follow full HeAP strategy of rotate&all - for (auto &c : ct_count) + for (auto &c : bucket_count) { if (c.second >= 0.98 * int(place_cells.size())) { heap_runs.clear(); break; } + } if (cfg.placeAllAtOnce) { // Never want to deal with LUTs, FFs, MUXFxs separately, @@ -201,7 +208,7 @@ class HeAPPlacer heap_runs.clear(); } - heap_runs.push_back(all_celltypes); + heap_runs.push_back(all_buckets); // The main HeAP placer loop log_info("Running main analytical placer.\n"); while (stalled < 5 && (solved_hpwl <= legal_hpwl * 0.8)) { @@ -238,7 +245,7 @@ class HeAPPlacer for (auto type : sorted(run)) if (std::all_of(cfg.cellGroups.begin(), cfg.cellGroups.end(), - [type](const std::unordered_set<IdString> &grp) { return !grp.count(type); })) + [type](const std::unordered_set<BelBucketId> &grp) { return !grp.count(type); })) CutSpreader(this, {type}).run(); update_all_chains(); @@ -248,8 +255,10 @@ class HeAPPlacer legal_hpwl = total_hpwl(); auto run_stopt = std::chrono::high_resolution_clock::now(); + + IdString bucket_name = ctx->getBelBucketName(*run.begin()); log_info(" at iteration #%d, type %s: wirelen solved = %d, spread = %d, legal = %d; time = %.02fs\n", - iter + 1, (run.size() > 1 ? "ALL" : run.begin()->c_str(ctx)), int(solved_hpwl), + iter + 1, (run.size() > 1 ? "ALL" : bucket_name.c_str(ctx)), int(solved_hpwl), int(spread_hpwl), int(legal_hpwl), std::chrono::duration<double>(run_stopt - run_startt).count()); } @@ -318,16 +327,9 @@ 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, - // for each Bel type this goes from x or y to the nearest x or y where a Bel of a given type exists - // This is particularly important for the iCE40 architecture, where multipliers and BRAM only exist at the - // edges and corners respectively - std::vector<std::vector<int>> nearest_row_with_bel; - std::vector<std::vector<int>> nearest_col_with_bel; - struct BoundingBox { // Actual bounding box @@ -384,13 +386,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)); @@ -410,66 +413,30 @@ class HeAPPlacer ctx->yield(); } - // 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)); - nearest_col_with_bel.resize(num_bel_types, std::vector<int>(max_x + 1, -1)); - for (auto bel : ctx->getBels()) { - if (!ctx->checkBelAvail(bel)) - continue; - Loc loc = ctx->getBelLocation(bel); - int type_idx = std::get<0>(bel_types.at(ctx->getBelType(bel))); - auto &nr = nearest_row_with_bel.at(type_idx), &nc = nearest_col_with_bel.at(type_idx); - // Traverse outwards through nearest_row_with_bel and nearest_col_with_bel, stopping once - // another row/col is already recorded as being nearer - for (int x = loc.x; x <= max_x; x++) { - if (nc.at(x) != -1 && std::abs(loc.x - nc.at(x)) <= (x - loc.x)) - break; - nc.at(x) = loc.x; - } - for (int x = loc.x - 1; x >= 0; x--) { - if (nc.at(x) != -1 && std::abs(loc.x - nc.at(x)) <= (loc.x - x)) - break; - nc.at(x) = loc.x; - } - for (int y = loc.y; y <= max_y; y++) { - if (nr.at(y) != -1 && std::abs(loc.y - nr.at(y)) <= (y - loc.y)) - break; - nr.at(y) = loc.y; - } - for (int y = loc.y - 1; y >= 0; y--) { - if (nr.at(y) != -1 && std::abs(loc.y - nr.at(y)) <= (loc.y - y)) - break; - nr.at(y) = loc.y; - } + std::unordered_set<IdString> cell_types_in_use; + std::unordered_set<BelBucketId> buckets_in_use; + for (auto cell : sorted(ctx->cells)) { + IdString cell_type = cell.second->type; + cell_types_in_use.insert(cell_type); + BelBucketId bucket = ctx->getBelBucketForCellType(cell_type); + buckets_in_use.insert(bucket); + } + + for (auto cell_type : cell_types_in_use) { + fast_bels.addCellType(cell_type); + } + for (auto bucket : buckets_in_use) { + fast_bels.addBelBucket(bucket); } // Determine bounding boxes of region constraints @@ -523,15 +490,30 @@ class HeAPPlacer // FIXME: Are there better approaches to the initial placement (e.g. greedy?) void seed_placement() { + std::unordered_set<IdString> cell_types; + for (const auto &cell : ctx->cells) { + cell_types.insert(cell.second->type); + } + + std::unordered_set<BelId> bels_used; std::unordered_map<IdString, std::deque<BelId>> available_bels; + for (auto bel : ctx->getBels()) { - if (!ctx->checkBelAvail(bel)) + if (!ctx->checkBelAvail(bel)) { continue; - available_bels[ctx->getBelType(bel)].push_back(bel); + } + + for (auto cell_type : cell_types) { + if (ctx->isValidBelForCellType(cell_type, bel)) { + available_bels[cell_type].push_back(bel); + } + } } + for (auto &t : available_bels) { ctx->shuffle(t.second.begin(), t.second.end()); } + for (auto cell : sorted(ctx->cells)) { CellInfo *ci = cell.second; if (ci->bel != BelId()) { @@ -544,21 +526,48 @@ class HeAPPlacer bool placed = false; int attempt_count = 0; 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)); ++attempt_count; - if (attempt_count > 25000) + if (attempt_count > 25000) { log_error("Unable to find a placement location for cell '%s'\n", ci->name.c_str(ctx)); - BelId bel = available_bels.at(ci->type).back(); - available_bels.at(ci->type).pop_back(); + } + + // Make sure this cell type is in the available BEL map at + // all. + if (!available_bels.count(ci->type)) { + log_error("Unable to place cell '%s', no BELs remaining to implement cell type '%s'\n", + ci->name.c_str(ctx), ci->type.c_str(ctx)); + } + + // Find an unused BEL from bels_for_cell_type. + auto &bels_for_cell_type = available_bels.at(ci->type); + BelId bel; + while (true) { + if (bels_for_cell_type.empty()) { + log_error("Unable to place cell '%s', no BELs remaining to implement cell type '%s'\n", + ci->name.c_str(ctx), ci->type.c_str(ctx)); + } + + BelId candidate_bel = bels_for_cell_type.back(); + bels_for_cell_type.pop_back(); + if (bels_used.count(candidate_bel)) { + // candidate_bel has already been used by another + // cell type, skip it. + continue; + } + + bel = candidate_bel; + break; + } + 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) && !cfg.ioBufTypes.count(ci->type)) { + bels_used.insert(bel); place_cells.push_back(ci); placed = true; } else { @@ -566,6 +575,7 @@ class HeAPPlacer ctx->bindBel(bel, ci, STRENGTH_STRONG); cell_locs[cell.first].locked = true; placed = true; + bels_used.insert(bel); } else { available_bels.at(ci->type).push_front(bel); } @@ -576,7 +586,7 @@ class HeAPPlacer } // Setup the cells to be solved, returns the number of rows - int setup_solve_cells(std::unordered_set<IdString> *celltypes = nullptr) + int setup_solve_cells(std::unordered_set<BelBucketId> *buckets = nullptr) { int row = 0; solve_cells.clear(); @@ -585,7 +595,7 @@ class HeAPPlacer cell.second->udata = dont_solve; // Then update cells to be placed, which excludes cell children for (auto cell : place_cells) { - if (celltypes && !celltypes->count(cell->type)) + if (buckets && !buckets->count(ctx->getBelBucketForCellType(cell->type))) continue; cell->udata = row++; solve_cells.push_back(cell); @@ -814,8 +824,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 +874,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; } } @@ -885,14 +895,11 @@ class HeAPPlacer if (ny < 0 || ny > max_y) continue; - // 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 +919,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 +969,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; @@ -979,7 +986,7 @@ class HeAPPlacer if (vc->region != nullptr && vc->region->constr_bels && !vc->region->bels.count(target)) goto fail; CellInfo *bound; - if (target == BelId() || ctx->getBelType(target) != vc->type) + if (target == BelId() || !ctx->isValidBelForCellType(vc->type, target)) goto fail; bound = ctx->getBoundBelCell(target); // Chains cannot overlap @@ -1081,13 +1088,17 @@ class HeAPPlacer class CutSpreader { public: - CutSpreader(HeAPPlacer *p, const std::unordered_set<IdString> &beltype) : p(p), ctx(p->ctx), beltype(beltype) + CutSpreader(HeAPPlacer *p, const std::unordered_set<BelBucketId> &buckets) : p(p), ctx(p->ctx), buckets(buckets) { - int idx = 0; - for (IdString type : sorted(beltype)) { - type_index[type] = idx; - fb.emplace_back(&(p->fast_bels.at(std::get<0>(p->bel_types.at(type))))); + // Get fast BELs data for all buckets being Cut/Spread. + size_t idx = 0; + for (BelBucketId bucket : sorted(buckets)) { + type_index[bucket] = idx; + FastBels::FastBelsData *fast_bels; + p->fast_bels.getBelsForBelBucket(bucket, &fast_bels); + fb.push_back(fast_bels); ++idx; + NPNR_ASSERT(fb.size() == idx); } } static int seq; @@ -1169,8 +1180,8 @@ class HeAPPlacer private: HeAPPlacer *p; Context *ctx; - std::unordered_set<IdString> beltype; - std::unordered_map<IdString, int> type_index; + std::unordered_set<BelBucketId> buckets; + std::unordered_map<BelBucketId, size_t> type_index; std::vector<std::vector<std::vector<int>>> occupancy; std::vector<std::vector<int>> groups; std::vector<std::vector<ChainExtent>> chaines; @@ -1192,16 +1203,23 @@ class HeAPPlacer return int(fb.at(type)->at(x).at(y).size()); } + bool is_cell_fixed(const CellInfo &cell) const + { + return buckets.count(ctx->getBelBucketForCellType(cell.type)) == 0; + } + + size_t cell_index(const CellInfo &cell) const { return type_index.at(ctx->getBelBucketForCellType(cell.type)); } + void init() { occupancy.resize(p->max_x + 1, - std::vector<std::vector<int>>(p->max_y + 1, std::vector<int>(beltype.size(), 0))); + std::vector<std::vector<int>>(p->max_y + 1, std::vector<int>(buckets.size(), 0))); groups.resize(p->max_x + 1, std::vector<int>(p->max_y + 1, -1)); chaines.resize(p->max_x + 1, std::vector<ChainExtent>(p->max_y + 1)); cells_at_location.resize(p->max_x + 1, std::vector<std::vector<CellInfo *>>(p->max_y + 1)); for (int x = 0; x <= p->max_x; x++) for (int y = 0; y <= p->max_y; y++) { - for (int t = 0; t < int(beltype.size()); t++) { + for (int t = 0; t < int(buckets.size()); t++) { occupancy.at(x).at(y).at(t) = 0; } groups.at(x).at(y) = -1; @@ -1219,55 +1237,77 @@ class HeAPPlacer } }; - for (auto &cell : p->cell_locs) { - if (!beltype.count(ctx->cells.at(cell.first)->type)) + for (auto &cell_loc : p->cell_locs) { + IdString cell_name = cell_loc.first; + const CellInfo &cell = *ctx->cells.at(cell_name); + const CellLocation &loc = cell_loc.second; + if (is_cell_fixed(cell)) { continue; - if (ctx->cells.at(cell.first)->belStrength > STRENGTH_STRONG) + } + + if (cell.belStrength > STRENGTH_STRONG) { continue; - occupancy.at(cell.second.x).at(cell.second.y).at(type_index.at(ctx->cells.at(cell.first)->type))++; + } + + occupancy.at(cell_loc.second.x).at(cell_loc.second.y).at(cell_index(cell))++; + // Compute ultimate extent of each chain root - if (p->chain_root.count(cell.first)) { - set_chain_ext(p->chain_root.at(cell.first)->name, cell.second.x, cell.second.y); - } else if (!ctx->cells.at(cell.first)->constr_children.empty()) { - set_chain_ext(cell.first, cell.second.x, cell.second.y); + if (p->chain_root.count(cell_name)) { + set_chain_ext(p->chain_root.at(cell_name)->name, loc.x, loc.y); + } else if (!ctx->cells.at(cell_name)->constr_children.empty()) { + set_chain_ext(cell_name, loc.x, loc.y); } } - for (auto &cell : p->cell_locs) { - if (!beltype.count(ctx->cells.at(cell.first)->type)) + + for (auto &cell_loc : p->cell_locs) { + IdString cell_name = cell_loc.first; + const CellInfo &cell = *ctx->cells.at(cell_name); + const CellLocation &loc = cell_loc.second; + if (is_cell_fixed(cell)) { continue; - // Transfer chain extents to the actual chaines structure + } + + // Transfer chain extents to the actual chains structure ChainExtent *ce = nullptr; - if (p->chain_root.count(cell.first)) - ce = &(cell_extents.at(p->chain_root.at(cell.first)->name)); - else if (!ctx->cells.at(cell.first)->constr_children.empty()) - ce = &(cell_extents.at(cell.first)); + if (p->chain_root.count(cell_name)) { + ce = &(cell_extents.at(p->chain_root.at(cell_name)->name)); + } else if (!ctx->cells.at(cell_name)->constr_children.empty()) { + ce = &(cell_extents.at(cell_name)); + } + if (ce) { - auto &lce = chaines.at(cell.second.x).at(cell.second.y); + auto &lce = chaines.at(loc.x).at(loc.y); lce.x0 = std::min(lce.x0, ce->x0); lce.y0 = std::min(lce.y0, ce->y0); lce.x1 = std::max(lce.x1, ce->x1); lce.y1 = std::max(lce.y1, ce->y1); } } + for (auto cell : p->solve_cells) { - if (!beltype.count(cell->type)) + if (is_cell_fixed(*cell)) { continue; + } + cells_at_location.at(p->cell_locs.at(cell->name).x).at(p->cell_locs.at(cell->name).y).push_back(cell); } } + void merge_regions(SpreaderRegion &merged, SpreaderRegion &mergee) { // Prevent grow_region from recursing while doing this - for (int x = mergee.x0; x <= mergee.x1; x++) + for (int x = mergee.x0; x <= mergee.x1; x++) { for (int y = mergee.y0; y <= mergee.y1; y++) { // log_info("%d %d\n", groups.at(x).at(y), mergee.id); NPNR_ASSERT(groups.at(x).at(y) == mergee.id); groups.at(x).at(y) = merged.id; - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { merged.cells.at(t) += occ_at(x, y, t); merged.bels.at(t) += bels_at(x, y, t); } } + } + merged_regions.insert(mergee.id); grow_region(merged, mergee.x0, mergee.y0, mergee.x1, mergee.y1); } @@ -1286,11 +1326,12 @@ class HeAPPlacer auto process_location = [&](int x, int y) { // Merge with any overlapping regions if (groups.at(x).at(y) == -1) { - for (int t = 0; t < int(beltype.size()); t++) { + for (size_t t = 0; t < buckets.size(); t++) { r.bels.at(t) += bels_at(x, y, t); r.cells.at(t) += occ_at(x, y, t); } } + if (groups.at(x).at(y) != -1 && groups.at(x).at(y) != r.id) merge_regions(r, regions.at(groups.at(x).at(y))); groups.at(x).at(y) = r.id; @@ -1320,12 +1361,13 @@ class HeAPPlacer if (groups.at(x).at(y) != -1) continue; bool overutilised = false; - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { if (occ_at(x, y, t) > bels_at(x, y, t)) { overutilised = true; break; } } + if (!overutilised) continue; // log_info("%d %d %d\n", x, y, occ_at(x, y)); @@ -1335,7 +1377,7 @@ class HeAPPlacer reg.id = id; reg.x0 = reg.x1 = x; reg.y0 = reg.y1 = y; - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { reg.bels.push_back(bels_at(x, y, t)); reg.cells.push_back(occ_at(x, y, t)); } @@ -1352,7 +1394,7 @@ class HeAPPlacer if (reg.x1 < p->max_x) { bool over_occ_x = false; for (int y1 = reg.y0; y1 <= reg.y1; y1++) { - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { if (occ_at(reg.x1 + 1, y1, t) > bels_at(reg.x1 + 1, y1, t)) { over_occ_x = true; break; @@ -1368,7 +1410,7 @@ class HeAPPlacer if (reg.y1 < p->max_y) { bool over_occ_y = false; for (int x1 = reg.x0; x1 <= reg.x1; x1++) { - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { if (occ_at(x1, reg.y1 + 1, t) > bels_at(x1, reg.y1 + 1, t)) { over_occ_y = true; break; @@ -1430,10 +1472,12 @@ class HeAPPlacer } } if (!changed) { - for (auto bt : sorted(beltype)) { - if (reg.cells > reg.bels) + for (auto bucket : sorted(buckets)) { + if (reg.cells > reg.bels) { + IdString bucket_name = ctx->getBelBucketName(bucket); log_error("Failed to expand region (%d, %d) |_> (%d, %d) of %d %ss\n", reg.x0, reg.y0, - reg.x1, reg.y1, reg.cells.at(type_index.at(bt)), bt.c_str(ctx)); + reg.x1, reg.y1, reg.cells.at(type_index.at(bucket)), bucket_name.c_str(ctx)); + } } break; } @@ -1454,7 +1498,7 @@ class HeAPPlacer for (int x = r.x0; x <= r.x1; x++) { for (int y = r.y0; y <= r.y1; y++) { std::copy(cal.at(x).at(y).begin(), cal.at(x).at(y).end(), std::back_inserter(cut_cells)); - for (size_t t = 0; t < beltype.size(); t++) + for (size_t t = 0; t < buckets.size(); t++) total_bels += bels_at(x, y, t); } } @@ -1506,26 +1550,34 @@ class HeAPPlacer int trimmed_l = dir ? r.y0 : r.x0, trimmed_r = dir ? r.y1 : r.x1; while (trimmed_l < (dir ? r.y1 : r.x1)) { bool have_bels = false; - for (int i = dir ? r.x0 : r.y0; i <= (dir ? r.x1 : r.y1); i++) - for (size_t t = 0; t < beltype.size(); t++) + for (int i = dir ? r.x0 : r.y0; i <= (dir ? r.x1 : r.y1); i++) { + for (size_t t = 0; t < buckets.size(); t++) { if (bels_at(dir ? i : trimmed_l, dir ? trimmed_l : i, t) > 0) { have_bels = true; break; } + } + } + if (have_bels) break; + trimmed_l++; } while (trimmed_r > (dir ? r.y0 : r.x0)) { bool have_bels = false; - for (int i = dir ? r.x0 : r.y0; i <= (dir ? r.x1 : r.y1); i++) - for (size_t t = 0; t < beltype.size(); t++) + for (int i = dir ? r.x0 : r.y0; i <= (dir ? r.x1 : r.y1); i++) { + for (size_t t = 0; t < buckets.size(); t++) { if (bels_at(dir ? i : trimmed_r, dir ? trimmed_r : i, t) > 0) { have_bels = true; break; } + } + } + if (have_bels) break; + trimmed_r--; } // log_info("tl %d tr %d cl %d cr %d\n", trimmed_l, trimmed_r, clearance_l, clearance_r); @@ -1533,27 +1585,27 @@ class HeAPPlacer return {}; // Now find the initial target cut that minimises utilisation imbalance, whilst // meeting the clearance requirements for any large macros - std::vector<int> left_cells_v(beltype.size(), 0), right_cells_v(beltype.size(), 0); - std::vector<int> left_bels_v(beltype.size(), 0), right_bels_v(r.bels); + std::vector<int> left_cells_v(buckets.size(), 0), right_cells_v(buckets.size(), 0); + std::vector<int> left_bels_v(buckets.size(), 0), right_bels_v(r.bels); for (int i = 0; i <= pivot; i++) - left_cells_v.at(type_index.at(cut_cells.at(i)->type)) += + left_cells_v.at(cell_index(*cut_cells.at(i))) += p->chain_size.count(cut_cells.at(i)->name) ? p->chain_size.at(cut_cells.at(i)->name) : 1; for (int i = pivot + 1; i < int(cut_cells.size()); i++) - right_cells_v.at(type_index.at(cut_cells.at(i)->type)) += + right_cells_v.at(cell_index(*cut_cells.at(i))) += p->chain_size.count(cut_cells.at(i)->name) ? p->chain_size.at(cut_cells.at(i)->name) : 1; int best_tgt_cut = -1; double best_deltaU = std::numeric_limits<double>::max(); // std::pair<int, int> target_cut_bels; - std::vector<int> slither_bels(beltype.size(), 0); + std::vector<int> slither_bels(buckets.size(), 0); for (int i = trimmed_l; i <= trimmed_r; i++) { - for (size_t t = 0; t < beltype.size(); t++) + for (size_t t = 0; t < buckets.size(); t++) slither_bels.at(t) = 0; for (int j = dir ? r.x0 : r.y0; j <= (dir ? r.x1 : r.y1); j++) { - for (size_t t = 0; t < beltype.size(); t++) + for (size_t t = 0; t < buckets.size(); t++) slither_bels.at(t) += dir ? bels_at(j, i, t) : bels_at(i, j, t); } - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { left_bels_v.at(t) += slither_bels.at(t); right_bels_v.at(t) -= slither_bels.at(t); } @@ -1561,7 +1613,7 @@ class HeAPPlacer if (((i - trimmed_l) + 1) >= clearance_l && ((trimmed_r - i) + 1) >= clearance_r) { // Solution is potentially valid double aU = 0; - for (size_t t = 0; t < beltype.size(); t++) + for (size_t t = 0; t < buckets.size(); t++) aU += (left_cells_v.at(t) + right_cells_v.at(t)) * std::abs(double(left_cells_v.at(t)) / double(std::max(left_bels_v.at(t), 1)) - double(right_cells_v.at(t)) / double(std::max(right_bels_v.at(t), 1))); @@ -1575,19 +1627,19 @@ class HeAPPlacer return {}; // left_bels = target_cut_bels.first; // right_bels = target_cut_bels.second; - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { left_bels_v.at(t) = 0; right_bels_v.at(t) = 0; } for (int x = r.x0; x <= (dir ? r.x1 : best_tgt_cut); x++) for (int y = r.y0; y <= (dir ? best_tgt_cut : r.y1); y++) { - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { left_bels_v.at(t) += bels_at(x, y, t); } } for (int x = dir ? r.x0 : (best_tgt_cut + 1); x <= r.x1; x++) for (int y = dir ? (best_tgt_cut + 1) : r.y0; y <= r.y1; y++) { - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { right_bels_v.at(t) += bels_at(x, y, t); } } @@ -1607,15 +1659,15 @@ class HeAPPlacer while (pivot > 0 && is_part_overutil(false)) { auto &move_cell = cut_cells.at(pivot); int size = p->chain_size.count(move_cell->name) ? p->chain_size.at(move_cell->name) : 1; - left_cells_v.at(type_index.at(cut_cells.at(pivot)->type)) -= size; - right_cells_v.at(type_index.at(cut_cells.at(pivot)->type)) += size; + left_cells_v.at(cell_index(*cut_cells.at(pivot))) -= size; + right_cells_v.at(cell_index(*cut_cells.at(pivot))) += size; pivot--; } while (pivot < int(cut_cells.size()) - 1 && is_part_overutil(true)) { auto &move_cell = cut_cells.at(pivot + 1); int size = p->chain_size.count(move_cell->name) ? p->chain_size.at(move_cell->name) : 1; - left_cells_v.at(type_index.at(cut_cells.at(pivot)->type)) += size; - right_cells_v.at(type_index.at(cut_cells.at(pivot)->type)) -= size; + left_cells_v.at(cell_index(*cut_cells.at(pivot))) += size; + right_cells_v.at(cell_index(*cut_cells.at(pivot))) -= size; pivot++; } |