4 ms·

Concurrency (single CPU context switching) is "easy". Parallel programming (multiple tasks on multiple CPUs) is _hard_. I'm currently studying the internals of

by oniTony 15y ago

Concurrency (single CPU context switching) is "easy". Parallel programming (multiple tasks on multiple CPUs) is _hard_. I'm currently studying the internals of parallel programming, I am amazed by how much magic MapReduce abstracts away.

fleitz 15y ago
Parallel programs are only difficult if you're playing giant state machine poking at bits in memory, once you stop doing that and start using immutable data structures and passing messages it gets much easier. You'll notice that map reduce is built around the idea of immutable data. Map reduce also helps with "serial" programs making them much more readable.
- oniTony 15y ago
  lock-free data structures are also really really neat. Implementing such is another matter though...
barrkel 15y ago
I don't agree with your terminology. Concurrency is having more than one task in flight; it's inherently non-deterministic when the tasks can interact via shared resources. Parallelism is having more than one operation happening simultaneously; it can be a way of implementing concurrency, but it is not necessarily non-deterministic, depending on how it is exposed in the model. And indeed, map-reduce with pure functions is a way of using deterministic parallelism. Concurrency is a high-level concept; it comes in at the architectural layer. Servers open for multiple clients, where those clients are asking the server to operate on shared mutable memory, are non-deterministic; small differences in timing make all the difference. Parallelism in an implementation-level concept. Depending on how it is put to use, it can be merely a way of speeding up deterministic computations; or it can be directly harnessed to implement concurrency.
- oniTony 15y ago
  Right. Those are stricter definitions. Although wouldn't Parallelism's multiple operations each be "in-flight"? That is, it's pretty clear that one can have concurrency without parallelism, but you seem to suggest that one can have parallelism without concurrency ("deterministic parallelism"). Which doesn't _sound_ right... Even with MapReduce, the order in which tasks are complete are not deterministic (different hardware, network latency, etc), so I don't see how you could determine in which order mappers are passed on to reducers.
  - 0x12 15y ago
    SIMD is an example of parallelism without concurrency.
    - oniTony 15y ago
      my RISC-architectured world has been shattered. Neat example.
  - wtallis 15y ago
    When you do map and reduce operations with functions that have no side effects (and your reduction function is associative), then changes in the ordering of operations don't affect the result of the overall map or reduce operation, any more than when a CPU reorders instructions to avoid pipeline stalls. Map and Reduce are a way of breaking your problem up in to pieces that have no inter-dependencies or shared mutable state, so that they can be executed in parallel without any of the pitfalls of concurrency.
  - barrkel 15y ago
    If your map and reduce functions are pure, it's impossible to tell which one got executed first, or perfectly simultaneously, etc. It's important to talk about the right level of abstraction; otherwise we could argue that sequential algorithms are actually parallel, because the world is not a single-threaded simulation, etc.
- nandemo 15y ago
  I agree with the first part of your explanation. I'm not sure about the rest. Compare to this: > Concurrency is concerned with nondeterministic composition of programs (or their components). Parallelism is concerned with asymptotic efficiency of programs with deterministic behavior. Concurrency is all about managing the unmanageable: events arrive for reasons beyond our control, and we must respond to them. (...) Parallelism, on the other hand, is all about dependencies among the subcomputations of a deterministic computation > Now I can hear you object, but isn’t concurrency required to implement parallelism? Well, yes, it is, but concurrency is also required to implement sequentiality too! The timing signal on your processor chip is essentially a synchronization mechanism with which to coordinate the otherwise independent activity of the components of the processor. (...) The point is that concurrency is not relevant to parallelism, even if the engineers who build our parallel computing platforms must deal with concurrency. Another way to say the same thing is that parallelism is a useful abstraction, and abstractions should never be confused with their implementations.
  - barrkel 15y ago
    There's a danger of talking about different levels of abstraction, yes; but if we start bringing in chip-level timing signals, I think we've lost sight of programming language level models, so I ultimately I think that's a red herring. (I considered linking to that blog post, but decided against it in small part because of this.)
  - nandemo 15y ago
    I forgot the link to source: http://existentialtype.wordpress.com/2011/03/17/parallelism-is-not-concurrency/ http://existentialtype.wordpress.com/2011/03/17/parallelism-...
