5 ms·
Google's Introduction to Parallel Programming and MapReduce
- oniTony 15y agoConcurrency (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 agoParallel 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 agolock-free data structures are also really really neat. Implementing such is another matter though...
- barrkel 15y agoI 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 agoRight. 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 agoSIMD is an example of parallelism without concurrency.
- oniTony 15y agomy RISC-architectured world has been shattered. Neat example.
- wtallis 15y agoWhen 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 agoIf 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
- nivertech 15y agoConcurrency 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
- NickBomb 15y agoCool, 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.
- mark_l_watson 15y agoI 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.
- thy 15y agodoodlin' http://wonderfl.net/c/zzQD http://wonderfl.net/c/zzQD
- deleted 15y ago[deleted]
- gruseom 15y agoThe 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.
- defen 15y ago[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.
- SamReidHughes 15y agoSince 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.
- gruseom 15y agoSo 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?
- oniTony 15y agoThe 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.
- moultano 15y agoThe mapper only has a small fraction of the data for each reduce key.
- gruseom 15y agoCouldn'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.
- moultano 15y agoYes that's sometimes an option, but very often the reduce isn't associative.
- gruseom 15y agoAh, 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.