7 ms·

Everything You Know (about Parallel Programming) Is Wrong

70 points by 6ren 15y ago

alexchamberlain 15y ago
I disagree with a couple of points... First of all, even handhelds will have thousands of CPUs. Second of all, it's not necessary to scale to this level. Rather, we will run more concurrent, independent tasks. Servers with thousands of workers will be common at home.
- Someone 15y ago
  What would those thousands of workers do? If they are independent of each other, why put them all in a single server instead of in an ASIC? If they are dependent of each other, why will thousands of thread/processes be the architecturally best choice on at server?
  - alexchamberlain 15y ago
    A web server, for example. A server would be cheaper?
    - varelse 15y ago
      It's only cheaper if the underlying memory system has enough bandwidth to handle the throughput of all those cores at once. Otherwise, a fraction of the cores end up as dead-weight, which is surprisingly common in x86 systems set up like this.
      - alexchamberlain 15y ago
        Does that include I/O over a network?
  - deleted 15y ago
    [deleted]
drostie 15y ago
This is very interesting -- is there any hope to get video of the talk?
mooism2 15y ago
When is this from? It talks about "the end of the first decade of the new century" as if it's not in the past.
6ren 15y ago
more discussion on reddit: http://www.reddit.com/r/programming/comments/reo77/everything_you_know_about_parallel_programming_is/ http://www.reddit.com/r/programming/comments/reo77/everythin... interview with author (about the talk): http://channel9.msdn.com/Blogs/Charles/SPLASH-2011-David-Ungar-Self-ManyCore-and-Embracing-Non-Determinism http://channel9.msdn.com/Blogs/Charles/SPLASH-2011-David-Ung... the project homepage: http://soft.vub.ac.be/~smarr/renaissance/ http://soft.vub.ac.be/~smarr/renaissance/
moonchrome 15y ago
OK how is this different from distributed computing ?
- scott_w 15y ago
  Because in distributed computing, the communication lag is more noticeable. It is also harder to synchronise distributed nodes. Multiple cores on a single machine will probably share read-only resources e.g. the clock.
  - moonchrome 15y ago
    Sure, but that's actually a positive and allows special case optimizations of the existing algorithms. My point is this certainly doesn't mean that everything we know is wrong, in fact we have been dealing with this class of problem "in the wild" for last 5-10 years with cloud/cluster computing and GPGPU. Also I feel this "many core is just around the corner" is a lot of hype and little actual results considering that Intel was announcing 70 core CPU by 2011 back in 2007 and we barely hit the 16 cores with AMD. There are some exotic CPUs and GPUs but nothing mainstream, desktops are still at 4-8 core ceiling, mobile is the same. Hopefully SOC GPUs with OpenCL support become mainstream, that will allow interesting things in the mobile space with, but beyond that I don't see this trend hitting the industry any time soon, eg. in 5+ years.
- robfig 15y ago
  I was wondering the same thing. Clearly Google et al has some success with parallel computation without giving up determinism. Thinking about how the cloud model (collaborating services via RPC) maps to a single machine -- I guess that looks like a actor / message passing model where each process gets its own core or something. Plenty of programming languages make this sort of thing straightforward -- (I'm most familiar with Go, where it is absolutely trivial). To me, it looks like the industry is actually very well poised to handle to multi-core onslaught, without requiring some kind of fundamental rethink like nondeterminism.
  - onemoreact 15y ago
fmstephe 15y ago
My reaction to this is that I am sure he is right that embracing nondeterminism and relaxing synchronization will allow us to scale up to these many core PCs. However, this does not solve the problem of how 'the rest of us' program them effectively. One of the biggest challenges I see practically are that concurrency and parallelism are the hardest thing to push down under a layer of abstraction. These effects leak out all the way through your application (and even into other applications). It strikes me that this kind of non-deterministic approach will leak everywhere. And then who can program in this way? Who among us can reason effectively about just how far from the true answer we are. If this is the only way we can really harness the many-many-core PCUs of the future then we will have the change the way we make software. The IBM approach of armies of programmers will not work. As much as I hate this approach to software it is the way most software (at least in the enterprise) is made. Will we go back to the long beards? Or will we end up in even more aggressively restrictive frameworks that work harder to prevent us from doing this wrong. If this approach to parallelism turns out to be important I hope that the problem of reasoning about these types of program is tractible. To push well understood software development even further away from the reach of most programmers. If we all end up having to learn a bit of statistics that wouldn't be a bad thing.
- deleted 15y ago
  [deleted]
- mooism2 15y ago
  > And then who can program in this way? Who among us can reason effectively about just how far from the true answer we are. If floating point math is anything to go by, most programmers won't be able to cope with this. (Then again, most languages do nothing to help programmers keep track of how large the inaccuracies get.)
  - fmstephe 15y ago
    An interesting point. I suppose if this becomes a really important technique we may see some very interesting language support. Fun times :)
