Work "overtime" to find better solutions in routing search algorithm

Signed-off-by: Clifford Wolf <clifford@clifford.at>

1 files changed, 23 insertions, 9 deletions

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<IdString> rippedNets;
     std::unordered_map<WireId, QueuedWire> 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<IdString> 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 "