From c4241db1177b6caf1d5c44d83d434136c16e3dd4 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 16 Jun 2018 16:54:57 +0200 Subject: Tweaking placer and router Signed-off-by: David Shah --- common/place.cc | 7 +++++-- common/route.cc | 4 ++-- 2 files changed, 7 insertions(+), 4 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index 55a4d021..dfca313f 100644 --- a/common/place.cc +++ b/common/place.cc @@ -122,6 +122,7 @@ static float get_wirelength(Chip *chip, NetInfo *net) return 0; consider_driver = chip->estimatePosition(driver_cell->bel, driver_x, driver_y); + WireId drv_wire = chip->getWireBelPin(driver_cell->bel, portPinFromId(net->driver.port)); if (!consider_driver) return 0; for (auto load : net->users) { @@ -131,8 +132,10 @@ static float get_wirelength(Chip *chip, NetInfo *net) int 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); + //chip->estimatePosition(load_cell->bel, load_x, load_y); + WireId user_wire = chip->getWireBelPin(load_cell->bel, portPinFromId(load.port)); + //wirelength += std::abs(load_x - driver_x) + std::abs(load_y - driver_y); + wirelength += chip->estimateDelay(drv_wire, user_wire); } return wirelength; } diff --git a/common/route.cc b/common/route.cc index 247c8840..32212c7d 100644 --- a/common/route.cc +++ b/common/route.cc @@ -440,8 +440,8 @@ void route_design(Design *design, bool verbose) "routing.\n", int(netsQueue.size())); - ripup_pip_penalty *= 1.5; - ripup_wire_penalty *= 1.5; + ripup_pip_penalty += 5; + ripup_wire_penalty += 5; } } -- cgit v1.2.3 From bb92dc09a8d3450a7d356edf0ac2e9971083cf2f Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 16 Jun 2018 17:09:41 +0200 Subject: ice40: Promote reset signal Signed-off-by: David Shah --- common/place.cc | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) (limited to 'common') diff --git a/common/place.cc b/common/place.cc index dfca313f..a6d3040f 100644 --- a/common/place.cc +++ b/common/place.cc @@ -122,7 +122,8 @@ static float get_wirelength(Chip *chip, NetInfo *net) return 0; consider_driver = chip->estimatePosition(driver_cell->bel, driver_x, driver_y); - WireId drv_wire = chip->getWireBelPin(driver_cell->bel, portPinFromId(net->driver.port)); + WireId drv_wire = chip->getWireBelPin(driver_cell->bel, + portPinFromId(net->driver.port)); if (!consider_driver) return 0; for (auto load : net->users) { @@ -132,9 +133,11 @@ static float get_wirelength(Chip *chip, NetInfo *net) int load_x = 0, load_y = 0; if (load_cell->bel == BelId()) continue; - //chip->estimatePosition(load_cell->bel, load_x, load_y); - WireId user_wire = chip->getWireBelPin(load_cell->bel, portPinFromId(load.port)); - //wirelength += std::abs(load_x - driver_x) + std::abs(load_y - driver_y); + // chip->estimatePosition(load_cell->bel, load_x, load_y); + WireId user_wire = + chip->getWireBelPin(load_cell->bel, portPinFromId(load.port)); + // wirelength += std::abs(load_x - driver_x) + std::abs(load_y - + // driver_y); wirelength += chip->estimateDelay(drv_wire, user_wire); } return wirelength; -- cgit v1.2.3 From 6d68af1e622fb960c64b0bf899d1397c2ba69995 Mon Sep 17 00:00:00 2001 From: ZipCPU Date: Sat, 16 Jun 2018 11:59:42 -0400 Subject: Renamed placer to Simulated-Annealing placer --- common/place.cc | 393 ----------------------------------------------------- common/place_sa.cc | 393 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 393 insertions(+), 393 deletions(-) delete mode 100644 common/place.cc create mode 100644 common/place_sa.cc (limited to 'common') diff --git a/common/place.cc b/common/place.cc deleted file mode 100644 index a6d3040f..00000000 --- a/common/place.cc +++ /dev/null @@ -1,393 +0,0 @@ -/* - * nextpnr -- Next Generation Place and Route - * - * Copyright (C) 2018 Clifford Wolf - * - * Permission to use, copy, modify, and/or distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - * - */ - -#include "place.h" -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include "arch_place.h" -#include "log.h" - -NEXTPNR_NAMESPACE_BEGIN - -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) / (4294967296 / limit); -} - -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(); - float best_score = std::numeric_limits::infinity(); - 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) && - isValidBelForCell(design, cell, bel)) { - float score = random_float_upto(rnd, 1.0); - if (score <= best_score) { - best_score = score; - best_bel = bel; - } - } - } - 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(); -} - -// Stores the state of the SA placer -struct SAState -{ - std::unordered_map wirelengths; - float curr_wirelength = std::numeric_limits::infinity(); - float temp = 1000; - bool improved = false; - int n_move, n_accept; - int diameter = 35; - std::vector>>> fast_bels; -}; - -// Get the total estimated wirelength for a net -static float get_wirelength(Chip *chip, NetInfo *net) -{ - float wirelength = 0; - int 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); - WireId drv_wire = chip->getWireBelPin(driver_cell->bel, - portPinFromId(net->driver.port)); - if (!consider_driver) - return 0; - for (auto load : net->users) { - if (load.cell == nullptr) - continue; - CellInfo *load_cell = load.cell; - int load_x = 0, load_y = 0; - if (load_cell->bel == BelId()) - continue; - // chip->estimatePosition(load_cell->bel, load_x, load_y); - WireId user_wire = - chip->getWireBelPin(load_cell->bel, portPinFromId(load.port)); - // wirelength += std::abs(load_x - driver_x) + std::abs(load_y - - // driver_y); - wirelength += chip->estimateDelay(drv_wire, user_wire); - } - 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) -{ - 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); - 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.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.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))) { - state.n_accept++; - if (delta < 0) - state.improved = true; - } else { - if (other != IdString()) - chip.unbindBel(oldBel); - chip.unbindBel(newBel); - goto swap_fail; - } - state.curr_wirelength = new_wirelength; - for (auto new_wl : new_lengths) - state.wirelengths.at(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; -} - -// 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) -{ - BelId best_bel = BelId(); - Chip &chip = design->chip; - BelType targetType = belTypeFromId(cell->type); - assert(int(targetType) < state.fast_bels.size()); - int 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); - 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())); - } -} - -void place_design_sa(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); - } - } - log_info("place_constraints placed %d\n", int(placed_cells)); - rnd_state rnd; - 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()) { - place_initial(design, ci, rnd); - autoplaced.push_back(cell.second); - placed_cells++; - } - log_info("placed %d/%d\n", int(placed_cells), int(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()) { - int 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); - 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.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.curr_wirelength += wl; - } - - int n_no_progress = 0; - 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.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"; - } 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 = std::max(max_x, max_y) + 1; - - double upper = 0.6, lower = 0.4; - - 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; - } 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 diff --git a/common/place_sa.cc b/common/place_sa.cc new file mode 100644 index 00000000..a6d3040f --- /dev/null +++ b/common/place_sa.cc @@ -0,0 +1,393 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Clifford Wolf + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "place.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include "arch_place.h" +#include "log.h" + +NEXTPNR_NAMESPACE_BEGIN + +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) / (4294967296 / limit); +} + +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(); + float best_score = std::numeric_limits::infinity(); + 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) && + isValidBelForCell(design, cell, bel)) { + float score = random_float_upto(rnd, 1.0); + if (score <= best_score) { + best_score = score; + best_bel = bel; + } + } + } + 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(); +} + +// Stores the state of the SA placer +struct SAState +{ + std::unordered_map wirelengths; + float curr_wirelength = std::numeric_limits::infinity(); + float temp = 1000; + bool improved = false; + int n_move, n_accept; + int diameter = 35; + std::vector>>> fast_bels; +}; + +// Get the total estimated wirelength for a net +static float get_wirelength(Chip *chip, NetInfo *net) +{ + float wirelength = 0; + int 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); + WireId drv_wire = chip->getWireBelPin(driver_cell->bel, + portPinFromId(net->driver.port)); + if (!consider_driver) + return 0; + for (auto load : net->users) { + if (load.cell == nullptr) + continue; + CellInfo *load_cell = load.cell; + int load_x = 0, load_y = 0; + if (load_cell->bel == BelId()) + continue; + // chip->estimatePosition(load_cell->bel, load_x, load_y); + WireId user_wire = + chip->getWireBelPin(load_cell->bel, portPinFromId(load.port)); + // wirelength += std::abs(load_x - driver_x) + std::abs(load_y - + // driver_y); + wirelength += chip->estimateDelay(drv_wire, user_wire); + } + 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) +{ + 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); + 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.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.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))) { + state.n_accept++; + if (delta < 0) + state.improved = true; + } else { + if (other != IdString()) + chip.unbindBel(oldBel); + chip.unbindBel(newBel); + goto swap_fail; + } + state.curr_wirelength = new_wirelength; + for (auto new_wl : new_lengths) + state.wirelengths.at(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; +} + +// 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) +{ + BelId best_bel = BelId(); + Chip &chip = design->chip; + BelType targetType = belTypeFromId(cell->type); + assert(int(targetType) < state.fast_bels.size()); + int 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); + 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())); + } +} + +void place_design_sa(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); + } + } + log_info("place_constraints placed %d\n", int(placed_cells)); + rnd_state rnd; + 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()) { + place_initial(design, ci, rnd); + autoplaced.push_back(cell.second); + placed_cells++; + } + log_info("placed %d/%d\n", int(placed_cells), int(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()) { + int 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); + 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.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.curr_wirelength += wl; + } + + int n_no_progress = 0; + 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.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"; + } 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 = std::max(max_x, max_y) + 1; + + double upper = 0.6, lower = 0.4; + + 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; + } 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 41156d188e608804444a81146270fa10c8b4d309 Mon Sep 17 00:00:00 2001 From: ZipCPU Date: Sat, 16 Jun 2018 12:03:25 -0400 Subject: Changed place.h place_sa.h --- common/place.h | 30 ------------------------------ common/place_sa.h | 30 ++++++++++++++++++++++++++++++ 2 files changed, 30 insertions(+), 30 deletions(-) delete mode 100644 common/place.h create mode 100644 common/place_sa.h (limited to 'common') diff --git a/common/place.h b/common/place.h deleted file mode 100644 index f320111e..00000000 --- a/common/place.h +++ /dev/null @@ -1,30 +0,0 @@ -/* - * nextpnr -- Next Generation Place and Route - * - * Copyright (C) 2018 Clifford Wolf - * - * Permission to use, copy, modify, and/or distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - * - */ -#ifndef PLACE_H -#define PLACE_H - -#include "nextpnr.h" - -NEXTPNR_NAMESPACE_BEGIN - -extern void place_design_sa(Design *design); - -NEXTPNR_NAMESPACE_END - -#endif // PLACE_H diff --git a/common/place_sa.h b/common/place_sa.h new file mode 100644 index 00000000..f320111e --- /dev/null +++ b/common/place_sa.h @@ -0,0 +1,30 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Clifford Wolf + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ +#ifndef PLACE_H +#define PLACE_H + +#include "nextpnr.h" + +NEXTPNR_NAMESPACE_BEGIN + +extern void place_design_sa(Design *design); + +NEXTPNR_NAMESPACE_END + +#endif // PLACE_H -- cgit v1.2.3 From 218c4cd740bd88f52c0162356a440929e2f4815f Mon Sep 17 00:00:00 2001 From: ZipCPU Date: Sat, 16 Jun 2018 12:09:51 -0400 Subject: Renamed place.h to place_sa.h in place_sa.cc Signed-off-by: ZipCPU --- common/place_sa.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index a6d3040f..1635d97f 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -17,7 +17,7 @@ * */ -#include "place.h" +#include "place_sa.h" #include #include #include -- cgit v1.2.3 From e497575c8eb2eeef520e1e3b8b90f5d5ce811dd8 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 16 Jun 2018 18:45:32 +0200 Subject: place: Fix placer validity checks Signed-off-by: David Shah --- common/place_sa.cc | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index a6d3040f..9e3d3022 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -177,13 +177,16 @@ static bool try_swap_position(Design *design, CellInfo *cell, BelId newBel, } 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); - } + chip.bindBel(oldBel, other_cell->name); + } + + if (!isBelLocationValid(design, newBel) || ((other != IdString() && !isBelLocationValid(design, oldBel)))) { + chip.unbindBel(newBel); + if (other != IdString()) + chip.unbindBel(oldBel); + goto swap_fail; } cell->bel = newBel; -- cgit v1.2.3 From e95f38e88ebcd07e0cf313cabbd5c2e56a6db85c Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 10:55:19 +0200 Subject: place_sa: Run a validity check at the end of placement Signed-off-by: David Shah --- common/place_sa.cc | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index 157d7c38..aecbb80d 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -391,6 +391,15 @@ void place_design_sa(Design *design) } } } + for (auto bel : design->chip.getBels()) { + if (!isBelLocationValid(design, bel)) { + std::string cell_text = "no cell"; + IdString cell = design->chip.getBelCell(bel, false); + if (cell != IdString()) + cell_text = std::string("cell '") + cell.str() + "'"; + log_error("post-placement validity check failed for Bel '%s' (%s)", design->chip.getBelName(bel).c_str(), cell_text.c_str()); + } + } } NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From f9bfccf68e939a2d14c0d94a14234822e9727b89 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 11:14:49 +0200 Subject: Add 'get or default' functions Signed-off-by: David Shah --- common/util.h | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 63 insertions(+) create mode 100644 common/util.h (limited to 'common') diff --git a/common/util.h b/common/util.h new file mode 100644 index 00000000..2313a290 --- /dev/null +++ b/common/util.h @@ -0,0 +1,63 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 David Shah + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef UTIL_H +#define UTIL_H + +#include +#include "nextpnr.h" + +NEXTPNR_NAMESPACE_BEGIN + +// Get a value from a map-style container, returning default if value is not +// found +template +ValueType get_or_default(const Container &ct, const KeyType &key, + ValueType def = ValueType()) +{ + auto found = ct.find(key); + if (found == ct.end()) + return def; + else + return found->second; +}; + +// Get a value from a map-style container, converting to int, and returning +// default if value is not found +template +int int_or_default(const Container &ct, const KeyType &key, + int def = 0) +{ + auto found = ct.find(key); + if (found == ct.end()) + return def; + else + return std::stoi(found->second); +}; + +// As above, but convert to bool +template +bool bool_or_default(const Container &ct, const KeyType &key, + bool def = false) +{ + return bool(int_or_default(ct, key, int(def))); +}; +NEXTPNR_NAMESPACE_END + +#endif -- cgit v1.2.3 From c604426341c75bc34b9d97ad5cd49cc28f9198fb Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 11:33:31 +0200 Subject: place_sa: Ignore Bels locked by manual placement for SA swaps Signed-off-by: David Shah --- common/place_sa.cc | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index aecbb80d..aef759f8 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -107,6 +107,7 @@ struct SAState int n_move, n_accept; int diameter = 35; std::vector>>> fast_bels; + std::unordered_set locked_bels; }; // Get the total estimated wirelength for a net @@ -255,12 +256,17 @@ BelId random_bel_for_cell(Design *design, CellInfo *cell, SAState &state, 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())); + BelId bel = fb.at(random_int_between(rnd, 0, fb.size())); + if (state.locked_bels.find(bel) != state.locked_bels.end()) + continue; + return bel; } } void place_design_sa(Design *design) { + SAState state; + size_t total_cells = design->cells.size(), placed_cells = 0; std::queue visit_cells; // Initial constraints placer @@ -286,6 +292,7 @@ void place_design_sa(Design *design) cell->bel = bel; design->chip.bindBel(bel, cell->name); + state.locked_bels.insert(bel); placed_cells++; visit_cells.push(cell); } @@ -294,7 +301,6 @@ void place_design_sa(Design *design) rnd_state rnd; rnd.state = 1; std::vector autoplaced; - SAState state; // Place cells randomly initially for (auto cell : design->cells) { CellInfo *ci = cell.second; -- cgit v1.2.3 From 3afce5ff5a6adfa1baccb4f4625005300b9a3862 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 11:45:41 +0200 Subject: Improving the placer output Signed-off-by: David Shah --- common/design_utils.cc | 23 ++++++++++++++++++++++- common/design_utils.h | 3 +++ common/place_sa.cc | 14 ++++++++------ common/util.h | 12 +++++------- 4 files changed, 38 insertions(+), 14 deletions(-) (limited to 'common') diff --git a/common/design_utils.cc b/common/design_utils.cc index 85895a75..c6504fb9 100644 --- a/common/design_utils.cc +++ b/common/design_utils.cc @@ -18,7 +18,9 @@ */ #include "design_utils.h" - +#include +#include "log.h" +#include "util.h" NEXTPNR_NAMESPACE_BEGIN void replace_port(CellInfo *old_cell, IdString old_name, CellInfo *rep_cell, @@ -49,4 +51,23 @@ void replace_port(CellInfo *old_cell, IdString old_name, CellInfo *rep_cell, } } +// Print utilisation of a design +void print_utilisation(const Design *design) +{ + // Sort by Bel type + std::map used_types; + for (auto cell : design->cells) { + used_types[belTypeFromId(cell.second->type)]++; + } + std::map available_types; + for (auto bel : design->chip.getBels()) { + available_types[design->chip.getBelType(bel)]++; + } + log("\nDesign utilisation:\n"); + for (auto type : available_types) { + log("\t%20s: %5d/%5d\n", belTypeToId(type.first).c_str(), + get_or_default(used_types, type.first, 0), type.second); + } +} + NEXTPNR_NAMESPACE_END diff --git a/common/design_utils.h b/common/design_utils.h index 8d231d4c..0a33b168 100644 --- a/common/design_utils.h +++ b/common/design_utils.h @@ -83,6 +83,9 @@ CellInfo *net_driven_by(const NetInfo *net, F1 cell_pred, IdString port) } } +void print_utilisation(const Design *design); + + NEXTPNR_NAMESPACE_END #endif diff --git a/common/place_sa.cc b/common/place_sa.cc index aef759f8..7532213c 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -183,7 +183,8 @@ static bool try_swap_position(Design *design, CellInfo *cell, BelId newBel, chip.bindBel(oldBel, other_cell->name); } - if (!isBelLocationValid(design, newBel) || ((other != IdString() && !isBelLocationValid(design, oldBel)))) { + if (!isBelLocationValid(design, newBel) || + ((other != IdString() && !isBelLocationValid(design, oldBel)))) { chip.unbindBel(newBel); if (other != IdString()) chip.unbindBel(oldBel); @@ -309,7 +310,7 @@ void place_design_sa(Design *design) autoplaced.push_back(cell.second); placed_cells++; } - log_info("placed %d/%d\n", int(placed_cells), int(total_cells)); + // log_info("placed %d/%d\n", int(placed_cells), int(total_cells)); } // Build up a fast position/type to Bel lookup table int max_x = 0, max_y = 0; @@ -345,9 +346,9 @@ void place_design_sa(Design *design) 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.curr_wirelength); + if (iter % 5 == 0) + log(" at iteration #%d: temp = %f, wire length = %f\n", iter, + state.temp, state.curr_wirelength); for (int m = 0; m < 15; ++m) { // Loop through all automatically placed cells @@ -403,7 +404,8 @@ void place_design_sa(Design *design) IdString cell = design->chip.getBelCell(bel, false); if (cell != IdString()) cell_text = std::string("cell '") + cell.str() + "'"; - log_error("post-placement validity check failed for Bel '%s' (%s)", design->chip.getBelName(bel).c_str(), cell_text.c_str()); + log_error("post-placement validity check failed for Bel '%s' (%s)", + design->chip.getBelName(bel).c_str(), cell_text.c_str()); } } } diff --git a/common/util.h b/common/util.h index 2313a290..34b2ed02 100644 --- a/common/util.h +++ b/common/util.h @@ -27,7 +27,7 @@ NEXTPNR_NAMESPACE_BEGIN // Get a value from a map-style container, returning default if value is not // found -template +template ValueType get_or_default(const Container &ct, const KeyType &key, ValueType def = ValueType()) { @@ -40,9 +40,8 @@ ValueType get_or_default(const Container &ct, const KeyType &key, // Get a value from a map-style container, converting to int, and returning // default if value is not found -template -int int_or_default(const Container &ct, const KeyType &key, - int def = 0) +template +int int_or_default(const Container &ct, const KeyType &key, int def = 0) { auto found = ct.find(key); if (found == ct.end()) @@ -52,9 +51,8 @@ int int_or_default(const Container &ct, const KeyType &key, }; // As above, but convert to bool -template -bool bool_or_default(const Container &ct, const KeyType &key, - bool def = false) +template +bool bool_or_default(const Container &ct, const KeyType &key, bool def = false) { return bool(int_or_default(ct, key, int(def))); }; -- cgit v1.2.3 From 6a937e0b45ed9993d6cf4fd659693757c73b4f8f Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 11:49:57 +0200 Subject: Updating copyrights Signed-off-by: David Shah --- common/design_utils.cc | 1 + common/design_utils.h | 1 + common/place_sa.cc | 4 ++++ common/pybindings.cc | 2 +- common/pybindings.h | 2 +- common/pycontainers.h | 2 +- 6 files changed, 9 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/design_utils.cc b/common/design_utils.cc index c6504fb9..ae6e21ed 100644 --- a/common/design_utils.cc +++ b/common/design_utils.cc @@ -2,6 +2,7 @@ * nextpnr -- Next Generation Place and Route * * Copyright (C) 2018 Clifford Wolf + * Copyright (C) 2018 David Shah * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above diff --git a/common/design_utils.h b/common/design_utils.h index 0a33b168..b63c75c3 100644 --- a/common/design_utils.h +++ b/common/design_utils.h @@ -2,6 +2,7 @@ * nextpnr -- Next Generation Place and Route * * Copyright (C) 2018 Clifford Wolf + * Copyright (C) 2018 David Shah * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above diff --git a/common/place_sa.cc b/common/place_sa.cc index 7532213c..79700d3f 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -2,6 +2,10 @@ * nextpnr -- Next Generation Place and Route * * Copyright (C) 2018 Clifford Wolf + * Copyright (C) 2018 David Shah + * + * Simulated annealing implementation based on arachne-pnr + * Copyright (C) 2015-2018 Cotton Seed * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above diff --git a/common/pybindings.cc b/common/pybindings.cc index 10bbab7b..89f98716 100644 --- a/common/pybindings.cc +++ b/common/pybindings.cc @@ -2,7 +2,7 @@ * nextpnr -- Next Generation Place and Route * * Copyright (C) 2018 Clifford Wolf - * Copyright (C) 2018 David Shah + * Copyright (C) 2018 David Shah * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above diff --git a/common/pybindings.h b/common/pybindings.h index de6aa4c7..7616c055 100644 --- a/common/pybindings.h +++ b/common/pybindings.h @@ -2,7 +2,7 @@ * nextpnr -- Next Generation Place and Route * * Copyright (C) 2018 Clifford Wolf - * Copyright (C) 2018 David Shah + * Copyright (C) 2018 David Shah * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above diff --git a/common/pycontainers.h b/common/pycontainers.h index 992d0de9..9160dfb6 100644 --- a/common/pycontainers.h +++ b/common/pycontainers.h @@ -2,7 +2,7 @@ * nextpnr -- Next Generation Place and Route * * Copyright (C) 2018 Clifford Wolf - * Copyright (C) 2018 David Shah + * Copyright (C) 2018 David Shah * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above -- cgit v1.2.3 From 1b077320dc63b4dc1ecd1e9310dc80d89492d113 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 12:53:39 +0200 Subject: General reformatting Signed-off-by: David Shah --- common/design_utils.h | 1 - 1 file changed, 1 deletion(-) (limited to 'common') diff --git a/common/design_utils.h b/common/design_utils.h index b63c75c3..d640bf68 100644 --- a/common/design_utils.h +++ b/common/design_utils.h @@ -86,7 +86,6 @@ CellInfo *net_driven_by(const NetInfo *net, F1 cell_pred, IdString port) void print_utilisation(const Design *design); - NEXTPNR_NAMESPACE_END #endif -- cgit v1.2.3 From 153b800f6a5da9af277e64b4cd4aee1c10ca0a01 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 13:24:42 +0200 Subject: place_sa: Make placement independant of unordered_map ordering Signed-off-by: David Shah --- common/place_sa.cc | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index 79700d3f..22e750c2 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -306,15 +306,19 @@ void place_design_sa(Design *design) rnd_state rnd; rnd.state = 1; std::vector autoplaced; - // Place cells randomly initially + // Sort to-place cells for deterministic initial placement for (auto cell : design->cells) { CellInfo *ci = cell.second; if (ci->bel == BelId()) { - place_initial(design, ci, rnd); autoplaced.push_back(cell.second); - placed_cells++; } - // log_info("placed %d/%d\n", int(placed_cells), int(total_cells)); + } + std::sort(autoplaced.begin(), autoplaced.end(), + [](CellInfo *a, CellInfo *b) { return a->name < b->name; }); + // Place cells randomly initially + for (auto cell : autoplaced) { + place_initial(design, cell, rnd); + placed_cells++; } // Build up a fast position/type to Bel lookup table int max_x = 0, max_y = 0; -- cgit v1.2.3