You'll recall we began our discussion of parallel computing by the notions of
parallel efficiency. So it's worth trying to figure out what is
the parallel efficiency of MapReduce. Let's assume that the data which is
emitted by all the mappers put together is D.
This might be much less than the data emitted by the.
If we use combiners efficiently, D may actually be significantly less, than the
total amount of data input to the MapReduce program.
We also assume that their will be processors that will include mappers and
reducers. And will assume there is really no overlap
between mappers and reducers so that we have P by two mappers and P by two
reducers. Clearly parallel efficiency depends on
overhead such as communications between processors.
And so the ideal way to compute the minimum parallel efficiency is to assume
that there is no real useful work being done.
Now we will actually assume that there is no real useful work being performed as in
terms of an algorithm. Instead, we are only considering the
efficiency of the map-produced platform itself, where all the work that it really
does, is, sort, p by two of these blocks, each of size, d divided by p by two, and
then communicate the results, to, the different reducers.
Now, the actual efficiency of any algorithm using MapReduce will be at least
this much, provided that algorithm requires this sorting process for its
completion. That need not always be the case though,
but for the moment we assume that it is. Now let's consider the communication
costs. That is, 2D by P of data, in each block
here, each mapper, has to be communicated to, to P by two reducers.
Each reducer gets one by one p by 2th of the data so each reducer gets about 4d by
p squared data and this has, has to go, go to p by two reducers in particular it has
to be collected from p by two mappers at each reducer.
So. This requires P by two separate steps of
communication. So you multiply this by P by two to get 2D
by P as representing the communicating costs.
The serial costs are of course. The cost required to, to sort P by two
blocks of this size. Which works to something, which is
constant multiplier times D by P. Log D by P times P.
And so we get. Of, a term like this.
The same term in the denominator, plus the communication costs.
This, of course, is the formula for efficiency, where you have the serial,
time, in the numerator, the parallel time, in the denominator which is, the serial
time divided by p in this case. And multiplied by P and the communication
cost. Simplifying this, you get an expression
that looks something like one over one plus, two times some communication cost
and constant divide by a work constant times log of D by P.
Notice that we have liberally removed, constants like the two which might have,
might occur in the, the log over here because that only, adds a, constant,
additive factor. We've also, been fairly liberal about,
factors of two here and there, just to get the form of this equation, correctly.
Remember what we said about an algorithm being scalable.
If efficiency approaches one as P by P grows than the algorithm is set to be
scalable. As d/p becomes very large this term
becomes extremely small and efficiency does indeed become close to one.
So the platform for maproduce is actually scalable in this sense The caveat is of
course that the algorithm, that we perform on this platform actually requires this
serial work to be performed, in other words, there is a need for sorting in the
algorithm, of some kind. This is not always the case of course.
For example there are many tasks which can just as well performed by only a map phase
not requiring any reduce or any sorting. Such task may be called embarrassingly
parallel in which case simply using the map reduce platform will add overhead,
which is avoidable.