4 ms·
Despite the limitations apparently present in single chip/CPU systems, they can still provide an insane amount of performance if used properly. There are also
by bob1029 5y ago
Despite the limitations apparently present in single chip/CPU systems, they can still provide an insane amount of performance if used properly.
There are also many problems that are literally impossible to make faster or more correct than by simply running them on a single thread/processor/core/etc. There always will be forever and ever. This is not a "we lack the innovation" problem. It's an information-theoretic / causality problem you can demonstrate with actual math & physics. Does a future event's processing circumstances maybe depend on all events received up until now? If yes, congratulations. You now have a total ordering problem just like pretty much everyone else. Yes, you can cheat and say "well these pieces here and here dont have a hard dependency on each other", but its incredibly hard to get this shit right if you decide to go down that path.
The most fundamental demon present in any distributed system is latency. The difference between L1 and a network hop in the same datacenter can add up very quickly.
Again, for many classes of problems, there is simply no handwaving this away. You either wait the requisite # of microseconds for the synchronous ack to come back, or you hope your business doesnt care if john doe gets duplicated a few times in the database on a totally random basis.
- AnthonyMouse 5y agoThe 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.
- tsimionescu 5y agoNot 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).
- AnthonyMouse 5y agoComputational 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.
- deleted 5y ago[deleted]
- chii 5y agoBut 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...
- AbbeSomething 5y agoAre 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.
- chii 5y agoNone that are usable i'm sure - it's merely a theoretical idea.
- ReactiveJelly 5y agoExcept that synchronizing two or more cores is, as a rule of thumb, too expensive to do per-instruction?
- josefx 5y agoIt 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".
- userbinator 5y agothey can still provide an insane amount of performance if used properly. In other words, software bloat has eaten up the bulk of the performance.
- tgamblin 5y agoAll 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.
- eslaught 5y agoLike 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.
- apbytes 5y agoWait what‽ Do you have any resources you can point to for parallelism in finite automata?
- eslaught 5y agoIt'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://github.com/vqd8a/DFAGE https://onlinelibrary.wiley.com/doi/epdf/10.1002/stvr.1796 https://onlinelibrary.wiley.com/doi/epdf/10.1002/stvr.1796
- xyzzy21 5y agoGood 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.