From 90086698679d8a3c5f9e58d619bc18a284ab17e1 Mon Sep 17 00:00:00 2001 From: David Shah Date: Tue, 19 Jun 2018 14:44:49 +0200 Subject: Major performance improvement to placement validity check Signed-off-by: David Shah --- common/place_sa.cc | 30 ++++++++++++++++++------------ dummy/arch_place.cc | 9 +++++++-- dummy/arch_place.h | 20 +++++++++++++------- ice40/arch.h | 8 ++++++-- ice40/arch_place.cc | 51 ++++++++++++++++++++++++++++++--------------------- ice40/arch_place.h | 26 ++++++++++++++++++++------ ice40/cells.cc | 7 ++++--- 7 files changed, 98 insertions(+), 53 deletions(-) diff --git a/common/place_sa.cc b/common/place_sa.cc index 1178a247..91711266 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -43,14 +43,15 @@ NEXTPNR_NAMESPACE_BEGIN // Initial random placement -static void place_initial(Context *ctx, CellInfo *cell) +static void place_initial(Context *ctx, CellInfo *cell, + PlaceValidityChecker *checker) { bool all_placed = false; int iters = 25; while (!all_placed) { BelId best_bel = BelId(); uint64_t best_score = std::numeric_limits::max(), - best_ripup_score = std::numeric_limits::max(); + best_ripup_score = std::numeric_limits::max(); CellInfo *ripup_target = nullptr; BelId ripup_bel = BelId(); if (cell->bel != BelId()) { @@ -60,7 +61,7 @@ static void place_initial(Context *ctx, CellInfo *cell) BelType targetType = ctx->belTypeFromId(cell->type); for (auto bel : ctx->getBels()) { if (ctx->getBelType(bel) == targetType && - isValidBelForCell(ctx, cell, bel)) { + checker->isValidBelForCell(cell, bel)) { if (ctx->checkBelAvail(bel)) { uint64_t score = ctx->rng64(); if (score <= best_score) { @@ -110,6 +111,7 @@ struct SAState std::unordered_map bel_types; std::vector>>> fast_bels; std::unordered_set locked_bels; + PlaceValidityChecker *checker; }; // Get the total estimated wirelength for a net @@ -146,7 +148,8 @@ static float get_wirelength(Context *ctx, NetInfo *net) } // Attempt a SA position swap, return true on success or false on failure -static bool try_swap_position(Context *ctx, CellInfo *cell, BelId newBel, SAState &state) +static bool try_swap_position(Context *ctx, CellInfo *cell, BelId newBel, + SAState &state) { static std::unordered_set update; static std::vector> new_lengths; @@ -178,8 +181,8 @@ static bool try_swap_position(Context *ctx, CellInfo *cell, BelId newBel, SAStat ctx->bindBel(oldBel, other_cell->name); } - if (!isBelLocationValid(ctx, newBel) || - ((other != IdString() && !isBelLocationValid(ctx, oldBel)))) { + if (!state.checker->isBelLocationValid(newBel) || + ((other != IdString() && !state.checker->isBelLocationValid(oldBel)))) { ctx->unbindBel(newBel); if (other != IdString()) ctx->unbindBel(oldBel); @@ -204,7 +207,7 @@ static bool try_swap_position(Context *ctx, CellInfo *cell, BelId newBel, SAStat // SA acceptance criterea if (delta < 0 || (state.temp > 1e-6 && - (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / state.temp))) { + (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / state.temp))) { state.n_accept++; if (delta < 0) state.improved = true; @@ -237,8 +240,10 @@ BelId random_bel_for_cell(Context *ctx, CellInfo *cell, SAState &state) int x = 0, y = 0; ctx->estimatePosition(cell->bel, x, y); while (true) { - int nx = ctx->rng(2 * state.diameter + 1) + std::max(x - state.diameter, 0); - int ny = ctx->rng(2 * state.diameter + 1) + std::max(y - state.diameter, 0); + int nx = ctx->rng(2 * state.diameter + 1) + + std::max(x - state.diameter, 0); + int ny = ctx->rng(2 * state.diameter + 1) + + std::max(y - state.diameter, 0); int beltype_idx = state.bel_types.at(targetType); if (nx >= int(state.fast_bels.at(beltype_idx).size())) continue; @@ -257,7 +262,7 @@ BelId random_bel_for_cell(Context *ctx, CellInfo *cell, SAState &state) void place_design_sa(Context *ctx) { SAState state; - + state.checker = new PlaceValidityChecker(ctx); size_t placed_cells = 0; std::queue visit_cells; // Initial constraints placer @@ -302,7 +307,7 @@ void place_design_sa(Context *ctx) [](CellInfo *a, CellInfo *b) { return a->name < b->name; }); // Place cells randomly initially for (auto cell : autoplaced) { - place_initial(ctx, cell); + place_initial(ctx, cell, state.checker); placed_cells++; } // Build up a fast position/type to Bel lookup table @@ -400,7 +405,7 @@ void place_design_sa(Context *ctx) } } for (auto bel : ctx->getBels()) { - if (!isBelLocationValid(ctx, bel)) { + if (!state.checker->isBelLocationValid(bel)) { std::string cell_text = "no cell"; IdString cell = ctx->getBelCell(bel, false); if (cell != IdString()) @@ -409,6 +414,7 @@ void place_design_sa(Context *ctx) ctx->getBelName(bel).c_str(ctx), cell_text.c_str()); } } + delete state.checker; } NEXTPNR_NAMESPACE_END diff --git a/dummy/arch_place.cc b/dummy/arch_place.cc index 4e712f6d..f35cb6fe 100644 --- a/dummy/arch_place.cc +++ b/dummy/arch_place.cc @@ -21,8 +21,13 @@ NEXTPNR_NAMESPACE_BEGIN -bool isValidBelForCell(Context *ctx, CellInfo *cell, BelId bel) { return true; } +PlaceValidityChecker::PlaceValidityChecker(Context *ctx) {} -bool isBelLocationValid(Context *ctx, BelId bel) { return true; } +bool PlaceValidityChecker::isValidBelForCell(CellInfo *cell, BelId bel) +{ + return true; +} + +bool PlaceValidityChecker::isBelLocationValid(BelId bel) { return true; } NEXTPNR_NAMESPACE_END diff --git a/dummy/arch_place.h b/dummy/arch_place.h index 3abd80c5..1111ac42 100644 --- a/dummy/arch_place.h +++ b/dummy/arch_place.h @@ -26,13 +26,19 @@ NEXTPNR_NAMESPACE_BEGIN // Architecure-specific placement functions -// Whether or not a given cell can be placed at a given Bel -// This is not intended for Bel type checks, but finer-grained constraints -// such as conflicting set/reset signals, etc -bool isValidBelForCell(Context *ctx, CellInfo *cell, BelId bel); - -// Return true whether all Bels at a given location are valid -bool isBelLocationValid(Context *ctx, BelId bel); +class PlaceValidityChecker +{ + public: + PlaceValidityChecker(Context *ctx); + + // Whether or not a given cell can be placed at a given Bel + // This is not intended for Bel type checks, but finer-grained constraints + // such as conflicting set/reset signals, etc + bool isValidBelForCell(CellInfo *cell, BelId bel); + + // Return true whether all Bels at a given location are valid + bool isBelLocationValid(BelId bel); +}; NEXTPNR_NAMESPACE_END diff --git a/ice40/arch.h b/ice40/arch.h index 0fdacfde..290bc9d3 100644 --- a/ice40/arch.h +++ b/ice40/arch.h @@ -279,8 +279,12 @@ template <> struct hash } }; -template <> struct hash : hash {}; -template <> struct hash : hash {}; +template <> struct hash : hash +{ +}; +template <> struct hash : hash +{ +}; } // namespace std NEXTPNR_NAMESPACE_BEGIN diff --git a/ice40/arch_place.cc b/ice40/arch_place.cc index c8806852..c607c9c6 100644 --- a/ice40/arch_place.cc +++ b/ice40/arch_place.cc @@ -24,6 +24,15 @@ NEXTPNR_NAMESPACE_BEGIN +PlaceValidityChecker::PlaceValidityChecker(Context *ctx) + : ctx(ctx), id_icestorm_lc(ctx, "ICESTORM_LC"), id_sb_io(ctx, "SB_IO"), + id_sb_gb(ctx, "SB_GB"), id_cen(ctx, "CEN"), id_clk(ctx, "CLK"), + id_sr(ctx, "SR"), id_i0(ctx, "I0"), id_i1(ctx, "I1"), + id_i2(ctx, "I2"), id_i3(ctx, "I3"), id_dff_en(ctx, "DFF_ENABLE"), + id_neg_clk(ctx, "NEG_CLK") +{ +} + static const NetInfo *get_net_or_empty(const CellInfo *cell, const IdString port) { @@ -34,20 +43,20 @@ static const NetInfo *get_net_or_empty(const CellInfo *cell, return nullptr; }; -static bool logicCellsCompatible(const Context *ctx, - const std::vector &cells) +bool PlaceValidityChecker::logicCellsCompatible( + const Context *ctx, const std::vector &cells) { bool dffs_exist = false, dffs_neg = false; const NetInfo *cen = nullptr, *clk = nullptr, *sr = nullptr; int locals_count = 0; for (auto cell : cells) { - if (bool_or_default(cell->params, "DFF_ENABLE")) { + if (bool_or_default(cell->params, id_dff_en)) { if (!dffs_exist) { dffs_exist = true; - cen = get_net_or_empty(cell, "CEN"); - clk = get_net_or_empty(cell, "CLK"); - sr = get_net_or_empty(cell, "SR"); + cen = get_net_or_empty(cell, id_cen); + clk = get_net_or_empty(cell, id_clk); + sr = get_net_or_empty(cell, id_sr); if (!is_global_net(ctx, cen) && cen != nullptr) locals_count++; @@ -56,25 +65,25 @@ static bool logicCellsCompatible(const Context *ctx, if (!is_global_net(ctx, sr) && sr != nullptr) locals_count++; - if (bool_or_default(cell->params, "NEG_CLK")) { + if (bool_or_default(cell->params, id_neg_clk)) { dffs_neg = true; } } else { - if (cen != get_net_or_empty(cell, "CEN")) + if (cen != get_net_or_empty(cell, id_cen)) return false; - if (clk != get_net_or_empty(cell, "CLK")) + if (clk != get_net_or_empty(cell, id_clk)) return false; - if (sr != get_net_or_empty(cell, "SR")) + if (sr != get_net_or_empty(cell, id_sr)) return false; - if (dffs_neg != bool_or_default(cell->params, "NEG_CLK")) + if (dffs_neg != bool_or_default(cell->params, id_neg_clk)) return false; } } - const NetInfo *i0 = get_net_or_empty(cell, "I0"), - *i1 = get_net_or_empty(cell, "I1"), - *i2 = get_net_or_empty(cell, "I2"), - *i3 = get_net_or_empty(cell, "I3"); + const NetInfo *i0 = get_net_or_empty(cell, id_i0), + *i1 = get_net_or_empty(cell, id_i1), + *i2 = get_net_or_empty(cell, id_i2), + *i3 = get_net_or_empty(cell, id_i3); if (i0 != nullptr) locals_count++; if (i1 != nullptr) @@ -88,7 +97,7 @@ static bool logicCellsCompatible(const Context *ctx, return locals_count <= 32; } -bool isBelLocationValid(Context *ctx, BelId bel) +bool PlaceValidityChecker::isBelLocationValid(BelId bel) { if (ctx->getBelType(bel) == TYPE_ICESTORM_LC) { std::vector cells; @@ -105,13 +114,13 @@ bool isBelLocationValid(Context *ctx, BelId bel) if (cellId == IdString()) return true; else - return isValidBelForCell(ctx, ctx->cells.at(cellId), bel); + return isValidBelForCell(ctx->cells.at(cellId), bel); } } -bool isValidBelForCell(Context *ctx, CellInfo *cell, BelId bel) +bool PlaceValidityChecker::isValidBelForCell(CellInfo *cell, BelId bel) { - if (cell->type == "ICESTORM_LC") { + if (cell->type == id_icestorm_lc) { assert(ctx->getBelType(bel) == TYPE_ICESTORM_LC); std::vector cells; @@ -126,9 +135,9 @@ bool isValidBelForCell(Context *ctx, CellInfo *cell, BelId bel) cells.push_back(cell); return logicCellsCompatible(ctx, cells); - } else if (cell->type == "SB_IO") { + } else if (cell->type == id_sb_io) { return ctx->getBelPackagePin(bel) != ""; - } else if (cell->type == "SB_GB") { + } else if (cell->type == id_sb_gb) { bool is_reset = false, is_cen = false; assert(cell->ports.at("GLOBAL_BUFFER_OUTPUT").net != nullptr); for (auto user : cell->ports.at("GLOBAL_BUFFER_OUTPUT").net->users) { diff --git a/ice40/arch_place.h b/ice40/arch_place.h index 3d05ed7a..d276b9c4 100644 --- a/ice40/arch_place.h +++ b/ice40/arch_place.h @@ -26,13 +26,27 @@ NEXTPNR_NAMESPACE_BEGIN -// Whether or not a given cell can be placed at a given Bel -// This is not intended for Bel type checks, but finer-grained constraints -// such as conflicting set/reset signals, etc -bool isValidBelForCell(Context *ctx, CellInfo *cell, BelId bel); +class PlaceValidityChecker +{ + public: + PlaceValidityChecker(Context *ctx); + // Whether or not a given cell can be placed at a given Bel + // This is not intended for Bel type checks, but finer-grained constraints + // such as conflicting set/reset signals, etc + bool isValidBelForCell(CellInfo *cell, BelId bel); -// Return true whether all Bels at a given location are valid -bool isBelLocationValid(Context *ctx, BelId bel); + // Return true whether all Bels at a given location are valid + bool isBelLocationValid(BelId bel); + + private: + bool logicCellsCompatible(const Context *ctx, + const std::vector &cells); + IdString id_icestorm_lc, id_sb_io, id_sb_gb; + IdString id_cen, id_clk, id_sr; + IdString id_i0, id_i1, id_i2, id_i3; + IdString id_dff_en, id_neg_clk; + Context *ctx; +}; NEXTPNR_NAMESPACE_END diff --git a/ice40/cells.cc b/ice40/cells.cc index 582e5c14..c2bc4609 100644 --- a/ice40/cells.cc +++ b/ice40/cells.cc @@ -211,9 +211,10 @@ void nxio_to_sb(Context *ctx, CellInfo *nxio, CellInfo *sbio) replace_port(tbuf, "E", sbio, "OUTPUT_ENABLE"); ctx->nets.erase(donet->name); if (!donet->users.empty()) - log_error("unsupported tristate IO pattern for IO buffer '%s', " - "instantiate SB_IO manually to ensure correct behaviour\n", - nxio->name.c_str(ctx)); + log_error( + "unsupported tristate IO pattern for IO buffer '%s', " + "instantiate SB_IO manually to ensure correct behaviour\n", + nxio->name.c_str(ctx)); ctx->cells.erase(tbuf->name); } } -- cgit v1.2.3