Speeding up CPython

Posted Dec 17, 2020 22:03 UTC (Thu) by NYKevin (subscriber, #129325)
In reply to: Speeding up CPython by jayalane
Parent article: Speeding up CPython

It heavily depends on the problem you are trying to solve. If you want to do something embarrassingly parallel, then Amdahl's law basically says you can use all of the cores at 100%, just as you might naively expect. If you are trying to do something with a significant non-parallelizable component (e.g. the Bellman-Ford algorithm), you will likely find it difficult* to even write a highly parallel implementation, and performance will suffer.

* 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. The clearest result I could find seems to say that the serial component is at least O(|V|) in time complexity, but I'm having a hard time following the synchronization primitives which it describes, so I might be misinterpreting something. But it's definitely not an embarrassingly parallel algorithm.

Speeding up CPython

Posted Dec 18, 2020 1:26 UTC (Fri) by excors (subscriber, #95769) [Link]

> 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).

Speeding up CPython

Posted Dec 24, 2020 15:55 UTC (Thu) by ejr (subscriber, #51652) [Link]

For people who have done this and published, see:
V. T. Chakaravarthy, F. Checconi, F. Petrini and Y. Sabharwal, "Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems," 2014 IEEE 28th International Parallel and Distributed Processing Symposium, Phoenix, AZ, 2014, pp. 889-901, doi: 10.1109/IPDPS.2014.96.

A search through Google Scholar or something similar likely will turn up an open copy.