4 ms·

,,Hardware changes with the times, but best-in-class algorithms are eternal'' Nowdays for these kind of problems the really interesting solution is the best pa

,,Hardware changes with the times, but best-in-class algorithms are eternal'' Nowdays for these kind of problems the really interesting solution is the best parallel solution. It may be elegant to still prove things for turing machines, but a GPU has 2000 running threads (and if the tensor cores could be used, it's even more instructions), so an algorithm implementation that's not using it is about 100x inferior in practice.

wongarsu 8y ago
Also traditionally steps of computations are counted for finding the best algorithm, but today the bottleneck for many problems is memory bandwidth. An algorithm that used to be best-in-class can become quite bad by just changing the ratio of CPU speed to memory speed.
- learc83 8y ago
  Writing game logic, I run into this all the time. Many classic algorithms were written when data locality wasn't nearly as big an issue. It's not just specific algorithms, but entire methods of problem solving. Graph traversal is so incredibly slow because of data locality.
bigred100 8y ago
I saw Jack Dongarra say that plain parallelism is now old and the thing is “communication avoidance”. Also made the point (relevant to your quotation) that changing hardware means redoing the algorithms every ten years to exploit it.
- xiphias2 8y ago
  That's a great model that even helps running algorithms on FPGAs. Are there researchers working on finding the theoritical communicication limits of classical numerical problems?
- 4thaccount 8y ago
  As if the algorithms behind numerical methods weren't hard enough, now we have to add parallelism :)
svat 8y ago
But 100x is just a constant factor. What bearing does it have on the asymptotic complexity of the algorithm? (Or to put it differently: It may very well work in practice, but how does it work in theory?)
- xiphias2 8y ago
  If you want to go even further into the details (caching/RAM/Swap), you really get closer to the fact that the communication density between computations is what really matters, and n steps in the Turing machine runs in n*log(n) time in reality.
  - xiphias2 8y ago
    Just a correction: the Random Access Machine needs n*log(n) time, the Turing machine doesn't, as bandwidth is not a problem for the caching layers for sigle threaded execution, just the random access latency.

wongarsu 8y ago

Also traditionally steps of computations are counted for finding the best algorithm, but today the bottleneck for many problems is memory bandwidth. An algorithm that used to be best-in-class can become quite bad by just changing the ratio of CPU speed to memory speed.

learc83 8y ago
Writing game logic, I run into this all the time. Many classic algorithms were written when data locality wasn't nearly as big an issue. It's not just specific algorithms, but entire methods of problem solving. Graph traversal is so incredibly slow because of data locality.

bigred100 8y ago

I saw Jack Dongarra say that plain parallelism is now old and the thing is “communication avoidance”. Also made the point (relevant to your quotation) that changing hardware means redoing the algorithms every ten years to exploit it.

xiphias2 8y ago
That's a great model that even helps running algorithms on FPGAs. Are there researchers working on finding the theoritical communicication limits of classical numerical problems?
4thaccount 8y ago
As if the algorithms behind numerical methods weren't hard enough, now we have to add parallelism :)

svat 8y ago

But 100x is just a constant factor. What bearing does it have on the asymptotic complexity of the algorithm? (Or to put it differently: It may very well work in practice, but how does it work in theory?)

xiphias2 8y ago
If you want to go even further into the details (caching/RAM/Swap), you really get closer to the fact that the communication density between computations is what really matters, and n steps in the Turing machine runs in n*log(n) time in reality.
- xiphias2 8y ago
  Just a correction: the Random Access Machine needs n*log(n) time, the Turing machine doesn't, as bandwidth is not a problem for the caching layers for sigle threaded execution, just the random access latency.