diff options
| author | David Shah <davey1576@gmail.com> | 2018-06-19 14:31:49 +0200 |
|---|---|---|
| committer | David Shah <davey1576@gmail.com> | 2018-06-19 14:31:49 +0200 |
| commit | 786bd6b25a2d7db691e70fd2bc9a60c796e0df35 (patch) | |
| tree | 5fd2b6bccfc67290697bdc9bdc22b98e01116b40 | |
| parent | a8071a418ddb35698cf1b9958c6caddc2e839cb2 (diff) | |
| download | nextpnr-786bd6b25a2d7db691e70fd2bc9a60c796e0df35.tar.gz nextpnr-786bd6b25a2d7db691e70fd2bc9a60c796e0df35.tar.bz2 nextpnr-786bd6b25a2d7db691e70fd2bc9a60c796e0df35.zip | |
place_sa: Use context-wide rng
Signed-off-by: David Shah <davey1576@gmail.com>
| -rw-r--r-- | common/place_sa.cc | 61 |
1 files changed, 14 insertions, 47 deletions
diff --git a/common/place_sa.cc b/common/place_sa.cc index 7588b245..1178a247 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -42,42 +42,15 @@ 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) - 0.00001); -} - // Initial random placement -static void place_initial(Context *ctx, CellInfo *cell, rnd_state &rnd) +static void place_initial(Context *ctx, CellInfo *cell) { bool all_placed = false; int iters = 25; while (!all_placed) { BelId best_bel = BelId(); - float best_score = std::numeric_limits<float>::infinity(), - best_ripup_score = std::numeric_limits<float>::infinity(); + uint64_t best_score = std::numeric_limits<uint64_t>::max(), + best_ripup_score = std::numeric_limits<uint64_t>::max(); CellInfo *ripup_target = nullptr; BelId ripup_bel = BelId(); if (cell->bel != BelId()) { @@ -89,13 +62,13 @@ static void place_initial(Context *ctx, CellInfo *cell, rnd_state &rnd) if (ctx->getBelType(bel) == targetType && isValidBelForCell(ctx, cell, bel)) { if (ctx->checkBelAvail(bel)) { - float score = random_float_upto(rnd, 1.0); + uint64_t score = ctx->rng64(); if (score <= best_score) { best_score = score; best_bel = bel; } } else { - float score = random_float_upto(rnd, 1.0); + uint64_t score = ctx->rng64(); if (score <= best_ripup_score) { best_ripup_score = score; ripup_target = @@ -173,8 +146,7 @@ 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, - rnd_state &rnd, SAState &state) +static bool try_swap_position(Context *ctx, CellInfo *cell, BelId newBel, SAState &state) { static std::unordered_set<NetInfo *> update; static std::vector<std::pair<NetInfo *, float>> new_lengths; @@ -232,7 +204,7 @@ static bool try_swap_position(Context *ctx, CellInfo *cell, BelId newBel, // SA acceptance criterea if (delta < 0 || (state.temp > 1e-6 && - random_float_upto(rnd, 1.0) <= std::exp(-delta / state.temp))) { + (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / state.temp))) { state.n_accept++; if (delta < 0) state.improved = true; @@ -259,17 +231,14 @@ swap_fail: // Find a random Bel of the correct type for a cell, within the specified // diameter -BelId random_bel_for_cell(Context *ctx, CellInfo *cell, SAState &state, - rnd_state &rnd) +BelId random_bel_for_cell(Context *ctx, CellInfo *cell, SAState &state) { BelType targetType = ctx->belTypeFromId(cell->type); int x = 0, y = 0; ctx->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 = 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; @@ -278,7 +247,7 @@ BelId random_bel_for_cell(Context *ctx, CellInfo *cell, SAState &state, const auto &fb = state.fast_bels.at(beltype_idx).at(nx).at(ny); if (fb.size() == 0) continue; - BelId bel = fb.at(random_int_between(rnd, 0, fb.size())); + BelId bel = fb.at(ctx->rng(int(fb.size()))); if (state.locked_bels.find(bel) != state.locked_bels.end()) continue; return bel; @@ -321,8 +290,6 @@ void place_design_sa(Context *ctx) } } log_info("place_constraints placed %d\n", int(placed_cells)); - rnd_state rnd; - rnd.state = ctx->rng(); std::vector<CellInfo *> autoplaced; // Sort to-place cells for deterministic initial placement for (auto cell : ctx->cells) { @@ -335,7 +302,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, rnd); + place_initial(ctx, cell); placed_cells++; } // Build up a fast position/type to Bel lookup table @@ -388,11 +355,11 @@ void place_design_sa(Context *ctx) // Loop through all automatically placed cells for (auto cell : autoplaced) { // Find another random Bel for this cell - BelId try_bel = random_bel_for_cell(ctx, cell, state, rnd); + BelId try_bel = random_bel_for_cell(ctx, cell, state); // 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(ctx, cell, try_bel, rnd, state); + try_swap_position(ctx, cell, try_bel, state); } } // Heuristic to improve placement on the 8k |