[Routing] Incremental Slack Timing Analysis Does Not Match When Computed From Scratch

[AlexandreSinger]

While working on the Analytical Placer, I generated a very basic clustering and cluster placement. The quality of both of these was meant to be low as this is mainly just a PoC flow through VPR. These tests go through routing without an issue; however, for one test they fail.

When the assert level is set to 4, there is a debug check which verifies that the incremental slack timing analysis gets the same answer as one computed from scratch:

vtr-verilog-to-routing/vpr/src/timing/slack_evaluation.cpp

Lines 286 to 288 in 3e53a93

	VTR_ASSERT_DEBUG_MSG(verify_max_req_worst_slack(timing_graph, analyzer), "Calculated max required times and worst slacks should match those computed from scratch");

I have found on my testcase, this check gets tripped.

VTR was built with the following command:

make -j12 CMAKE_PARAMS="-DWITH_ODIN=off -DVTR_ASSERT_LEVEL=4"

Note: The assert level being 4 is important.

The testcase circuits and a testing script can be found in this tar file:
timing_bug.tar.gz

It contains a bash script with the command I used to run VPR:

VTR_DIR=~/vtr-verilog-to-routing                                                                                                                                                                            
                                                                                                                                                                                                            
$VTR_DIR/vpr/vpr \                                                                                                                                                                                          
    fixed_k6_frac_N8_22nm.xml \                                                                                                                                                                             
    ch_intrinsics \                                                                                                                                                                                         
    --circuit_file ch_intrinsics.pre-vpr.blif \                                                                                                                                                             
    --net_file ch_intrinsics.net \                                                                                                                                                                          
    --place_file ch_intrinsics.place \                                                                                                                                                                      
    --route \                                                                                                                                                                                               
    --device unnamed_device \                                                                                                                                                                               
    --read_vpr_constraints ch_intrinsics_fixed_io.xml \                                                                                                                                                     
    --min_route_chan_width_hint 40

The output looks like as follows:

This is the second routing attempt after routing at a channel width of 40.

Interestingly, if you do not provide the min chan width hint of --min_route_chan_width_hint 40 this does not happen.

[AlexandreSinger]

Refer to PR #2752 for more context.

[AlexandreSinger]

This issue is now appearing in Master. Needs to be investigated soon.
https://github.com/verilog-to-routing/vtr-verilog-to-routing/actions/runs/11301269116/job/31435439924

[AlexandreSinger]

@vaughnbetz I found the problem. It is not a precision issue it is a bit more nuanced than that. Investigating the code, we actually want the floating point values to be exactly equal in this case since the slack is not being recomputed, but is instead finding the min of, which does necessarily need to be equal.

The issue is that the incremental timing analysis is not stably deterministic. When there is a tie for the lowest slack, the first node checked by the analysis is used. If the order in which you check the nodes is different you will get a different worst slack node (but the same worst slack). This is why the errors always say that the "Calculated worst slack nodes does not match", but the worst slack always does match.

To fix the issue, in the incremental and recompute slack functions, I added a tie-breaking condition which would prefer the node with the lower ID in the case of a tie for minimum slack (similar to what we did for the parallel router). This also should be fixed for the required times as well as the slack since they are computed in the same way. What do you think about this change?

[vaughnbetz]

As we discussed in the hall, I think we can simply stop checking which nodes are returned, and instead just check that the worst case slacks are equal. This case occurs when we have multiple critical paths, and it isn't really a problem; we base all optimization decisions on slack, not which node is the most critical in the whole circuit.

[rs-dhow]

Your decision here is fine, but I would point out that this is a case of some related issues I've seen in EDA since Actel in the 80s. Namely, (i) it's best if comparisons are complete: if two objects do not refer to the same memory region, they cannot be equal (your ID tie-breaker achieves this); (ii) sorts should be stable; (iii) enumeration order should never depend on memory addresses (nothing should depend on memory addresses). FWIW YMMV etc. Enjoy.