- 15y ago
DanielBMarkham 15y ago
So quantum computing says that instead of one calculation, I perform multiple calculations simultaneously in different universes. Now this guy says that I have to give up the idea of computing as being deterministic and always getting the right answer? It has to be true, because it makes no sense whatsoever. Web designers of the future will have a great reply to customers. "The site gives wrong answers? Well, you need to realize that asking for correct answers isn't what we do with computers. And besides that, in another universe the answers are correct. Boy, are you really happy over there!" That was perhaps a too-long-winded snark with a point: it's not that I don't feel that we're headed in the right direction, it's that visionaries always seem to concentrate on the brain-exploding part of what they're saying instead of talking about how it all integrates together. While I think this might sell some website views, it doesn't do much for the practitioner looking for insight.
- fmstephe 15y ago
  I think it is fair to say that this approach only works in some domains. We won't be using it where giving the 'wrong' answer upsets the people with the money. But if you listen to the channel 9 interview put up by 6ren he clearly outlines a number of scenarios that are appropriate. <not-snarky>It isn't clear what quantum computing has to do with this discussion.</not-snarky> Edit: Mitigate snarkiness of final comment.
  - DanielBMarkham 15y ago
    "...It isn't clear what quantum computing has to do with this discussion..." My entire point was that the way we describe future tech emphasizes the differences and exotic nature of the concepts instead of how it's all going to eventually work together anyway. Quantum computing was my second example. Apologies if I didn't make that clear enough.
    - fmstephe 15y ago
      I agree with your sentiment that it isn't clear how this will fit into software development in general. Fair enough about the quantum comment. Also, my comments sounds snarkier that it was intented, so apologies for that :) (what a polite bunch we all are)
varelse 15y ago
While I absolutely agree that we have to give up on nondeterministic execution (did so years and years ago), I flat out disagree that this necessarily leads to nondeterministic output/results. That's just lazy and a nightmare to debug. Speaking from my own experience, there's usually a way to order the results either by sorting, by accumulating them in a deterministic manner (extended fixed-point math or by ordered reduction), or by halting execution upon reaching a consistent degree of convergence. And we already know one way to program such beasts: in a map-reduce like manner where chunks of computation are doled out to all the cores, each executed deterministically within them, but doled out in a nondeterministic order.
riffraff 15y ago
Please, if you are going to be astonished and or irritated about the bit in TFA related to "non determinism", consider that, in Ungar's own words: """ To the extent that an application remains acceptable to its end users with respect to their business needs, we aim to permit – or no longer attempt to prevent – inconsistency relating to the order in which concurrent updates and queries are received and processed """ This is something many people are already familiar with: you can giveup some correctness or timeliness, if it doesn't matter much. It's what's behind eventual consistency, yesterday's youtube architecture article, redis' nofsync settings etc. [1] http://soft.vub.ac.be/~smarr/renaissance/ungar-kimelman-adams-2011-inconsistency-robustness-for-scalability-in-interactive-concurrent-update-in-memory-molap-cubes.pdf http://soft.vub.ac.be/~smarr/renaissance/ungar-kimelman-adam...

