From 681c9654d7c49d407a999b2b03c980d66bcefd8f Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 14:36:19 +0200 Subject: place_sa: Add a rip-up feature when initial placement fails Signed-off-by: David Shah --- common/place_sa.cc | 71 ++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 48 insertions(+), 23 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index 22e750c2..61f9f748 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -72,33 +72,58 @@ static int random_int_between(rnd_state &rnd, int a, int b) // 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; + bool all_placed = false; + int iters = 25; + while(!all_placed) { + BelId best_bel = BelId(); + float best_score = std::numeric_limits::infinity(), best_ripup_score = std::numeric_limits::infinity(); + Chip &chip = design->chip; + CellInfo *ripup_target = nullptr; + BelId ripup_bel = BelId(); + 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 && isValidBelForCell(design, cell, bel)) { + if (chip.checkBelAvail(bel)) { + float score = random_float_upto(rnd, 1.0); + if (score <= best_score) { + best_score = score; + best_bel = bel; + } + } else { + float score = random_float_upto(rnd, 1.0); + if (score <= best_ripup_score) { + best_ripup_score = score; + ripup_target = design->cells.at(chip.getBelCell(bel, true)); + ripup_bel = bel; + } + + } + } } + if (best_bel == BelId()) { + if (iters == 0 || ripup_bel == BelId()) + log_error("failed to place cell '%s' of type '%s'\n", + cell->name.c_str(), cell->type.c_str()); + --iters; + chip.unbindBel(ripup_target->bel); + ripup_target->bel = BelId(); + best_bel = ripup_bel; + } else { + all_placed = true; + } + cell->bel = best_bel; + chip.bindBel(cell->bel, cell->name); + + // Back annotate location + cell->attrs["BEL"] = chip.getBelName(cell->bel).str(); + cell = ripup_target; } - 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 -- cgit v1.2.3 From 748171dae29c65182e6360a12a9e2bdbbfc35163 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 15:04:53 +0200 Subject: place_sa: Adding seed option Signed-off-by: David Shah --- common/place_sa.cc | 20 ++++++++++---------- common/place_sa.h | 2 +- 2 files changed, 11 insertions(+), 11 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index 61f9f748..e8b3725c 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -74,9 +74,10 @@ static void place_initial(Design *design, CellInfo *cell, rnd_state &rnd) { bool all_placed = false; int iters = 25; - while(!all_placed) { + while (!all_placed) { BelId best_bel = BelId(); - float best_score = std::numeric_limits::infinity(), best_ripup_score = std::numeric_limits::infinity(); + float best_score = std::numeric_limits::infinity(), + best_ripup_score = std::numeric_limits::infinity(); Chip &chip = design->chip; CellInfo *ripup_target = nullptr; BelId ripup_bel = BelId(); @@ -86,7 +87,8 @@ static void place_initial(Design *design, CellInfo *cell, rnd_state &rnd) } BelType targetType = belTypeFromId(cell->type); for (auto bel : chip.getBels()) { - if (chip.getBelType(bel) == targetType && isValidBelForCell(design, cell, bel)) { + if (chip.getBelType(bel) == targetType && + isValidBelForCell(design, cell, bel)) { if (chip.checkBelAvail(bel)) { float score = random_float_upto(rnd, 1.0); if (score <= best_score) { @@ -97,18 +99,17 @@ static void place_initial(Design *design, CellInfo *cell, rnd_state &rnd) float score = random_float_upto(rnd, 1.0); if (score <= best_ripup_score) { best_ripup_score = score; - ripup_target = design->cells.at(chip.getBelCell(bel, true)); + ripup_target = + design->cells.at(chip.getBelCell(bel, true)); ripup_bel = bel; } - } - } } if (best_bel == BelId()) { if (iters == 0 || ripup_bel == BelId()) log_error("failed to place cell '%s' of type '%s'\n", - cell->name.c_str(), cell->type.c_str()); + cell->name.c_str(), cell->type.c_str()); --iters; chip.unbindBel(ripup_target->bel); ripup_target->bel = BelId(); @@ -123,7 +124,6 @@ static void place_initial(Design *design, CellInfo *cell, rnd_state &rnd) cell->attrs["BEL"] = chip.getBelName(cell->bel).str(); cell = ripup_target; } - } // Stores the state of the SA placer @@ -293,7 +293,7 @@ BelId random_bel_for_cell(Design *design, CellInfo *cell, SAState &state, } } -void place_design_sa(Design *design) +void place_design_sa(Design *design, int seed) { SAState state; @@ -329,7 +329,7 @@ void place_design_sa(Design *design) } log_info("place_constraints placed %d\n", int(placed_cells)); rnd_state rnd; - rnd.state = 1; + rnd.state = seed; std::vector autoplaced; // Sort to-place cells for deterministic initial placement for (auto cell : design->cells) { diff --git a/common/place_sa.h b/common/place_sa.h index f320111e..944cb97e 100644 --- a/common/place_sa.h +++ b/common/place_sa.h @@ -23,7 +23,7 @@ NEXTPNR_NAMESPACE_BEGIN -extern void place_design_sa(Design *design); +extern void place_design_sa(Design *design, int seed); NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From f66999a8830c5829872b93ce15491de1673cb4e3 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 16:03:16 +0200 Subject: Minor performance tweaks and fixes Signed-off-by: David Shah --- common/place_sa.cc | 2 +- common/route.cc | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index e8b3725c..12ca30d8 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -66,7 +66,7 @@ static float random_float_upto(rnd_state &rnd, float limit) static int random_int_between(rnd_state &rnd, int a, int b) { - return a + int(random_float_upto(rnd, b - a)); + return a + int(random_float_upto(rnd, b - a) - 0.00001); } // Initial random placement diff --git a/common/route.cc b/common/route.cc index 32212c7d..247c8840 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 += 5; - ripup_wire_penalty += 5; + ripup_pip_penalty *= 1.5; + ripup_wire_penalty *= 1.5; } } -- cgit v1.2.3