As we all know, microprocessors are
becoming cheaper and faster every day.
Computing power doubles every eighteen for
the same price.
And this has been going on for more than
40 years.
So, in the early days of parallel
computing, such as the 80s.
By the time one figured how one could use
many processors to do the work of one
processor faster, that one processor
itself became twice as fast.
So parallel computing really had to play a
catch up game.
However, in recent years you may have
noticed that all your PCs and servers come
with multiple cores, four cores, eight
cores, sixteen cores, and, soon will be 32
cores or 64 cores on every chip.
What that's really meaning is that the
limits of the speed of light are requiring
parallel computing to be used in everyday
life, within every computer which was
never the case twenty or 30 years ago.
On the web, parallel computing is used at
a macro level with hundreds of thousands
or even millions of servers powering the
large search engines and social media
platforms, such as Google and Facebook.
So, in two different ways, within chips on
the one hand and in the web on the other,
parallel computing, has seen, a new life,
in the past five years.
So it's important to understand some basic
principles, when one tries to do things
faster using more machines.
If one uses P machines, one would, expect
that one can do the same task which took
t1 time, in less time.
Let's call it Tp.
This will obviously be greater than one
and will increase as you increase the
number of processors.
So for example, you have twenty
processors, you might get speed up of
somewhere around fifteen or sixteen.
If you have 40 processors, you might get
somewhere around 29 or 30.
But as the number of processors increases,
for a variety of reasons, the speed up
doesn't go on forever.
So another important concept is, the
efficiency.
The expected speed up is P, with P
processors.
So the efficiency measures how close we
are to achieving that speed up, and that's
something less than one.
When you have a small number of processors
like two or four or eight you can get
close to one as your efficiency.
But as the number of processors goes up,
we will see that the efficiency will
actually come down.
There are reasons for this and the primary
reason is communication between processors
or coordination between processors.
Think of it like this, if you have two or
three people to perform a task, it's
probably easier but if you put a 100
people to perform a task, the task doesn't
necessarily become 100 times faster
because the people will have to talk to
each other and coordinate their actions.
So, do we lose hope?
Is there no way we can really exploit
thousands and millions of processors?
Well, there is actually.
And the trick is to not solve the same
problem, but to solve bigger problems if
you have more processors.
There's no point indexing a file of a
megabyte with a million machines, you only
need a million machines if you have
billions and billions of web pages to
index.
A scalable algorithm is one which allows
you to increase the problem size without
suffering any loss in efficiency.
On the contrary, because you have large
number of processors, and a large problem
size, the effect of coordination costs
should actually go down as a ratio of the
overall work being performed.
So your efficiency should actually
increase as the ratio and over p increases
So scalar algorithm is one where, as the
problem size goes up in proportion to the
number of processors that you throw at the
problem, you get better and better
efficiency.
Parallel programming is considerably more
difficult than normal serial programming.
Because one has to deal with coordinating
the actions of many different processors.
There are two fundamental paradigms that
have been used historically for parallel
programming one is shared memory.
For example, one might partition work
using shared memory in this way.
Each processor does a particular piece of
work called W sub P.
And different processors do different work
by locking that part of the data which
they are working on doing their work.
And then unlocking the data or piece of
data that they just worked on.
And as long as every processor accesses
the different part of the data that some
other processor is accessing, this is
reasonably fast.
Of course, the problem arises if they try
to access the same piece of data in which
case, they might find it to be locked by
somebody else.
And that's where the costs of coordination
or communication overhead slow down the
procedure and reduce the efficiency.
Another paradigm which has been used
historically is message passing, for
example, by partitioning the data.
So each processor does the same
computational work but on different parts
of the data.
So for example, a processor might have
this slice of the data.
So the data is divided into n over p
slices and each processor gets one slice
but performs the same work on this slice
of data.
Of course, if that was all there was to
it, the problem is what is called
embarrassingly parallel and it becomes
fairly trivial.
However, in most cases, the problem is a
bit more difficult because the results of
work done on one slice of data need to use
the results from the work done on another
slice of data.
Think of adding up n numbers, you simply
couldn't add up each small slice and
expect to get the answer, but you'd have
to exchange, the results of these partial
sums, with at least one processor, or
maybe, many of them in a tree structure,
so that you could finally compute, the sum
of all the numbers, in parallel.
Therefore, in the message-passing model,
processors need to exchange data after
performing some work on their slice.
So that they can perform more work based
on the results of the work done by other
processors on other slices.
This make message passing a bit more
difficult to programme than shared memory,
but it's also much more scalable because
things like shared memory itself are
really difficult to implement when you
have thousands or millions of processors.
Of course, you can have shared memory and
also partition the data.
Just as you could have message passing,
and partition the work.
The map produce programming paradigm is a,
higher level, abstraction then, pure
message passing or shared memory.
But it is a message passing and data
parallel paradigm.