From 2cc7ade05b52b89186f5210c97ebbc61aa5c166d Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 27 Jun 2018 12:00:13 +0200 Subject: Refactor common placement functions out of SA placer for use in legaliser Signed-off-by: David Shah --- common/nextpnr.h | 3 +- common/place_common.cc | 92 ++++++++++++++++++++++++++++++++++++++++++++++++++ common/place_common.h | 40 ++++++++++++++++++++++ common/place_sa.cc | 61 +++------------------------------ 4 files changed, 138 insertions(+), 58 deletions(-) create mode 100644 common/place_common.cc create mode 100644 common/place_common.h diff --git a/common/nextpnr.h b/common/nextpnr.h index efe5936f..8d4714bf 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -200,7 +200,7 @@ struct BaseCtx BaseCtx() { - //assert(IdString::global_ctx == nullptr); + // assert(IdString::global_ctx == nullptr); IdString::global_ctx = this; idstring_str_to_idx = new std::unordered_map; @@ -229,6 +229,7 @@ struct Context : Arch bool verbose = false; bool debug = false; bool force = false; + bool timing_driven = true; Context(ArchArgs args) : Arch(args) {} diff --git a/common/place_common.cc b/common/place_common.cc new file mode 100644 index 00000000..86060cd8 --- /dev/null +++ b/common/place_common.cc @@ -0,0 +1,92 @@ +/* + * 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. + * + */ + +#include "place_common.h" +#include +#include "log.h" +#include "util.h" +NEXTPNR_NAMESPACE_BEGIN + +// Get the total estimated wirelength for a net +wirelen_t get_net_wirelength(const Context *ctx, const NetInfo *net, float &tns) +{ + wirelen_t wirelength = 0; + int driver_x, driver_y; + bool driver_gb; + CellInfo *driver_cell = net->driver.cell; + if (!driver_cell) + return 0; + if (driver_cell->bel == BelId()) + return 0; + ctx->estimatePosition(driver_cell->bel, driver_x, driver_y, driver_gb); + WireId drv_wire = ctx->getWireBelPin(driver_cell->bel, ctx->portPinFromId(net->driver.port)); + if (driver_gb) + return 0; + float worst_slack = 1000; + int xmin = driver_x, xmax = driver_x, ymin = driver_y, ymax = driver_y; + for (auto load : net->users) { + if (load.cell == nullptr) + continue; + CellInfo *load_cell = load.cell; + if (load_cell->bel == BelId()) + continue; + if (ctx->timing_driven) { + WireId user_wire = ctx->getWireBelPin(load_cell->bel, ctx->portPinFromId(load.port)); + delay_t raw_wl = ctx->estimateDelay(drv_wire, user_wire); + float slack = ctx->getDelayNS(load.budget) - ctx->getDelayNS(raw_wl); + if (slack < 0) + tns += slack; + worst_slack = std::min(slack, worst_slack); + } + + int load_x, load_y; + bool load_gb; + ctx->estimatePosition(load_cell->bel, load_x, load_y, load_gb); + if (load_gb) + continue; + xmin = std::min(xmin, load_x); + ymin = std::min(ymin, load_y); + xmax = std::max(xmax, load_x); + ymax = std::max(ymax, load_y); + } + if (ctx->timing_driven) { + wirelength = wirelen_t((((ymax - ymin) + (xmax - xmin)) * std::min(5.0, (1.0 + std::exp(-worst_slack / 5))))); + } else { + wirelength = wirelen_t((ymax - ymin) + (xmax - xmin)); + } + + return wirelength; +} + +// Get the total wirelength for a cell +wirelen_t get_cell_wirelength(const Context *ctx, const CellInfo *cell) +{ + std::set nets; + for (auto p : cell->ports) { + nets.insert(p.first); + } + wirelen_t wirelength = 0; + float tns = 0; + for (auto n : nets) { + wirelength += get_net_wirelength(ctx, ctx->nets.at(n).get(), tns); + } + return wirelength; +} + +NEXTPNR_NAMESPACE_END diff --git a/common/place_common.h b/common/place_common.h new file mode 100644 index 00000000..b81574b9 --- /dev/null +++ b/common/place_common.h @@ -0,0 +1,40 @@ +/* + * 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 PLACE_COMMON_H +#define PLACE_COMMON_H + +#include "nextpnr.h" + +NEXTPNR_NAMESPACE_BEGIN + +typedef int64_t wirelen_t; + +// Return the wirelength of a net +wirelen_t get_net_wirelength(const Context *ctx, const NetInfo *net, float &tns); + +// Return the wirelength of all nets connected to a cell +wirelen_t get_cell_wirelength(const Context *ctx, const CellInfo *cell); + +// Place a single cell in the lowest wirelength Bel available, optionally requiring validity check +bool place_single_cell(const Context *ctx, CellInfo *cell, bool require_legality); + +NEXTPNR_NAMESPACE_END + +#endif diff --git a/common/place_sa.cc b/common/place_sa.cc index 3e900c84..ed584d60 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -37,11 +37,10 @@ #include #include #include "log.h" +#include "place_common.h" NEXTPNR_NAMESPACE_BEGIN -typedef int64_t wirelen_t; - class SAPlacer { public: @@ -138,7 +137,7 @@ class SAPlacer curr_wirelength = 0; curr_tns = 0; for (auto &net : ctx->nets) { - wirelen_t wl = get_wirelength(net.second.get(), curr_tns); + wirelen_t wl = get_net_wirelength(ctx, net.second.get(), curr_tns); wirelengths[net.first] = wl; curr_wirelength += wl; } @@ -212,7 +211,7 @@ class SAPlacer curr_wirelength = 0; curr_tns = 0; for (auto &net : ctx->nets) { - wirelen_t wl = get_wirelength(net.second.get(), curr_tns); + wirelen_t wl = get_net_wirelength(ctx, net.second.get(), curr_tns); wirelengths[net.first] = wl; curr_wirelength += wl; } @@ -289,58 +288,6 @@ class SAPlacer } } - // Get the total estimated wirelength for a net - wirelen_t get_wirelength(NetInfo *net, float &tns) - { - wirelen_t wirelength = 0; - int driver_x, driver_y; - bool driver_gb; - CellInfo *driver_cell = net->driver.cell; - if (!driver_cell) - return 0; - if (driver_cell->bel == BelId()) - return 0; - ctx->estimatePosition(driver_cell->bel, driver_x, driver_y, driver_gb); - WireId drv_wire = ctx->getWireBelPin(driver_cell->bel, ctx->portPinFromId(net->driver.port)); - if (driver_gb) - return 0; - float worst_slack = 1000; - int xmin = driver_x, xmax = driver_x, ymin = driver_y, ymax = driver_y; - for (auto load : net->users) { - if (load.cell == nullptr) - continue; - CellInfo *load_cell = load.cell; - if (load_cell->bel == BelId()) - continue; - if (timing_driven) { - WireId user_wire = ctx->getWireBelPin(load_cell->bel, ctx->portPinFromId(load.port)); - delay_t raw_wl = ctx->estimateDelay(drv_wire, user_wire); - float slack = ctx->getDelayNS(load.budget) - ctx->getDelayNS(raw_wl); - if (slack < 0) - tns += slack; - worst_slack = std::min(slack, worst_slack); - } - - int load_x, load_y; - bool load_gb; - ctx->estimatePosition(load_cell->bel, load_x, load_y, load_gb); - if (load_gb) - continue; - xmin = std::min(xmin, load_x); - ymin = std::min(ymin, load_y); - xmax = std::max(xmax, load_x); - ymax = std::max(ymax, load_y); - } - if (timing_driven) { - wirelength = - wirelen_t((((ymax - ymin) + (xmax - xmin)) * std::min(5.0, (1.0 + std::exp(-worst_slack / 5))))); - } else { - wirelength = wirelen_t((ymax - ymin) + (xmax - xmin)); - } - - return wirelength; - } - // Attempt a SA position swap, return true on success or false on failure bool try_swap_position(CellInfo *cell, BelId newBel) { @@ -387,7 +334,7 @@ class SAPlacer for (auto net : update) { new_wirelength -= wirelengths.at(net->name); float temp_tns = 0; - wirelen_t net_new_wl = get_wirelength(net, temp_tns); + wirelen_t net_new_wl = get_net_wirelength(ctx, net, temp_tns); new_wirelength += net_new_wl; new_lengths.push_back(std::make_pair(net->name, net_new_wl)); } -- cgit v1.2.3