From e91241f10d68fcaaf0a81fa77e9a91666120ccee Mon Sep 17 00:00:00 2001
From: Clifford Wolf <clifford@clifford.at>
Date: Tue, 4 Sep 2018 17:55:43 +0200
Subject: Dispose of far too long routes earlier (use 3x est. delay as limit)

Signed-off-by: Clifford Wolf <clifford@clifford.at>
---
 common/router1.cc | 33 +++++++++++++++++++++------------
 1 file changed, 21 insertions(+), 12 deletions(-)

diff --git a/common/router1.cc b/common/router1.cc
index 5cd4414c..e47a9ae3 100644
--- a/common/router1.cc
+++ b/common/router1.cc
@@ -53,14 +53,15 @@ struct QueuedWire
     WireId wire;
     PipId pip;
 
-    delay_t delay = 0, togo = 0;
+    delay_t delay = 0, penalty = 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;
+            delay_t l = lhs.delay + lhs.penalty + lhs.togo;
+            delay_t r = rhs.delay + rhs.penalty + rhs.togo;
             return l == r ? lhs.randtag > rhs.randtag : l > r;
         }
     };
@@ -119,7 +120,7 @@ struct Router
     delay_t maxDelay = 0.0;
     WireId failedDest;
 
-    void route(const std::unordered_map<WireId, delay_t> &src_wires, WireId dst_wire)
+    void route(const std::unordered_map<WireId, delay_t> &src_wires, WireId dst_wire, delay_t max_delay)
     {
         std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> queue;
 
@@ -129,7 +130,8 @@ struct Router
             QueuedWire qw;
             qw.wire = it.first;
             qw.pip = PipId();
-            qw.delay = it.second - (it.second / 16);
+            qw.delay = it.second;
+            qw.penalty = -(it.second / 16);
             if (cfg.useEstimate)
                 qw.togo = ctx->estimateDelay(qw.wire, dst_wire);
             qw.randtag = ctx->rng();
@@ -150,12 +152,16 @@ struct Router
 
             for (auto pip : ctx->getPipsDownhill(qw.wire)) {
                 delay_t next_delay = qw.delay + ctx->getPipDelay(pip).maxDelay();
+                delay_t next_penalty = qw.penalty;
                 WireId next_wire = ctx->getPipDstWire(pip);
                 bool foundRipupNet = false;
                 thisVisitCnt++;
 
                 next_delay += ctx->getWireDelay(next_wire).maxDelay();
 
+                if (max_delay > 0 && next_delay > max_delay)
+                    continue;
+
                 if (!ctx->checkWireAvail(next_wire)) {
                     if (!ripup)
                         continue;
@@ -165,11 +171,11 @@ struct Router
 
                     auto it1 = scores.wireScores.find(next_wire);
                     if (it1 != scores.wireScores.end())
-                        next_delay += (it1->second * ripup_penalty) / 8;
+                        next_penalty += (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;
+                        next_penalty += it2->second * ripup_penalty;
 
                     foundRipupNet = true;
                 }
@@ -183,22 +189,23 @@ struct Router
 
                     auto it1 = scores.pipScores.find(pip);
                     if (it1 != scores.pipScores.end())
-                        next_delay += (it1->second * ripup_penalty) / 8;
+                        next_penalty += (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;
+                        next_penalty += it2->second * ripup_penalty;
 
                     foundRipupNet = true;
                 }
 
                 if (foundRipupNet)
-                    next_delay += ripup_penalty;
+                    next_penalty += ripup_penalty;
 
                 NPNR_ASSERT(next_delay >= 0);
+                NPNR_ASSERT(next_delay + next_penalty >= 0);
 
                 if (visited.count(next_wire)) {
-                    if (visited.at(next_wire).delay <= next_delay + ctx->getDelayEpsilon())
+                    if (visited.at(next_wire).delay + visited.at(next_wire).penalty <= next_delay + next_penalty + ctx->getDelayEpsilon())
                         continue;
 #if 0 // FIXME
                     if (ctx->debug)
@@ -217,6 +224,7 @@ struct Router
                 next_qw.wire = next_wire;
                 next_qw.pip = pip;
                 next_qw.delay = next_delay;
+                next_qw.penalty = next_penalty;
                 if (cfg.useEstimate)
                     next_qw.togo = ctx->estimateDelay(next_wire, dst_wire);
                 next_qw.randtag = ctx->rng();
@@ -235,7 +243,7 @@ struct Router
     {
         std::unordered_map<WireId, delay_t> src_wires;
         src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay();
-        route(src_wires, dst_wire);
+        route(src_wires, dst_wire, 0);
         routedOkay = visited.count(dst_wire);
 
         if (ctx->debug) {
@@ -369,7 +377,8 @@ struct Router
                 log("    Path delay estimate: %.2f\n", float(ctx->estimateDelay(src_wire, dst_wire)));
             }
 
-            route(src_wires, dst_wire);
+            delay_t max_delay = 3 * ctx->estimateDelay(src_wire, dst_wire);
+            route(src_wires, dst_wire, max_delay);
 
             if (visited.count(dst_wire) == 0) {
                 if (ctx->debug)
-- 
cgit v1.2.3