From 6b74d326d42063dc1b68f8276c5892bf90099b26 Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 13 Jun 2018 17:07:42 +0200 Subject: experiment: Simple heuristic-based placer Signed-off-by: David Shah --- common/design_utils.h | 2 +- common/place.cc | 128 +++++++++++++++++++++++++++++++++++++++++++++++++- common/place.h | 2 + 3 files changed, 129 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/design_utils.h b/common/design_utils.h index daf6e050..8d231d4c 100644 --- a/common/design_utils.h +++ b/common/design_utils.h @@ -72,7 +72,7 @@ CellInfo *net_only_drives(NetInfo *net, F1 cell_pred, IdString port, // If a net is driven by a given port of a cell matching a predicate, return // that cell, otherwise nullptr template -CellInfo *net_driven_by(NetInfo *net, F1 cell_pred, IdString port) +CellInfo *net_driven_by(const NetInfo *net, F1 cell_pred, IdString port) { if (net == nullptr) return nullptr; diff --git a/common/place.cc b/common/place.cc index 92c09e78..2b69aa28 100644 --- a/common/place.cc +++ b/common/place.cc @@ -17,20 +17,21 @@ * */ +#include "place.h" #include +#include #include #include #include +#include #include #include #include #include #include #include - #include "arch_place.h" #include "log.h" -#include "place.h" NEXTPNR_NAMESPACE_BEGIN @@ -122,4 +123,127 @@ void place_design(Design *design) } } +static void place_cell(Design *design, CellInfo *cell, BelId closeTo, + size_t &placed_cells, + std::queue &visit_cells) +{ + assert(cell->bel == BelId()); + float best_distance = std::numeric_limits::infinity(); + BelId best_bel = BelId(); + Chip &chip = design->chip; + BelType targetType = belTypeFromId(cell->type); + PosInfo origin; + if (closeTo != BelId()) { + origin = chip.getBelPosition(closeTo); + for (auto bel : chip.getBelsAtSameTile(closeTo)) { + if (chip.getBelType(bel) == targetType && chip.checkBelAvail(bel) && + isValidBelForCell(design, cell, bel)) { + // prefer same tile + best_bel = bel; + goto placed; + } + } + } + for (auto bel : chip.getBels()) { + if (chip.getBelType(bel) == targetType && chip.checkBelAvail(bel) && + isValidBelForCell(design, cell, bel)) { + if (closeTo == BelId()) { + best_distance = 0; + best_bel = bel; + goto placed; + } else { + float distance = + chip.estimateDelay(origin, chip.getBelPosition(bel)); + if (distance < best_distance) { + best_distance = distance; + best_bel = bel; + } + } + } + } +placed: + if (best_bel == BelId()) { + log_error("failed to place cell '%s' of type '%s'\n", + cell->name.c_str(), cell->type.c_str()); + } + cell->bel = best_bel; + chip.bindBel(cell->bel, cell->name); + + // Back annotate location + cell->attrs["BEL"] = chip.getBelName(cell->bel).str(); + placed_cells++; + visit_cells.push(cell); +} + +static void place_cell_neighbours(Design *design, CellInfo *cell, + size_t &placed_cells, + std::queue &visit_cells) +{ + if (cell->bel == BelId()) + return; + for (auto port : cell->ports) { + NetInfo *net = port.second.net; + if (net != nullptr) { + if (net->users.size() > 3) // don't follow high fanout nets + continue; + for (auto user : net->users) { + if (user.cell != nullptr && user.cell->bel == BelId()) + place_cell(design, user.cell, cell->bel, placed_cells, + visit_cells); + } + if (net->driver.cell != nullptr && net->driver.cell->bel == BelId()) + place_cell(design, net->driver.cell, cell->bel, placed_cells, + visit_cells); + } + } +} + +void place_design_heuristic(Design *design) +{ + size_t total_cells = design->cells.size(), placed_cells = 0; + std::queue visit_cells; + // Initial constraints placer + for (auto cell_entry : design->cells) { + CellInfo *cell = cell_entry.second; + auto loc = cell->attrs.find("BEL"); + if (loc != cell->attrs.end()) { + std::string loc_name = loc->second; + BelId bel = design->chip.getBelByName(IdString(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()); + } + + BelType bel_type = design->chip.getBelType(bel); + if (bel_type != belTypeFromId(cell->type)) { + log_error("Bel \'%s\' of type \'%s\' does not match cell " + "\'%s\' of type \'%s\'", + loc_name.c_str(), belTypeToId(bel_type).c_str(), + cell->name.c_str(), cell->type.c_str()); + } + + cell->bel = bel; + design->chip.bindBel(bel, cell->name); + placed_cells++; + visit_cells.push(cell); + } + } + while (placed_cells < total_cells) { + if (!visit_cells.empty()) { + CellInfo *next = visit_cells.front(); + visit_cells.pop(); + place_cell_neighbours(design, next, placed_cells, visit_cells); + } else { + // Nothing to visit (netlist is split), pick the next unplaced cell + for (auto cell : design->cells) { + CellInfo *ci = cell.second; + if (ci->bel == BelId()) + place_cell(design, ci, BelId(), placed_cells, visit_cells); + } + } + log_info("placed %d/%d\n", placed_cells, total_cells); + } +} + NEXTPNR_NAMESPACE_END diff --git a/common/place.h b/common/place.h index 7df84873..fd4de534 100644 --- a/common/place.h +++ b/common/place.h @@ -25,6 +25,8 @@ NEXTPNR_NAMESPACE_BEGIN extern void place_design(Design *design); +extern void place_design_heuristic(Design *design); + NEXTPNR_NAMESPACE_END #endif // PLACE_H -- cgit v1.2.3 From b1e08fa064f58bce759cbd8d341554d5ec4dc14c Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 13 Jun 2018 18:53:58 +0200 Subject: Playing about with placement heuristics Signed-off-by: David Shah --- common/place.cc | 24 +++++++++++++++++++----- 1 file changed, 19 insertions(+), 5 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index 2b69aa28..fbb74395 100644 --- a/common/place.cc +++ b/common/place.cc @@ -181,21 +181,32 @@ static void place_cell_neighbours(Design *design, CellInfo *cell, { if (cell->bel == BelId()) return; + int placed_count = 0; + const int count_thresh = 15; for (auto port : cell->ports) { NetInfo *net = port.second.net; if (net != nullptr) { - if (net->users.size() > 3) // don't follow high fanout nets - continue; for (auto user : net->users) { - if (user.cell != nullptr && user.cell->bel == BelId()) + if (net->users.size() > 3) + continue; + if (user.cell != nullptr && user.cell->bel == BelId()) { place_cell(design, user.cell, cell->bel, placed_cells, visit_cells); + placed_count++; + if (placed_count > count_thresh) + return; + } } - if (net->driver.cell != nullptr && net->driver.cell->bel == BelId()) + if (net->driver.cell != nullptr && net->driver.cell->bel == BelId()) { place_cell(design, net->driver.cell, cell->bel, placed_cells, visit_cells); + placed_count++; + } + if (placed_count > count_thresh) + return; } } + } void place_design_heuristic(Design *design) @@ -229,6 +240,7 @@ void place_design_heuristic(Design *design) visit_cells.push(cell); } } + log_info("place_constraints placed %d\n", placed_cells); while (placed_cells < total_cells) { if (!visit_cells.empty()) { CellInfo *next = visit_cells.front(); @@ -238,8 +250,10 @@ void place_design_heuristic(Design *design) // Nothing to visit (netlist is split), pick the next unplaced cell for (auto cell : design->cells) { CellInfo *ci = cell.second; - if (ci->bel == BelId()) + if (ci->bel == BelId()) { place_cell(design, ci, BelId(), placed_cells, visit_cells); + break; + } } } log_info("placed %d/%d\n", placed_cells, total_cells); -- cgit v1.2.3 From 3ef45d2a27416ee14239dde6a69b43c870ea07b7 Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 13 Jun 2018 19:10:12 +0200 Subject: Another heuristic experiment Signed-off-by: David Shah --- common/place.cc | 95 +++++++++++---------------------------------------------- 1 file changed, 18 insertions(+), 77 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index fbb74395..d28d7ce9 100644 --- a/common/place.cc +++ b/common/place.cc @@ -123,45 +123,32 @@ void place_design(Design *design) } } -static void place_cell(Design *design, CellInfo *cell, BelId closeTo, - size_t &placed_cells, - std::queue &visit_cells) +static void place_cell(Design *design, CellInfo *cell) { assert(cell->bel == BelId()); float best_distance = std::numeric_limits::infinity(); BelId best_bel = BelId(); Chip &chip = design->chip; BelType targetType = belTypeFromId(cell->type); - PosInfo origin; - if (closeTo != BelId()) { - origin = chip.getBelPosition(closeTo); - for (auto bel : chip.getBelsAtSameTile(closeTo)) { - if (chip.getBelType(bel) == targetType && chip.checkBelAvail(bel) && - isValidBelForCell(design, cell, bel)) { - // prefer same tile - best_bel = bel; - goto placed; - } - } - } for (auto bel : chip.getBels()) { if (chip.getBelType(bel) == targetType && chip.checkBelAvail(bel) && isValidBelForCell(design, cell, bel)) { - if (closeTo == BelId()) { - best_distance = 0; - best_bel = bel; - goto placed; - } else { - float distance = - chip.estimateDelay(origin, chip.getBelPosition(bel)); - if (distance < best_distance) { - best_distance = distance; - best_bel = bel; + float distance = 0; + PosInfo belPosition = chip.getBelPosition(bel); + for (auto port : cell->ports) { + const PortInfo &pi = port.second; + if(pi.net != nullptr && pi.type == PORT_IN) { + CellInfo *drv = pi.net->driver.cell; + if (drv != nullptr && drv->bel != BelId()) + distance += chip.estimateDelay(chip.getBelPosition(drv->bel), belPosition); } } + if (distance < best_distance) { + best_distance = distance; + best_bel = bel; + } } } -placed: if (best_bel == BelId()) { log_error("failed to place cell '%s' of type '%s'\n", cell->name.c_str(), cell->type.c_str()); @@ -171,42 +158,6 @@ placed: // Back annotate location cell->attrs["BEL"] = chip.getBelName(cell->bel).str(); - placed_cells++; - visit_cells.push(cell); -} - -static void place_cell_neighbours(Design *design, CellInfo *cell, - size_t &placed_cells, - std::queue &visit_cells) -{ - if (cell->bel == BelId()) - return; - int placed_count = 0; - const int count_thresh = 15; - for (auto port : cell->ports) { - NetInfo *net = port.second.net; - if (net != nullptr) { - for (auto user : net->users) { - if (net->users.size() > 3) - continue; - if (user.cell != nullptr && user.cell->bel == BelId()) { - place_cell(design, user.cell, cell->bel, placed_cells, - visit_cells); - placed_count++; - if (placed_count > count_thresh) - return; - } - } - if (net->driver.cell != nullptr && net->driver.cell->bel == BelId()) { - place_cell(design, net->driver.cell, cell->bel, placed_cells, - visit_cells); - placed_count++; - } - if (placed_count > count_thresh) - return; - } - } - } void place_design_heuristic(Design *design) @@ -241,21 +192,11 @@ void place_design_heuristic(Design *design) } } log_info("place_constraints placed %d\n", placed_cells); - while (placed_cells < total_cells) { - if (!visit_cells.empty()) { - CellInfo *next = visit_cells.front(); - visit_cells.pop(); - place_cell_neighbours(design, next, placed_cells, visit_cells); - } else { - // Nothing to visit (netlist is split), pick the next unplaced cell - for (auto cell : design->cells) { - CellInfo *ci = cell.second; - if (ci->bel == BelId()) { - place_cell(design, ci, BelId(), placed_cells, visit_cells); - break; - } - } - } + for (auto cell : design->cells) { + CellInfo *ci = cell.second; + if (ci->bel == BelId()) + place_cell(design, ci); + placed_cells++; log_info("placed %d/%d\n", placed_cells, total_cells); } } -- cgit v1.2.3 From 2f01ec51571db02ff1f1fb5b9d6bf47b8ab5f35d Mon Sep 17 00:00:00 2001 From: David Shah Date: Thu, 14 Jun 2018 15:21:00 +0200 Subject: Update basic placer to use new API Signed-off-by: David Shah --- common/place.cc | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index d28d7ce9..7573e061 100644 --- a/common/place.cc +++ b/common/place.cc @@ -18,6 +18,7 @@ */ #include "place.h" +#include #include #include #include @@ -134,13 +135,18 @@ static void place_cell(Design *design, CellInfo *cell) if (chip.getBelType(bel) == targetType && chip.checkBelAvail(bel) && isValidBelForCell(design, cell, bel)) { float distance = 0; - PosInfo belPosition = chip.getBelPosition(bel); + float belx, bely; + chip.estimatePosition(bel, belx, bely); for (auto port : cell->ports) { const PortInfo &pi = port.second; - if(pi.net != nullptr && pi.type == PORT_IN) { + if (pi.net != nullptr && pi.type == PORT_IN) { CellInfo *drv = pi.net->driver.cell; - if (drv != nullptr && drv->bel != BelId()) - distance += chip.estimateDelay(chip.getBelPosition(drv->bel), belPosition); + if (drv != nullptr && drv->bel != BelId()) { + float otherx, othery; + chip.estimatePosition(drv->bel, otherx, othery); + distance += std::pow(belx - otherx, 2) + + std::pow(bely - othery, 2); + } } } if (distance < best_distance) { -- cgit v1.2.3 From 828c96f80ba4695d39ade82a5431b01a84fcec76 Mon Sep 17 00:00:00 2001 From: David Shah Date: Thu, 14 Jun 2018 20:25:35 +0200 Subject: Updating placer Signed-off-by: David Shah --- common/place.cc | 42 +++++++++++++++++++++++++++++++++++------- 1 file changed, 35 insertions(+), 7 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index 7573e061..15455834 100644 --- a/common/place.cc +++ b/common/place.cc @@ -126,10 +126,14 @@ void place_design(Design *design) static void place_cell(Design *design, CellInfo *cell) { - assert(cell->bel == BelId()); + float best_distance = std::numeric_limits::infinity(); BelId best_bel = BelId(); Chip &chip = design->chip; + if(cell->bel != BelId()) { + chip.unbindBel(cell->bel); + cell->bel = BelId(); + } BelType targetType = belTypeFromId(cell->type); for (auto bel : chip.getBels()) { if (chip.getBelType(bel) == targetType && chip.checkBelAvail(bel) && @@ -139,17 +143,28 @@ static void place_cell(Design *design, CellInfo *cell) chip.estimatePosition(bel, belx, bely); for (auto port : cell->ports) { const PortInfo &pi = port.second; - if (pi.net != nullptr && pi.type == PORT_IN) { + if (pi.net != nullptr) { CellInfo *drv = pi.net->driver.cell; if (drv != nullptr && drv->bel != BelId()) { float otherx, othery; chip.estimatePosition(drv->bel, otherx, othery); - distance += std::pow(belx - otherx, 2) + - std::pow(bely - othery, 2); + distance += std::abs(belx - otherx) + + std::abs(bely - othery); + } + if (pi.net->users.size() < 5) { + for (auto user : pi.net->users) { + CellInfo *uc = user.cell; + if (uc != nullptr && uc->bel != BelId()) { + float otherx, othery; + chip.estimatePosition(uc->bel, otherx, othery); + distance += std::abs(belx - otherx) + + std::abs(bely - othery); + } + } } } } - if (distance < best_distance) { + if (distance <= best_distance) { best_distance = distance; best_bel = bel; } @@ -198,13 +213,26 @@ void place_design_heuristic(Design *design) } } log_info("place_constraints placed %d\n", placed_cells); + std::unordered_set autoplaced; for (auto cell : design->cells) { CellInfo *ci = cell.second; - if (ci->bel == BelId()) + if (ci->bel == BelId()) { place_cell(design, ci); - placed_cells++; + autoplaced.insert(cell.first); + placed_cells++; + } log_info("placed %d/%d\n", placed_cells, total_cells); } + for (int i = 0 ; i < 3; i ++) { + int replaced_cells = 0; + for (auto cell : autoplaced) { + CellInfo *ci = design->cells[cell]; + place_cell(design, ci); + replaced_cells++; + log_info("replaced %d/%d\n", replaced_cells, autoplaced.size()); + } + } + } NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From 104c2dad9b4148586b05d41e482101a925cf681f Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 15 Jun 2018 09:27:02 +0200 Subject: Adding randomness and changes metrics to placer Signed-off-by: David Shah --- common/place.cc | 34 +++++++++++++++++++++++++--------- 1 file changed, 25 insertions(+), 9 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index 15455834..35299604 100644 --- a/common/place.cc +++ b/common/place.cc @@ -31,6 +31,8 @@ #include #include #include +#include +#include #include "arch_place.h" #include "log.h" @@ -124,9 +126,9 @@ void place_design(Design *design) } } -static void place_cell(Design *design, CellInfo *cell) +static void place_cell(Design *design, CellInfo *cell, std::mt19937 &rnd) { - + std::uniform_real_distribution random_wirelength(0.0, 30.0); float best_distance = std::numeric_limits::infinity(); BelId best_bel = BelId(); Chip &chip = design->chip; @@ -140,16 +142,21 @@ static void place_cell(Design *design, CellInfo *cell) isValidBelForCell(design, cell, bel)) { float distance = 0; float belx, bely; + bool has_conns = false; chip.estimatePosition(bel, belx, bely); for (auto port : cell->ports) { const PortInfo &pi = port.second; if (pi.net != nullptr) { CellInfo *drv = pi.net->driver.cell; + float pin_wirelength = std::numeric_limits::infinity(); if (drv != nullptr && drv->bel != BelId()) { float otherx, othery; chip.estimatePosition(drv->bel, otherx, othery); - distance += std::abs(belx - otherx) + + float local_wl = std::abs(belx - otherx) + std::abs(bely - othery); + if (local_wl < pin_wirelength) + pin_wirelength = local_wl; + has_conns = true; } if (pi.net->users.size() < 5) { for (auto user : pi.net->users) { @@ -157,13 +164,20 @@ static void place_cell(Design *design, CellInfo *cell) if (uc != nullptr && uc->bel != BelId()) { float otherx, othery; chip.estimatePosition(uc->bel, otherx, othery); - distance += std::abs(belx - otherx) + + float local_wl = std::abs(belx - otherx) + std::abs(bely - othery); + if (local_wl < pin_wirelength) + pin_wirelength = local_wl; + has_conns = true; } } } + if (!std::isinf(pin_wirelength)) + distance += pin_wirelength; } } + if (!has_conns) + distance = random_wirelength(rnd); if (distance <= best_distance) { best_distance = distance; best_bel = bel; @@ -213,21 +227,23 @@ void place_design_heuristic(Design *design) } } log_info("place_constraints placed %d\n", placed_cells); - std::unordered_set autoplaced; + std::mt19937 rnd; + std::vector autoplaced; for (auto cell : design->cells) { CellInfo *ci = cell.second; if (ci->bel == BelId()) { - place_cell(design, ci); - autoplaced.insert(cell.first); + place_cell(design, ci, rnd); + autoplaced.push_back(cell.first); placed_cells++; } log_info("placed %d/%d\n", placed_cells, total_cells); } - for (int i = 0 ; i < 3; i ++) { + for (int i = 0 ; i < 2; i ++) { int replaced_cells = 0; + std::shuffle(autoplaced.begin(), autoplaced.end(), rnd); for (auto cell : autoplaced) { CellInfo *ci = design->cells[cell]; - place_cell(design, ci); + place_cell(design, ci, rnd); replaced_cells++; log_info("replaced %d/%d\n", replaced_cells, autoplaced.size()); } -- cgit v1.2.3 From 32dcf6b3fe02f2338558be1610257605a94b0d38 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 15 Jun 2018 10:14:12 +0200 Subject: Experimenting with more unplacing Signed-off-by: David Shah --- common/place.cc | 17 +++++++++++------ 1 file changed, 11 insertions(+), 6 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index 35299604..e622ae71 100644 --- a/common/place.cc +++ b/common/place.cc @@ -148,14 +148,15 @@ static void place_cell(Design *design, CellInfo *cell, std::mt19937 &rnd) const PortInfo &pi = port.second; if (pi.net != nullptr) { CellInfo *drv = pi.net->driver.cell; - float pin_wirelength = std::numeric_limits::infinity(); + //float pin_wirelength = std::numeric_limits::infinity(); + float pin_wirelength = 0; if (drv != nullptr && drv->bel != BelId()) { float otherx, othery; chip.estimatePosition(drv->bel, otherx, othery); float local_wl = std::abs(belx - otherx) + std::abs(bely - othery); - if (local_wl < pin_wirelength) - pin_wirelength = local_wl; + //if (local_wl < pin_wirelength) + pin_wirelength += local_wl; has_conns = true; } if (pi.net->users.size() < 5) { @@ -166,8 +167,8 @@ static void place_cell(Design *design, CellInfo *cell, std::mt19937 &rnd) chip.estimatePosition(uc->bel, otherx, othery); float local_wl = std::abs(belx - otherx) + std::abs(bely - othery); - if (local_wl < pin_wirelength) - pin_wirelength = local_wl; + //if (local_wl < pin_wirelength) + pin_wirelength += local_wl; has_conns = true; } } @@ -238,8 +239,12 @@ void place_design_heuristic(Design *design) } log_info("placed %d/%d\n", placed_cells, total_cells); } - for (int i = 0 ; i < 2; i ++) { + for (int i = 0 ; i < 5; i ++) { int replaced_cells = 0; + for (int j = 0; j < autoplaced.size() / 10; j++) { + design->chip.unbindBel(design->cells.at(autoplaced.at(j))->bel); + design->cells.at(autoplaced.at(j))->bel = BelId(); + } std::shuffle(autoplaced.begin(), autoplaced.end(), rnd); for (auto cell : autoplaced) { CellInfo *ci = design->cells[cell]; -- cgit v1.2.3 From 2d993d8ee9e5ef2b4bb74ea2504c7d68499e298d Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 15 Jun 2018 13:42:21 +0200 Subject: Very slow SA placer based on arachne-pnr Signed-off-by: David Shah --- common/place.cc | 301 +++++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 241 insertions(+), 60 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index e622ae71..99d5de32 100644 --- a/common/place.cc +++ b/common/place.cc @@ -126,11 +126,30 @@ void place_design(Design *design) } } -static void place_cell(Design *design, CellInfo *cell, std::mt19937 &rnd) +struct rnd_state { + uint32_t state; +}; + +/* The state word must be initialized to non-zero */ +static uint32_t xorshift32(rnd_state &rnd) +{ + /* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */ + uint32_t x = rnd.state; + x ^= x << 13; + x ^= x >> 17; + x ^= x << 5; + rnd.state = x; + return x; +} + +static float random_float_upto(rnd_state &rnd, float limit) { + return xorshift32(rnd) / (4294967295 / limit); +} + +static void place_initial(Design *design, CellInfo *cell, rnd_state &rnd) { - std::uniform_real_distribution random_wirelength(0.0, 30.0); - float best_distance = std::numeric_limits::infinity(); BelId best_bel = BelId(); + float best_score = std::numeric_limits::infinity(); Chip &chip = design->chip; if(cell->bel != BelId()) { chip.unbindBel(cell->bel); @@ -140,47 +159,9 @@ static void place_cell(Design *design, CellInfo *cell, std::mt19937 &rnd) for (auto bel : chip.getBels()) { if (chip.getBelType(bel) == targetType && chip.checkBelAvail(bel) && isValidBelForCell(design, cell, bel)) { - float distance = 0; - float belx, bely; - bool has_conns = false; - chip.estimatePosition(bel, belx, bely); - for (auto port : cell->ports) { - const PortInfo &pi = port.second; - if (pi.net != nullptr) { - CellInfo *drv = pi.net->driver.cell; - //float pin_wirelength = std::numeric_limits::infinity(); - float pin_wirelength = 0; - if (drv != nullptr && drv->bel != BelId()) { - float otherx, othery; - chip.estimatePosition(drv->bel, otherx, othery); - float local_wl = std::abs(belx - otherx) + - std::abs(bely - othery); - //if (local_wl < pin_wirelength) - pin_wirelength += local_wl; - has_conns = true; - } - if (pi.net->users.size() < 5) { - for (auto user : pi.net->users) { - CellInfo *uc = user.cell; - if (uc != nullptr && uc->bel != BelId()) { - float otherx, othery; - chip.estimatePosition(uc->bel, otherx, othery); - float local_wl = std::abs(belx - otherx) + - std::abs(bely - othery); - //if (local_wl < pin_wirelength) - pin_wirelength += local_wl; - has_conns = true; - } - } - } - if (!std::isinf(pin_wirelength)) - distance += pin_wirelength; - } - } - if (!has_conns) - distance = random_wirelength(rnd); - if (distance <= best_distance) { - best_distance = distance; + float score = random_float_upto(rnd, 1.0); + if (score <= best_score) { + best_score = score; best_bel = bel; } } @@ -196,6 +177,141 @@ static void place_cell(Design *design, CellInfo *cell, std::mt19937 &rnd) cell->attrs["BEL"] = chip.getBelName(cell->bel).str(); } +struct SAState { + std::unordered_map wirelengths; + float best_wirelength = std::numeric_limits::infinity(); + float temp = 1000; + bool improved = false; + int n_move, n_accept; + int diameter = 35; +}; + +static float get_wirelength(Chip *chip, NetInfo *net) { + float wirelength = 0; + float driver_x = 0, driver_y = 0; + bool consider_driver = false; + CellInfo *driver_cell = net->driver.cell; + if (!driver_cell) + return 0; + if (driver_cell->bel == BelId()) + return 0; + consider_driver = chip->estimatePosition(driver_cell->bel, driver_x, driver_y); + if (!consider_driver) + return 0; + for (auto load : net->users) { + if (load.cell == nullptr) + continue; + CellInfo *load_cell = load.cell; + float load_x = 0, load_y = 0; + if (load_cell->bel == BelId()) + continue; + chip->estimatePosition(load_cell->bel, load_x, load_y); + wirelength += std::abs(load_x - driver_x) + std::abs(load_y - driver_y); + } + return wirelength; +} + +static bool try_swap_position(Design *design, CellInfo *cell, BelId newBel, rnd_state &rnd, SAState &state) { + std::unordered_set update; + std::unordered_map new_lengths; + Chip &chip = design->chip; + BelId oldBel = cell->bel; + IdString other = chip.getBelCell(newBel, true); + CellInfo *other_cell = nullptr; + float new_wirelength = 0, delta; + chip.unbindBel(oldBel); + if (other != IdString()) { + other_cell = design->cells[other]; + chip.unbindBel(newBel); + } + if (!isValidBelForCell(design, cell, newBel)) + goto swap_fail; + + for (const auto &port : cell->ports) + if (port.second.net != nullptr) + update.insert(port.second.net); + + if (other != IdString()) { + if (!isValidBelForCell(design, other_cell, oldBel)) + goto swap_fail; + for (const auto &port : other_cell->ports) + if (port.second.net != nullptr) + update.insert(port.second.net); + } + + chip.bindBel(newBel, cell->name); + if (other != IdString()) { + if (!isValidBelForCell(design, other_cell, oldBel)) { + chip.unbindBel(newBel); + goto swap_fail; + } else { + chip.bindBel(oldBel, other_cell->name); + } + } + + cell->bel = newBel; + if (other != IdString()) + other_cell->bel = oldBel; + + new_wirelength = state.best_wirelength; + for (auto net : update) { + new_wirelength -= state.wirelengths.at(net); + float net_new_wl = get_wirelength(&chip, net); + new_wirelength += net_new_wl; + new_lengths[net] = net_new_wl; + } + delta = new_wirelength - state.best_wirelength; + state.n_move++; + + if (delta < 0 || (state.temp > 1e-6 && random_float_upto(rnd, 1.0) <= std::exp(-delta/state.temp))) { + state.n_accept++; + if (delta < 0) + state.improved = true; + } else { + if (other != IdString()) + chip.unbindBel(oldBel); + chip.unbindBel(newBel); + goto swap_fail; + } + state.best_wirelength = new_wirelength; + for (auto new_wl : new_lengths) + state.wirelengths[new_wl.first] = new_wl.second; + + return true; +swap_fail: + chip.bindBel(oldBel, cell->name); + cell->bel = oldBel; + if (other != IdString()) { + chip.bindBel(newBel, other); + other_cell->bel = newBel; + } + return false; +} + +BelId random_bel_for_cell(Design *design, CellInfo *cell, SAState state, rnd_state &rnd) +{ + BelId best_bel = BelId(); + float best_score = std::numeric_limits::infinity(); + Chip &chip = design->chip; + BelType targetType = belTypeFromId(cell->type); + float x = 0, y = 0; + chip.estimatePosition(cell->bel, x, y); + for (auto bel : chip.getBels()) { + if (chip.getBelType(bel) == targetType) { + float score = random_float_upto(rnd, 1.0); + float nx = 0, ny = 0; + chip.estimatePosition(bel, nx, ny); + if (std::abs(nx - x) > state.diameter || std::abs(ny - y) > state.diameter) + continue; + if (score <= best_score) { + best_score = score; + best_bel = bel; + } + } + } + return best_bel; +} + void place_design_heuristic(Design *design) { size_t total_cells = design->cells.size(), placed_cells = 0; @@ -228,32 +344,97 @@ void place_design_heuristic(Design *design) } } log_info("place_constraints placed %d\n", placed_cells); - std::mt19937 rnd; - std::vector autoplaced; + rnd_state rnd; + rnd.state = 1; + std::vector autoplaced; for (auto cell : design->cells) { CellInfo *ci = cell.second; if (ci->bel == BelId()) { - place_cell(design, ci, rnd); - autoplaced.push_back(cell.first); + place_initial(design, ci, rnd); + autoplaced.push_back(cell.second); placed_cells++; } log_info("placed %d/%d\n", placed_cells, total_cells); } - for (int i = 0 ; i < 5; i ++) { - int replaced_cells = 0; - for (int j = 0; j < autoplaced.size() / 10; j++) { - design->chip.unbindBel(design->cells.at(autoplaced.at(j))->bel); - design->cells.at(autoplaced.at(j))->bel = BelId(); + SAState state; + state.best_wirelength = 0; + for (auto net : design->nets) { + float wl = get_wirelength(&design->chip, net.second); + state.wirelengths[net.second] = wl; + state.best_wirelength += wl; + } + + int n_no_progress = 0; + double avg_wirelength = state.best_wirelength; + state.temp = 10000; + for (int iter=1;; iter++) + { + state.n_move = state.n_accept = 0; + state.improved = false; + + //if (iter % 50 == 0) + log(" at iteration #%d: temp = %f, wire length = %f\n", iter, state.temp, state.best_wirelength); + + for (int m = 0; m < 15; ++m) + { + for (auto cell : autoplaced) + { + BelId try_bel = random_bel_for_cell(design, cell, state, rnd); + if (try_bel != BelId() && try_bel != cell->bel) + try_swap_position(design, cell, try_bel, rnd, state); + } + } - std::shuffle(autoplaced.begin(), autoplaced.end(), rnd); - for (auto cell : autoplaced) { - CellInfo *ci = design->cells[cell]; - place_cell(design, ci, rnd); - replaced_cells++; - log_info("replaced %d/%d\n", replaced_cells, autoplaced.size()); + + if (state.improved) + { + n_no_progress = 0; + // std::cout << "improved\n"; } - } + else + ++n_no_progress; + + if (state.temp <= 1e-3 + /*&& n_no_progress >= 5*/) + break; + + double Raccept = (double)state.n_accept / (double)state.n_move; + + + int M = 30; + double upper = 0.6, + lower = 0.4; + + if (state.best_wirelength < 0.95 * avg_wirelength) + avg_wirelength = 0.8*avg_wirelength + 0.2 * state.best_wirelength; + else + { + if (Raccept >= 0.8) + { + state.temp *= 0.7; + } + else if (Raccept > upper) + { + if (state.diameter < M) + ++state.diameter; + else + state.temp *= 0.9; + } + else if (Raccept > lower) + { + state.temp *= 0.95; + } + else + { + // Raccept < 0.3 + if (state.diameter > 1) + --state.diameter; + else + state.temp *= 0.8; + } + } + } } NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From 47566cf5e930aeb9a447dbef603ba64690335382 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 15 Jun 2018 18:26:31 +0200 Subject: Improving SA placer performance Signed-off-by: David Shah --- common/place.cc | 71 ++++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 50 insertions(+), 21 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index 99d5de32..e3f183a2 100644 --- a/common/place.cc +++ b/common/place.cc @@ -36,6 +36,14 @@ #include "arch_place.h" #include "log.h" +namespace std { + template <> struct hash> { + size_t operator()(const std::tuple &x) const noexcept { + return std::hash()(get<0>(x)) + std::hash()(get<1>(x)) + std::hash()(get<2>(x)); + } + }; +}; + NEXTPNR_NAMESPACE_BEGIN void place_design(Design *design) @@ -143,7 +151,12 @@ static uint32_t xorshift32(rnd_state &rnd) } static float random_float_upto(rnd_state &rnd, float limit) { - return xorshift32(rnd) / (4294967295 / limit); + return xorshift32(rnd) / (4294967296 / limit); +} + + +static int random_int_between(rnd_state &rnd, int a, int b) { + return a + int(random_float_upto(rnd, b - a)); } static void place_initial(Design *design, CellInfo *cell, rnd_state &rnd) @@ -184,6 +197,7 @@ struct SAState { bool improved = false; int n_move, n_accept; int diameter = 35; + std::vector>>> fast_bels; }; static float get_wirelength(Chip *chip, NetInfo *net) { @@ -212,8 +226,10 @@ static float get_wirelength(Chip *chip, NetInfo *net) { } static bool try_swap_position(Design *design, CellInfo *cell, BelId newBel, rnd_state &rnd, SAState &state) { - std::unordered_set update; - std::unordered_map new_lengths; + static std::unordered_set update; + static std::vector> new_lengths; + new_lengths.clear(); + update.clear(); Chip &chip = design->chip; BelId oldBel = cell->bel; IdString other = chip.getBelCell(newBel, true); @@ -258,7 +274,7 @@ static bool try_swap_position(Design *design, CellInfo *cell, BelId newBel, rnd_ new_wirelength -= state.wirelengths.at(net); float net_new_wl = get_wirelength(&chip, net); new_wirelength += net_new_wl; - new_lengths[net] = net_new_wl; + new_lengths.push_back(std::make_pair(net, net_new_wl)); } delta = new_wirelength - state.best_wirelength; state.n_move++; @@ -275,7 +291,7 @@ static bool try_swap_position(Design *design, CellInfo *cell, BelId newBel, rnd_ } state.best_wirelength = new_wirelength; for (auto new_wl : new_lengths) - state.wirelengths[new_wl.first] = new_wl.second; + state.wirelengths.at(new_wl.first) = new_wl.second; return true; swap_fail: @@ -288,28 +304,26 @@ swap_fail: return false; } -BelId random_bel_for_cell(Design *design, CellInfo *cell, SAState state, rnd_state &rnd) +BelId random_bel_for_cell(Design *design, CellInfo *cell, SAState& state, rnd_state &rnd) { BelId best_bel = BelId(); - float best_score = std::numeric_limits::infinity(); Chip &chip = design->chip; BelType targetType = belTypeFromId(cell->type); + assert(int(targetType) < state.fast_bels.size()); float x = 0, y = 0; chip.estimatePosition(cell->bel, x, y); - for (auto bel : chip.getBels()) { - if (chip.getBelType(bel) == targetType) { - float score = random_float_upto(rnd, 1.0); - float nx = 0, ny = 0; - chip.estimatePosition(bel, nx, ny); - if (std::abs(nx - x) > state.diameter || std::abs(ny - y) > state.diameter) - continue; - if (score <= best_score) { - best_score = score; - best_bel = bel; - } - } + while (true) { + int nx = random_int_between(rnd, std::max(int(x) - state.diameter, 0), int(x) + state.diameter + 1); + int ny = random_int_between(rnd, std::max(int(y) - state.diameter, 0), int(y) + state.diameter + 1); + if (nx >= state.fast_bels.at(int(targetType)).size()) + continue; + if (ny >= state.fast_bels.at(int(targetType)).at(nx).size()) + continue; + const auto &fb = state.fast_bels.at(int(targetType)).at(nx).at(ny); + if (fb.size() == 0) + continue; + return fb.at(random_int_between(rnd, 0, fb.size())); } - return best_bel; } void place_design_heuristic(Design *design) @@ -347,6 +361,8 @@ void place_design_heuristic(Design *design) rnd_state rnd; rnd.state = 1; std::vector autoplaced; + SAState state; + for (auto cell : design->cells) { CellInfo *ci = cell.second; if (ci->bel == BelId()) { @@ -356,7 +372,20 @@ void place_design_heuristic(Design *design) } log_info("placed %d/%d\n", placed_cells, total_cells); } - SAState state; + + for (auto bel : design->chip.getBels()) { + float x, y; + design->chip.estimatePosition(bel, x, y); + BelType type = design->chip.getBelType(bel); + if (state.fast_bels.size() < int(type)+1) + state.fast_bels.resize(int(type)+1); + if (state.fast_bels.at(int(type)).size() < int(x)+1) + state.fast_bels.at(int(type)).resize(int(x) + 1); + if (state.fast_bels.at(int(type)).at(int(x)).size() < int(y)+1) + state.fast_bels.at(int(type)).at(int(x)).resize(int(y) + 1); + state.fast_bels.at(int(type)).at(int(x)).at(int((y))).push_back(bel); + } + state.best_wirelength = 0; for (auto net : design->nets) { float wl = get_wirelength(&design->chip, net.second); -- cgit v1.2.3 From 432fe522742c28d6561c85fa8ab16a216a0ac3c5 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 15 Jun 2018 20:00:11 +0200 Subject: Remove dead code Signed-off-by: David Shah --- common/place.cc | 8 -------- 1 file changed, 8 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index e3f183a2..0bb5f3af 100644 --- a/common/place.cc +++ b/common/place.cc @@ -36,14 +36,6 @@ #include "arch_place.h" #include "log.h" -namespace std { - template <> struct hash> { - size_t operator()(const std::tuple &x) const noexcept { - return std::hash()(get<0>(x)) + std::hash()(get<1>(x)) + std::hash()(get<2>(x)); - } - }; -}; - NEXTPNR_NAMESPACE_BEGIN void place_design(Design *design) -- cgit v1.2.3 From 579455d1b0700108c8e327f80bb903f703e57a79 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Fri, 15 Jun 2018 20:54:57 +0200 Subject: Fix router for routing to the same dest wire twice Signed-off-by: Clifford Wolf --- common/route.cc | 37 ++++++++++++++++--------------------- 1 file changed, 16 insertions(+), 21 deletions(-) (limited to 'common') diff --git a/common/route.cc b/common/route.cc index 17e3b63b..30d40577 100644 --- a/common/route.cc +++ b/common/route.cc @@ -167,19 +167,18 @@ struct Router visited[qw.wire] = qw; } - while (!queue.empty()) { - visitCnt++; + while (!queue.empty() && !visited.count(dst_wire)) { QueuedWire qw = queue.top(); queue.pop(); for (auto pip : chip.getPipsDownhill(qw.wire)) { float next_delay = qw.delay; + visitCnt++; if (!chip.checkPipAvail(pip)) { - if (ripup) - next_delay += ripup_pip_penalty; - else + if (!ripup || net_name == chip.getPipNet(pip, true)) continue; + next_delay += ripup_pip_penalty; } WireId next_wire = chip.getPipDstWire(pip); @@ -188,19 +187,21 @@ struct Router if (visited.count(next_wire)) { if (visited.at(next_wire).delay <= next_delay + 1e-3) continue; +#if 0 // FIXME if (verbose) log("Found better route to %s. Old vs new delay " "estimate: %.2f %.2f\n", chip.getWireName(next_wire).c_str(), visited.at(next_wire).delay, next_delay); +#endif revisitCnt++; } if (!chip.checkWireAvail(next_wire)) { - if (ripup) - next_delay += ripup_wire_penalty; - else + if (!ripup || + net_name == chip.getWireNet(next_wire, true)) continue; + next_delay += ripup_wire_penalty; } QueuedWire next_qw; @@ -210,14 +211,6 @@ struct Router next_qw.togo = chip.estimateDelay(next_wire, dst_wire); visited[next_qw.wire] = next_qw; queue.push(next_qw); - - if (next_qw.wire == dst_wire) { - std::priority_queue, - QueuedWire::Greater> - empty_queue; - std::swap(queue, empty_queue); - break; - } } } @@ -393,9 +386,10 @@ void route_design(Design *design, bool verbose) netsQueue.clear(); - log_info(" processed %d nets. (%d routed, %d failed)\n", netCnt, - netCnt - int(ripupQueue.size()), int(ripupQueue.size())); - log_info("routing pass visited %d wires (%.2f%% revisits).\n", visitCnt, + if (netCnt % 100 != 0) + log_info(" processed %d nets. (%d routed, %d failed)\n", netCnt, + netCnt - int(ripupQueue.size()), int(ripupQueue.size())); + log_info("routing pass visited %d PIPs (%.2f%% revisits).\n", visitCnt, (100.0 * revisitCnt) / visitCnt); if (!ripupQueue.empty()) { @@ -431,8 +425,9 @@ void route_design(Design *design, bool verbose) ripCnt); } - log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt); - log_info("routing pass visited %d wires (%.2f%% revisits).\n", + if (netCnt % 100 != 0) + log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt); + log_info("routing pass visited %d PIPs (%.2f%% revisits).\n", visitCnt, (100.0 * revisitCnt) / visitCnt); log_info("ripped up %d previously routed nets. continue routing.\n", -- cgit v1.2.3 From 2479b4ecbf629192db18e3873dd9b4716f8b4752 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 15 Jun 2018 21:16:53 +0200 Subject: Improve placement heuristic Signed-off-by: David Shah --- common/place.cc | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index 0bb5f3af..ea9f5e34 100644 --- a/common/place.cc +++ b/common/place.cc @@ -415,8 +415,7 @@ void place_design_heuristic(Design *design) else ++n_no_progress; - if (state.temp <= 1e-3 - /*&& n_no_progress >= 5*/) + if (state.temp <= 1e-3 && n_no_progress >= 5) break; double Raccept = (double)state.n_accept / (double)state.n_move; -- cgit v1.2.3 From 71903e29d4cb535f9244f55036d7980fe09de782 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 15 Jun 2018 21:29:32 +0200 Subject: place: Reformat placer Signed-off-by: David Shah --- common/place.cc | 95 ++++++++++++++++++++++++++++----------------------------- 1 file changed, 46 insertions(+), 49 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index ea9f5e34..6610ac37 100644 --- a/common/place.cc +++ b/common/place.cc @@ -18,6 +18,7 @@ */ #include "place.h" +#include #include #include #include @@ -25,14 +26,13 @@ #include #include #include +#include #include #include #include #include #include #include -#include -#include #include "arch_place.h" #include "log.h" @@ -126,7 +126,8 @@ void place_design(Design *design) } } -struct rnd_state { +struct rnd_state +{ uint32_t state; }; @@ -142,12 +143,13 @@ static uint32_t xorshift32(rnd_state &rnd) return x; } -static float random_float_upto(rnd_state &rnd, float limit) { +static float random_float_upto(rnd_state &rnd, float limit) +{ return xorshift32(rnd) / (4294967296 / limit); } - -static int random_int_between(rnd_state &rnd, int a, int b) { +static int random_int_between(rnd_state &rnd, int a, int b) +{ return a + int(random_float_upto(rnd, b - a)); } @@ -156,7 +158,7 @@ static void place_initial(Design *design, CellInfo *cell, rnd_state &rnd) BelId best_bel = BelId(); float best_score = std::numeric_limits::infinity(); Chip &chip = design->chip; - if(cell->bel != BelId()) { + if (cell->bel != BelId()) { chip.unbindBel(cell->bel); cell->bel = BelId(); } @@ -182,7 +184,8 @@ static void place_initial(Design *design, CellInfo *cell, rnd_state &rnd) cell->attrs["BEL"] = chip.getBelName(cell->bel).str(); } -struct SAState { +struct SAState +{ std::unordered_map wirelengths; float best_wirelength = std::numeric_limits::infinity(); float temp = 1000; @@ -192,7 +195,8 @@ struct SAState { std::vector>>> fast_bels; }; -static float get_wirelength(Chip *chip, NetInfo *net) { +static float get_wirelength(Chip *chip, NetInfo *net) +{ float wirelength = 0; float driver_x = 0, driver_y = 0; bool consider_driver = false; @@ -201,7 +205,8 @@ static float get_wirelength(Chip *chip, NetInfo *net) { return 0; if (driver_cell->bel == BelId()) return 0; - consider_driver = chip->estimatePosition(driver_cell->bel, driver_x, driver_y); + consider_driver = + chip->estimatePosition(driver_cell->bel, driver_x, driver_y); if (!consider_driver) return 0; for (auto load : net->users) { @@ -217,7 +222,9 @@ static float get_wirelength(Chip *chip, NetInfo *net) { return wirelength; } -static bool try_swap_position(Design *design, CellInfo *cell, BelId newBel, rnd_state &rnd, SAState &state) { +static bool try_swap_position(Design *design, CellInfo *cell, BelId newBel, + rnd_state &rnd, SAState &state) +{ static std::unordered_set update; static std::vector> new_lengths; new_lengths.clear(); @@ -271,7 +278,9 @@ static bool try_swap_position(Design *design, CellInfo *cell, BelId newBel, rnd_ delta = new_wirelength - state.best_wirelength; state.n_move++; - if (delta < 0 || (state.temp > 1e-6 && random_float_upto(rnd, 1.0) <= std::exp(-delta/state.temp))) { + if (delta < 0 || + (state.temp > 1e-6 && + random_float_upto(rnd, 1.0) <= std::exp(-delta / state.temp))) { state.n_accept++; if (delta < 0) state.improved = true; @@ -296,7 +305,8 @@ swap_fail: return false; } -BelId random_bel_for_cell(Design *design, CellInfo *cell, SAState& state, rnd_state &rnd) +BelId random_bel_for_cell(Design *design, CellInfo *cell, SAState &state, + rnd_state &rnd) { BelId best_bel = BelId(); Chip &chip = design->chip; @@ -305,8 +315,10 @@ BelId random_bel_for_cell(Design *design, CellInfo *cell, SAState& state, rnd_st float x = 0, y = 0; chip.estimatePosition(cell->bel, x, y); while (true) { - int nx = random_int_between(rnd, std::max(int(x) - state.diameter, 0), int(x) + state.diameter + 1); - int ny = random_int_between(rnd, std::max(int(y) - state.diameter, 0), int(y) + state.diameter + 1); + int nx = random_int_between(rnd, std::max(int(x) - state.diameter, 0), + int(x) + state.diameter + 1); + int ny = random_int_between(rnd, std::max(int(y) - state.diameter, 0), + int(y) + state.diameter + 1); if (nx >= state.fast_bels.at(int(targetType)).size()) continue; if (ny >= state.fast_bels.at(int(targetType)).at(nx).size()) @@ -369,11 +381,11 @@ void place_design_heuristic(Design *design) float x, y; design->chip.estimatePosition(bel, x, y); BelType type = design->chip.getBelType(bel); - if (state.fast_bels.size() < int(type)+1) - state.fast_bels.resize(int(type)+1); - if (state.fast_bels.at(int(type)).size() < int(x)+1) + if (state.fast_bels.size() < int(type) + 1) + state.fast_bels.resize(int(type) + 1); + if (state.fast_bels.at(int(type)).size() < int(x) + 1) state.fast_bels.at(int(type)).resize(int(x) + 1); - if (state.fast_bels.at(int(type)).at(int(x)).size() < int(y)+1) + if (state.fast_bels.at(int(type)).at(int(x)).size() < int(y) + 1) state.fast_bels.at(int(type)).at(int(x)).resize(int(y) + 1); state.fast_bels.at(int(type)).at(int(x)).at(int((y))).push_back(bel); } @@ -388,31 +400,26 @@ void place_design_heuristic(Design *design) int n_no_progress = 0; double avg_wirelength = state.best_wirelength; state.temp = 10000; - for (int iter=1;; iter++) - { + for (int iter = 1;; iter++) { state.n_move = state.n_accept = 0; state.improved = false; - //if (iter % 50 == 0) - log(" at iteration #%d: temp = %f, wire length = %f\n", iter, state.temp, state.best_wirelength); + // if (iter % 50 == 0) + log(" at iteration #%d: temp = %f, wire length = %f\n", iter, + state.temp, state.best_wirelength); - for (int m = 0; m < 15; ++m) - { - for (auto cell : autoplaced) - { + for (int m = 0; m < 15; ++m) { + for (auto cell : autoplaced) { BelId try_bel = random_bel_for_cell(design, cell, state, rnd); if (try_bel != BelId() && try_bel != cell->bel) try_swap_position(design, cell, try_bel, rnd, state); } - } - if (state.improved) - { + if (state.improved) { n_no_progress = 0; // std::cout << "improved\n"; - } - else + } else ++n_no_progress; if (state.temp <= 1e-3 && n_no_progress >= 5) @@ -420,33 +427,23 @@ void place_design_heuristic(Design *design) double Raccept = (double)state.n_accept / (double)state.n_move; - int M = 30; - double upper = 0.6, - lower = 0.4; + double upper = 0.6, lower = 0.4; if (state.best_wirelength < 0.95 * avg_wirelength) - avg_wirelength = 0.8*avg_wirelength + 0.2 * state.best_wirelength; - else - { - if (Raccept >= 0.8) - { + avg_wirelength = 0.8 * avg_wirelength + 0.2 * state.best_wirelength; + else { + if (Raccept >= 0.8) { state.temp *= 0.7; - } - else if (Raccept > upper) - { + } else if (Raccept > upper) { if (state.diameter < M) ++state.diameter; else state.temp *= 0.9; - } - else if (Raccept > lower) - { + } else if (Raccept > lower) { state.temp *= 0.95; - } - else - { + } else { // Raccept < 0.3 if (state.diameter > 1) --state.diameter; -- cgit v1.2.3 From c0a26271790b8eb6c67d97b45f089660cdcfa37d Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 16 Jun 2018 12:04:38 +0200 Subject: place: Tidying up the SA placer Signed-off-by: David Shah --- common/place.cc | 140 ++++++++++++++------------------------------------------ common/place.h | 4 +- 2 files changed, 36 insertions(+), 108 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index 6610ac37..cdc29042 100644 --- a/common/place.cc +++ b/common/place.cc @@ -38,94 +38,6 @@ NEXTPNR_NAMESPACE_BEGIN -void place_design(Design *design) -{ - std::set types_used; - std::set::iterator not_found, element; - std::set used_bels; - - log_info("Placing..\n"); - - // Initial constraints placer - for (auto cell_entry : design->cells) { - CellInfo *cell = cell_entry.second; - auto loc = cell->attrs.find("BEL"); - if (loc != cell->attrs.end()) { - std::string loc_name = loc->second; - BelId bel = design->chip.getBelByName(IdString(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()); - } - - BelType bel_type = design->chip.getBelType(bel); - if (bel_type != belTypeFromId(cell->type)) { - log_error("Bel \'%s\' of type \'%s\' does not match cell " - "\'%s\' of type \'%s\'", - loc_name.c_str(), belTypeToId(bel_type).c_str(), - cell->name.c_str(), cell->type.c_str()); - } - - cell->bel = bel; - design->chip.bindBel(bel, cell->name); - } - } - - for (auto cell_entry : design->cells) { - CellInfo *cell = cell_entry.second; - // Ignore already placed cells - if (cell->bel != BelId()) - continue; - - BelType bel_type; - - element = types_used.find(cell->type); - if (element != types_used.end()) { - continue; - } - - bel_type = belTypeFromId(cell->type); - if (bel_type == BelType()) { - log_error("No Bel of type \'%s\' defined for " - "this chip\n", - cell->type.c_str()); - } - types_used.insert(cell->type); - } - - for (auto bel_type_name : types_used) { - auto blist = design->chip.getBels(); - BelType bel_type = belTypeFromId(bel_type_name); - auto bi = blist.begin(); - - for (auto cell_entry : design->cells) { - CellInfo *cell = cell_entry.second; - - // Ignore already placed cells - if (cell->bel != BelId()) - continue; - // Only place one type of Bel at a time - if (cell->type != bel_type_name) - continue; - - while ((bi != blist.end()) && - ((design->chip.getBelType(*bi) != bel_type || - !design->chip.checkBelAvail(*bi)) || - !isValidBelForCell(design, cell, *bi))) - bi++; - if (bi == blist.end()) - log_error("Too many \'%s\' used in design\n", - cell->type.c_str()); - cell->bel = *bi++; - design->chip.bindBel(cell->bel, cell->name); - - // Back annotate location - cell->attrs["BEL"] = design->chip.getBelName(cell->bel).str(); - } - } -} - struct rnd_state { uint32_t state; @@ -153,6 +65,7 @@ static int random_int_between(rnd_state &rnd, int a, int b) return a + int(random_float_upto(rnd, b - a)); } +// Initial random placement static void place_initial(Design *design, CellInfo *cell, rnd_state &rnd) { BelId best_bel = BelId(); @@ -184,10 +97,11 @@ static void place_initial(Design *design, CellInfo *cell, rnd_state &rnd) cell->attrs["BEL"] = chip.getBelName(cell->bel).str(); } +// Stores the state of the SA placer struct SAState { std::unordered_map wirelengths; - float best_wirelength = std::numeric_limits::infinity(); + float curr_wirelength = std::numeric_limits::infinity(); float temp = 1000; bool improved = false; int n_move, n_accept; @@ -195,6 +109,7 @@ struct SAState std::vector>>> fast_bels; }; +// Get the total estimated wirelength for a net static float get_wirelength(Chip *chip, NetInfo *net) { float wirelength = 0; @@ -222,6 +137,7 @@ static float get_wirelength(Chip *chip, NetInfo *net) return wirelength; } +// Attempt a SA position swap, return true on success or false on failure static bool try_swap_position(Design *design, CellInfo *cell, BelId newBel, rnd_state &rnd, SAState &state) { @@ -268,16 +184,18 @@ static bool try_swap_position(Design *design, CellInfo *cell, BelId newBel, if (other != IdString()) other_cell->bel = oldBel; - new_wirelength = state.best_wirelength; + new_wirelength = state.curr_wirelength; + + // Recalculate wirelengths for all nets touched by the peturbation for (auto net : update) { new_wirelength -= state.wirelengths.at(net); float net_new_wl = get_wirelength(&chip, net); new_wirelength += net_new_wl; new_lengths.push_back(std::make_pair(net, net_new_wl)); } - delta = new_wirelength - state.best_wirelength; + delta = new_wirelength - state.curr_wirelength; state.n_move++; - + // SA acceptance criterea if (delta < 0 || (state.temp > 1e-6 && random_float_upto(rnd, 1.0) <= std::exp(-delta / state.temp))) { @@ -290,7 +208,7 @@ static bool try_swap_position(Design *design, CellInfo *cell, BelId newBel, chip.unbindBel(newBel); goto swap_fail; } - state.best_wirelength = new_wirelength; + state.curr_wirelength = new_wirelength; for (auto new_wl : new_lengths) state.wirelengths.at(new_wl.first) = new_wl.second; @@ -305,6 +223,8 @@ swap_fail: return false; } +// Find a random Bel of the correct type for a cell, within the specified +// diameter BelId random_bel_for_cell(Design *design, CellInfo *cell, SAState &state, rnd_state &rnd) { @@ -330,7 +250,7 @@ BelId random_bel_for_cell(Design *design, CellInfo *cell, SAState &state, } } -void place_design_heuristic(Design *design) +void place_design_sa(Design *design) { size_t total_cells = design->cells.size(), placed_cells = 0; std::queue visit_cells; @@ -366,7 +286,7 @@ void place_design_heuristic(Design *design) rnd.state = 1; std::vector autoplaced; SAState state; - + // Place cells randomly initially for (auto cell : design->cells) { CellInfo *ci = cell.second; if (ci->bel == BelId()) { @@ -376,7 +296,8 @@ void place_design_heuristic(Design *design) } log_info("placed %d/%d\n", placed_cells, total_cells); } - + // Build up a fast position/type to Bel lookup table + int max_x = 0, max_y = 0; for (auto bel : design->chip.getBels()) { float x, y; design->chip.estimatePosition(bel, x, y); @@ -387,35 +308,44 @@ void place_design_heuristic(Design *design) state.fast_bels.at(int(type)).resize(int(x) + 1); if (state.fast_bels.at(int(type)).at(int(x)).size() < int(y) + 1) state.fast_bels.at(int(type)).at(int(x)).resize(int(y) + 1); + max_x = std::max(max_x, int(x)); + max_y = std::max(max_y, int(y)); state.fast_bels.at(int(type)).at(int(x)).at(int((y))).push_back(bel); } - - state.best_wirelength = 0; + state.diameter = std::max(max_x, max_y) + 1; + // Calculate wirelength after initial placement + state.curr_wirelength = 0; for (auto net : design->nets) { float wl = get_wirelength(&design->chip, net.second); state.wirelengths[net.second] = wl; - state.best_wirelength += wl; + state.curr_wirelength += wl; } int n_no_progress = 0; - double avg_wirelength = state.best_wirelength; + double avg_wirelength = state.curr_wirelength; state.temp = 10000; + + // Main simulated annealing loop for (int iter = 1;; iter++) { state.n_move = state.n_accept = 0; state.improved = false; // if (iter % 50 == 0) log(" at iteration #%d: temp = %f, wire length = %f\n", iter, - state.temp, state.best_wirelength); + state.temp, state.curr_wirelength); 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(design, cell, state, rnd); + // 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(design, cell, try_bel, rnd, state); } } - + // Heuristic to improve placement on the 8k if (state.improved) { n_no_progress = 0; // std::cout << "improved\n"; @@ -427,12 +357,12 @@ void place_design_heuristic(Design *design) double Raccept = (double)state.n_accept / (double)state.n_move; - int M = 30; + int M = std::max(max_x, max_y) + 1; double upper = 0.6, lower = 0.4; - if (state.best_wirelength < 0.95 * avg_wirelength) - avg_wirelength = 0.8 * avg_wirelength + 0.2 * state.best_wirelength; + if (state.curr_wirelength < 0.95 * avg_wirelength) + avg_wirelength = 0.8 * avg_wirelength + 0.2 * state.curr_wirelength; else { if (Raccept >= 0.8) { state.temp *= 0.7; diff --git a/common/place.h b/common/place.h index fd4de534..f320111e 100644 --- a/common/place.h +++ b/common/place.h @@ -23,9 +23,7 @@ NEXTPNR_NAMESPACE_BEGIN -extern void place_design(Design *design); - -extern void place_design_heuristic(Design *design); +extern void place_design_sa(Design *design); NEXTPNR_NAMESPACE_END -- cgit v1.2.3