Hacker News Reader

Comment by xiphias2 | Hacker News Reader

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

View on HN

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.

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?

As if the algorithms behind numerical methods weren't hard enough, now we have to add parallelism :)

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.

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.

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

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.

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.

Reply on news.ycombinator.com