aboutsummaryrefslogtreecommitdiffstats
path: root/common
diff options
context:
space:
mode:
Diffstat (limited to 'common')
-rw-r--r--common/placer_heap.cc148
1 files changed, 130 insertions, 18 deletions
diff --git a/common/placer_heap.cc b/common/placer_heap.cc
index 6cd0459d..6b6a6225 100644
--- a/common/placer_heap.cc
+++ b/common/placer_heap.cc
@@ -207,6 +207,7 @@ class HeAPPlacer
struct CellLocation
{
int x, y;
+ double rawx, rawy;
bool locked, global;
};
std::unordered_map<IdString, CellLocation> cell_locs;
@@ -414,11 +415,11 @@ class HeAPPlacer
for (auto child : cell->constr_children) {
chain_size[root->name]++;
if (child->constr_x != child->UNCONSTR)
- cell_locs[child->name].x = base.x + child->constr_x;
+ cell_locs[child->name].x = std::min(max_x, base.x + child->constr_x);
else
cell_locs[child->name].x = base.x; // better handling of UNCONSTR?
if (child->constr_y != child->UNCONSTR)
- cell_locs[child->name].y = base.y + child->constr_y;
+ cell_locs[child->name].y = std::min(max_y, base.y + child->constr_y);
else
cell_locs[child->name].y = base.y; // better handling of UNCONSTR?
chain_root[cell->name] = root;
@@ -531,18 +532,20 @@ class HeAPPlacer
}
// Build the system of equations for either X or Y
- void solve_equations(EquationSystem<double> &es, bool yaxis)
- {
+ void solve_equations(EquationSystem<double> &es, bool yaxis) {
// Return the x or y position of a cell, depending on ydir
auto cell_pos = [&](CellInfo *cell) { return yaxis ? cell_locs.at(cell->name).y : cell_locs.at(cell->name).x; };
std::vector<double> vals;
std::transform(solve_cells.begin(), solve_cells.end(), std::back_inserter(vals), cell_pos);
es.solve(vals);
for (size_t i = 0; i < vals.size(); i++)
- if (yaxis)
+ if (yaxis) {
+ cell_locs.at(solve_cells.at(i)->name).rawy = vals.at(i);
cell_locs.at(solve_cells.at(i)->name).y = std::min(max_y, std::max(0, int(vals.at(i) + 0.5)));
- else
+ } else {
+ cell_locs.at(solve_cells.at(i)->name).rawx = vals.at(i);
cell_locs.at(solve_cells.at(i)->name).x = std::min(max_x, std::max(0, int(vals.at(i) + 0.5)));
+ }
}
// Compute HPWL
@@ -724,10 +727,15 @@ class HeAPPlacer
std::vector<std::vector<int>> occupancy;
std::vector<std::vector<int>> groups;
std::vector<std::vector<ChainExtent>> chaines;
+ std::map<IdString, ChainExtent> cell_extents;
+
std::vector<std::vector<std::vector<BelId>>> &fb;
std::vector<LegaliserRegion> regions;
std::unordered_set<int> merged_regions;
+ // Cells at a location, sorted by real (not integer) x and y
+ std::vector<std::vector<std::vector<CellInfo*>>> cells_at_location_sx;
+ std::vector<std::vector<std::vector<CellInfo*>>> cells_at_location_sy;
int occ_at(int x, int y) { return occupancy.at(x).at(y); }
@@ -738,12 +746,12 @@ class HeAPPlacer
return int(fb.at(x).at(y).size());
}
- void init()
- {
+ void init() {
occupancy.resize(p->max_x + 1, std::vector<int>(p->max_y + 1, 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_sx.resize(p->max_x + 1, std::vector<std::vector<CellInfo *>>(p->max_y + 1));
+ cells_at_location_sy.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++) {
occupancy.at(x).at(y) = 0;
@@ -751,16 +759,15 @@ class HeAPPlacer
chaines.at(x).at(y) = {x, y, x, y};
}
- std::map<IdString, ChainExtent> cr_extents;
auto set_chain_ext = [&](IdString cell, int x, int y) {
- if (!cr_extents.count(cell))
- cr_extents[cell] = {x, y, x, y};
+ if (!cell_extents.count(cell))
+ cell_extents[cell] = {x, y, x, y};
else {
- cr_extents[cell].x0 = std::min(cr_extents[cell].x0, x);
- cr_extents[cell].y0 = std::min(cr_extents[cell].y0, y);
- cr_extents[cell].x1 = std::max(cr_extents[cell].x1, x);
- cr_extents[cell].y1 = std::max(cr_extents[cell].y1, y);
+ cell_extents[cell].x0 = std::min(cell_extents[cell].x0, x);
+ cell_extents[cell].y0 = std::min(cell_extents[cell].y0, y);
+ cell_extents[cell].x1 = std::max(cell_extents[cell].x1, x);
+ cell_extents[cell].y1 = std::max(cell_extents[cell].y1, y);
}
};
@@ -778,9 +785,9 @@ class HeAPPlacer
// Transfer chain extents to the actual chaines structure
ChainExtent *ce = nullptr;
if (p->chain_root.count(cell.first))
- ce = &(cr_extents.at(p->chain_root.at(cell.first)->name));
+ ce = &(cell_extents.at(p->chain_root.at(cell.first)->name));
else if (!ctx->cells.at(cell.first)->constr_children.empty())
- ce = &(cr_extents.at(cell.first));
+ ce = &(cell_extents.at(cell.first));
if (ce) {
auto &lce = chaines.at(cell.second.x).at(cell.second.y);
lce.x0 = std::min(lce.x0, ce->x0);
@@ -789,6 +796,20 @@ class HeAPPlacer
lce.y1 = std::max(lce.y1, ce->y1);
}
}
+ for (auto cell : p->solve_cells) {
+ cells_at_location_sx.at(p->cell_locs.at(cell->name).x).at(p->cell_locs.at(cell->name).y).push_back(cell);
+ cells_at_location_sy.at(p->cell_locs.at(cell->name).x).at(p->cell_locs.at(cell->name).y).push_back(cell);
+ }
+ for (auto &col : cells_at_location_sx)
+ for (auto &loc : col)
+ std::sort(loc.begin(), loc.end(), [&](const CellInfo *a, const CellInfo *b){
+ return p->cell_locs.at(a->name).rawx < p->cell_locs.at(b->name).rawx;
+ });
+ for (auto &col : cells_at_location_sy)
+ for (auto &loc : col)
+ std::sort(loc.begin(), loc.end(), [&](const CellInfo *a, const CellInfo *b){
+ return p->cell_locs.at(a->name).rawy < p->cell_locs.at(b->name).rawy;
+ });
}
void merge_regions(LegaliserRegion &merged, LegaliserRegion &mergee)
{
@@ -950,6 +971,97 @@ class HeAPPlacer
}
}
}
+
+ // Implementation of the recursive cut-based spreading as described in the HeAP paper
+ // Note we use "left" to mean "-x/-y" depending on dir and "right" to mean "+x/+y" depending on dir
+
+ std::vector<CellInfo *> cut_cells;
+
+ void cut_region(LegaliserRegion &r, bool dir) {
+ cut_cells.clear();
+ auto &cal = dir ? cells_at_location_sy : cells_at_location_sx;
+ 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));
+ }
+ }
+ // Find the cells midpoint, counting chains in terms of their total size - making the initial source cut
+ int pivot_cells = 0;
+ int pivot = 0;
+ for (auto &cell : cut_cells) {
+ pivot_cells += p->chain_size.count(cell->name) ? p->chain_size.at(cell->name) : 1;
+ if (pivot_cells >= r.cells / 2)
+ break;
+ pivot++;
+ }
+ // Find the clearance required either side of the pivot
+ int clearance_l = 0, clearance_r = 0;
+ for (size_t i = 0; i < cut_cells.size(); i++) {
+ int size;
+ if (cell_extents.count(cut_cells.at(i)->name)) {
+ auto &ce = cell_extents.at(cut_cells.at(i)->name);
+ size = dir ? (ce.y1 - ce.y0 + 1) : (ce.x1 - ce.x0 + 1);
+ } else {
+ size = 1;
+ }
+ if (i < pivot)
+ clearance_l = std::max(clearance_l, size);
+ else
+ clearance_r = std::max(clearance_r, size);
+ }
+ // Find the target cut that minimises difference in utilisation, whilst trying to ensure that all chains
+ // still fit
+
+ // First trim the boundaries of the region in the axis-of-interest, skipping any rows/cols without any
+ // bels of the appropriate type
+ 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++)
+ if (bels_at(dir ? i : trimmed_l, dir ? trimmed_l : i) > 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++)
+ if (bels_at(dir ? i : trimmed_l, dir ? trimmed_l : i) > 0) {
+ have_bels = true;
+ break;
+ }
+ if (have_bels)
+ break;
+ trimmed_r--;
+ }
+
+ // Now find the initial target cut that minimises utilisation imbalance, whilst
+ // meeting the clearance requirements for any large macros
+ int left_cells = pivot_cells, right_cells = r.cells - pivot_cells;
+ int left_bels = 0, right_bels = r.bels;
+ int best_tgt_cut = -1;
+ double best_deltaU = std::numeric_limits<double>::max();
+
+ for (int i = trimmed_l; i <= trimmed_r; i++) {
+ int slither_bels = 0;
+ for (int j = dir ? r.x0 : r.y0; j <= (dir ? r.x1 : r.y1); j++) {
+ slither_bels += dir ? bels_at(j, i) : bels_at(i, j);
+ }
+ left_bels += slither_bels;
+ right_bels -= slither_bels;
+ if (((i - trimmed_l) + 1) >= clearance_l && ((trimmed_r - i) + 1) >= clearance_r) {
+ // Solution is potentially valid
+ double aU = std::abs(double(left_cells) / double(left_bels) - double(right_bels) / double(right_cells));
+ if (aU < best_deltaU) {
+ best_deltaU = aU;
+ best_tgt_cut = i;
+ }
+ }
+ }
+ }
};
typedef decltype(CellInfo::udata) cell_udata_t;
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-10 09:18:26 +0000