Describe the bug
To reproduce the bug, run the parallel version of AceRoute on case mlcad, where the bounding box enlargement is automatically enabled, and you need to manually keep using the bidirectional search (in src/aceroute-par.cc:route_connections_batch, uncomment the line // use_ba = true).
Analyze the causes
Using gdb to backtrace, you will find when restoring the connection path by recursively querying node->prev, the path leads to incorrect source INT node, which makes the assertion fail. I print the connections_routed attribute of each rnodes in the path and find the value changed halfway, which is impossible in the sequential version since the algorithm guarantees that the path is formed in a single A* search between a connection source INT and sink INT.
Consequently, I assume the root cause is that the search paths of multiple threads may adjoint, leading to the prev node of some node is altered again after recording an established path. Current partition paradigm in the parallel mode may not be able to cover the ever-enlarging bounding boxes of each connection to route, which causes the conflict. The bidirectional search is also more conflict-prune than the single-directional search.
Describe the bug
To reproduce the bug, run the parallel version of AceRoute on case
mlcad, where the bounding box enlargement is automatically enabled, and you need to manually keep using the bidirectional search (insrc/aceroute-par.cc:route_connections_batch, uncomment the line// use_ba = true).Analyze the causes
Using gdb to backtrace, you will find when restoring the connection path by recursively querying
node->prev, the path leads to incorrect source INT node, which makes the assertion fail. I print theconnections_routedattribute of each rnodes in the path and find the value changed halfway, which is impossible in the sequential version since the algorithm guarantees that the path is formed in a single A* search between a connection source INT and sink INT.Consequently, I assume the root cause is that the search paths of multiple threads may adjoint, leading to the prev node of some node is altered again after recording an established path. Current partition paradigm in the parallel mode may not be able to cover the ever-enlarging bounding boxes of each connection to route, which causes the conflict. The bidirectional search is also more conflict-prune than the single-directional search.