Google's Introduction to Parallel Programming and MapReduce(code.google.com)
code.google.com
Google's Introduction to Parallel Programming and MapReduce
http://code.google.com/edu/parallel/mapreduce-tutorial.html
6 comments
So the map worker saves map results to its local disk, and eventually a reduce worker does an RPC call to copy that data over the network so it can perform the reduce. What is the advantage of doing this over having the map worker do the reduce part itself?
The mapper only has a small fraction of the data for each reduce key.
Couldn't it at least perform the reduce on the portion it does have? i.e. transfer partial reductions from M to R, instead of the raw map results? Presumably there are many problems where this would be a win.
Yes that's sometimes an option, but very often the reduce isn't associative.
Ah, so that's the reason. Do you ever have the problem that the reduce computation, for a given key, is too big for one reduce worker and itself needs to be parallelized? Or does this boil down to the same thing as my previous question - i.e. if the reduce computation isn't associative, you couldn't parallelize it anyway, and if it is then you can just do partial reductions on M.
Yes that is often a problem and is probably my biggest criticism of mapreduce as a framework. Extreme reduce keys often have to be handled differently and in a way dependent on the nature of the problem. Mapreduce doesn't provide great tools for handling it, though I'm not even sure what abstraction you could build that would be comprehensive enough.
The advantage is that you don't need 1:1 ratio of tasks. You could have many mappers and just a few reducers, or the other way around.. depending on how the problem is broken up into tasks.
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.
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.
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.
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.
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.
> 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 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-...
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.
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
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
I have found the best resource for map reduce algorithms to be "Data-Intensive Text Processing with MapReduce" by Chris Dyer and Jimmy Lin - a short and very useful book that characterizes map reduce problems and their solutions.
The article says that Fibonacci can't be parallelized. But I seem to recall that there is a true data-parallel way of doing Fibonacci - one of those virtuoso tricks where something that seems intrinsically sequential gets transformed into a parallel computation. Does anyone know what I'm talking about?
Edit: to be clear, I don't mean the obvious but useless trick where you can compute F(n-1) and F(n-2) recursively in parallel, which is just redoing most of the work. I mean a way to model the problem as operations on data-parallel vectors.
Edit: to be clear, I don't mean the obvious but useless trick where you can compute F(n-1) and F(n-2) recursively in parallel, which is just redoing most of the work. I mean a way to model the problem as operations on data-parallel vectors.
[1 1; 1 0]^n = [Fn+1 Fn; Fn Fn-1]
So you could rewrite n as a sum of m powers of 2 (just write it in binary), then for each "1" there, send it to a separate processor to compute [1 1; 1 0]^k using exponentiation by squaring (where k is the corresponding power of 2). Your reduce step multiplies the resulting matrices together.
Note: this is just the first thing that comes to mind, I have no idea if this is what you were thinking of, or if it's even a good idea.
So you could rewrite n as a sum of m powers of 2 (just write it in binary), then for each "1" there, send it to a separate processor to compute [1 1; 1 0]^k using exponentiation by squaring (where k is the corresponding power of 2). Your reduce step multiplies the resulting matrices together.
Note: this is just the first thing that comes to mind, I have no idea if this is what you were thinking of, or if it's even a good idea.
Since computing [1 1; 1 0]^(2k) where k is a power of 2 would involve computing [1 1; 1 0]^k first, you'll end up reproducing the exact same work on all your machines, and you might as well just use the one.
Cool, I actually attended a talk about MapReduce hosted by Google a few weeks ago. Sadly, I have to say that this page explains it better than their engineer did, though.