Hacker News Reader

All of this is true, but I’ll just be nitpicky to make a point:

> Does a future event's processing circumstances maybe depend on all events received up until now?

In a parallel prefix sum, the final sum does depend on all prior inputs, but a good parallel implementation runs in O(log(n)) time. It is, of course, not a total ordering problem, but that’s not obvious at first glance — I’ve always thought it was a beautiful example of something that appears to be entirely sequential but actually parallelizes really well.

All of which is to say that, yeah, we’re latency bound at the end of the day, but there’s a lot more innovation and performance left to be wrung out of most systems. A little creativity goes a long way, and I like the idea of a universe where the software is the main determinant of performance — where you can’t get away with just waiting for the next generation of chips.

It's a very simple example and knowing that addition is commutative, it's obvious that there is no ordering.

Prefix sum depends on associativity, not commutativity.

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.

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

they can still provide an insane amount of performance if used properly.

In other words, software bloat has eaten up the bulk of the performance.

Like the sibling comments have indicated, many apparently sequential computations are actually parallelizable. I'll just add finite automata as another example in this category. On the surface it looks quite sequential (process one input at a time), but there are nice parallel algorithms that you can even implement on a GPU!

So yeah, there's a lot of nonobvious parallelism in the world. Just because something seems sequential doesn't mean it is.

I think the real reason why a lot of software is sequential/inefficient in practice is because we're just not smart enough to figure out how to optimize it (or don't have the proper incentives/it's not a priority). But that's something that's conceivably solvable; it's not limited by laws of physics the way hardware is.

Wait what‽ Do you have any resources you can point to for parallelism in finite automata?

It's been a while, but here are a couple things I found on Google for the search "finite automata gpu":

https://github.com/vqd8a/DFAGE

https://onlinelibrary.wiley.com/doi/epdf/10.1002/stvr.1796

Good Coding is still in major deficit these days so absolutely true.

Going back to "coding intensity" that used to be common in 8-bit processors to overcome bloatware is still open territory. One may themselves code with libraries efficiently but the libraries are very seldom very efficient.

This is still one of the better ways of "extending Moore's Law" - stop bloating code.

Architecture innovation is another.

Chiplets is probably the best physical/electronics way right now to continue the status quo of laziness.