nivertech 15y ago
Concurrency property of systems in which several computational processes are executing at the same time, and potentially interacting with each other Parallelism computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently (i.e. "in parallel") http://www.slideshare.net/nivertech/migrationtomulticore http://www.slideshare.net/nivertech/migrationtomulticore

by oniTony 15y ago

fleitz 15y ago

Parallel programs are only difficult if you're playing giant state machine poking at bits in memory, once you stop doing that and start using immutable data structures and passing messages it gets much easier. You'll notice that map reduce is built around the idea of immutable data. Map reduce also helps with "serial" programs making them much more readable.

oniTony 15y ago
lock-free data structures are also really really neat. Implementing such is another matter though...

barrkel 15y ago

I don't agree with your terminology. Concurrency is having more than one task in flight; it's inherently non-deterministic when the tasks can interact via shared resources. Parallelism is having more than one operation happening simultaneously; it can be a way of implementing concurrency, but it is not necessarily non-deterministic, depending on how it is exposed in the model. And indeed, map-reduce with pure functions is a way of using deterministic parallelism. Concurrency is a high-level concept; it comes in at the architectural layer. Servers open for multiple clients, where those clients are asking the server to operate on shared mutable memory, are non-deterministic; small differences in timing make all the difference. Parallelism in an implementation-level concept. Depending on how it is put to use, it can be merely a way of speeding up deterministic computations; or it can be directly harnessed to implement concurrency.

oniTony 15y ago
Right. Those are stricter definitions. Although wouldn't Parallelism's multiple operations each be "in-flight"? That is, it's pretty clear that one can have concurrency without parallelism, but you seem to suggest that one can have parallelism without concurrency ("deterministic parallelism"). Which doesn't _sound_ right... Even with MapReduce, the order in which tasks are complete are not deterministic (different hardware, network latency, etc), so I don't see how you could determine in which order mappers are passed on to reducers.
- 0x12 15y ago
  SIMD is an example of parallelism without concurrency.
  - oniTony 15y ago
    my RISC-architectured world has been shattered. Neat example.
- wtallis 15y ago
  When you do map and reduce operations with functions that have no side effects (and your reduction function is associative), then changes in the ordering of operations don't affect the result of the overall map or reduce operation, any more than when a CPU reorders instructions to avoid pipeline stalls. Map and Reduce are a way of breaking your problem up in to pieces that have no inter-dependencies or shared mutable state, so that they can be executed in parallel without any of the pitfalls of concurrency.
- barrkel 15y ago
  If your map and reduce functions are pure, it's impossible to tell which one got executed first, or perfectly simultaneously, etc. It's important to talk about the right level of abstraction; otherwise we could argue that sequential algorithms are actually parallel, because the world is not a single-threaded simulation, etc.
nandemo 15y ago
I agree with the first part of your explanation. I'm not sure about the rest. Compare to this: > Concurrency is concerned with nondeterministic composition of programs (or their components). Parallelism is concerned with asymptotic efficiency of programs with deterministic behavior. Concurrency is all about managing the unmanageable: events arrive for reasons beyond our control, and we must respond to them. (...) Parallelism, on the other hand, is all about dependencies among the subcomputations of a deterministic computation > Now I can hear you object, but isn’t concurrency required to implement parallelism? Well, yes, it is, but concurrency is also required to implement sequentiality too! The timing signal on your processor chip is essentially a synchronization mechanism with which to coordinate the otherwise independent activity of the components of the processor. (...) The point is that concurrency is not relevant to parallelism, even if the engineers who build our parallel computing platforms must deal with concurrency. Another way to say the same thing is that parallelism is a useful abstraction, and abstractions should never be confused with their implementations.
- barrkel 15y ago
  There's a danger of talking about different levels of abstraction, yes; but if we start bringing in chip-level timing signals, I think we've lost sight of programming language level models, so I ultimately I think that's a red herring. (I considered linking to that blog post, but decided against it in small part because of this.)
- nandemo 15y ago
  I forgot the link to source: http://existentialtype.wordpress.com/2011/03/17/parallelism-is-not-concurrency/ http://existentialtype.wordpress.com/2011/03/17/parallelism-...

nivertech 15y ago

Concurrency property of systems in which several computational processes are executing at the same time, and potentially interacting with each other Parallelism computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently (i.e. "in parallel") http://www.slideshare.net/nivertech/migrationtomulticore http://www.slideshare.net/nivertech/migrationtomulticore