-
Notifications
You must be signed in to change notification settings - Fork 415
Router lookahead inefficiency for large blocks #1580
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Comments
@litghost @acomodi @tangxifan FYI. |
Hi @vaughnbetz ,
It seems that @acomodi has patched the issue as you said. Currently, the sink coordinate to be used in calculating the Something we can try is to elaborate the
Looking forward to your reply. |
Thanks Xifan.
|
I agree with your plan (reproduced below), but fixed a typo: |
@vaughnbetz Thanks for the insights.
vtr-verilog-to-routing/vpr/src/route/rr_graph.cpp Line 1437 in 574525c
You can see (xlow, ylow) is the left-bottom point of a grid, while (xhigh, yhigh) is the top-right point of a grid.
Given the facts, I can focus on optimizing the coordinate adjustment in router lookahead map. There is no need to change the rr_graph builder. |
Thanks @tangxifan. I agree. |
@vaughnbetz I have started the code implementation. But I have realized a serious problem: Therefore, I would like to learn any solution that can build the fan_in edges quickly. I have two solutions in my mind:
|
So one memory efficient way to do this is change how vtr-verilog-to-routing/vpr/src/route/rr_graph_storage.cpp Lines 406 to 413 in ce725b0
When you do this kind of sorting, you need to put it back once you are done. Basically the process would look something like:
This operation is potentially CPU heavy, but won't increase the memory footprint. |
Could we do this operation once (at rr_graph build or load time) by walking through an on-demand created fanin edge list (routines to create it exist), and updating the location of a SINK to be the average of the fan-in IPINs? Then this computation moves out of the CPU- and memory-critical router routines. I think it achieves the same results as computing the average of the pin locations during route time; we just pre-compute and store it as the SINK locations. |
Sending this to @nedsels for consideration -- a bunch of this is brainstorming on large block sink locations for the router lookahead which should be relevant to the fix up you're contemplating. |
Tagging @AlexandreSinger and @amin1377 as they may also be interested. |
Currently the router lookahead takes two things:
For large blocks, VPR's rr-graph builder sets the (x,y) of all SINK nodes to the lower-left corner of the block. This may be far from the actual pins we're trying to get to, making the router slower and less effective.
Expected Behaviour
Router should route these connections efficiently.
Current Behaviour
Titan results suggest this is hurting us on large blocks; logically equivalent pins on those blocks don't help us as much as expected and we get some circuitous routes to large blocks both with and without logical equivalence.
Possible Solution
I think the cleanest solution would be for the rr-graph builder to assign a smarter (x,y) for SINKs in large blocks. It could be the average (x,y) of the IPINs that can reach that SINK, or the (x,y) of a randomly chosen IPIN that reaches the SINK.
The text was updated successfully, but these errors were encountered: