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(-) 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 +++++--- ice40/arch_place.cc | 14 ++++++++++ ice40/cells.cc | 20 +++++++++++++++ ice40/cells.h | 6 +++++ ice40/pack.cc | 74 ++++++++++++++++++++++++++++++----------------------- 5 files changed, 89 insertions(+), 36 deletions(-) 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; diff --git a/ice40/arch_place.cc b/ice40/arch_place.cc index 492ed846..19c95816 100644 --- a/ice40/arch_place.cc +++ b/ice40/arch_place.cc @@ -99,6 +99,20 @@ bool isValidBelForCell(Design *design, CellInfo *cell, BelId bel) return logicCellsCompatible(cells); } else if (cell->type == "SB_IO") { return design->chip.getBelPackagePin(bel) != ""; + } else if (cell->type == "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) { + if (is_reset_port(user)) + is_reset = true; + } + IdString glb_net = chip.getWireName( + chip.getWireBelPin(bel, PIN_GLOBAL_BUFFER_OUTPUT)); + int glb_id = std::stoi(std::string("") + glb_net.str().back()); + if (is_reset) + return (glb_id % 2) == 0; + else + return true; } else { // TODO: IO cell clock checks return true; diff --git a/ice40/cells.cc b/ice40/cells.cc index 61b24ce3..52356711 100644 --- a/ice40/cells.cc +++ b/ice40/cells.cc @@ -190,6 +190,26 @@ void nxio_to_sb(CellInfo *nxio, CellInfo *sbio) } } +bool is_clock_port(const PortRef &port) +{ + if (port.cell == nullptr) + return false; + if (is_ff(port.cell)) + return port.port == "C"; + if (is_ram(port.cell)) + return port.port == "RCLK" || port.port == "WCLK"; + return false; +} + +bool is_reset_port(const PortRef &port) +{ + if (port.cell == nullptr) + return false; + if (is_ff(port.cell)) + return port.port == "R" || port.port == "S"; + return false; +} + bool is_global_net(const NetInfo *net) { return bool(net_driven_by(net, is_gbuf, "GLOBAL_BUFFER_OUTPUT")); diff --git a/ice40/cells.h b/ice40/cells.h index a2fa4c16..f1bc5d1f 100644 --- a/ice40/cells.h +++ b/ice40/cells.h @@ -77,6 +77,12 @@ void nxio_to_sb(CellInfo *nxio, CellInfo *sbio); // Return true if a net is a global net bool is_global_net(const NetInfo *net); +// Return true if a port is a clock port +bool is_clock_port(const PortRef &port); + +// Return true if a port is a reset port +bool is_reset_port(const PortRef &port); + NEXTPNR_NAMESPACE_END #endif diff --git a/ice40/pack.cc b/ice40/pack.cc index e045c05c..d88870e0 100644 --- a/ice40/pack.cc +++ b/ice40/pack.cc @@ -276,15 +276,34 @@ static void pack_io(Design *design) } } -static bool is_clock_port(const PortRef &port) +static void insert_global(Design *design, NetInfo *net, bool is_reset, + bool is_cen) { - if (port.cell == nullptr) - return false; - if (is_ff(port.cell)) - return port.port == "C"; - if (is_ram(port.cell)) - return port.port == "RCLK" || port.port == "WCLK"; - return false; + CellInfo *gb = create_ice_cell(design, "SB_GB"); + gb->ports["USER_SIGNAL_TO_GLOBAL_BUFFER"].net = net; + PortRef pr; + pr.cell = gb; + pr.port = "USER_SIGNAL_TO_GLOBAL_BUFFER"; + net->users.push_back(pr); + + pr.cell = gb; + pr.port = "GLOBAL_BUFFER_OUTPUT"; + NetInfo *glbnet = new NetInfo(); + glbnet->name = net->name.str() + "_glb"; + glbnet->driver = pr; + design->nets[glbnet->name] = glbnet; + gb->ports["GLOBAL_BUFFER_OUTPUT"].net = glbnet; + std::vector keep_users; + for (auto user : net->users) { + if (is_clock_port(user) || (is_reset && is_reset_port(user))) { + user.cell->ports[user.port].net = glbnet; + glbnet->users.push_back(user); + } else { + keep_users.push_back(user); + } + } + net->users = keep_users; + design->cells[gb->name] = gb; } // Simple global promoter (clock only) @@ -293,13 +312,18 @@ static void promote_globals(Design *design) log_info("Promoting globals..\n"); std::unordered_map clock_count; + std::unordered_map reset_count; + for (auto net : design->nets) { NetInfo *ni = net.second; if (ni->driver.cell != nullptr && !is_global_net(ni)) { clock_count[net.first] = 0; + reset_count[net.first] = 0; for (auto user : ni->users) { if (is_clock_port(user)) clock_count[net.first]++; + if (is_reset_port(user)) + reset_count[net.first]++; } } } @@ -310,30 +334,16 @@ static void promote_globals(Design *design) }); if (global_clock->second > 0) { NetInfo *clknet = design->nets[global_clock->first]; - CellInfo *gb = create_ice_cell(design, "SB_GB"); - gb->ports["USER_SIGNAL_TO_GLOBAL_BUFFER"].net = clknet; - PortRef pr; - pr.cell = gb; - pr.port = "USER_SIGNAL_TO_GLOBAL_BUFFER"; - clknet->users.push_back(pr); - - pr.cell = gb; - pr.port = "GLOBAL_BUFFER_OUTPUT"; - NetInfo *glbnet = new NetInfo(); - glbnet->name = clknet->name.str() + "_glb"; - glbnet->driver = pr; - design->nets[glbnet->name] = glbnet; - std::vector keep_users; - for (auto user : clknet->users) { - if (is_clock_port(user)) { - user.cell->ports[user.port].net = glbnet; - glbnet->users.push_back(user); - } else { - keep_users.push_back(user); - } - } - clknet->users = keep_users; - design->cells[gb->name] = gb; + insert_global(design, clknet, false, false); + } + auto global_reset = std::max_element(reset_count.begin(), reset_count.end(), + [](const std::pair &a, + const std::pair &b) { + return a.second < b.second; + }); + if (global_reset->second > 0) { + NetInfo *rstnet = design->nets[global_reset->first]; + insert_global(design, rstnet, true, false); } } -- cgit v1.2.3 From 1e6124309fb02824c43549e0861d4023fc5827d8 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 16 Jun 2018 17:44:35 +0200 Subject: ice40: Proper global promotion Signed-off-by: David Shah --- ice40/arch_place.cc | 8 +++++- ice40/cells.cc | 17 +++++++++++- ice40/cells.h | 3 ++ ice40/pack.cc | 79 ++++++++++++++++++++++++++++++++++++++--------------- 4 files changed, 83 insertions(+), 24 deletions(-) diff --git a/ice40/arch_place.cc b/ice40/arch_place.cc index 19c95816..c991af13 100644 --- a/ice40/arch_place.cc +++ b/ice40/arch_place.cc @@ -105,12 +105,18 @@ bool isValidBelForCell(Design *design, CellInfo *cell, BelId bel) for (auto user : cell->ports.at("GLOBAL_BUFFER_OUTPUT").net->users) { if (is_reset_port(user)) is_reset = true; + if (is_enable_port(user)) + is_cen = true; } IdString glb_net = chip.getWireName( chip.getWireBelPin(bel, PIN_GLOBAL_BUFFER_OUTPUT)); int glb_id = std::stoi(std::string("") + glb_net.str().back()); - if (is_reset) + if (is_reset && is_cen) + return false; + else if (is_reset) return (glb_id % 2) == 0; + else if (is_cen) + return (glb_id % 2) == 1; else return true; } else { diff --git a/ice40/cells.cc b/ice40/cells.cc index 52356711..4cc4f29c 100644 --- a/ice40/cells.cc +++ b/ice40/cells.cc @@ -196,7 +196,9 @@ bool is_clock_port(const PortRef &port) return false; if (is_ff(port.cell)) return port.port == "C"; - if (is_ram(port.cell)) + if (port.cell->type == "ICESTORM_LC") + return port.port == "CLK"; + if (is_ram(port.cell) || port.cell->type == "ICESTORM_RAM") return port.port == "RCLK" || port.port == "WCLK"; return false; } @@ -207,6 +209,19 @@ bool is_reset_port(const PortRef &port) return false; if (is_ff(port.cell)) return port.port == "R" || port.port == "S"; + if (port.cell->type == "ICESTORM_LC") + return port.port == "SR"; + return false; +} + +bool is_enable_port(const PortRef &port) +{ + if (port.cell == nullptr) + return false; + if (is_ff(port.cell)) + return port.port == "E"; + if (port.cell->type == "ICESTORM_LC") + return port.port == "CEN"; return false; } diff --git a/ice40/cells.h b/ice40/cells.h index f1bc5d1f..ff8cc93d 100644 --- a/ice40/cells.h +++ b/ice40/cells.h @@ -83,6 +83,9 @@ bool is_clock_port(const PortRef &port); // Return true if a port is a reset port bool is_reset_port(const PortRef &port); +// Return true if a port is a clock enable port +bool is_enable_port(const PortRef &port); + NEXTPNR_NAMESPACE_END #endif diff --git a/ice40/pack.cc b/ice40/pack.cc index d88870e0..dde8ed57 100644 --- a/ice40/pack.cc +++ b/ice40/pack.cc @@ -289,13 +289,15 @@ static void insert_global(Design *design, NetInfo *net, bool is_reset, pr.cell = gb; pr.port = "GLOBAL_BUFFER_OUTPUT"; NetInfo *glbnet = new NetInfo(); - glbnet->name = net->name.str() + "_glb"; + glbnet->name = net->name.str() + std::string("_glb_") + + (is_reset ? "sr" : (is_cen ? "ce" : "clk")); glbnet->driver = pr; design->nets[glbnet->name] = glbnet; gb->ports["GLOBAL_BUFFER_OUTPUT"].net = glbnet; std::vector keep_users; for (auto user : net->users) { - if (is_clock_port(user) || (is_reset && is_reset_port(user))) { + if (is_clock_port(user) || (is_reset && is_reset_port(user)) || + (is_cen && is_enable_port(user))) { user.cell->ports[user.port].net = glbnet; glbnet->users.push_back(user); } else { @@ -311,39 +313,72 @@ static void promote_globals(Design *design) { log_info("Promoting globals..\n"); - std::unordered_map clock_count; - std::unordered_map reset_count; - + std::unordered_map clock_count, reset_count, cen_count; for (auto net : design->nets) { NetInfo *ni = net.second; if (ni->driver.cell != nullptr && !is_global_net(ni)) { clock_count[net.first] = 0; reset_count[net.first] = 0; + cen_count[net.first] = 0; + for (auto user : ni->users) { if (is_clock_port(user)) clock_count[net.first]++; if (is_reset_port(user)) reset_count[net.first]++; + if (is_enable_port(user)) + cen_count[net.first]++; } } } - auto global_clock = std::max_element(clock_count.begin(), clock_count.end(), - [](const std::pair &a, - const std::pair &b) { - return a.second < b.second; - }); - if (global_clock->second > 0) { - NetInfo *clknet = design->nets[global_clock->first]; - insert_global(design, clknet, false, false); - } - auto global_reset = std::max_element(reset_count.begin(), reset_count.end(), - [](const std::pair &a, - const std::pair &b) { - return a.second < b.second; - }); - if (global_reset->second > 0) { - NetInfo *rstnet = design->nets[global_reset->first]; - insert_global(design, rstnet, true, false); + int prom_globals = 0, prom_resets = 0, prom_cens = 0; + int gbs_available = 8; + for (auto cell : design->cells) + if (is_gbuf(cell.second)) + --gbs_available; + while (prom_globals < gbs_available) { + auto global_clock = + std::max_element(clock_count.begin(), clock_count.end(), + [](const std::pair &a, + const std::pair &b) { + return a.second < b.second; + }); + + auto global_reset = + std::max_element(reset_count.begin(), reset_count.end(), + [](const std::pair &a, + const std::pair &b) { + return a.second < b.second; + }); + auto global_cen = + std::max_element(cen_count.begin(), cen_count.end(), + [](const std::pair &a, + const std::pair &b) { + return a.second < b.second; + }); + if (global_reset->second > global_clock->second && prom_resets < 4) { + NetInfo *rstnet = design->nets[global_reset->first]; + insert_global(design, rstnet, true, false); + ++prom_globals; + ++prom_resets; + clock_count.erase(rstnet->name); + reset_count.erase(rstnet->name); + + } else if (global_cen->second > global_clock->second && prom_cens < 4) { + NetInfo *cennet = design->nets[global_cen->first]; + insert_global(design, cennet, false, true); + ++prom_globals; + ++prom_cens; + cen_count.erase(cennet->name); + clock_count.erase(cennet->name); + } else if (global_clock->second != 0) { + NetInfo *clknet = design->nets[global_clock->first]; + insert_global(design, clknet, false, false); + ++prom_globals; + clock_count.erase(clknet->name); + } else { + break; + } } } -- 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 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 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(-) 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 +++++++++------ ice40/arch_place.cc | 21 +++++++++++++++++++++ ice40/arch_place.h | 3 +++ 3 files changed, 33 insertions(+), 6 deletions(-) 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; diff --git a/ice40/arch_place.cc b/ice40/arch_place.cc index c991af13..93b7beb4 100644 --- a/ice40/arch_place.cc +++ b/ice40/arch_place.cc @@ -79,6 +79,27 @@ static bool logicCellsCompatible(const std::vector &cells) return locals.size() <= 32; } +bool isBelLocationValid(Design *design, BelId bel) { + const Chip &chip = design->chip; + if (chip.getBelType(bel) == TYPE_ICESTORM_LC) { + std::vector cells; + for (auto bel_other : chip.getBelsAtSameTile(bel)) { + IdString cell_other = chip.getBelCell(bel_other, false); + if (cell_other != IdString()) { + const CellInfo *ci_other = design->cells[cell_other]; + cells.push_back(ci_other); + } + } + return logicCellsCompatible(cells); + } else { + IdString cellId = chip.getBelCell(bel, false); + if (cellId == IdString()) + return true; + else + return isValidBelForCell(design, design->cells.at(cellId), bel); + } +} + bool isValidBelForCell(Design *design, CellInfo *cell, BelId bel) { const Chip &chip = design->chip; diff --git a/ice40/arch_place.h b/ice40/arch_place.h index a505f4db..1db29a54 100644 --- a/ice40/arch_place.h +++ b/ice40/arch_place.h @@ -30,6 +30,9 @@ NEXTPNR_NAMESPACE_BEGIN // such as conflicting set/reset signals, etc bool isValidBelForCell(Design *design, CellInfo *cell, BelId bel); +// Return true whether all Bels at a given location are valid +bool isBelLocationValid(Design *design, BelId bel); + NEXTPNR_NAMESPACE_END #endif -- cgit v1.2.3 From 8ab0b06f5f21c5c077edd5b174d21cc26a5b9343 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 10:35:37 +0200 Subject: ice40: Fixing build Signed-off-by: David Shah --- ice40/arch_place.h | 2 +- ice40/main.cc | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/ice40/arch_place.h b/ice40/arch_place.h index 1db29a54..469bd6d8 100644 --- a/ice40/arch_place.h +++ b/ice40/arch_place.h @@ -12,7 +12,7 @@ * 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 + * ACTION OF CONTRACT, NeEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. * */ diff --git a/ice40/main.cc b/ice40/main.cc index fea53631..4917574d 100644 --- a/ice40/main.cc +++ b/ice40/main.cc @@ -31,7 +31,7 @@ #include "nextpnr.h" #include "pack.h" #include "pcf.h" -#include "place.h" +#include "place_sa.h" #include "pybindings.h" #include "route.h" #include "version.h" -- 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(+) 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 +++++++++++++++++++++++++++++++++++++++++++++++++++++ ice40/arch_place.cc | 7 +++--- 2 files changed, 67 insertions(+), 3 deletions(-) create mode 100644 common/util.h 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 diff --git a/ice40/arch_place.cc b/ice40/arch_place.cc index 93b7beb4..83dd63aa 100644 --- a/ice40/arch_place.cc +++ b/ice40/arch_place.cc @@ -19,6 +19,7 @@ #include "arch_place.h" #include "cells.h" +#include "util.h" NEXTPNR_NAMESPACE_BEGIN @@ -39,7 +40,7 @@ static bool logicCellsCompatible(const std::vector &cells) std::unordered_set locals; for (auto cell : cells) { - if (std::stoi(cell->params.at("DFF_ENABLE"))) { + if (bool_or_default(cell->params, "DFF_ENABLE")) { if (!dffs_exist) { dffs_exist = true; cen = get_net_or_nullptr(cell, "CEN"); @@ -53,7 +54,7 @@ static bool logicCellsCompatible(const std::vector &cells) if (!is_global_net(sr)) locals.insert(sr); - if (std::stoi(cell->params.at("NEG_CLK"))) { + if (bool_or_default(cell->params, "NEG_CLK")) { dffs_neg = true; } } else { @@ -63,7 +64,7 @@ static bool logicCellsCompatible(const std::vector &cells) return false; if (sr != get_net_or_nullptr(cell, "SR")) return false; - if (dffs_neg != bool(std::stoi(cell->params.at("NEG_CLK")))) + if (dffs_neg != bool_or_default(cell->params, "NEG_CLK")) return false; } } -- 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(-) 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 +++++------- ice40/arch_place.cc | 3 ++- ice40/main.cc | 2 ++ 6 files changed, 42 insertions(+), 15 deletions(-) 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))); }; diff --git a/ice40/arch_place.cc b/ice40/arch_place.cc index 83dd63aa..ceb6f07f 100644 --- a/ice40/arch_place.cc +++ b/ice40/arch_place.cc @@ -80,7 +80,8 @@ static bool logicCellsCompatible(const std::vector &cells) return locals.size() <= 32; } -bool isBelLocationValid(Design *design, BelId bel) { +bool isBelLocationValid(Design *design, BelId bel) +{ const Chip &chip = design->chip; if (chip.getBelType(bel) == TYPE_ICESTORM_LC) { std::vector cells; diff --git a/ice40/main.cc b/ice40/main.cc index 4917574d..3cd97f48 100644 --- a/ice40/main.cc +++ b/ice40/main.cc @@ -35,6 +35,7 @@ #include "pybindings.h" #include "route.h" #include "version.h" +#include "design_utils.h" void svg_dump_el(const GraphicElement &el) { @@ -221,6 +222,7 @@ int main(int argc, char *argv[]) } pack_design(&design); + print_utilisation(&design); if (!vm.count("pack-only")) { place_design_sa(&design); route_design(&design, verbose); -- 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 +- ice40/arch_place.cc | 1 + ice40/arch_place.h | 1 + ice40/bitstream.cc | 2 +- ice40/bitstream.h | 1 + ice40/cells.cc | 1 + ice40/cells.h | 3 ++- ice40/pack.cc | 2 +- ice40/pack.h | 1 + ice40/pcf.cc | 1 + ice40/pcf.h | 1 + ice40/pybindings.cc | 2 +- 17 files changed, 21 insertions(+), 7 deletions(-) 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 diff --git a/ice40/arch_place.cc b/ice40/arch_place.cc index ceb6f07f..1c6361a1 100644 --- a/ice40/arch_place.cc +++ b/ice40/arch_place.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/ice40/arch_place.h b/ice40/arch_place.h index 469bd6d8..5cd14809 100644 --- a/ice40/arch_place.h +++ b/ice40/arch_place.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/ice40/bitstream.cc b/ice40/bitstream.cc index a9c46ea8..a0a32171 100644 --- a/ice40/bitstream.cc +++ b/ice40/bitstream.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/ice40/bitstream.h b/ice40/bitstream.h index 11547163..0e2a4aa9 100644 --- a/ice40/bitstream.h +++ b/ice40/bitstream.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/ice40/cells.cc b/ice40/cells.cc index 4cc4f29c..b11a2a77 100644 --- a/ice40/cells.cc +++ b/ice40/cells.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/ice40/cells.h b/ice40/cells.h index ff8cc93d..82d9f60e 100644 --- a/ice40/cells.h +++ b/ice40/cells.h @@ -2,7 +2,8 @@ * 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 * copyright notice and this permission notice appear in all copies. diff --git a/ice40/pack.cc b/ice40/pack.cc index dde8ed57..0b76f3f3 100644 --- a/ice40/pack.cc +++ b/ice40/pack.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/ice40/pack.h b/ice40/pack.h index 4a92a7ab..60f22ef3 100644 --- a/ice40/pack.h +++ b/ice40/pack.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/ice40/pcf.cc b/ice40/pcf.cc index 75c32731..3bef962f 100644 --- a/ice40/pcf.cc +++ b/ice40/pcf.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/ice40/pcf.h b/ice40/pcf.h index c4a7d991..ec2f4923 100644 --- a/ice40/pcf.h +++ b/ice40/pcf.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/ice40/pybindings.cc b/ice40/pybindings.cc index 5ccf9495..c161949b 100644 --- a/ice40/pybindings.cc +++ b/ice40/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 -- cgit v1.2.3 From 12818fb69479cd6a1908bcae37de2b817632d33c Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 12:38:21 +0200 Subject: ice40: Add symbol output to bitstream generation Signed-off-by: David Shah --- ice40/bitstream.cc | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) diff --git a/ice40/bitstream.cc b/ice40/bitstream.cc index a0a32171..918eb01b 100644 --- a/ice40/bitstream.cc +++ b/ice40/bitstream.cc @@ -287,12 +287,6 @@ void write_asc(const Design &design, std::ostream &out) TileType tile = tile_at(chip, x, y); TileInfoPOD &ti = bi.tiles_nonrouting[tile]; - // disable RAM to stop icebox_vlog crashing (FIXME) - if ((tile == TILE_RAMB) && (chip.args.type == ChipArgs::LP1K || - chip.args.type == ChipArgs::HX1K)) { - set_config(ti, config.at(y).at(x), "RamConfig.PowerUp", true); - } - // set all ColBufCtrl bits (FIXME) bool setColBufCtrl = true; if (chip.args.type == ChipArgs::LP1K || @@ -398,6 +392,14 @@ void write_asc(const Design &design, std::ostream &out) } } } + + // Write symbols + const bool write_symbols = 1; + for (auto wire : chip.getWires()) { + IdString net = chip.getWireNet(wire, false); + if (net != IdString()) + out << ".sym " << wire.index << " net_" << net << std::endl; + } } NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From 459a7a0b82a3442dc551027af76f4a905855d083 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sun, 17 Jun 2018 12:53:29 +0200 Subject: frontend/json: Look up netnames properly instead of using number Signed-off-by: David Shah --- frontend/json/jsonparse.cc | 50 +++++++++++++++++++++++++++++++++++++++------- 1 file changed, 43 insertions(+), 7 deletions(-) diff --git a/frontend/json/jsonparse.cc b/frontend/json/jsonparse.cc index 82874703..3c060fd7 100644 --- a/frontend/json/jsonparse.cc +++ b/frontend/json/jsonparse.cc @@ -345,6 +345,7 @@ static int const_net_idx = 0; template void json_import_ports(Design *design, const string &modname, + const std::vector &netnames, const string &obj_name, const string &port_name, JsonNode *dir_node, JsonNode *wire_group_node, F visitor) { @@ -432,7 +433,10 @@ void json_import_ports(Design *design, const string &modname, // A simple net, specified by a number net_num = wire_node->data_number; - net_id = std::to_string(net_num); + if (net_num < netnames.size()) + net_id = netnames.at(net_num); + else + net_id = std::to_string(net_num); if (design->nets.count(net_id) == 0) { // The net doesn't exist in the design (yet) // Create in now @@ -511,8 +515,9 @@ void json_import_ports(Design *design, const string &modname, } } -void json_import_cell(Design *design, string modname, JsonNode *cell_node, - string cell_name) +void json_import_cell(Design *design, string modname, + const std::vector &netnames, + JsonNode *cell_node, string cell_name) { JsonNode *cell_type, *param_node, *attr_node; @@ -616,7 +621,7 @@ void json_import_cell(Design *design, string modname, JsonNode *cell_node, wire_group_node = connections->data_dict.at(port_name); json_import_ports( - design, modname, cell->name, port_name, dir_node, + design, modname, netnames, cell->name, port_name, dir_node, wire_group_node, [cell](PortType type, const std::string &name, NetInfo *net) { cell->ports[name] = PortInfo{name, net, type}; @@ -696,12 +701,14 @@ static void insert_iobuf(Design *design, NetInfo *net, PortType type, } void json_import_toplevel_port(Design *design, const string &modname, + const std::vector &netnames, const string &portname, JsonNode *node) { JsonNode *dir_node = node->data_dict.at("direction"); JsonNode *nets_node = node->data_dict.at("bits"); json_import_ports( - design, modname, "Top Level IO", portname, dir_node, nets_node, + design, modname, netnames, "Top Level IO", portname, dir_node, + nets_node, [design](PortType type, const std::string &name, NetInfo *net) { insert_iobuf(design, net, type, name); }); @@ -714,6 +721,35 @@ void json_import(Design *design, string modname, JsonNode *node) log_info("Importing module %s\n", modname.c_str()); + // Import netnames + std::vector netnames; + if (node->data_dict.count("netnames")) { + JsonNode *cell_parent = node->data_dict.at("netnames"); + for (int nnid = 0; nnid < GetSize(cell_parent->data_dict_keys); + nnid++) { + JsonNode *here; + + here = cell_parent->data_dict.at(cell_parent->data_dict_keys[nnid]); + std::string basename = cell_parent->data_dict_keys[nnid]; + if (here->data_dict.count("bits")) { + JsonNode *bits = here->data_dict.at("bits"); + assert(bits->type == 'A'); + size_t num_bits = bits->data_array.size(); + for (size_t i = 0; i < num_bits; i++) { + int netid = bits->data_array.at(i)->data_number; + if (netid >= netnames.size()) + netnames.resize(netid + 1); + netnames.at(netid) = + basename + + (num_bits == 1 + ? "" + : std::string("[") + std::to_string(i) + + std::string("]")); + } + } + } + } + if (node->data_dict.count("cells")) { JsonNode *cell_parent = node->data_dict.at("cells"); // @@ -727,7 +763,7 @@ void json_import(Design *design, string modname, JsonNode *node) here = cell_parent->data_dict.at( cell_parent->data_dict_keys[cellid]); - json_import_cell(design, modname, here, + json_import_cell(design, modname, netnames, here, cell_parent->data_dict_keys[cellid]); } } @@ -744,7 +780,7 @@ void json_import(Design *design, string modname, JsonNode *node) here = ports_parent->data_dict.at( ports_parent->data_dict_keys[portid]); - json_import_toplevel_port(design, modname, + json_import_toplevel_port(design, modname, netnames, ports_parent->data_dict_keys[portid], here); } -- 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 - ice40/bitstream.cc | 2 +- ice40/cells.h | 2 +- ice40/main.cc | 2 +- 4 files changed, 3 insertions(+), 4 deletions(-) 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 diff --git a/ice40/bitstream.cc b/ice40/bitstream.cc index 918eb01b..9309a7da 100644 --- a/ice40/bitstream.cc +++ b/ice40/bitstream.cc @@ -398,7 +398,7 @@ void write_asc(const Design &design, std::ostream &out) for (auto wire : chip.getWires()) { IdString net = chip.getWireNet(wire, false); if (net != IdString()) - out << ".sym " << wire.index << " net_" << net << std::endl; + out << ".sym " << wire.index << " " << net << std::endl; } } diff --git a/ice40/cells.h b/ice40/cells.h index 82d9f60e..45e81fd1 100644 --- a/ice40/cells.h +++ b/ice40/cells.h @@ -3,7 +3,7 @@ * * 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 * copyright notice and this permission notice appear in all copies. diff --git a/ice40/main.cc b/ice40/main.cc index 3cd97f48..eb92d92f 100644 --- a/ice40/main.cc +++ b/ice40/main.cc @@ -25,6 +25,7 @@ #include #include #include "bitstream.h" +#include "design_utils.h" #include "jsonparse.h" #include "log.h" #include "mainwindow.h" @@ -35,7 +36,6 @@ #include "pybindings.h" #include "route.h" #include "version.h" -#include "design_utils.h" void svg_dump_el(const GraphicElement &el) { -- 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(-) 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