From c27c96f4f0ec66d13bea7d7cdea25fbeb2e189b7 Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 20 Jun 2018 20:12:23 +0200 Subject: place_sa: Improvements including supporting force and ordering consistency Signed-off-by: David Shah --- common/place_sa.cc | 24 ++++++++++++++++-------- 1 file changed, 16 insertions(+), 8 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index 2b8b960b..7325c557 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -145,7 +145,7 @@ class SAPlacer curr_wirelength = 0; for (auto net : ctx->nets) { float wl = get_wirelength(net.second); - wirelengths[net.second] = wl; + wirelengths[net.first] = wl; curr_wirelength += wl; } @@ -221,9 +221,17 @@ class SAPlacer std::string cell_text = "no cell"; if (cell != IdString()) cell_text = std::string("cell '") + cell.str(ctx) + "'"; - log_error("post-placement validity check failed for Bel '%s' " - "(%s)", - ctx->getBelName(bel).c_str(ctx), cell_text.c_str()); + if (ctx->force) { + log_warning( + "post-placement validity check failed for Bel '%s' " + "(%s)\n", + ctx->getBelName(bel).c_str(ctx), cell_text.c_str()); + } else { + log_error( + "post-placement validity check failed for Bel '%s' " + "(%s)\n", + ctx->getBelName(bel).c_str(ctx), cell_text.c_str()); + } } } return true; @@ -328,7 +336,7 @@ class SAPlacer bool try_swap_position(CellInfo *cell, BelId newBel) { static std::unordered_set update; - static std::vector> new_lengths; + static std::vector> new_lengths; new_lengths.clear(); update.clear(); BelId oldBel = cell->bel; @@ -373,10 +381,10 @@ class SAPlacer // Recalculate wirelengths for all nets touched by the peturbation for (auto net : update) { - new_wirelength -= wirelengths.at(net); + new_wirelength -= wirelengths.at(net->name); float net_new_wl = get_wirelength(net); new_wirelength += net_new_wl; - new_lengths.push_back(std::make_pair(net, net_new_wl)); + new_lengths.push_back(std::make_pair(net->name, net_new_wl)); } delta = new_wirelength - curr_wirelength; n_move++; @@ -434,7 +442,7 @@ class SAPlacer } Context *ctx; - std::unordered_map wirelengths; + std::unordered_map wirelengths; float curr_wirelength = std::numeric_limits::infinity(); float temp = 1000; bool improved = false; -- cgit v1.2.3 From 1df8a8b44091246acc8929cc803578c6d705eee1 Mon Sep 17 00:00:00 2001 From: David Shah Date: Wed, 20 Jun 2018 20:25:48 +0200 Subject: place_sa: Reduce effect of rounding errors Signed-off-by: David Shah --- common/place_sa.cc | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index 7325c557..4a2fc86e 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -30,7 +30,6 @@ #include #include #include -#include #include #include #include @@ -213,6 +212,15 @@ class SAPlacer temp *= 0.8; } } + + // Recalculate total wirelength entirely to avoid rounding errors + // accumulating over time + curr_wirelength = 0; + for (auto net : ctx->nets) { + float wl = get_wirelength(net.second); + wirelengths[net.first] = wl; + curr_wirelength += wl; + } } // Final post-pacement validitiy check for (auto bel : ctx->getBels()) { -- cgit v1.2.3 From e526a4115bddab74441ac9dbdb4aa56ff6f6bf3f Mon Sep 17 00:00:00 2001 From: David Shah Date: Thu, 21 Jun 2018 10:45:18 +0200 Subject: place_sa: Use int64_t for "wirelength" metric Signed-off-by: David Shah --- common/place_sa.cc | 35 +++++++++++++++++++---------------- 1 file changed, 19 insertions(+), 16 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index 4a2fc86e..39855e47 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -41,6 +41,8 @@ NEXTPNR_NAMESPACE_BEGIN +typedef int64_t wirelen_t; + class SAPlacer { public: @@ -143,7 +145,7 @@ class SAPlacer // Calculate wirelength after initial placement curr_wirelength = 0; for (auto net : ctx->nets) { - float wl = get_wirelength(net.second); + wirelen_t wl = get_wirelength(net.second); wirelengths[net.first] = wl; curr_wirelength += wl; } @@ -159,7 +161,7 @@ class SAPlacer if (iter % 5 == 0 || iter == 1) log_info(" at iteration #%d: temp = %f, wire length = %f\n", - iter, temp, curr_wirelength); + iter, temp, double(curr_wirelength)); for (int m = 0; m < 15; ++m) { // Loop through all automatically placed cells @@ -182,7 +184,7 @@ class SAPlacer if (iter % 5 != 0) log_info( " at iteration #%d: temp = %f, wire length = %f\n", - iter, temp, curr_wirelength); + iter, temp, double(curr_wirelength)); break; } @@ -217,7 +219,7 @@ class SAPlacer // accumulating over time curr_wirelength = 0; for (auto net : ctx->nets) { - float wl = get_wirelength(net.second); + wirelen_t wl = get_wirelength(net.second); wirelengths[net.first] = wl; curr_wirelength += wl; } @@ -304,9 +306,9 @@ class SAPlacer } // Get the total estimated wirelength for a net - float get_wirelength(NetInfo *net) + wirelen_t get_wirelength(NetInfo *net) { - float wirelength = 0; + wirelen_t wirelength = 0; int driver_x, driver_y; bool driver_gb; CellInfo *driver_cell = net->driver.cell; @@ -331,10 +333,11 @@ class SAPlacer // wirelength += std::abs(load_x - driver_x) + std::abs(load_y - // driver_y); delay_t raw_wl = ctx->estimateDelay(drv_wire, user_wire); - wirelength += pow(1.3, (ctx->getDelayNS(raw_wl) - - ctx->getDelayNS(load.budget)) / - 10) + - ctx->getDelayNS(raw_wl); + wirelength += wirelen_t((pow(1.3, (ctx->getDelayNS(raw_wl) - + ctx->getDelayNS(load.budget)) / + 10) + + ctx->getDelayNS(raw_wl)) * + 10); // wirelength += pow(ctx->estimateDelay(drv_wire, user_wire), 2.0); } return wirelength; @@ -344,13 +347,13 @@ class SAPlacer bool try_swap_position(CellInfo *cell, BelId newBel) { static std::unordered_set update; - static std::vector> new_lengths; + static std::vector> new_lengths; new_lengths.clear(); update.clear(); BelId oldBel = cell->bel; IdString other = ctx->getBelCell(newBel, true); CellInfo *other_cell = nullptr; - float new_wirelength = 0, delta; + wirelen_t new_wirelength = 0, delta; ctx->unbindBel(oldBel); if (other != IdString()) { other_cell = ctx->cells[other]; @@ -390,7 +393,7 @@ class SAPlacer // Recalculate wirelengths for all nets touched by the peturbation for (auto net : update) { new_wirelength -= wirelengths.at(net->name); - float net_new_wl = get_wirelength(net); + wirelen_t net_new_wl = get_wirelength(net); new_wirelength += net_new_wl; new_lengths.push_back(std::make_pair(net->name, net_new_wl)); } @@ -400,7 +403,7 @@ class SAPlacer if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { n_accept++; - if (delta < 0) + if (delta < 2) improved = true; } else { if (other != IdString()) @@ -450,8 +453,8 @@ class SAPlacer } Context *ctx; - std::unordered_map wirelengths; - float curr_wirelength = std::numeric_limits::infinity(); + std::unordered_map wirelengths; + wirelen_t curr_wirelength = std::numeric_limits::max(); float temp = 1000; bool improved = false; int n_move, n_accept; -- cgit v1.2.3 From 9e28e45bd5e1f322f11f4759e8174d861df2eb2c Mon Sep 17 00:00:00 2001 From: David Shah Date: Thu, 21 Jun 2018 11:45:58 +0200 Subject: place_sa: Make the heuristic closer to arachne, seems to improve routability Signed-off-by: David Shah --- common/place_sa.cc | 31 ++++++++++++++++++++----------- 1 file changed, 20 insertions(+), 11 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index 39855e47..e792474d 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -321,25 +321,33 @@ class SAPlacer 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; - // ctx->estimatePosition(load_cell->bel, load_x, load_y, load_gb); + WireId user_wire = ctx->getWireBelPin( load_cell->bel, ctx->portPinFromId(load.port)); - // wirelength += std::abs(load_x - driver_x) + std::abs(load_y - - // driver_y); delay_t raw_wl = ctx->estimateDelay(drv_wire, user_wire); - wirelength += wirelen_t((pow(1.3, (ctx->getDelayNS(raw_wl) - - ctx->getDelayNS(load.budget)) / - 10) + - ctx->getDelayNS(raw_wl)) * - 10); - // wirelength += pow(ctx->estimateDelay(drv_wire, user_wire), 2.0); + float slack = + ctx->getDelayNS(raw_wl) - ctx->getDelayNS(load.budget); + 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); } + wirelength = wirelen_t((((ymax - ymin) + (xmax - xmin)) * + (1.0 + std::exp(-worst_slack / 5)))); return wirelength; } @@ -400,8 +408,9 @@ class SAPlacer delta = new_wirelength - curr_wirelength; n_move++; // SA acceptance criterea - if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= - std::exp(-delta / temp))) { + if (delta < 0 || + (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= + std::exp(-(delta / 2) / temp))) { n_accept++; if (delta < 2) improved = true; -- cgit v1.2.3 From 56ed679f831f703ad2f170713e0b127a97da40b3 Mon Sep 17 00:00:00 2001 From: David Shah Date: Thu, 21 Jun 2018 11:59:20 +0200 Subject: Add frequency setting and fix slack calculation Signed-off-by: David Shah --- common/place_sa.cc | 2 +- common/timing.cc | 11 +++++------ 2 files changed, 6 insertions(+), 7 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index e792474d..2f8fb122 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -334,7 +334,7 @@ class SAPlacer load_cell->bel, ctx->portPinFromId(load.port)); delay_t raw_wl = ctx->estimateDelay(drv_wire, user_wire); float slack = - ctx->getDelayNS(raw_wl) - ctx->getDelayNS(load.budget); + ctx->getDelayNS(load.budget) - ctx->getDelayNS(raw_wl); worst_slack = std::min(slack, worst_slack); int load_x, load_y; bool load_gb; diff --git a/common/timing.cc b/common/timing.cc index 8da26077..a7b37f9d 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -101,7 +101,6 @@ void assign_budget(Context *ctx, float default_clock) } } } - const bool debug = true; // Post-allocation check for (auto net : ctx->nets) { @@ -111,11 +110,11 @@ void assign_budget(Context *ctx, float default_clock) "timing budget of %fns\n", user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx), ctx->getDelayNS(user.budget)); - if (debug) - log_warning("port %s.%s, connected to net '%s', has " - "timing budget of %fns\n", - user.cell->name.c_str(ctx), user.port.c_str(ctx), - net.first.c_str(ctx), ctx->getDelayNS(user.budget)); + if (ctx->verbose) + log_info("port %s.%s, connected to net '%s', has " + "timing budget of %fns\n", + user.cell->name.c_str(ctx), user.port.c_str(ctx), + net.first.c_str(ctx), ctx->getDelayNS(user.budget)); } } } -- cgit v1.2.3 From 9c03909ebaec8157824a9cb13eeea774d29b35e1 Mon Sep 17 00:00:00 2001 From: Miodrag Milanovic Date: Thu, 21 Jun 2018 13:41:16 +0200 Subject: Make arch specific main window --- common/emb.cc | 138 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ common/emb.h | 20 +++++++++ 2 files changed, 158 insertions(+) create mode 100644 common/emb.cc create mode 100644 common/emb.h (limited to 'common') diff --git a/common/emb.cc b/common/emb.cc new file mode 100644 index 00000000..2e3379d5 --- /dev/null +++ b/common/emb.cc @@ -0,0 +1,138 @@ +// +// Copyright (C) 2011 Mateusz Loskot +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// Blog article: http://mateusz.loskot.net/?p=2819 + +#include "emb.h" +#include +#include +#include +#include + +namespace emb { +struct Stdout +{ + PyObject_HEAD stdout_write_type write; +}; + +PyObject *Stdout_write(PyObject *self, PyObject *args) +{ + std::size_t written(0); + Stdout *selfimpl = reinterpret_cast(self); + if (selfimpl->write) { + char *data; + if (!PyArg_ParseTuple(args, "s", &data)) + return 0; + + std::string str(data); + selfimpl->write(str); + written = str.size(); + } + return PyLong_FromSize_t(written); +} + +PyObject *Stdout_flush(PyObject *self, PyObject *args) +{ + // no-op + return Py_BuildValue(""); +} + +PyMethodDef Stdout_methods[] = { + {"write", Stdout_write, METH_VARARGS, "sys.stdout.write"}, + {"flush", Stdout_flush, METH_VARARGS, "sys.stdout.write"}, + {0, 0, 0, 0} // sentinel +}; + +PyTypeObject StdoutType = { + PyVarObject_HEAD_INIT(0, 0) "emb.StdoutType", /* tp_name */ + sizeof(Stdout), /* tp_basicsize */ + 0, /* tp_itemsize */ + 0, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + 0, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT, /* tp_flags */ + "emb.Stdout objects", /* tp_doc */ + 0, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + 0, /* tp_iter */ + 0, /* tp_iternext */ + Stdout_methods, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + 0, /* tp_init */ + 0, /* tp_alloc */ + 0, /* tp_new */ +}; + +PyModuleDef embmodule = { + PyModuleDef_HEAD_INIT, "emb", 0, -1, 0, +}; + +// Internal state +PyObject *g_stdout; +PyObject *g_stdout_saved; + +PyMODINIT_FUNC PyInit_emb(void) +{ + g_stdout = 0; + g_stdout_saved = 0; + + StdoutType.tp_new = PyType_GenericNew; + if (PyType_Ready(&StdoutType) < 0) + return 0; + + PyObject *m = PyModule_Create(&embmodule); + if (m) { + Py_INCREF(&StdoutType); + PyModule_AddObject(m, "Stdout", + reinterpret_cast(&StdoutType)); + } + return m; +} + +void set_stdout(stdout_write_type write) +{ + if (!g_stdout) { + g_stdout_saved = PySys_GetObject("stdout"); // borrowed + g_stdout = StdoutType.tp_new(&StdoutType, 0, 0); + } + + Stdout *impl = reinterpret_cast(g_stdout); + impl->write = write; + PySys_SetObject("stdout", g_stdout); +} + +void reset_stdout() +{ + if (g_stdout_saved) + PySys_SetObject("stdout", g_stdout_saved); + + Py_XDECREF(g_stdout); + g_stdout = 0; +} + +void append_inittab() { PyImport_AppendInittab("emb", emb::PyInit_emb); } + +} // namespace emb diff --git a/common/emb.h b/common/emb.h new file mode 100644 index 00000000..3daa7ca3 --- /dev/null +++ b/common/emb.h @@ -0,0 +1,20 @@ +// +// Copyright (C) 2011 Mateusz Loskot +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// Blog article: http://mateusz.loskot.net/?p=2819 + +#include +#include +#include + +namespace emb { +typedef std::function stdout_write_type; + +void set_stdout(stdout_write_type write); +void reset_stdout(); + +void append_inittab(); +} // namespace emb -- cgit v1.2.3 From 693c34ad0646aac1bb766e783eb94d710f8ff72b Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 14:08:45 +0200 Subject: Improvements in router Signed-off-by: Clifford Wolf --- common/nextpnr.h | 1 + common/route.cc | 212 ++++++++++++++++++++++++++++++++++++++----------------- 2 files changed, 149 insertions(+), 64 deletions(-) (limited to 'common') diff --git a/common/nextpnr.h b/common/nextpnr.h index 5ccbf057..db6901fe 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -289,6 +289,7 @@ NEXTPNR_NAMESPACE_BEGIN struct Context : Arch { bool verbose = false; + bool debug = false; bool force = false; Context(ArchArgs args) : Arch(args) {} diff --git a/common/route.cc b/common/route.cc index 6a410397..cf87ebaa 100644 --- a/common/route.cc +++ b/common/route.cc @@ -23,6 +23,38 @@ #include "log.h" #include "route.h" +namespace std { +template <> +struct hash> +{ + std::size_t + operator()(const pair &arg) const noexcept + { + std::size_t seed = hash()(arg.first); + seed ^= hash()(arg.second) + + 0x9e3779b9 + (seed << 6) + (seed >> 2); + return seed; + } +}; + +template <> +struct hash< + pair> +{ + std::size_t + operator()(const pair &arg) const noexcept + { + std::size_t seed = hash()(arg.first); + seed ^= hash()(arg.second) + + 0x9e3779b9 + (seed << 6) + (seed >> 2); + return seed; + } +}; +} // namespace std + namespace { USING_NEXTPNR_NAMESPACE @@ -46,6 +78,12 @@ struct QueuedWire }; }; +struct RipupScoreboard +{ + std::unordered_map, int> wireScores; + std::unordered_map, int> pipScores; +}; + void ripup_net(Context *ctx, IdString net_name) { auto net_info = ctx->nets.at(net_name); @@ -62,7 +100,9 @@ void ripup_net(Context *ctx, IdString net_name) struct Router { Context *ctx; + RipupScoreboard scores; IdString net_name; + bool ripup; delay_t ripup_penalty; @@ -99,31 +139,41 @@ struct Router queue.pop(); for (auto pip : ctx->getPipsDownhill(qw.wire)) { - delay_t next_delay = qw.delay; - IdString ripupNet = net_name; + delay_t next_delay = + qw.delay + ctx->getPipDelay(pip).avgDelay(); + WireId next_wire = ctx->getPipDstWire(pip); + bool foundRipupNet = false; visitCnt++; - if (!ctx->checkPipAvail(pip)) { + if (!ctx->checkWireAvail(next_wire)) { if (!ripup) continue; - ripupNet = ctx->getPipNet(pip, true); - if (ripupNet == net_name) + IdString ripupWireNet = ctx->getWireNet(next_wire, true); + if (ripupWireNet == net_name || ripupWireNet == IdString()) continue; + auto it = scores.wireScores.find( + std::make_pair(ripupWireNet, next_wire)); + if (it != scores.wireScores.end()) + next_delay += it->second * ripup_penalty; + foundRipupNet = true; } - WireId next_wire = ctx->getPipDstWire(pip); - next_delay += ctx->getPipDelay(pip).avgDelay(); - - if (!ctx->checkWireAvail(next_wire)) { + if (!ctx->checkPipAvail(pip)) { if (!ripup) continue; - ripupNet = ctx->getWireNet(next_wire, true); - if (ripupNet == net_name) + IdString ripupPipNet = ctx->getPipNet(pip, true); + if (ripupPipNet == net_name || ripupPipNet == IdString()) continue; + auto it = scores.pipScores.find( + std::make_pair(ripupPipNet, pip)); + if (it != scores.pipScores.end()) + next_delay += it->second * ripup_penalty; + foundRipupNet = true; } - if (ripupNet != net_name) + if (foundRipupNet) next_delay += ripup_penalty; + assert(next_delay >= 0); if (visited.count(next_wire)) { @@ -131,7 +181,7 @@ struct Router next_delay + ctx->getDelayEpsilon()) continue; #if 0 // FIXME - if (ctx->verbose) + if (ctx->debug) log("Found better route to %s. Old vs new delay " "estimate: %.3f %.3f\n", ctx->getWireName(next_wire).c_str(), @@ -154,16 +204,17 @@ struct Router } } - Router(Context *ctx, WireId src_wire, WireId dst_wire, bool ripup = false, - delay_t ripup_penalty = 0) - : ctx(ctx), ripup(ripup), ripup_penalty(ripup_penalty) + Router(Context *ctx, RipupScoreboard &scores, WireId src_wire, + WireId dst_wire, bool ripup = false, delay_t ripup_penalty = 0) + : ctx(ctx), scores(scores), ripup(ripup), + ripup_penalty(ripup_penalty) { std::unordered_map src_wires; src_wires[src_wire] = 0; route(src_wires, dst_wire); routedOkay = visited.count(dst_wire); - if (ctx->verbose) { + if (ctx->debug) { log("Route (from destination to source):\n"); WireId cursor = dst_wire; @@ -180,17 +231,17 @@ struct Router } } - Router(Context *ctx, IdString net_name, bool ripup = false, - delay_t ripup_penalty = 0) - : ctx(ctx), net_name(net_name), ripup(ripup), + Router(Context *ctx, RipupScoreboard &scores, IdString net_name, + bool ripup = false, delay_t ripup_penalty = 0) + : ctx(ctx), scores(scores), net_name(net_name), ripup(ripup), ripup_penalty(ripup_penalty) { auto net_info = ctx->nets.at(net_name); - if (ctx->verbose) + if (ctx->debug) log("Routing net %s.\n", net_name.c_str(ctx)); - if (ctx->verbose) + if (ctx->debug) log(" Source: %s.%s.\n", net_info->driver.cell->name.c_str(ctx), net_info->driver.port.c_str(ctx)); @@ -201,7 +252,7 @@ struct Router net_info->driver.cell->name.c_str(ctx), net_info->driver.cell->type.c_str(ctx)); - if (ctx->verbose) + if (ctx->debug) log(" Source bel: %s\n", ctx->getBelName(src_bel).c_str(ctx)); IdString driver_port = net_info->driver.port; @@ -220,7 +271,7 @@ struct Router net_info->driver.cell->name.c_str(ctx), ctx->getBelName(src_bel).c_str(ctx)); - if (ctx->verbose) + if (ctx->debug) log(" Source wire: %s\n", ctx->getWireName(src_wire).c_str(ctx)); std::unordered_map src_wires; @@ -232,7 +283,7 @@ struct Router ctx->shuffle(users_array); for (auto &user_it : users_array) { - if (ctx->verbose) + if (ctx->debug) log(" Route to: %s.%s.\n", user_it.cell->name.c_str(ctx), user_it.port.c_str(ctx)); @@ -243,7 +294,7 @@ struct Router user_it.cell->name.c_str(ctx), user_it.cell->type.c_str(ctx)); - if (ctx->verbose) + if (ctx->debug) log(" Destination bel: %s\n", ctx->getBelName(dst_bel).c_str(ctx)); @@ -264,7 +315,7 @@ struct Router user_it.cell->name.c_str(ctx), ctx->getBelName(dst_bel).c_str(ctx)); - if (ctx->verbose) { + if (ctx->debug) { log(" Destination wire: %s\n", ctx->getWireName(dst_wire).c_str(ctx)); log(" Path delay estimate: %.2f\n", @@ -274,7 +325,7 @@ struct Router route(src_wires, dst_wire); if (visited.count(dst_wire) == 0) { - if (ctx->verbose) + if (ctx->debug) log("Failed to route %s -> %s.\n", ctx->getWireName(src_wire).c_str(ctx), ctx->getWireName(dst_wire).c_str(ctx)); @@ -287,18 +338,18 @@ struct Router return; } - if (ctx->verbose) + if (ctx->debug) log(" Final path delay: %.3f\n", ctx->getDelayNS(visited[dst_wire].delay)); maxDelay = fmaxf(maxDelay, visited[dst_wire].delay); - if (ctx->verbose) + if (ctx->debug) log(" Route (from destination to source):\n"); WireId cursor = dst_wire; while (1) { - if (ctx->verbose) + if (ctx->debug) log(" %8.3f %s\n", ctx->getDelayNS(visited[cursor].delay), ctx->getWireName(cursor).c_str(ctx)); @@ -306,22 +357,31 @@ struct Router if (src_wires.count(cursor)) break; - IdString conflicting_net = ctx->getWireNet(cursor, true); + IdString conflicting_wire_net = ctx->getWireNet(cursor, true); + IdString conflicting_pip_net = + ctx->getPipNet(visited[cursor].pip, true); - if (conflicting_net != IdString()) { + if (conflicting_wire_net != IdString()) { assert(ripup); - assert(conflicting_net != net_name); - ripup_net(ctx, conflicting_net); - rippedNets.insert(conflicting_net); + assert(conflicting_wire_net != net_name); + ripup_net(ctx, conflicting_wire_net); + rippedNets.insert(conflicting_wire_net); + scores.wireScores[std::make_pair(net_name, cursor)]++; + scores.wireScores[std::make_pair(conflicting_wire_net, + cursor)]++; } - conflicting_net = ctx->getPipNet(visited[cursor].pip, true); - - if (conflicting_net != IdString()) { + if (conflicting_pip_net != IdString()) { assert(ripup); - assert(conflicting_net != net_name); - ripup_net(ctx, conflicting_net); - rippedNets.insert(conflicting_net); + assert(conflicting_pip_net != net_name); + if (conflicting_wire_net != conflicting_pip_net) { + ripup_net(ctx, conflicting_pip_net); + rippedNets.insert(conflicting_pip_net); + } + scores.pipScores[std::make_pair(net_name, + visited[cursor].pip)]++; + scores.pipScores[std::make_pair(conflicting_pip_net, + visited[cursor].pip)]++; } net_info->wires[cursor] = visited[cursor].pip; @@ -343,7 +403,8 @@ NEXTPNR_NAMESPACE_BEGIN bool route_design(Context *ctx) { - delay_t ripup_penalty = 5; + delay_t ripup_penalty = ctx->getRipupDelayPenalty(); + RipupScoreboard scores; log_info("Routing..\n"); @@ -425,17 +486,23 @@ bool route_design(Context *ctx) while (!netsQueue.empty()) { if (iterCnt == 200) { - log_info("giving up after %d iterations.\n", iterCnt); + log_warning("giving up after %d iterations.\n", iterCnt); return false; } - log_info("-- %d --\n", ++iterCnt); + + iterCnt++; + if (ctx->verbose) + log_info("-- %d --\n", iterCnt); int visitCnt = 0, revisitCnt = 0, netCnt = 0; std::unordered_set ripupQueue; - log_info("routing queue contains %d nets.\n", int(netsQueue.size())); - bool printNets = netsQueue.size() < 10; + if (ctx->verbose || iterCnt == 1) + log_info("routing queue contains %d nets.\n", + int(netsQueue.size())); + + bool printNets = ctx->verbose && (netsQueue.size() < 10); std::vector netsArray(netsQueue.begin(), netsQueue.end()); ctx->sorted_shuffle(netsArray); @@ -446,7 +513,7 @@ bool route_design(Context *ctx) log_info(" routing net %s. (%d users)\n", net_name.c_str(ctx), int(ctx->nets.at(net_name)->users.size())); - Router router(ctx, net_name, false); + Router router(ctx, scores, net_name, false); netCnt++; visitCnt += router.visitCnt; @@ -459,23 +526,29 @@ bool route_design(Context *ctx) ripupQueue.insert(net_name); } - if (!printNets && netCnt % 100 == 0) + if ((ctx->verbose || iterCnt == 1) && !printNets && + (netCnt % 100 == 0)) log_info(" processed %d nets. (%d routed, %d failed)\n", netCnt, netCnt - int(ripupQueue.size()), int(ripupQueue.size())); } - if (netCnt % 100 != 0) + int normalRouteCnt = netCnt - int(ripupQueue.size()); + + if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0)) log_info(" processed %d nets. (%d routed, %d failed)\n", netCnt, - netCnt - int(ripupQueue.size()), int(ripupQueue.size())); - log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt); + normalRouteCnt, int(ripupQueue.size())); + + if (ctx->verbose) + log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt); if (!ripupQueue.empty()) { - log_info("failed to route %d nets. re-routing in ripup mode.\n", - int(ripupQueue.size())); + if (ctx->verbose || iterCnt == 1) + log_info("failed to route %d nets. re-routing in ripup mode.\n", + int(ripupQueue.size())); - printNets = ripupQueue.size() < 10; + printNets = ctx->verbose && (ripupQueue.size() < 10); visitCnt = 0; revisitCnt = 0; @@ -492,8 +565,7 @@ bool route_design(Context *ctx) net_name.c_str(ctx), int(ctx->nets.at(net_name)->users.size())); - Router router(ctx, net_name, true, - ripup_penalty * (iterCnt - 1)); + Router router(ctx, scores, net_name, true, ripup_penalty); netCnt++; visitCnt += router.visitCnt; @@ -521,22 +593,33 @@ bool route_design(Context *ctx) ripCnt += router.rippedNets.size(); - if (!printNets && netCnt % 100 == 0) + if ((ctx->verbose || iterCnt == 1) && !printNets && + (netCnt % 100 == 0)) log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt); } - if (netCnt % 100 != 0) + if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0)) log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt); - log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt); + if (ctx->verbose) + log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt); - if (!netsQueue.empty()) + if (ctx->verbose && !netsQueue.empty()) log_info(" ripped up %d previously routed nets. continue " "routing.\n", int(netsQueue.size())); } + + if (!ctx->verbose) + log_info("iteration %d: routed %d nets without ripup, routed %d " + "nets with ripup.\n", + iterCnt, normalRouteCnt, int(ripupQueue.size())); + + if (iterCnt == 8 || iterCnt == 16 || iterCnt == 32 || iterCnt == 64 || + iterCnt == 128) + ripup_penalty += ctx->getRipupDelayPenalty(); } log_info("routing complete after %d iterations.\n", iterCnt); @@ -546,7 +629,8 @@ bool route_design(Context *ctx) bool get_actual_route_delay(Context *ctx, WireId src_wire, WireId dst_wire, delay_t &delay) { - Router router(ctx, src_wire, dst_wire); + RipupScoreboard scores; + Router router(ctx, scores, src_wire, dst_wire); if (router.routedOkay) delay = router.visited.at(dst_wire).delay; return router.routedOkay; -- cgit v1.2.3 From 993f6ef7d31ceee5fc71a99fcec19b521694e4f3 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 14:09:50 +0200 Subject: Improve log messages, move many messages to verbose mode Signed-off-by: Clifford Wolf --- common/design_utils.cc | 8 +++++--- common/log.cc | 12 +----------- common/log.h | 18 +----------------- common/place_sa.cc | 8 +++++--- common/route.cc | 1 + 5 files changed, 13 insertions(+), 34 deletions(-) (limited to 'common') diff --git a/common/design_utils.cc b/common/design_utils.cc index 4fbd16f1..535b6fda 100644 --- a/common/design_utils.cc +++ b/common/design_utils.cc @@ -64,11 +64,13 @@ void print_utilisation(const Context *ctx) for (auto bel : ctx->getBels()) { available_types[ctx->getBelType(bel)]++; } - log("\nDesign utilisation:\n"); + log_break(); + log_info("Device utilisation:\n"); for (auto type : available_types) { - log("\t%20s: %5d/%5d\n", ctx->belTypeToId(type.first).c_str(ctx), - get_or_default(used_types, type.first, 0), type.second); + log_info("\t%20s: %5d/%5d\n", ctx->belTypeToId(type.first).c_str(ctx), + get_or_default(used_types, type.first, 0), type.second); } + log_break(); } NEXTPNR_NAMESPACE_END diff --git a/common/log.cc b/common/log.cc index 2868e03f..b0cd802a 100644 --- a/common/log.cc +++ b/common/log.cc @@ -212,7 +212,7 @@ void log_cmd_error(const char *format, ...) logv_error(format, ap); } -void log_spacer() +void log_break() { if (log_newline_count < 2) log("\n"); @@ -220,12 +220,6 @@ void log_spacer() log("\n"); } -void log_push() {} - -void log_pop() { log_flush(); } - -void log_reset_stack() { log_flush(); } - void log_flush() { for (auto f : log_files) @@ -235,8 +229,4 @@ void log_flush() f->flush(); } -void log_cell(CellInfo *cell, std::string indent) {} - -void log_net(NetInfo *net, std::string indent) {} - NEXTPNR_NAMESPACE_END diff --git a/common/log.h b/common/log.h index 597b5fac..381843b3 100644 --- a/common/log.h +++ b/common/log.h @@ -71,25 +71,9 @@ NXP_NORETURN void log_error(const char *format, ...) NXP_NORETURN void log_cmd_error(const char *format, ...) NXP_ATTRIBUTE(format(printf, 1, 2), noreturn); -void log_spacer(); -void log_push(); -void log_pop(); - -void log_backtrace(const char *prefix, int levels); -void log_reset_stack(); +void log_break(); void log_flush(); -/* -const char *log_id(RTLIL::IdString id); - -template static inline const char *log_id(T *obj) { - return log_id(obj->name); -} -*/ - -void log_cell(CellInfo *cell, std::string indent = ""); -void log_net(NetInfo *net, std::string indent = ""); - #ifndef NDEBUG static inline void log_assert_worker(bool cond, const char *expr, const char *file, int line) diff --git a/common/place_sa.cc b/common/place_sa.cc index 2f8fb122..591766aa 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -77,6 +77,8 @@ class SAPlacer bool place() { + log_break(); + size_t placed_cells = 0; // Initial constraints placer for (auto cell_entry : ctx->cells) { @@ -408,9 +410,9 @@ class SAPlacer delta = new_wirelength - curr_wirelength; n_move++; // SA acceptance criterea - if (delta < 0 || - (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= - std::exp(-(delta / 2) / temp))) { + if (delta < 0 || (temp > 1e-6 && + (ctx->rng() / float(0x3fffffff)) <= + std::exp(-(delta / 2) / temp))) { n_accept++; if (delta < 2) improved = true; diff --git a/common/route.cc b/common/route.cc index cf87ebaa..bdb2f5b5 100644 --- a/common/route.cc +++ b/common/route.cc @@ -406,6 +406,7 @@ bool route_design(Context *ctx) delay_t ripup_penalty = ctx->getRipupDelayPenalty(); RipupScoreboard scores; + log_break(); log_info("Routing..\n"); std::unordered_set netsQueue; -- cgit v1.2.3 From 08020400b379a0c2d7069bbd62f43782d438598b Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 14:16:07 +0200 Subject: Fix build of "dummy" architexture Signed-off-by: Clifford Wolf --- common/route.cc | 44 ++++++++++++++++++-------------------------- 1 file changed, 18 insertions(+), 26 deletions(-) (limited to 'common') diff --git a/common/route.cc b/common/route.cc index bdb2f5b5..bf11b7d2 100644 --- a/common/route.cc +++ b/common/route.cc @@ -23,41 +23,32 @@ #include "log.h" #include "route.h" -namespace std { -template <> -struct hash> +namespace { + +USING_NEXTPNR_NAMESPACE + +struct hash_id_wire { - std::size_t - operator()(const pair &arg) const noexcept + std::size_t operator()(const std::pair &arg) const + noexcept { - std::size_t seed = hash()(arg.first); - seed ^= hash()(arg.second) + - 0x9e3779b9 + (seed << 6) + (seed >> 2); + std::size_t seed = std::hash()(arg.first); + seed ^= std::hash()(arg.second) + 0x9e3779b9 + (seed << 6) + + (seed >> 2); return seed; } }; -template <> -struct hash< - pair> +struct hash_id_pip { - std::size_t - operator()(const pair &arg) const noexcept + std::size_t operator()(const std::pair &arg) const noexcept { - std::size_t seed = hash()(arg.first); - seed ^= hash()(arg.second) + - 0x9e3779b9 + (seed << 6) + (seed >> 2); + std::size_t seed = std::hash()(arg.first); + seed ^= std::hash()(arg.second) + 0x9e3779b9 + (seed << 6) + + (seed >> 2); return seed; } }; -} // namespace std - -namespace { - -USING_NEXTPNR_NAMESPACE struct QueuedWire { @@ -80,8 +71,9 @@ struct QueuedWire struct RipupScoreboard { - std::unordered_map, int> wireScores; - std::unordered_map, int> pipScores; + std::unordered_map, int, hash_id_wire> + wireScores; + std::unordered_map, int, hash_id_pip> pipScores; }; void ripup_net(Context *ctx, IdString net_name) -- cgit v1.2.3 From a29bfc788eba9f11f1e0cd3d62a32c3894cddf49 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 15:47:41 +0200 Subject: Add ctx->checksum(), slightly improve log messages Signed-off-by: Clifford Wolf --- common/design_utils.cc | 6 ++- common/nextpnr.cc | 123 +++++++++++++++++++++++++++++++++++++++++++++++++ common/nextpnr.h | 8 +++- common/place_sa.cc | 1 + common/route.cc | 2 + common/timing.cc | 3 ++ 6 files changed, 140 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/design_utils.cc b/common/design_utils.cc index 535b6fda..fa914ee2 100644 --- a/common/design_utils.cc +++ b/common/design_utils.cc @@ -67,8 +67,10 @@ void print_utilisation(const Context *ctx) log_break(); log_info("Device utilisation:\n"); for (auto type : available_types) { - log_info("\t%20s: %5d/%5d\n", ctx->belTypeToId(type.first).c_str(ctx), - get_or_default(used_types, type.first, 0), type.second); + IdString type_id = ctx->belTypeToId(type.first); + int used_bels = get_or_default(used_types, type.first, 0); + log_info("\t%20s: %5d/%5d %5d%%\n", type_id.c_str(ctx), + used_bels, type.second, 100*used_bels/type.second); } log_break(); } diff --git a/common/nextpnr.cc b/common/nextpnr.cc index b093d855..144da7c8 100644 --- a/common/nextpnr.cc +++ b/common/nextpnr.cc @@ -53,4 +53,127 @@ void IdString::initialize_add(const BaseCtx *ctx, const char *s, int idx) ctx->idstring_idx_to_str->push_back(&insert_rc.first->first); } +static uint32_t xorshift32(uint32_t x) +{ + x ^= x << 13; + x ^= x >> 17; + x ^= x << 5; + return x; +} + +uint32_t Context::checksum() const +{ + uint32_t cksum = xorshift32(123456789); + + uint32_t cksum_nets_sum = 0; + for (auto &it : nets) + { + auto &ni = *it.second; + uint32_t x = 123456789; + x = xorshift32(x + xorshift32(it.first.index)); + x = xorshift32(x + xorshift32(ni.name.index)); + if (ni.driver.cell) + x = xorshift32(x + xorshift32(ni.driver.cell->name.index)); + x = xorshift32(x + xorshift32(ni.driver.port.index)); + x = xorshift32(x + xorshift32(getDelayChecksum(ni.driver.budget))); + + for (auto &u : ni.users) { + if (u.cell) + x = xorshift32(x + xorshift32(u.cell->name.index)); + x = xorshift32(x + xorshift32(u.port.index)); + x = xorshift32(x + xorshift32(getDelayChecksum(u.budget))); + } + + uint32_t attr_x_sum = 0; + for (auto &a : ni.attrs) { + uint32_t attr_x = 123456789; + attr_x = xorshift32(attr_x + xorshift32(a.first.index)); + for (uint8_t ch : a.second) + attr_x = xorshift32(attr_x + xorshift32(ch)); + attr_x_sum += attr_x; + } + x = xorshift32(x + xorshift32(attr_x_sum)); + + uint32_t wire_x_sum = 0; + for (auto &w : ni.wires) { + uint32_t wire_x = 123456789; + wire_x = xorshift32(wire_x + xorshift32(getWireChecksum(w.first))); + wire_x = xorshift32(wire_x + xorshift32(getPipChecksum(w.second))); + wire_x_sum += wire_x; + } + x = xorshift32(x + xorshift32(wire_x_sum)); + + uint32_t pip_x_sum = 0; + for (auto &p : ni.pips) { + uint32_t pip_x = 123456789; + pip_x = xorshift32(pip_x + xorshift32(getPipChecksum(p.first))); + pip_x = xorshift32(pip_x + xorshift32(p.second)); + pip_x_sum += pip_x; + } + x = xorshift32(x + xorshift32(pip_x_sum)); + + cksum_nets_sum += x; + } + cksum = xorshift32(cksum + xorshift32(cksum_nets_sum)); + + uint32_t cksum_cells_sum = 0; + for (auto &it : cells) + { + auto &ci = *it.second; + uint32_t x = 123456789; + x = xorshift32(x + xorshift32(it.first.index)); + x = xorshift32(x + xorshift32(ci.name.index)); + x = xorshift32(x + xorshift32(ci.type.index)); + + uint32_t port_x_sum = 0; + for (auto &p : ci.ports) { + uint32_t port_x = 123456789; + port_x = xorshift32(port_x + xorshift32(p.first.index)); + port_x = xorshift32(port_x + xorshift32(p.second.name.index)); + if (p.second.net) + port_x = xorshift32(port_x + xorshift32(p.second.net->name.index)); + port_x = xorshift32(port_x + xorshift32(p.second.type)); + port_x_sum += port_x; + } + x = xorshift32(x + xorshift32(port_x_sum)); + + uint32_t attr_x_sum = 0; + for (auto &a : ci.attrs) { + uint32_t attr_x = 123456789; + attr_x = xorshift32(attr_x + xorshift32(a.first.index)); + for (uint8_t ch : a.second) + attr_x = xorshift32(attr_x + xorshift32(ch)); + attr_x_sum += attr_x; + } + x = xorshift32(x + xorshift32(attr_x_sum)); + + uint32_t param_x_sum = 0; + for (auto &p : ci.params) { + uint32_t param_x = 123456789; + param_x = xorshift32(param_x + xorshift32(p.first.index)); + for (uint8_t ch : p.second) + param_x = xorshift32(param_x + xorshift32(ch)); + param_x_sum += param_x; + } + x = xorshift32(x + xorshift32(param_x_sum)); + + x = xorshift32(x + xorshift32(getBelChecksum(ci.bel))); + x = xorshift32(x + xorshift32(ci.belStrength)); + + uint32_t pin_x_sum = 0; + for (auto &a : ci.pins) { + uint32_t pin_x = 123456789; + pin_x = xorshift32(pin_x + xorshift32(a.first.index)); + pin_x = xorshift32(pin_x + xorshift32(a.second.index)); + pin_x_sum += pin_x; + } + x = xorshift32(x + xorshift32(pin_x_sum)); + + cksum_cells_sum += x; + } + cksum = xorshift32(cksum + xorshift32(cksum_cells_sum)); + + return cksum; +} + NEXTPNR_NAMESPACE_END diff --git a/common/nextpnr.h b/common/nextpnr.h index db6901fe..e52f72c2 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -302,10 +302,14 @@ struct Context : Arch { // xorshift64star // https://arxiv.org/abs/1402.6246 + + uint64_t retval = rngstate * 0x2545F4914F6CDD1D; + rngstate ^= rngstate >> 12; rngstate ^= rngstate << 25; rngstate ^= rngstate >> 27; - return rngstate * 0x2545F4914F6CDD1D; + + return retval; } int rng() { return rng64() & 0x3fffffff; } @@ -351,6 +355,8 @@ struct Context : Arch std::sort(a.begin(), a.end()); shuffle(a); } + + uint32_t checksum() const; }; NEXTPNR_NAMESPACE_END diff --git a/common/place_sa.cc b/common/place_sa.cc index 591766aa..4d0d5d08 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -480,6 +480,7 @@ bool place_design_sa(Context *ctx) { SAPlacer placer(ctx); placer.place(); + log_info("Checksum: 0x%08x\n", ctx->checksum()); return true; } diff --git a/common/route.cc b/common/route.cc index bf11b7d2..69a314d7 100644 --- a/common/route.cc +++ b/common/route.cc @@ -480,6 +480,7 @@ bool route_design(Context *ctx) while (!netsQueue.empty()) { if (iterCnt == 200) { log_warning("giving up after %d iterations.\n", iterCnt); + log_info("Checksum: 0x%08x\n", ctx->checksum()); return false; } @@ -616,6 +617,7 @@ bool route_design(Context *ctx) } log_info("routing complete after %d iterations.\n", iterCnt); + log_info("Checksum: 0x%08x\n", ctx->checksum()); return true; } diff --git a/common/timing.cc b/common/timing.cc index a7b37f9d..ac116711 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -78,6 +78,7 @@ static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, void assign_budget(Context *ctx, float default_clock) { + log_break(); log_info("Annotating ports with timing budgets\n"); // Clear delays to a very high value first delay_t default_slack = delay_t(1.0e12 / default_clock); @@ -117,6 +118,8 @@ void assign_budget(Context *ctx, float default_clock) net.first.c_str(ctx), ctx->getDelayNS(user.budget)); } } + + log_info("Checksum: 0x%08x\n", ctx->checksum()); } NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From 4fefdbd57c52d6373456bd379e3e54df770e1945 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 16:16:58 +0200 Subject: Cleanup parse_json_file API, some other cleanups Signed-off-by: Clifford Wolf --- common/pybindings.cc | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'common') diff --git a/common/pybindings.cc b/common/pybindings.cc index 26e8bf69..02dc2395 100644 --- a/common/pybindings.cc +++ b/common/pybindings.cc @@ -52,8 +52,7 @@ void parse_json_shim(std::string filename, Context &d) std::ifstream inf(filename); if (!inf) throw std::runtime_error("failed to open file " + filename); - std::istream *ifp = &inf; - parse_json_file(ifp, filename, &d); + parse_json_file(inf, filename, &d); } // Create a new Chip and load design from json file -- cgit v1.2.3 From fcfb85e9dc7cc4a858c938692a8612cef3c9538b Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 16:25:25 +0200 Subject: Zero-initialize PortRef budgets Signed-off-by: Clifford Wolf --- common/nextpnr.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common') diff --git a/common/nextpnr.h b/common/nextpnr.h index e52f72c2..1cf0cbbb 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -208,7 +208,7 @@ struct PortRef { CellInfo *cell = nullptr; IdString port; - delay_t budget; + delay_t budget = 0; }; struct NetInfo -- cgit v1.2.3 From 54549d36e911aac8d0b0a2eea6074654c06c9717 Mon Sep 17 00:00:00 2001 From: Miodrag Milanovic Date: Thu, 21 Jun 2018 17:44:18 +0200 Subject: log_error now trows exception, main is covering catch --- common/log.cc | 6 +----- common/log.h | 4 ++++ 2 files changed, 5 insertions(+), 5 deletions(-) (limited to 'common') diff --git a/common/log.cc b/common/log.cc index b0cd802a..495f83b1 100644 --- a/common/log.cc +++ b/common/log.cc @@ -150,12 +150,8 @@ void logv_error(const char *format, va_list ap) #ifdef EMSCRIPTEN log_files = backup_log_files; - throw 0; -#elif defined(_MSC_VER) - _exit(EXIT_FAILURE); -#else - _Exit(EXIT_FAILURE); #endif + throw log_execution_error_exception(); } void log(const char *format, ...) diff --git a/common/log.h b/common/log.h index 381843b3..65b3f178 100644 --- a/common/log.h +++ b/common/log.h @@ -43,6 +43,10 @@ struct log_cmd_error_exception { }; +struct log_execution_error_exception +{ +}; + extern std::vector log_files; extern std::vector log_streams; extern FILE *log_errfile; -- cgit v1.2.3 From 8fac26c2b795865098b1ba16152cd1c510133f29 Mon Sep 17 00:00:00 2001 From: Miodrag Milanovic Date: Thu, 21 Jun 2018 17:56:45 +0200 Subject: Fixed return codes for packer, placer and router --- common/place_sa.cc | 12 +- common/route.cc | 332 +++++++++++++++++++++++++++-------------------------- 2 files changed, 179 insertions(+), 165 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index 4d0d5d08..69ba968f 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -478,10 +478,14 @@ class SAPlacer bool place_design_sa(Context *ctx) { - SAPlacer placer(ctx); - placer.place(); - log_info("Checksum: 0x%08x\n", ctx->checksum()); - return true; + try { + SAPlacer placer(ctx); + placer.place(); + log_info("Checksum: 0x%08x\n", ctx->checksum()); + return true; + } catch (log_execution_error_exception) { + return false; + } } NEXTPNR_NAMESPACE_END diff --git a/common/route.cc b/common/route.cc index 69a314d7..e747f09c 100644 --- a/common/route.cc +++ b/common/route.cc @@ -395,230 +395,240 @@ NEXTPNR_NAMESPACE_BEGIN bool route_design(Context *ctx) { - delay_t ripup_penalty = ctx->getRipupDelayPenalty(); - RipupScoreboard scores; - - log_break(); - log_info("Routing..\n"); - - std::unordered_set netsQueue; - - for (auto &net_it : ctx->nets) { - auto net_name = net_it.first; - auto net_info = net_it.second; - - if (net_info->driver.cell == nullptr) - continue; + try { + delay_t ripup_penalty = ctx->getRipupDelayPenalty(); + RipupScoreboard scores; - if (!net_info->wires.empty()) - continue; - - netsQueue.insert(net_name); - } - - if (netsQueue.empty()) { - log_info("found no unrouted nets. no routing necessary.\n"); - return true; - } + log_break(); + log_info("Routing..\n"); - log_info("found %d unrouted nets. starting routing procedure.\n", - int(netsQueue.size())); + std::unordered_set netsQueue; - delay_t estimatedTotalDelay = 0.0; - int estimatedTotalDelayCnt = 0; + for (auto &net_it : ctx->nets) { + auto net_name = net_it.first; + auto net_info = net_it.second; - for (auto net_name : netsQueue) { - auto net_info = ctx->nets.at(net_name); + if (net_info->driver.cell == nullptr) + continue; - auto src_bel = net_info->driver.cell->bel; + if (!net_info->wires.empty()) + continue; - if (src_bel == BelId()) - continue; + netsQueue.insert(net_name); + } - IdString driver_port = net_info->driver.port; + if (netsQueue.empty()) { + log_info("found no unrouted nets. no routing necessary.\n"); + return true; + } - auto driver_port_it = net_info->driver.cell->pins.find(driver_port); - if (driver_port_it != net_info->driver.cell->pins.end()) - driver_port = driver_port_it->second; + log_info("found %d unrouted nets. starting routing procedure.\n", + int(netsQueue.size())); - auto src_wire = - ctx->getWireBelPin(src_bel, ctx->portPinFromId(driver_port)); + delay_t estimatedTotalDelay = 0.0; + int estimatedTotalDelayCnt = 0; - if (src_wire == WireId()) - continue; + for (auto net_name : netsQueue) { + auto net_info = ctx->nets.at(net_name); - for (auto &user_it : net_info->users) { - auto dst_bel = user_it.cell->bel; + auto src_bel = net_info->driver.cell->bel; - if (dst_bel == BelId()) + if (src_bel == BelId()) continue; - IdString user_port = user_it.port; - - auto user_port_it = user_it.cell->pins.find(user_port); + IdString driver_port = net_info->driver.port; - if (user_port_it != user_it.cell->pins.end()) - user_port = user_port_it->second; + auto driver_port_it = net_info->driver.cell->pins.find(driver_port); + if (driver_port_it != net_info->driver.cell->pins.end()) + driver_port = driver_port_it->second; - auto dst_wire = - ctx->getWireBelPin(dst_bel, ctx->portPinFromId(user_port)); + auto src_wire = ctx->getWireBelPin(src_bel, + ctx->portPinFromId(driver_port)); - if (dst_wire == WireId()) + if (src_wire == WireId()) continue; - estimatedTotalDelay += ctx->estimateDelay(src_wire, dst_wire); - estimatedTotalDelayCnt++; - } - } + for (auto &user_it : net_info->users) { + auto dst_bel = user_it.cell->bel; - log_info("estimated total wire delay: %.2f (avg %.2f)\n", - float(estimatedTotalDelay), - float(estimatedTotalDelay) / estimatedTotalDelayCnt); + if (dst_bel == BelId()) + continue; - int iterCnt = 0; + IdString user_port = user_it.port; - while (!netsQueue.empty()) { - if (iterCnt == 200) { - log_warning("giving up after %d iterations.\n", iterCnt); - log_info("Checksum: 0x%08x\n", ctx->checksum()); - return false; - } - - iterCnt++; - if (ctx->verbose) - log_info("-- %d --\n", iterCnt); - - int visitCnt = 0, revisitCnt = 0, netCnt = 0; + auto user_port_it = user_it.cell->pins.find(user_port); - std::unordered_set ripupQueue; + if (user_port_it != user_it.cell->pins.end()) + user_port = user_port_it->second; - if (ctx->verbose || iterCnt == 1) - log_info("routing queue contains %d nets.\n", - int(netsQueue.size())); + auto dst_wire = ctx->getWireBelPin( + dst_bel, ctx->portPinFromId(user_port)); - bool printNets = ctx->verbose && (netsQueue.size() < 10); + if (dst_wire == WireId()) + continue; - std::vector netsArray(netsQueue.begin(), netsQueue.end()); - ctx->sorted_shuffle(netsArray); - netsQueue.clear(); - - for (auto net_name : netsArray) { - if (printNets) - log_info(" routing net %s. (%d users)\n", net_name.c_str(ctx), - int(ctx->nets.at(net_name)->users.size())); + estimatedTotalDelay += ctx->estimateDelay(src_wire, dst_wire); + estimatedTotalDelayCnt++; + } + } - Router router(ctx, scores, net_name, false); + log_info("estimated total wire delay: %.2f (avg %.2f)\n", + float(estimatedTotalDelay), + float(estimatedTotalDelay) / estimatedTotalDelayCnt); - netCnt++; - visitCnt += router.visitCnt; - revisitCnt += router.revisitCnt; + int iterCnt = 0; - if (!router.routedOkay) { - if (printNets) - log_info(" failed to route to %s.\n", - ctx->getWireName(router.failedDest).c_str(ctx)); - ripupQueue.insert(net_name); + while (!netsQueue.empty()) { + if (iterCnt == 200) { + log_warning("giving up after %d iterations.\n", iterCnt); + log_info("Checksum: 0x%08x\n", ctx->checksum()); + return false; } - if ((ctx->verbose || iterCnt == 1) && !printNets && - (netCnt % 100 == 0)) - log_info(" processed %d nets. (%d routed, %d failed)\n", - netCnt, netCnt - int(ripupQueue.size()), - int(ripupQueue.size())); - } - - int normalRouteCnt = netCnt - int(ripupQueue.size()); + iterCnt++; + if (ctx->verbose) + log_info("-- %d --\n", iterCnt); - if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0)) - log_info(" processed %d nets. (%d routed, %d failed)\n", netCnt, - normalRouteCnt, int(ripupQueue.size())); + int visitCnt = 0, revisitCnt = 0, netCnt = 0; - if (ctx->verbose) - log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt); + std::unordered_set ripupQueue; - if (!ripupQueue.empty()) { if (ctx->verbose || iterCnt == 1) - log_info("failed to route %d nets. re-routing in ripup mode.\n", - int(ripupQueue.size())); - - printNets = ctx->verbose && (ripupQueue.size() < 10); + log_info("routing queue contains %d nets.\n", + int(netsQueue.size())); - visitCnt = 0; - revisitCnt = 0; - netCnt = 0; - int ripCnt = 0; + bool printNets = ctx->verbose && (netsQueue.size() < 10); - std::vector ripupArray(ripupQueue.begin(), - ripupQueue.end()); - ctx->sorted_shuffle(ripupArray); + std::vector netsArray(netsQueue.begin(), netsQueue.end()); + ctx->sorted_shuffle(netsArray); + netsQueue.clear(); - for (auto net_name : ripupArray) { + for (auto net_name : netsArray) { if (printNets) log_info(" routing net %s. (%d users)\n", net_name.c_str(ctx), int(ctx->nets.at(net_name)->users.size())); - Router router(ctx, scores, net_name, true, ripup_penalty); + Router router(ctx, scores, net_name, false); netCnt++; visitCnt += router.visitCnt; revisitCnt += router.revisitCnt; - if (!router.routedOkay) - log_error("Net %s is impossible to route.\n", - net_name.c_str(ctx)); - - for (auto it : router.rippedNets) - netsQueue.insert(it); - - if (printNets) { - if (router.rippedNets.size() < 10) { - log_info(" ripped up %d other nets:\n", - int(router.rippedNets.size())); - for (auto n : router.rippedNets) - log_info(" %s (%d users)\n", n.c_str(ctx), - int(ctx->nets.at(n)->users.size())); - } else { - log_info(" ripped up %d other nets.\n", - int(router.rippedNets.size())); - } + if (!router.routedOkay) { + if (printNets) + log_info( + " failed to route to %s.\n", + ctx->getWireName(router.failedDest).c_str(ctx)); + ripupQueue.insert(net_name); } - ripCnt += router.rippedNets.size(); - if ((ctx->verbose || iterCnt == 1) && !printNets && (netCnt % 100 == 0)) - log_info(" routed %d nets, ripped %d nets.\n", netCnt, - ripCnt); + log_info(" processed %d nets. (%d routed, %d failed)\n", + netCnt, netCnt - int(ripupQueue.size()), + int(ripupQueue.size())); } + int normalRouteCnt = netCnt - int(ripupQueue.size()); + if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0)) - log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt); + log_info(" processed %d nets. (%d routed, %d failed)\n", + netCnt, normalRouteCnt, int(ripupQueue.size())); if (ctx->verbose) log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", visitCnt, (100.0 * revisitCnt) / visitCnt); - if (ctx->verbose && !netsQueue.empty()) - log_info(" ripped up %d previously routed nets. continue " - "routing.\n", - int(netsQueue.size())); - } + if (!ripupQueue.empty()) { + if (ctx->verbose || iterCnt == 1) + log_info("failed to route %d nets. re-routing in ripup " + "mode.\n", + int(ripupQueue.size())); + + printNets = ctx->verbose && (ripupQueue.size() < 10); + + visitCnt = 0; + revisitCnt = 0; + netCnt = 0; + int ripCnt = 0; + + std::vector ripupArray(ripupQueue.begin(), + ripupQueue.end()); + ctx->sorted_shuffle(ripupArray); + + for (auto net_name : ripupArray) { + if (printNets) + log_info(" routing net %s. (%d users)\n", + net_name.c_str(ctx), + int(ctx->nets.at(net_name)->users.size())); + + Router router(ctx, scores, net_name, true, ripup_penalty); + + netCnt++; + visitCnt += router.visitCnt; + revisitCnt += router.revisitCnt; + + if (!router.routedOkay) + log_error("Net %s is impossible to route.\n", + net_name.c_str(ctx)); + + for (auto it : router.rippedNets) + netsQueue.insert(it); + + if (printNets) { + if (router.rippedNets.size() < 10) { + log_info(" ripped up %d other nets:\n", + int(router.rippedNets.size())); + for (auto n : router.rippedNets) + log_info(" %s (%d users)\n", n.c_str(ctx), + int(ctx->nets.at(n)->users.size())); + } else { + log_info(" ripped up %d other nets.\n", + int(router.rippedNets.size())); + } + } - if (!ctx->verbose) - log_info("iteration %d: routed %d nets without ripup, routed %d " - "nets with ripup.\n", - iterCnt, normalRouteCnt, int(ripupQueue.size())); + ripCnt += router.rippedNets.size(); - if (iterCnt == 8 || iterCnt == 16 || iterCnt == 32 || iterCnt == 64 || - iterCnt == 128) - ripup_penalty += ctx->getRipupDelayPenalty(); - } + if ((ctx->verbose || iterCnt == 1) && !printNets && + (netCnt % 100 == 0)) + log_info(" routed %d nets, ripped %d nets.\n", netCnt, + ripCnt); + } + + if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0)) + log_info(" routed %d nets, ripped %d nets.\n", netCnt, + ripCnt); - log_info("routing complete after %d iterations.\n", iterCnt); - log_info("Checksum: 0x%08x\n", ctx->checksum()); - return true; + if (ctx->verbose) + log_info(" routing pass visited %d PIPs (%.2f%% " + "revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt); + + if (ctx->verbose && !netsQueue.empty()) + log_info(" ripped up %d previously routed nets. continue " + "routing.\n", + int(netsQueue.size())); + } + + if (!ctx->verbose) + log_info( + "iteration %d: routed %d nets without ripup, routed %d " + "nets with ripup.\n", + iterCnt, normalRouteCnt, int(ripupQueue.size())); + + if (iterCnt == 8 || iterCnt == 16 || iterCnt == 32 || + iterCnt == 64 || iterCnt == 128) + ripup_penalty += ctx->getRipupDelayPenalty(); + } + + log_info("routing complete after %d iterations.\n", iterCnt); + log_info("Checksum: 0x%08x\n", ctx->checksum()); + return true; + } catch (log_execution_error_exception) { + return false; + } } bool get_actual_route_delay(Context *ctx, WireId src_wire, WireId dst_wire, -- cgit v1.2.3 From 38dc1cc5504961f666da32d7249532a23d5876ad Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 19:17:04 +0200 Subject: Work "overtime" to find better solutions in routing search algorithm Signed-off-by: Clifford Wolf --- common/route.cc | 32 +++++++++++++++++++++++--------- 1 file changed, 23 insertions(+), 9 deletions(-) (limited to 'common') diff --git a/common/route.cc b/common/route.cc index 69a314d7..0c072c3a 100644 --- a/common/route.cc +++ b/common/route.cc @@ -100,7 +100,7 @@ struct Router std::unordered_set rippedNets; std::unordered_map visited; - int visitCnt = 0, revisitCnt = 0; + int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0; bool routedOkay = false; delay_t maxDelay = 0.0; WireId failedDest; @@ -126,16 +126,22 @@ struct Router visited[qw.wire] = qw; } - while (!queue.empty() && !visited.count(dst_wire)) { + int thisVisitCnt = 0; + int thisVisitCntLimit = 0; + + while (!queue.empty() && (thisVisitCntLimit == 0 || thisVisitCnt < thisVisitCntLimit)) { QueuedWire qw = queue.top(); queue.pop(); + if (thisVisitCntLimit == 0 && visited.count(dst_wire)) + thisVisitCntLimit = (thisVisitCnt*3)/2; + for (auto pip : ctx->getPipsDownhill(qw.wire)) { delay_t next_delay = qw.delay + ctx->getPipDelay(pip).avgDelay(); WireId next_wire = ctx->getPipDstWire(pip); bool foundRipupNet = false; - visitCnt++; + thisVisitCnt++; if (!ctx->checkWireAvail(next_wire)) { if (!ripup) @@ -180,7 +186,10 @@ struct Router ctx->getDelayNS(visited.at(next_wire).delay), ctx->getDelayNS(next_delay)); #endif - revisitCnt++; + if (thisVisitCntLimit == 0) + revisitCnt++; + else + overtimeRevisitCnt++; } QueuedWire next_qw; @@ -194,6 +203,8 @@ struct Router queue.push(next_qw); } } + + visitCnt += thisVisitCnt; } Router(Context *ctx, RipupScoreboard &scores, WireId src_wire, @@ -488,7 +499,7 @@ bool route_design(Context *ctx) if (ctx->verbose) log_info("-- %d --\n", iterCnt); - int visitCnt = 0, revisitCnt = 0, netCnt = 0; + int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0, netCnt = 0; std::unordered_set ripupQueue; @@ -512,6 +523,7 @@ bool route_design(Context *ctx) netCnt++; visitCnt += router.visitCnt; revisitCnt += router.revisitCnt; + overtimeRevisitCnt += router.overtimeRevisitCnt; if (!router.routedOkay) { if (printNets) @@ -534,8 +546,8 @@ bool route_design(Context *ctx) normalRouteCnt, int(ripupQueue.size())); if (ctx->verbose) - log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt); + log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt); if (!ripupQueue.empty()) { if (ctx->verbose || iterCnt == 1) @@ -546,6 +558,7 @@ bool route_design(Context *ctx) visitCnt = 0; revisitCnt = 0; + overtimeRevisitCnt = 0; netCnt = 0; int ripCnt = 0; @@ -564,6 +577,7 @@ bool route_design(Context *ctx) netCnt++; visitCnt += router.visitCnt; revisitCnt += router.revisitCnt; + overtimeRevisitCnt += router.overtimeRevisitCnt; if (!router.routedOkay) log_error("Net %s is impossible to route.\n", @@ -597,8 +611,8 @@ bool route_design(Context *ctx) log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt); if (ctx->verbose) - log_info(" routing pass visited %d PIPs (%.2f%% revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt); + log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt); if (ctx->verbose && !netsQueue.empty()) log_info(" ripped up %d previously routed nets. continue " -- cgit v1.2.3 From 2c98231f88cd145267048b32a5ce0e4deadc2716 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 21 Jun 2018 19:36:20 +0200 Subject: Updates from clangformat Signed-off-by: Clifford Wolf --- common/design_utils.cc | 4 ++-- common/nextpnr.cc | 9 ++++----- common/route.cc | 20 +++++++++++++------- 3 files changed, 19 insertions(+), 14 deletions(-) (limited to 'common') diff --git a/common/design_utils.cc b/common/design_utils.cc index fa914ee2..92533fa3 100644 --- a/common/design_utils.cc +++ b/common/design_utils.cc @@ -69,8 +69,8 @@ void print_utilisation(const Context *ctx) for (auto type : available_types) { IdString type_id = ctx->belTypeToId(type.first); int used_bels = get_or_default(used_types, type.first, 0); - log_info("\t%20s: %5d/%5d %5d%%\n", type_id.c_str(ctx), - used_bels, type.second, 100*used_bels/type.second); + log_info("\t%20s: %5d/%5d %5d%%\n", type_id.c_str(ctx), used_bels, + type.second, 100 * used_bels / type.second); } log_break(); } diff --git a/common/nextpnr.cc b/common/nextpnr.cc index 144da7c8..b24f66ea 100644 --- a/common/nextpnr.cc +++ b/common/nextpnr.cc @@ -66,8 +66,7 @@ uint32_t Context::checksum() const uint32_t cksum = xorshift32(123456789); uint32_t cksum_nets_sum = 0; - for (auto &it : nets) - { + for (auto &it : nets) { auto &ni = *it.second; uint32_t x = 123456789; x = xorshift32(x + xorshift32(it.first.index)); @@ -117,8 +116,7 @@ uint32_t Context::checksum() const cksum = xorshift32(cksum + xorshift32(cksum_nets_sum)); uint32_t cksum_cells_sum = 0; - for (auto &it : cells) - { + for (auto &it : cells) { auto &ci = *it.second; uint32_t x = 123456789; x = xorshift32(x + xorshift32(it.first.index)); @@ -131,7 +129,8 @@ uint32_t Context::checksum() const port_x = xorshift32(port_x + xorshift32(p.first.index)); port_x = xorshift32(port_x + xorshift32(p.second.name.index)); if (p.second.net) - port_x = xorshift32(port_x + xorshift32(p.second.net->name.index)); + port_x = xorshift32(port_x + + xorshift32(p.second.net->name.index)); port_x = xorshift32(port_x + xorshift32(p.second.type)); port_x_sum += port_x; } diff --git a/common/route.cc b/common/route.cc index e6697349..967f9aa1 100644 --- a/common/route.cc +++ b/common/route.cc @@ -129,12 +129,13 @@ struct Router int thisVisitCnt = 0; int thisVisitCntLimit = 0; - while (!queue.empty() && (thisVisitCntLimit == 0 || thisVisitCnt < thisVisitCntLimit)) { + while (!queue.empty() && + (thisVisitCntLimit == 0 || thisVisitCnt < thisVisitCntLimit)) { QueuedWire qw = queue.top(); queue.pop(); if (thisVisitCntLimit == 0 && visited.count(dst_wire)) - thisVisitCntLimit = (thisVisitCnt*3)/2; + thisVisitCntLimit = (thisVisitCnt * 3) / 2; for (auto pip : ctx->getPipsDownhill(qw.wire)) { delay_t next_delay = @@ -500,7 +501,8 @@ bool route_design(Context *ctx) if (ctx->verbose) log_info("-- %d --\n", iterCnt); - int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0, netCnt = 0; + int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0, + netCnt = 0; std::unordered_set ripupQueue; @@ -549,8 +551,10 @@ bool route_design(Context *ctx) netCnt, normalRouteCnt, int(ripupQueue.size())); if (ctx->verbose) - log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt); + log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime " + "revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt, + (100.0 * overtimeRevisitCnt) / visitCnt); if (!ripupQueue.empty()) { if (ctx->verbose || iterCnt == 1) @@ -616,8 +620,10 @@ bool route_design(Context *ctx) ripCnt); if (ctx->verbose) - log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", - visitCnt, (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt); + log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% " + "overtime revisits).\n", + visitCnt, (100.0 * revisitCnt) / visitCnt, + (100.0 * overtimeRevisitCnt) / visitCnt); if (ctx->verbose && !netsQueue.empty()) log_info(" ripped up %d previously routed nets. continue " -- cgit v1.2.3 From 71176ac5384c696dde1d5601ea1beb5c46f281c6 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 22 Jun 2018 12:34:42 +0200 Subject: Fixing 5k bitstream gen and place heuristics Signed-off-by: David Shah --- common/place_sa.cc | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index 69ba968f..cd4e7282 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -410,9 +410,8 @@ class SAPlacer delta = new_wirelength - curr_wirelength; n_move++; // SA acceptance criterea - if (delta < 0 || (temp > 1e-6 && - (ctx->rng() / float(0x3fffffff)) <= - std::exp(-(delta / 2) / temp))) { + if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= + std::exp(-delta / temp))) { n_accept++; if (delta < 2) improved = true; -- cgit v1.2.3 From 63baa10032ecf301523e4cb1fca198d8a8b79e23 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 22 Jun 2018 12:57:22 +0200 Subject: ice40: Make the packer deterministic Signed-off-by: David Shah --- common/util.h | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'common') diff --git a/common/util.h b/common/util.h index 34b2ed02..8151564f 100644 --- a/common/util.h +++ b/common/util.h @@ -21,6 +21,7 @@ #define UTIL_H #include +#include #include "nextpnr.h" NEXTPNR_NAMESPACE_BEGIN @@ -56,6 +57,13 @@ bool bool_or_default(const Container &ct, const KeyType &key, bool def = false) { return bool(int_or_default(ct, key, int(def))); }; + +// Wrap an unordered_map, and allow it to be iterated over sorted by key +template std::map sorted(const std::unordered_map &orig) { + return std::map(orig.begin(), orig.end()); +}; + + NEXTPNR_NAMESPACE_END #endif -- cgit v1.2.3 From ce4ad44fd1837242324ca110a9058182eef99dcd Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 22 Jun 2018 14:58:27 +0200 Subject: Print quasi-TNS statistic during placement Signed-off-by: David Shah --- common/place_sa.cc | 24 ++++++++++++++++-------- common/util.h | 7 ++++--- 2 files changed, 20 insertions(+), 11 deletions(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index cd4e7282..11f46ad9 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -146,8 +146,9 @@ class SAPlacer // Calculate wirelength after initial placement curr_wirelength = 0; + curr_tns = 0; for (auto net : ctx->nets) { - wirelen_t wl = get_wirelength(net.second); + wirelen_t wl = get_wirelength(net.second, curr_tns); wirelengths[net.first] = wl; curr_wirelength += wl; } @@ -162,8 +163,9 @@ class SAPlacer improved = false; if (iter % 5 == 0 || iter == 1) - log_info(" at iteration #%d: temp = %f, wire length = %f\n", - iter, temp, double(curr_wirelength)); + log_info(" at iteration #%d: temp = %.02f, wire length = " + "%.0f, est tns = %.02fns\n", + iter, temp, double(curr_wirelength), curr_tns); for (int m = 0; m < 15; ++m) { // Loop through all automatically placed cells @@ -220,8 +222,9 @@ class SAPlacer // Recalculate total wirelength entirely to avoid rounding errors // accumulating over time curr_wirelength = 0; + curr_tns = 0; for (auto net : ctx->nets) { - wirelen_t wl = get_wirelength(net.second); + wirelen_t wl = get_wirelength(net.second, curr_tns); wirelengths[net.first] = wl; curr_wirelength += wl; } @@ -308,7 +311,7 @@ class SAPlacer } // Get the total estimated wirelength for a net - wirelen_t get_wirelength(NetInfo *net) + wirelen_t get_wirelength(NetInfo *net, float &tns) { wirelen_t wirelength = 0; int driver_x, driver_y; @@ -337,6 +340,8 @@ class SAPlacer 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; @@ -348,8 +353,9 @@ class SAPlacer xmax = std::max(xmax, load_x); ymax = std::max(ymax, load_y); } - wirelength = wirelen_t((((ymax - ymin) + (xmax - xmin)) * - (1.0 + std::exp(-worst_slack / 5)))); + wirelength = + wirelen_t((((ymax - ymin) + (xmax - xmin)) * + std::min(3.0, (1.0 + std::exp(-worst_slack / 10))))); return wirelength; } @@ -403,7 +409,8 @@ class SAPlacer // Recalculate wirelengths for all nets touched by the peturbation for (auto net : update) { new_wirelength -= wirelengths.at(net->name); - wirelen_t net_new_wl = get_wirelength(net); + float temp_tns = 0; + wirelen_t net_new_wl = get_wirelength(net, temp_tns); new_wirelength += net_new_wl; new_lengths.push_back(std::make_pair(net->name, net_new_wl)); } @@ -465,6 +472,7 @@ class SAPlacer Context *ctx; std::unordered_map wirelengths; wirelen_t curr_wirelength = std::numeric_limits::max(); + float curr_tns = 0; float temp = 1000; bool improved = false; int n_move, n_accept; diff --git a/common/util.h b/common/util.h index 8151564f..4c60292b 100644 --- a/common/util.h +++ b/common/util.h @@ -20,8 +20,8 @@ #ifndef UTIL_H #define UTIL_H -#include #include +#include #include "nextpnr.h" NEXTPNR_NAMESPACE_BEGIN @@ -59,11 +59,12 @@ bool bool_or_default(const Container &ct, const KeyType &key, bool def = false) }; // Wrap an unordered_map, and allow it to be iterated over sorted by key -template std::map sorted(const std::unordered_map &orig) { +template +std::map sorted(const std::unordered_map &orig) +{ return std::map(orig.begin(), orig.end()); }; - NEXTPNR_NAMESPACE_END #endif -- cgit v1.2.3 From d7939f96e6da6eeaffe2d2851f233d32bfb5d6cd Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 22 Jun 2018 15:03:33 +0200 Subject: place_sa: Fix temp printing Signed-off-by: David Shah --- common/place_sa.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index 11f46ad9..8b111c6c 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -163,7 +163,7 @@ class SAPlacer improved = false; if (iter % 5 == 0 || iter == 1) - log_info(" at iteration #%d: temp = %.02f, wire length = " + log_info(" at iteration #%d: temp = %f, wire length = " "%.0f, est tns = %.02fns\n", iter, temp, double(curr_wirelength), curr_tns); -- cgit v1.2.3 From f86a0d6c8c8792c36c87cf345665ce7c9fbcc60f Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 22 Jun 2018 15:17:00 +0200 Subject: place_sa: Tweak weighting given to timing Signed-off-by: David Shah --- common/place_sa.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common') diff --git a/common/place_sa.cc b/common/place_sa.cc index 8b111c6c..058f0a84 100644 --- a/common/place_sa.cc +++ b/common/place_sa.cc @@ -355,7 +355,7 @@ class SAPlacer } wirelength = wirelen_t((((ymax - ymin) + (xmax - xmin)) * - std::min(3.0, (1.0 + std::exp(-worst_slack / 10))))); + std::min(5.0, (1.0 + std::exp(-worst_slack / 5))))); return wirelength; } -- cgit v1.2.3