verilog-to-routing / vtr-verilog-to-routing

Verilog to Routing -- Open Source CAD Flow for FPGA Research
https://verilogtorouting.org
Other
979 stars 378 forks source link

[Route] Added astar_offset Parameter #2601

Open AlexandreSinger opened 3 weeks ago

AlexandreSinger commented 3 weeks ago

Using an astar_offset can help better tune the ordering heuristic for the search used to find the shortest path in the routing graph. It is also necessary to ensure that the heuristic is an underestimate (without setting the astar_fac to 0.0).

vaughnbetz commented 2 weeks ago

Should also do a QoR check to compare router runtimes and make sure there isn't a noticeable increase.

AlexandreSinger commented 2 weeks ago

@vaughnbetz FYI, this was the section I was concerned about regarding the RCV path manager:

image

The issue I see here is that the astar_fac is used to scale the raw delay and congestion costs independently (not the weighted sum as its done in the default router). I am not sure the affects this may have on the results but it may cause more critical nets to be biased toward / away from congestion / delay way more than intended.

For this PR I just followed the example and offset at the same point; but I wonder how this may affect RCV's results.

vaughnbetz commented 2 weeks ago

For RCV we need to keep the delay separate from congestion for longer, as we're not targeting min delay anymore but a delay window instead. RCV also won't work unless A fac is essentially 1 on the delay part; to hit a delay window you need to estimate pretty precisely, rather than overestimating to get a directed search. To make the search more directed I think we'd need to add an additional cost outside the delay window computation that was something like (Afac-1)remaining delay to make the search more directed. Or perhaps the resource cost being multiplied by Afac would be enough to drive toward the target.

I think we should avoid manipulating the delay part of the cost with RCV at all (no multiply by A*fac, no offset, etc.).