70 points by 6ren 15y ago

I disagree with a couple of points... First of all, even handhelds will have thousands of CPUs. Second of all, it's not necessary to scale to this level. Rather, we will run more concurrent, independent tasks. Servers with thousands of workers will be common at home.

Someone 15y ago
What would those thousands of workers do? If they are independent of each other, why put them all in a single server instead of in an ASIC? If they are dependent of each other, why will thousands of thread/processes be the architecturally best choice on at server?
- alexchamberlain 15y ago
  A web server, for example. A server would be cheaper?
  - varelse 15y ago
    It's only cheaper if the underlying memory system has enough bandwidth to handle the throughput of all those cores at once. Otherwise, a fraction of the cores end up as dead-weight, which is surprisingly common in x86 systems set up like this.
    - alexchamberlain 15y ago
      Does that include I/O over a network?
- deleted 15y ago
  [deleted]

drostie 15y ago

This is very interesting -- is there any hope to get video of the talk?

mooism2 15y ago

When is this from? It talks about "the end of the first decade of the new century" as if it's not in the past.

6ren 15y ago

more discussion on reddit: http://www.reddit.com/r/programming/comments/reo77/everything_you_know_about_parallel_programming_is/ http://www.reddit.com/r/programming/comments/reo77/everythin... interview with author (about the talk): http://channel9.msdn.com/Blogs/Charles/SPLASH-2011-David-Ungar-Self-ManyCore-and-Embracing-Non-Determinism http://channel9.msdn.com/Blogs/Charles/SPLASH-2011-David-Ung... the project homepage: http://soft.vub.ac.be/~smarr/renaissance/ http://soft.vub.ac.be/~smarr/renaissance/

moonchrome 15y ago

OK how is this different from distributed computing ?

scott_w 15y ago
Because in distributed computing, the communication lag is more noticeable. It is also harder to synchronise distributed nodes. Multiple cores on a single machine will probably share read-only resources e.g. the clock.
- moonchrome 15y ago
  Sure, but that's actually a positive and allows special case optimizations of the existing algorithms. My point is this certainly doesn't mean that everything we know is wrong, in fact we have been dealing with this class of problem "in the wild" for last 5-10 years with cloud/cluster computing and GPGPU. Also I feel this "many core is just around the corner" is a lot of hype and little actual results considering that Intel was announcing 70 core CPU by 2011 back in 2007 and we barely hit the 16 cores with AMD. There are some exotic CPUs and GPUs but nothing mainstream, desktops are still at 4-8 core ceiling, mobile is the same. Hopefully SOC GPUs with OpenCL support become mainstream, that will allow interesting things in the mobile space with, but beyond that I don't see this trend hitting the industry any time soon, eg. in 5+ years.
robfig 15y ago
I was wondering the same thing. Clearly Google et al has some success with parallel computation without giving up determinism. Thinking about how the cloud model (collaborating services via RPC) maps to a single machine -- I guess that looks like a actor / message passing model where each process gets its own core or something. Plenty of programming languages make this sort of thing straightforward -- (I'm most familiar with Go, where it is absolutely trivial). To me, it looks like the industry is actually very well poised to handle to multi-core onslaught, without requiring some kind of fundamental rethink like nondeterminism.
- onemoreact 15y ago

fmstephe 15y ago

My reaction to this is that I am sure he is right that embracing nondeterminism and relaxing synchronization will allow us to scale up to these many core PCs. However, this does not solve the problem of how 'the rest of us' program them effectively. One of the biggest challenges I see practically are that concurrency and parallelism are the hardest thing to push down under a layer of abstraction. These effects leak out all the way through your application (and even into other applications). It strikes me that this kind of non-deterministic approach will leak everywhere. And then who can program in this way? Who among us can reason effectively about just how far from the true answer we are. If this is the only way we can really harness the many-many-core PCUs of the future then we will have the change the way we make software. The IBM approach of armies of programmers will not work. As much as I hate this approach to software it is the way most software (at least in the enterprise) is made. Will we go back to the long beards? Or will we end up in even more aggressively restrictive frameworks that work harder to prevent us from doing this wrong. If this approach to parallelism turns out to be important I hope that the problem of reasoning about these types of program is tractible. To push well understood software development even further away from the reach of most programmers. If we all end up having to learn a bit of statistics that wouldn't be a bad thing.

deleted 15y ago
[deleted]
mooism2 15y ago
> And then who can program in this way? Who among us can reason effectively about just how far from the true answer we are. If floating point math is anything to go by, most programmers won't be able to cope with this. (Then again, most languages do nothing to help programmers keep track of how large the inaccuracies get.)
- fmstephe 15y ago
  An interesting point. I suppose if this becomes a really important technique we may see some very interesting language support. Fun times :)
