The-OpenROAD-Project
Skip known bad vertices in power recovery
In power recovery, vertices that have already been tried and rejected can be tried again if they happen to be on another path we look at. Usually, the result is the same – we reject the vertex. Not only is this work unnecessary, it also prevents us from trying another (possibly better) vertex later in the path. Some stats on vertices that are tried in #4982:
| Vertex | Total tries | Better | Worse |
|---|---|---|---|
max_length492/Y |
1325 | 1 | 1324 |
load_slew487/Y |
130 | 1 | 129 |
load_slew465/Y |
309 | 1 | 308 |
load_slew447/Y |
231 | 1 | 230 |
load_slew409/Y |
49 | 0 | 49 |
load_slew400/Y |
294 | 2 | 292 |
load_slew375/Y |
262 | 1 | 261 |
load_slew57/Y |
240 | 0 | 240 |
load_slew407/Y |
124 | 0 | 124 |
fdct_zigzag.dct_mod.dct_block_0.dct_unit_0.ddin\[7\]$_DFFE_PN0P_/QN |
141 | 0 | 141 |
max_length63/Y |
63 | 1 | 62 |
_085272_/Y |
481 | 0 | 481 |
load_slew402/Y |
56 | 1 | 55 |
_083048_/Y |
2 | 1 | 1 |
wire301/Y |
26 | 1 | 25 |
load_slew62/Y |
4 | 2 | 2 |
load_slew446/Y |
12 | 2 | 10 |
_078958_/Y |
3 | 0 | 3 |
load_slew399/Y |
2 | 1 | 1 |
load_slew486/Y |
14 | 1 | 13 |
load_slew462/Y |
27 | 2 | 25 |
load_slew461/Y |
8 | 1 | 7 |
_118922_/Y |
2 | 0 | 2 |
_122581_/CON |
3 | 0 | 3 |
load_slew177/Y |
3 | 0 | 3 |
In the worst case, one vertex is visited 1325 times, 1324 of which result in worse worst slack. That's also about a quarter of all attempts.
This patch makes it so we don't revisit the vertices that were already rejected.
In the example in #4982, this speeds up GRT from ~1.5h to around 6 minutes, so we're looking at ~15x the performance on that particular design.
Also, the actual power recovery seems overall more effective (not sure how to weigh these values against each other).
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}
bad_vertices_ needs to be cleared at the end of recoverPower so it doesn't persist between calls.
I tested the current recover power designs and they look fine. It just need the clear mentioned above to be ready to merge.