From dfd6b6e39e56a2c2b10b051b9b54926e120f319e Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 16 Oct 2020 13:33:44 +0100 Subject: nexus: Add a simple global routing pass Signed-off-by: David Shah --- nexus/arch.cc | 3 ++ nexus/arch.h | 4 ++ nexus/global.cc | 160 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 167 insertions(+) create mode 100644 nexus/global.cc diff --git a/nexus/arch.cc b/nexus/arch.cc index 8005a130..3435755b 100644 --- a/nexus/arch.cc +++ b/nexus/arch.cc @@ -446,6 +446,9 @@ bool Arch::place() bool Arch::route() { assign_budget(getCtx(), true); + + route_globals(); + std::string router = str_or_default(settings, id("router"), defaultRouter); bool result; if (router == "router1") { diff --git a/nexus/arch.h b/nexus/arch.h index 126d0a91..60b4b166 100644 --- a/nexus/arch.h +++ b/nexus/arch.h @@ -1319,6 +1319,10 @@ struct Arch : BaseCtx void assignArchInfo(); void assignCellInfo(CellInfo *cell); + // ------------------------------------------------- + // Arch-specific global routing + void route_globals(); + // ------------------------------------------------- std::vector getDecalGraphics(DecalId decal) const; diff --git a/nexus/global.cc b/nexus/global.cc new file mode 100644 index 00000000..2d183e95 --- /dev/null +++ b/nexus/global.cc @@ -0,0 +1,160 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2020 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 "log.h" +#include "nextpnr.h" +#include "util.h" + +#include + +NEXTPNR_NAMESPACE_BEGIN + +struct NexusGlobalRouter +{ + Context *ctx; + + NexusGlobalRouter(Context *ctx) : ctx(ctx){}; + + // When routing globals; we allow global->local for some tricky cases but never local->local + bool global_pip_filter(PipId pip) const + { + IdString dest_basename(ctx->wire_data(ctx->getPipDstWire(pip)).name); + const std::string &s = dest_basename.str(ctx); + if (s.size() > 2 && (s[0] == 'H' || s[0] == 'V') && s[1] == '0') + return false; + return true; + } + + // Dedicated backwards BFS routing for global networks + template + bool backwards_bfs_route(NetInfo *net, size_t user_idx, int iter_limit, bool strict, Tfilt pip_filter) + { + // Queue of wires to visit + std::queue visit; + // Wire -> upstream pip + std::unordered_map backtrace; + + // Lookup source and destination wires + WireId src = ctx->getNetinfoSourceWire(net); + WireId dst = ctx->getNetinfoSinkWire(net, net->users.at(user_idx)); + + if (ctx->getBoundWireNet(src) != net) + ctx->bindWire(src, net, STRENGTH_LOCKED); + + if (src == dst) { + // Nothing more to do + return true; + } + + visit.push(dst); + backtrace[dst] = PipId(); + + int iter = 0; + + while (!visit.empty() && (iter++ < iter_limit)) { + WireId cursor = visit.front(); + visit.pop(); + // Search uphill pips + for (PipId pip : ctx->getPipsUphill(cursor)) { + // Skip pip if unavailable, and not because it's already used for this net + if (!ctx->checkPipAvail(pip) && ctx->getBoundPipNet(pip) != net) + continue; + WireId prev = ctx->getPipSrcWire(pip); + // Ditto for the upstream wire + if (!ctx->checkWireAvail(prev) && ctx->getBoundWireNet(prev) != net) + continue; + // Skip already visited wires + if (backtrace.count(prev)) + continue; + // Apply our custom pip filter + if (!pip_filter(pip)) + continue; + // Add to the queue + visit.push(prev); + backtrace[prev] = pip; + // Check if we are done yet + if (prev == src) + goto done; + } + if (false) { + done: + break; + } + } + + if (backtrace.count(src)) { + WireId cursor = src; + std::vector pips; + // Create a list of pips on the routed path + while (true) { + PipId pip = backtrace.at(cursor); + if (pip == PipId()) + break; + pips.push_back(pip); + cursor = ctx->getPipDstWire(pip); + } + // Reverse that list + std::reverse(pips.begin(), pips.end()); + // Bind pips until we hit already-bound routing + for (PipId pip : pips) { + WireId dst = ctx->getPipDstWire(pip); + if (ctx->getBoundWireNet(dst) == net) + break; + ctx->bindPip(pip, net, STRENGTH_LOCKED); + } + return true; + } else { + if (strict) + log_error("Failed to route net '%s' from %s to %s using dedicated routing.\n", ctx->nameOf(net), + ctx->nameOfWire(src), ctx->nameOfWire(dst)); + return false; + } + } + + void route_clk_net(NetInfo *net) + { + for (size_t i = 0; i < net->users.size(); i++) + backwards_bfs_route(net, i, 1000000, true, [&](PipId pip) { return global_pip_filter(pip); }); + log_info(" routed net '%s' using global resources\n", ctx->nameOf(net)); + } + + void operator()() + { + log_info("Routing globals...\n"); + for (auto net : sorted(ctx->nets)) { + NetInfo *ni = net.second; + CellInfo *drv = ni->driver.cell; + if (drv == nullptr) + continue; + if (drv->type == id_DCC) { + route_clk_net(ni); + continue; + } + } + } +}; + +void Arch::route_globals() +{ + NexusGlobalRouter glb_router(getCtx()); + glb_router(); +} + +NEXTPNR_NAMESPACE_END -- cgit v1.2.3