15y ago

DanielBMarkham 15y ago

So quantum computing says that instead of one calculation, I perform multiple calculations simultaneously in different universes. Now this guy says that I have to give up the idea of computing as being deterministic and always getting the right answer? It has to be true, because it makes no sense whatsoever. Web designers of the future will have a great reply to customers. "The site gives wrong answers? Well, you need to realize that asking for correct answers isn't what we do with computers. And besides that, in another universe the answers are correct. Boy, are you really happy over there!" That was perhaps a too-long-winded snark with a point: it's not that I don't feel that we're headed in the right direction, it's that visionaries always seem to concentrate on the brain-exploding part of what they're saying instead of talking about how it all integrates together. While I think this might sell some website views, it doesn't do much for the practitioner looking for insight.

fmstephe 15y ago
I think it is fair to say that this approach only works in some domains. We won't be using it where giving the 'wrong' answer upsets the people with the money. But if you listen to the channel 9 interview put up by 6ren he clearly outlines a number of scenarios that are appropriate. <not-snarky>It isn't clear what quantum computing has to do with this discussion.</not-snarky> Edit: Mitigate snarkiness of final comment.
- DanielBMarkham 15y ago
  "...It isn't clear what quantum computing has to do with this discussion..." My entire point was that the way we describe future tech emphasizes the differences and exotic nature of the concepts instead of how it's all going to eventually work together anyway. Quantum computing was my second example. Apologies if I didn't make that clear enough.
  - fmstephe 15y ago
    I agree with your sentiment that it isn't clear how this will fit into software development in general. Fair enough about the quantum comment. Also, my comments sounds snarkier that it was intented, so apologies for that :) (what a polite bunch we all are)

varelse 15y ago

While I absolutely agree that we have to give up on nondeterministic execution (did so years and years ago), I flat out disagree that this necessarily leads to nondeterministic output/results. That's just lazy and a nightmare to debug. Speaking from my own experience, there's usually a way to order the results either by sorting, by accumulating them in a deterministic manner (extended fixed-point math or by ordered reduction), or by halting execution upon reaching a consistent degree of convergence. And we already know one way to program such beasts: in a map-reduce like manner where chunks of computation are doled out to all the cores, each executed deterministically within them, but doled out in a nondeterministic order.

riffraff 15y ago

Please, if you are going to be astonished and or irritated about the bit in TFA related to "non determinism", consider that, in Ungar's own words: """ To the extent that an application remains acceptable to its end users with respect to their business needs, we aim to permit – or no longer attempt to prevent – inconsistency relating to the order in which concurrent updates and queries are received and processed """ This is something many people are already familiar with: you can giveup some correctness or timeliness, if it doesn't matter much. It's what's behind eventual consistency, yesterday's youtube architecture article, redis' nofsync settings etc. [1] http://soft.vub.ac.be/~smarr/renaissance/ungar-kimelman-adams-2011-inconsistency-robustness-for-scalability-in-interactive-concurrent-update-in-memory-molap-cubes.pdf http://soft.vub.ac.be/~smarr/renaissance/ungar-kimelman-adam...