Hacker News Reader

Comment by AnthonyMouse | Hacker News Reader

The alternative is speculative execution. If you can guess what the result is going to be, you can proceed to the next calculation and you get there faster if it turns out you were right.

If you have parallel processors, you can stop guessing and just proceed under both assumptions concurrently and throw out the result that was wrong when you find out which one it was. This is going to be less efficient, but if your only concern is "make latency go down," it can beat waiting for the result or guessing wrong.

View on HN

Not necessarily. There are problems you can't speed up even if you are given a literal infinity of processors - the problems in EXP for example (well, EXP - NP). Even for NP problems, the number of processors you need for a meaningful speed up grows proportionally to the size of the problem (assuming P!=NP).

Computational complexity and parallelism are orthogonal. Many EXP algorithms are embarrassingly parallel. You still have to do 2^n calculations, but if you have 1000 processors then it will take 1000 times less wall clock time because you're doing 1000 calculations at once.

The reason parallelism doesn't "solve" EXP problems is that parallelism grows linearly against something whose time complexity grows exponentially. It's not that it doesn't work at all, it's that if you want to solve the problem for 2n in the same time as for n, you need to double the number of processors. So the number of processors you need to solve the problem in whatever you define as a reasonable amount of time grows exponentially with n, but having e.g. 2^n processors when n is 1000 is Not Gonna Happen.

Having 1000 processors will still solve the problem twice as fast as 500, but that's not much help in practice when it's the difference between 50 billion billion years and 100.

But what if the processor may be made organic, or encoded in DNA, so that replication and protein synthesis is akin to solving the problem? The "computer" grows exponentially, rather than linearly, and so for larger problems, it grows to the size that solves the problem?

Or we end up with grey goo...

Are there any examples of reusable "computers" like this? I've seen some demonstrations but they are not generic to the problem and reusable, they seem to have the data encoded in the makeup of the "computer" itself.

I write computers in quotation marks because even if they solve computational problems they are so different from what we are calling computers today, eg: mold growing in a maze and similar.

None that are usable i'm sure - it's merely a theoretical idea.

A problem that is not in NP is, by definition, a problem that can't be solved in polynomial time even with an infinity of processors (or equivalently, with speculative execution given a perfect oracle). So, it can't be embarrassingly parallel.

So, a problem in EXP - NP (that is, it can be solved in exponential time, but it can't be solved in polynomial time even if given an infinity of processors) will require exponentially more time to solve for a higher n than a lower n, regardless of how many processors you have - even up to infinity. You may get some kind of speed-up with more processors, but it will not be enough to remove the exponential runtime blow-up.

An example of a problem like this is the Travelling Salesman Problem. As far as is known right now, there isn't even a non-determinstic algorithm that can solve the problem in polynomial time. Even if you had an infinity of processors, and could solve the problem for 1000 cities in 1 minute, you would still need ~2^1000 minutes to solve the problem for 2000 cities. Note: this bound is not proven, there may be some non-deterministic algorithm that can solve it in polynomial time.

I will also note that even for a problem that is in EXP and in NP, so an EXP problem that is embarrassingly parallel, doubling the problem size would require 2^n more processors to keep the same run time, not 2n (assuming it's time complexity is O(2^n)).

Except that synchronizing two or more cores is, as a rule of thumb, too expensive to do per-instruction?

It would have to be done on the same hidden low level register manipulation as current speculation already does. Instead of rolling back to the wrong branch and starting over you would just drop it and continue with the correct computation.

The issue would be if you have a slow (value load from memory) and a fast (cached value) branch, currently only the most often used one gets predicted, so if you always hit the fast branch the predictor will never touch the slow branch. I think if you evaluate both in parallel you end up having no way to avoid the penalties introduced by the slow path. Imagine having your CPU cache constantly invalidated by code that never "runs".

Reply on news.ycombinator.com