Hacker News Reader

Comment by oniTony | Hacker News Reader

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.

View on HN

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.

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.

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.

SIMD is an example of parallelism without concurrency.

my RISC-architectured world has been shattered. Neat example.

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.

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.

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

I forgot the link to source:

http://existentialtype.wordpress.com/2011/03/17/parallelism-...

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.

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

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

Reply on news.ycombinator.com