Speeding up CPython

Posted Dec 18, 2020 1:26 UTC (Fri) by excors (subscriber, #95769)
In reply to: Speeding up CPython by NYKevin
Parent article: Speeding up CPython

> It is not impossible to write a parallel implementation of Bellman-Ford, as Google will happily tell you. But I've looked at several of the results, and I still only have a very rough idea of what the resulting algorithm would look like or how it would perform.

I guess it may look like the BGP routing protocol, since that's basically parallel Bellman-Ford. Each processor (i.e. router) is responsible for a single vertex and its associated edges, and the 'relax' step runs in parallel across all the processors. But instead of relaxing in lock-step |V| times, they all relax asynchronously and repeatedly and never explicitly stop, which makes it trickier to calculate bounds on convergence time.

Unfortunately BGP doesn't guarantee it will ever converge, because its metric is much more complex than just shortest-paths, and it can (and sometimes does) oscillate forever. If you simplify it enough to guarantee convergence, apparently it can still require O(|V|!) messages across the network before converging (https://dl.acm.org/doi/pdf/10.1145/347059.347428).