| /* |
| * nextpnr -- Next Generation Place and Route |
| * |
| * Copyright (C) 2018 Clifford Wolf <clifford@symbioticeda.com> |
| * |
| * 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 <cmath> |
| #include <queue> |
| |
| #include "log.h" |
| #include "router1.h" |
| #include "timing.h" |
| |
| namespace { |
| |
| USING_NEXTPNR_NAMESPACE |
| |
| struct hash_id_wire |
| { |
| std::size_t operator()(const std::pair<IdString, WireId> &arg) const noexcept |
| { |
| std::size_t seed = std::hash<IdString>()(arg.first); |
| seed ^= std::hash<WireId>()(arg.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2); |
| return seed; |
| } |
| }; |
| |
| struct hash_id_pip |
| { |
| std::size_t operator()(const std::pair<IdString, PipId> &arg) const noexcept |
| { |
| std::size_t seed = std::hash<IdString>()(arg.first); |
| seed ^= std::hash<PipId>()(arg.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2); |
| return seed; |
| } |
| }; |
| |
| struct QueuedWire |
| { |
| WireId wire; |
| PipId pip; |
| |
| delay_t delay = 0, togo = 0; |
| int randtag = 0; |
| |
| struct Greater |
| { |
| bool operator()(const QueuedWire &lhs, const QueuedWire &rhs) const noexcept |
| { |
| delay_t l = lhs.delay + lhs.togo, r = rhs.delay + rhs.togo; |
| return l == r ? lhs.randtag > rhs.randtag : l > r; |
| } |
| }; |
| }; |
| |
| struct RipupScoreboard |
| { |
| std::unordered_map<WireId, int> wireScores; |
| std::unordered_map<PipId, int> pipScores; |
| std::unordered_map<std::pair<IdString, WireId>, int, hash_id_wire> netWireScores; |
| std::unordered_map<std::pair<IdString, PipId>, int, hash_id_pip> netPipScores; |
| }; |
| |
| void ripup_net(Context *ctx, IdString net_name) |
| { |
| if (ctx->debug) |
| log("Ripping up all routing for net %s.\n", net_name.c_str(ctx)); |
| |
| auto net_info = ctx->nets.at(net_name).get(); |
| std::vector<PipId> pips; |
| std::vector<WireId> wires; |
| |
| pips.reserve(net_info->wires.size()); |
| wires.reserve(net_info->wires.size()); |
| |
| for (auto &it : net_info->wires) { |
| if (it.second.pip != PipId()) |
| pips.push_back(it.second.pip); |
| else |
| wires.push_back(it.first); |
| } |
| |
| for (auto pip : pips) |
| ctx->unbindPip(pip); |
| |
| for (auto wire : wires) |
| ctx->unbindWire(wire); |
| |
| NPNR_ASSERT(net_info->wires.empty()); |
| } |
| |
| struct Router |
| { |
| Context *ctx; |
| const Router1Cfg &cfg; |
| RipupScoreboard scores; |
| IdString net_name; |
| |
| bool ripup; |
| delay_t ripup_penalty; |
| |
| std::unordered_set<IdString> rippedNets; |
| std::unordered_map<WireId, QueuedWire> visited; |
| int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0; |
| bool routedOkay = false; |
| delay_t maxDelay = 0.0; |
| WireId failedDest; |
| |
| void route(const std::unordered_map<WireId, delay_t> &src_wires, WireId dst_wire) |
| { |
| std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> queue; |
| |
| visited.clear(); |
| |
| for (auto &it : src_wires) { |
| QueuedWire qw; |
| qw.wire = it.first; |
| qw.pip = PipId(); |
| qw.delay = it.second - (it.second / 16); |
| if (cfg.useEstimate) |
| qw.togo = ctx->estimateDelay(qw.wire, dst_wire); |
| qw.randtag = ctx->rng(); |
| |
| queue.push(qw); |
| visited[qw.wire] = qw; |
| } |
| |
| 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).maxDelay(); |
| WireId next_wire = ctx->getPipDstWire(pip); |
| bool foundRipupNet = false; |
| thisVisitCnt++; |
| |
| next_delay += ctx->getWireDelay(next_wire).maxDelay(); |
| |
| if (!ctx->checkWireAvail(next_wire)) { |
| if (!ripup) |
| continue; |
| NetInfo *ripupWireNet = ctx->getConflictingWireNet(next_wire); |
| if (ripupWireNet == nullptr || ripupWireNet->name == net_name) |
| continue; |
| |
| auto it1 = scores.wireScores.find(next_wire); |
| if (it1 != scores.wireScores.end()) |
| next_delay += (it1->second * ripup_penalty) / 8; |
| |
| auto it2 = scores.netWireScores.find(std::make_pair(ripupWireNet->name, next_wire)); |
| if (it2 != scores.netWireScores.end()) |
| next_delay += it2->second * ripup_penalty; |
| |
| foundRipupNet = true; |
| } |
| |
| if (!ctx->checkPipAvail(pip)) { |
| if (!ripup) |
| continue; |
| NetInfo *ripupPipNet = ctx->getConflictingPipNet(pip); |
| if (ripupPipNet == nullptr || ripupPipNet->name == net_name) |
| continue; |
| |
| auto it1 = scores.pipScores.find(pip); |
| if (it1 != scores.pipScores.end()) |
| next_delay += (it1->second * ripup_penalty) / 8; |
| |
| auto it2 = scores.netPipScores.find(std::make_pair(ripupPipNet->name, pip)); |
| if (it2 != scores.netPipScores.end()) |
| next_delay += it2->second * ripup_penalty; |
| |
| foundRipupNet = true; |
| } |
| |
| if (foundRipupNet) |
| next_delay += ripup_penalty; |
| |
| NPNR_ASSERT(next_delay >= 0); |
| |
| if (visited.count(next_wire)) { |
| if (visited.at(next_wire).delay <= next_delay + ctx->getDelayEpsilon()) |
| continue; |
| #if 0 // FIXME |
| if (ctx->debug) |
| log("Found better route to %s. Old vs new delay estimate: %.3f %.3f\n", |
| ctx->getWireName(next_wire).c_str(), |
| ctx->getDelayNS(visited.at(next_wire).delay), |
| ctx->getDelayNS(next_delay)); |
| #endif |
| if (thisVisitCntLimit == 0) |
| revisitCnt++; |
| else |
| overtimeRevisitCnt++; |
| } |
| |
| QueuedWire next_qw; |
| next_qw.wire = next_wire; |
| next_qw.pip = pip; |
| next_qw.delay = next_delay; |
| if (cfg.useEstimate) |
| next_qw.togo = ctx->estimateDelay(next_wire, dst_wire); |
| next_qw.randtag = ctx->rng(); |
| |
| visited[next_qw.wire] = next_qw; |
| queue.push(next_qw); |
| } |
| } |
| |
| visitCnt += thisVisitCnt; |
| } |
| |
| Router(Context *ctx, const Router1Cfg &cfg, RipupScoreboard &scores, WireId src_wire, WireId dst_wire, |
| bool ripup = false, delay_t ripup_penalty = 0) |
| : ctx(ctx), cfg(cfg), scores(scores), ripup(ripup), ripup_penalty(ripup_penalty) |
| { |
| std::unordered_map<WireId, delay_t> src_wires; |
| src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay(); |
| route(src_wires, dst_wire); |
| routedOkay = visited.count(dst_wire); |
| |
| if (ctx->debug) { |
| log("Route (from destination to source):\n"); |
| |
| WireId cursor = dst_wire; |
| |
| while (1) { |
| log(" %8.3f %s\n", ctx->getDelayNS(visited[cursor].delay), ctx->getWireName(cursor).c_str(ctx)); |
| |
| if (cursor == src_wire) |
| break; |
| |
| cursor = ctx->getPipSrcWire(visited[cursor].pip); |
| } |
| } |
| } |
| |
| Router(Context *ctx, const Router1Cfg &cfg, RipupScoreboard &scores, IdString net_name, int user_idx = -1, |
| bool reroute = false, bool ripup = false, delay_t ripup_penalty = 0) |
| : ctx(ctx), cfg(cfg), scores(scores), net_name(net_name), ripup(ripup), ripup_penalty(ripup_penalty) |
| { |
| auto net_info = ctx->nets.at(net_name).get(); |
| |
| if (ctx->debug) |
| log("Routing net %s.\n", net_name.c_str(ctx)); |
| |
| if (ctx->debug) |
| log(" Source: %s.%s.\n", net_info->driver.cell->name.c_str(ctx), net_info->driver.port.c_str(ctx)); |
| |
| auto src_wire = ctx->getNetinfoSourceWire(net_info); |
| |
| if (src_wire == WireId()) |
| log_error("No wire found for port %s on source cell %s.\n", net_info->driver.port.c_str(ctx), |
| net_info->driver.cell->name.c_str(ctx)); |
| |
| if (ctx->debug) |
| log(" Source wire: %s\n", ctx->getWireName(src_wire).c_str(ctx)); |
| |
| std::unordered_map<WireId, delay_t> src_wires; |
| std::vector<std::pair<delay_t, int>> users_array; |
| |
| if (user_idx < 0) { |
| // route all users, from worst to best slack |
| for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) { |
| auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]); |
| delay_t slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire); |
| users_array.push_back(std::pair<delay_t, int>(slack, user_idx)); |
| } |
| std::sort(users_array.begin(), users_array.end()); |
| } else { |
| // route only the selected user |
| users_array.push_back(std::pair<delay_t, int>(delay_t(), user_idx)); |
| } |
| |
| if (reroute) { |
| // complete ripup |
| ripup_net(ctx, net_name); |
| ctx->bindWire(src_wire, ctx->nets.at(net_name).get(), STRENGTH_WEAK); |
| src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay(); |
| } else { |
| // re-use existing routes as much as possible |
| if (net_info->wires.count(src_wire) == 0) |
| ctx->bindWire(src_wire, ctx->nets.at(net_name).get(), STRENGTH_WEAK); |
| src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay(); |
| |
| for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) { |
| auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]); |
| |
| if (dst_wire == WireId()) |
| log_error("No wire found for port %s on destination cell %s.\n", |
| net_info->users[user_idx].port.c_str(ctx), |
| net_info->users[user_idx].cell->name.c_str(ctx)); |
| |
| std::function<delay_t(WireId)> register_existing_path = |
| [ctx, net_info, &src_wires, ®ister_existing_path](WireId wire) -> delay_t { |
| auto it = src_wires.find(wire); |
| if (it != src_wires.end()) |
| return it->second; |
| |
| PipId pip = net_info->wires.at(wire).pip; |
| delay_t delay = register_existing_path(ctx->getPipSrcWire(pip)); |
| delay += ctx->getPipDelay(pip).maxDelay(); |
| delay += ctx->getWireDelay(wire).maxDelay(); |
| src_wires[wire] = delay; |
| |
| return delay; |
| }; |
| |
| WireId cursor = dst_wire; |
| while (src_wires.count(cursor) == 0) { |
| auto it = net_info->wires.find(cursor); |
| if (it == net_info->wires.end()) |
| goto check_next_user_for_existing_path; |
| NPNR_ASSERT(it->second.pip != PipId()); |
| cursor = ctx->getPipSrcWire(it->second.pip); |
| } |
| |
| register_existing_path(dst_wire); |
| check_next_user_for_existing_path:; |
| } |
| |
| std::vector<WireId> ripup_wires; |
| for (auto &it : net_info->wires) |
| if (src_wires.count(it.first) == 0) |
| ripup_wires.push_back(it.first); |
| |
| for (auto &it : ripup_wires) { |
| if (ctx->debug) |
| log(" Unbind dangling wire for net %s: %s\n", net_name.c_str(ctx), |
| ctx->getWireName(it).c_str(ctx)); |
| ctx->unbindWire(it); |
| } |
| } |
| |
| for (auto user_idx_it : users_array) { |
| int user_idx = user_idx_it.second; |
| |
| if (ctx->debug) |
| log(" Route to: %s.%s.\n", net_info->users[user_idx].cell->name.c_str(ctx), |
| net_info->users[user_idx].port.c_str(ctx)); |
| |
| auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]); |
| |
| if (dst_wire == WireId()) |
| log_error("No wire found for port %s on destination cell %s.\n", |
| net_info->users[user_idx].port.c_str(ctx), net_info->users[user_idx].cell->name.c_str(ctx)); |
| |
| if (ctx->debug) { |
| log(" Destination wire: %s\n", ctx->getWireName(dst_wire).c_str(ctx)); |
| log(" Path delay estimate: %.2f\n", float(ctx->estimateDelay(src_wire, dst_wire))); |
| } |
| |
| route(src_wires, dst_wire); |
| |
| if (visited.count(dst_wire) == 0) { |
| if (ctx->debug) |
| log("Failed to route %s -> %s.\n", ctx->getWireName(src_wire).c_str(ctx), |
| ctx->getWireName(dst_wire).c_str(ctx)); |
| else if (ripup) |
| log_info("Failed to route %s -> %s.\n", ctx->getWireName(src_wire).c_str(ctx), |
| ctx->getWireName(dst_wire).c_str(ctx)); |
| ripup_net(ctx, net_name); |
| failedDest = dst_wire; |
| return; |
| } |
| |
| if (ctx->debug) |
| log(" Final path delay: %.3f\n", ctx->getDelayNS(visited[dst_wire].delay)); |
| maxDelay = fmaxf(maxDelay, visited[dst_wire].delay); |
| |
| if (ctx->debug) |
| log(" Route (from destination to source):\n"); |
| |
| WireId cursor = dst_wire; |
| |
| while (1) { |
| if (ctx->debug) |
| log(" %8.3f %s\n", ctx->getDelayNS(visited[cursor].delay), ctx->getWireName(cursor).c_str(ctx)); |
| |
| if (src_wires.count(cursor)) |
| break; |
| |
| NetInfo *conflicting_wire_net = ctx->getConflictingWireNet(cursor); |
| |
| if (conflicting_wire_net != nullptr) { |
| NPNR_ASSERT(ripup); |
| NPNR_ASSERT(conflicting_wire_net->name != net_name); |
| |
| ctx->unbindWire(cursor); |
| if (!ctx->checkWireAvail(cursor)) |
| ripup_net(ctx, conflicting_wire_net->name); |
| |
| rippedNets.insert(conflicting_wire_net->name); |
| scores.wireScores[cursor]++; |
| scores.netWireScores[std::make_pair(net_name, cursor)]++; |
| scores.netWireScores[std::make_pair(conflicting_wire_net->name, cursor)]++; |
| } |
| |
| PipId pip = visited[cursor].pip; |
| NetInfo *conflicting_pip_net = ctx->getConflictingPipNet(pip); |
| |
| if (conflicting_pip_net != nullptr) { |
| NPNR_ASSERT(ripup); |
| NPNR_ASSERT(conflicting_pip_net->name != net_name); |
| |
| if (ctx->getBoundPipNet(pip) == conflicting_pip_net) |
| ctx->unbindPip(pip); |
| |
| if (!ctx->checkPipAvail(pip)) |
| ripup_net(ctx, conflicting_pip_net->name); |
| |
| rippedNets.insert(conflicting_pip_net->name); |
| scores.pipScores[visited[cursor].pip]++; |
| scores.netPipScores[std::make_pair(net_name, visited[cursor].pip)]++; |
| scores.netPipScores[std::make_pair(conflicting_pip_net->name, visited[cursor].pip)]++; |
| } |
| |
| ctx->bindPip(visited[cursor].pip, ctx->nets.at(net_name).get(), STRENGTH_WEAK); |
| src_wires[cursor] = visited[cursor].delay; |
| cursor = ctx->getPipSrcWire(visited[cursor].pip); |
| } |
| } |
| |
| routedOkay = true; |
| } |
| }; |
| |
| struct RouteJob |
| { |
| IdString net; |
| int user_idx = -1; |
| delay_t slack = 0; |
| int randtag = 0; |
| |
| struct Greater |
| { |
| bool operator()(const RouteJob &lhs, const RouteJob &rhs) const noexcept |
| { |
| return lhs.slack == rhs.slack ? lhs.randtag > rhs.randtag : lhs.slack > rhs.slack; |
| } |
| }; |
| }; |
| |
| void addFullNetRouteJob(Context *ctx, const Router1Cfg &cfg, IdString net_name, |
| std::unordered_map<IdString, std::vector<bool>> &cache, |
| std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> &queue) |
| { |
| NetInfo *net_info = ctx->nets.at(net_name).get(); |
| |
| if (net_info->driver.cell == nullptr) |
| return; |
| |
| auto src_wire = ctx->getNetinfoSourceWire(net_info); |
| |
| if (src_wire == WireId()) |
| log_error("No wire found for port %s on source cell %s.\n", net_info->driver.port.c_str(ctx), |
| net_info->driver.cell->name.c_str(ctx)); |
| |
| auto &net_cache = cache[net_name]; |
| |
| if (net_cache.empty()) |
| net_cache.resize(net_info->users.size()); |
| |
| RouteJob job; |
| job.net = net_name; |
| job.user_idx = -1; |
| job.slack = 0; |
| job.randtag = ctx->rng(); |
| |
| bool got_slack = false; |
| |
| for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) { |
| if (net_cache[user_idx]) |
| continue; |
| |
| auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]); |
| |
| if (dst_wire == WireId()) |
| log_error("No wire found for port %s on destination cell %s.\n", net_info->users[user_idx].port.c_str(ctx), |
| net_info->users[user_idx].cell->name.c_str(ctx)); |
| |
| if (user_idx == 0) |
| job.slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire); |
| else |
| job.slack = std::min(job.slack, net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire)); |
| |
| WireId cursor = dst_wire; |
| while (src_wire != cursor) { |
| auto it = net_info->wires.find(cursor); |
| if (it == net_info->wires.end()) { |
| if (!got_slack) |
| job.slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire); |
| else |
| job.slack = std::min(job.slack, |
| net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire)); |
| got_slack = true; |
| break; |
| } |
| NPNR_ASSERT(it->second.pip != PipId()); |
| cursor = ctx->getPipSrcWire(it->second.pip); |
| } |
| } |
| |
| queue.push(job); |
| |
| for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) |
| net_cache[user_idx] = true; |
| } |
| |
| void addNetRouteJobs(Context *ctx, const Router1Cfg &cfg, IdString net_name, |
| std::unordered_map<IdString, std::vector<bool>> &cache, |
| std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> &queue) |
| { |
| NetInfo *net_info = ctx->nets.at(net_name).get(); |
| |
| if (net_info->driver.cell == nullptr) |
| return; |
| |
| auto src_wire = ctx->getNetinfoSourceWire(net_info); |
| |
| if (src_wire == WireId()) |
| log_error("No wire found for port %s on source cell %s.\n", net_info->driver.port.c_str(ctx), |
| net_info->driver.cell->name.c_str(ctx)); |
| |
| auto &net_cache = cache[net_name]; |
| |
| if (net_cache.empty()) |
| net_cache.resize(net_info->users.size()); |
| |
| for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) { |
| if (net_cache[user_idx]) |
| continue; |
| |
| auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]); |
| |
| if (dst_wire == WireId()) |
| log_error("No wire found for port %s on destination cell %s.\n", net_info->users[user_idx].port.c_str(ctx), |
| net_info->users[user_idx].cell->name.c_str(ctx)); |
| |
| WireId cursor = dst_wire; |
| while (src_wire != cursor) { |
| auto it = net_info->wires.find(cursor); |
| if (it == net_info->wires.end()) { |
| RouteJob job; |
| job.net = net_name; |
| job.user_idx = user_idx; |
| job.slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire); |
| job.randtag = ctx->rng(); |
| queue.push(job); |
| net_cache[user_idx] = true; |
| break; |
| } |
| NPNR_ASSERT(it->second.pip != PipId()); |
| cursor = ctx->getPipSrcWire(it->second.pip); |
| } |
| } |
| } |
| |
| void cleanupReroute(Context *ctx, const Router1Cfg &cfg, RipupScoreboard &scores, |
| std::unordered_set<IdString> &cleanupQueue, |
| std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> &jobQueue, |
| int &totalVisitCnt, int &totalRevisitCnt, int &totalOvertimeRevisitCnt) |
| { |
| std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> cleanupJobs; |
| std::vector<NetInfo *> allNetinfos; |
| |
| for (auto net_name : cleanupQueue) { |
| NetInfo *net_info = ctx->nets.at(net_name).get(); |
| auto src_wire = ctx->getNetinfoSourceWire(net_info); |
| |
| if (ctx->verbose) |
| allNetinfos.push_back(net_info); |
| |
| std::unordered_map<WireId, int> useCounters; |
| std::vector<int> candidateArcs; |
| |
| for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) { |
| auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]); |
| |
| if (dst_wire == src_wire) |
| continue; |
| |
| auto cursor = dst_wire; |
| useCounters[cursor]++; |
| |
| while (cursor != src_wire) { |
| auto it = net_info->wires.find(cursor); |
| if (it == net_info->wires.end()) |
| break; |
| cursor = ctx->getPipSrcWire(it->second.pip); |
| useCounters[cursor]++; |
| } |
| |
| if (cursor != src_wire) |
| continue; |
| |
| candidateArcs.push_back(user_idx); |
| } |
| |
| for (int user_idx : candidateArcs) { |
| auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]); |
| |
| if (useCounters.at(dst_wire) != 1) |
| continue; |
| |
| RouteJob job; |
| job.net = net_name; |
| job.user_idx = user_idx; |
| job.slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire); |
| job.randtag = ctx->rng(); |
| cleanupJobs.push(job); |
| } |
| } |
| |
| log_info("running cleanup re-route of %d nets (%d arcs).\n", int(cleanupQueue.size()), int(cleanupJobs.size())); |
| |
| cleanupQueue.clear(); |
| |
| int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0; |
| int totalWireCountDelta = 0; |
| |
| if (ctx->verbose) { |
| for (auto it : allNetinfos) |
| totalWireCountDelta -= it->wires.size(); |
| } |
| |
| while (!cleanupJobs.empty()) { |
| RouteJob job = cleanupJobs.top(); |
| cleanupJobs.pop(); |
| |
| auto net_name = job.net; |
| auto user_idx = job.user_idx; |
| |
| NetInfo *net_info = ctx->nets.at(net_name).get(); |
| auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]); |
| |
| ctx->unbindWire(dst_wire); |
| |
| Router router(ctx, cfg, scores, net_name, user_idx, false, false); |
| |
| if (!router.routedOkay) |
| log_error("Failed to re-route arc %d of net %s.\n", user_idx, net_name.c_str(ctx)); |
| |
| visitCnt += router.visitCnt; |
| revisitCnt += router.revisitCnt; |
| overtimeRevisitCnt += router.overtimeRevisitCnt; |
| } |
| |
| if (ctx->verbose) { |
| for (auto it : allNetinfos) |
| totalWireCountDelta += it->wires.size(); |
| |
| log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime), %+d wires.\n", visitCnt, |
| (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt, totalWireCountDelta); |
| } |
| |
| totalVisitCnt += visitCnt; |
| totalRevisitCnt += revisitCnt; |
| totalOvertimeRevisitCnt += overtimeRevisitCnt; |
| } |
| |
| } // namespace |
| |
| NEXTPNR_NAMESPACE_BEGIN |
| |
| Router1Cfg::Router1Cfg(Context *ctx) : Settings(ctx) |
| { |
| maxIterCnt = get<int>("router1/maxIterCnt", 200); |
| cleanupReroute = get<bool>("router1/cleanupReroute", true); |
| fullCleanupReroute = get<bool>("router1/fullCleanupReroute", true); |
| useEstimate = get<bool>("router1/useEstimate", true); |
| } |
| |
| bool router1(Context *ctx, const Router1Cfg &cfg) |
| { |
| try { |
| int totalVisitCnt = 0, totalRevisitCnt = 0, totalOvertimeRevisitCnt = 0; |
| delay_t ripup_penalty = ctx->getRipupDelayPenalty(); |
| RipupScoreboard scores; |
| |
| log_break(); |
| log_info("Routing..\n"); |
| ctx->lock(); |
| |
| std::unordered_set<IdString> cleanupQueue; |
| std::unordered_map<IdString, std::vector<bool>> jobCache; |
| std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> jobQueue; |
| |
| for (auto &net_it : ctx->nets) |
| addNetRouteJobs(ctx, cfg, net_it.first, jobCache, jobQueue); |
| |
| if (jobQueue.empty()) { |
| log_info("found no unrouted source-sink pairs. no routing necessary.\n"); |
| ctx->unlock(); |
| return true; |
| } |
| |
| log_info("found %d unrouted source-sink pairs. starting routing procedure.\n", int(jobQueue.size())); |
| |
| int iterCnt = 0; |
| |
| while (!jobQueue.empty()) { |
| if (iterCnt == cfg.maxIterCnt) { |
| log_warning("giving up after %d iterations.\n", iterCnt); |
| log_info("Checksum: 0x%08x\n", ctx->checksum()); |
| #ifndef NDEBUG |
| ctx->check(); |
| #endif |
| ctx->unlock(); |
| return false; |
| } |
| |
| iterCnt++; |
| if (ctx->verbose) |
| log_info("-- %d --\n", iterCnt); |
| |
| int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0, jobCnt = 0, failedCnt = 0; |
| |
| std::unordered_set<IdString> normalRouteNets, ripupQueue; |
| |
| if (ctx->verbose || iterCnt == 1) |
| log_info("routing queue contains %d jobs.\n", int(jobQueue.size())); |
| else if (ctx->slack_redist_iter > 0 && iterCnt % ctx->slack_redist_iter == 0) |
| assign_budget(ctx, true /* quiet */); |
| |
| bool printNets = ctx->verbose && (jobQueue.size() < 10); |
| |
| while (!jobQueue.empty()) { |
| if (ctx->debug) |
| log("Next job slack: %f\n", double(jobQueue.top().slack)); |
| |
| auto net_name = jobQueue.top().net; |
| auto user_idx = jobQueue.top().user_idx; |
| jobQueue.pop(); |
| |
| if (cfg.fullCleanupReroute) |
| cleanupQueue.insert(net_name); |
| |
| if (printNets) { |
| if (user_idx < 0) |
| log_info(" routing all %d users of net %s\n", int(ctx->nets.at(net_name)->users.size()), |
| net_name.c_str(ctx)); |
| else |
| log_info(" routing user %d of net %s\n", user_idx, net_name.c_str(ctx)); |
| } |
| |
| Router router(ctx, cfg, scores, net_name, user_idx, false, false); |
| |
| jobCnt++; |
| visitCnt += router.visitCnt; |
| revisitCnt += router.revisitCnt; |
| overtimeRevisitCnt += router.overtimeRevisitCnt; |
| |
| if (!router.routedOkay) { |
| if (printNets) |
| log_info(" failed to route to %s.\n", ctx->getWireName(router.failedDest).c_str(ctx)); |
| ripupQueue.insert(net_name); |
| failedCnt++; |
| } else { |
| normalRouteNets.insert(net_name); |
| } |
| |
| if ((ctx->verbose || iterCnt == 1) && !printNets && (jobCnt % 100 == 0)) { |
| log_info(" processed %d jobs. (%d routed, %d failed)\n", jobCnt, jobCnt - failedCnt, failedCnt); |
| ctx->yield(); |
| } |
| } |
| |
| NPNR_ASSERT(jobQueue.empty()); |
| jobCache.clear(); |
| |
| if ((ctx->verbose || iterCnt == 1) && (jobCnt % 100 != 0)) { |
| log_info(" processed %d jobs. (%d routed, %d failed)\n", jobCnt, jobCnt - failedCnt, failedCnt); |
| ctx->yield(); |
| } |
| |
| if (ctx->verbose) |
| 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) |
| 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; |
| overtimeRevisitCnt = 0; |
| int netCnt = 0; |
| int ripCnt = 0; |
| |
| std::vector<IdString> ripupArray(ripupQueue.begin(), ripupQueue.end()); |
| ctx->sorted_shuffle(ripupArray); |
| |
| for (auto net_name : ripupArray) { |
| if (cfg.cleanupReroute) |
| cleanupQueue.insert(net_name); |
| |
| 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, cfg, scores, net_name, -1, false, true, ripup_penalty); |
| |
| netCnt++; |
| visitCnt += router.visitCnt; |
| revisitCnt += router.revisitCnt; |
| overtimeRevisitCnt += router.overtimeRevisitCnt; |
| |
| if (!router.routedOkay) |
| log_error("Net %s is impossible to route.\n", net_name.c_str(ctx)); |
| |
| for (auto it : router.rippedNets) { |
| addFullNetRouteJob(ctx, cfg, it, jobCache, jobQueue); |
| if (cfg.cleanupReroute) |
| cleanupQueue.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())); |
| } |
| } |
| |
| ripCnt += router.rippedNets.size(); |
| |
| if ((ctx->verbose || iterCnt == 1) && !printNets && (netCnt % 100 == 0)) { |
| log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt); |
| ctx->yield(); |
| } |
| } |
| |
| if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0)) |
| log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt); |
| |
| if (ctx->verbose) |
| log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", visitCnt, |
| (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt); |
| |
| if (ctx->verbose && !jobQueue.empty()) |
| log_info(" ripped up %d previously routed nets. continue routing.\n", int(jobQueue.size())); |
| } |
| |
| if (!ctx->verbose) |
| log_info("iteration %d: routed %d nets without ripup, routed %d nets with ripup.\n", iterCnt, |
| int(normalRouteNets.size()), int(ripupQueue.size())); |
| |
| totalVisitCnt += visitCnt; |
| totalRevisitCnt += revisitCnt; |
| totalOvertimeRevisitCnt += overtimeRevisitCnt; |
| |
| if (iterCnt == 8 || iterCnt == 16 || iterCnt == 32 || iterCnt == 64 || iterCnt == 128) |
| ripup_penalty += ctx->getRipupDelayPenalty(); |
| |
| if (jobQueue.empty() || (iterCnt % 5) == 0 || (cfg.fullCleanupReroute && iterCnt == 1)) |
| cleanupReroute(ctx, cfg, scores, cleanupQueue, jobQueue, totalVisitCnt, totalRevisitCnt, |
| totalOvertimeRevisitCnt); |
| |
| ctx->yield(); |
| } |
| |
| log_info("routing complete after %d iterations.\n", iterCnt); |
| |
| log_info("visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", totalVisitCnt, |
| (100.0 * totalRevisitCnt) / totalVisitCnt, (100.0 * totalOvertimeRevisitCnt) / totalVisitCnt); |
| |
| { |
| float tns = 0; |
| int tns_net_count = 0; |
| int tns_arc_count = 0; |
| for (auto &net_it : ctx->nets) { |
| bool got_negative_slack = false; |
| NetInfo *net_info = ctx->nets.at(net_it.first).get(); |
| for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) { |
| delay_t arc_delay = ctx->getNetinfoRouteDelay(net_info, net_info->users[user_idx]); |
| delay_t arc_budget = net_info->users[user_idx].budget; |
| delay_t arc_slack = arc_budget - arc_delay; |
| if (arc_slack < 0) { |
| if (!got_negative_slack) { |
| if (ctx->verbose) |
| log_info("net %s has negative slack arcs:\n", net_info->name.c_str(ctx)); |
| tns_net_count++; |
| } |
| if (ctx->verbose) |
| log_info(" arc %s -> %s has %f ns slack (delay %f, budget %f)\n", |
| ctx->getWireName(ctx->getNetinfoSourceWire(net_info)).c_str(ctx), |
| ctx->getWireName(ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx])) |
| .c_str(ctx), |
| ctx->getDelayNS(arc_slack), ctx->getDelayNS(arc_delay), |
| ctx->getDelayNS(arc_budget)); |
| tns += ctx->getDelayNS(arc_slack); |
| tns_arc_count++; |
| } |
| } |
| } |
| log_info("final tns with respect to arc budgets: %f ns (%d nets, %d arcs)\n", tns, tns_net_count, |
| tns_arc_count); |
| } |
| |
| NPNR_ASSERT(jobQueue.empty()); |
| jobCache.clear(); |
| |
| for (auto &net_it : ctx->nets) |
| addNetRouteJobs(ctx, cfg, net_it.first, jobCache, jobQueue); |
| |
| #ifndef NDEBUG |
| if (!jobQueue.empty()) { |
| log_info("Design strangely still contains unrouted source-sink pairs:\n"); |
| while (!jobQueue.empty()) { |
| log_info(" user %d on net %s.\n", jobQueue.top().user_idx, jobQueue.top().net.c_str(ctx)); |
| jobQueue.pop(); |
| } |
| log_info("Checksum: 0x%08x\n", ctx->checksum()); |
| ctx->check(); |
| ctx->unlock(); |
| return false; |
| } |
| #endif |
| |
| log_info("Checksum: 0x%08x\n", ctx->checksum()); |
| #ifndef NDEBUG |
| ctx->check(); |
| #endif |
| timing_analysis(ctx, true /* slack_histogram */, true /* print_path */); |
| ctx->unlock(); |
| return true; |
| } catch (log_execution_error_exception) { |
| #ifndef NDEBUG |
| ctx->check(); |
| #endif |
| ctx->unlock(); |
| return false; |
| } |
| } |
| |
| bool Context::getActualRouteDelay(WireId src_wire, WireId dst_wire, delay_t *delay, |
| std::unordered_map<WireId, PipId> *route, bool useEstimate) |
| { |
| RipupScoreboard scores; |
| Router1Cfg cfg(this); |
| cfg.useEstimate = useEstimate; |
| |
| Router router(this, cfg, scores, src_wire, dst_wire); |
| |
| if (!router.routedOkay) |
| return false; |
| |
| if (delay != nullptr) |
| *delay = router.visited.at(dst_wire).delay; |
| |
| if (route != nullptr) { |
| WireId cursor = dst_wire; |
| while (1) { |
| PipId pip = router.visited.at(cursor).pip; |
| (*route)[cursor] = pip; |
| if (pip == PipId()) |
| break; |
| cursor = getPipSrcWire(pip); |
| } |
| } |
| |
| return true; |
| } |
| |
| NEXTPNR_NAMESPACE_END |
