# Foundations of Computer Science/Parallel Processing

Computing is fundamentally about information processes. On a digital
computer such processes are carried out via symbol manipulations in
binary logic. With the advancement in semiconducting technology we have
been able to keep making computers run faster---manipulate bits at a
higher speed---by cramming more transistors into computer chips. This is
known as the Moore\'s law
originated around 1970\'s. The trend of increase has slowed down and
will eventually flatten due to limits in physics as predicted by some
physicist, who also
predicted potential new technologies that may replace semiconductors
(silicon) in computer hardware manufacturing.

In the meantime, hardware companies have tweaked their technologies to
maintain the growth in hardware capacity. Multicore technology replaces
one fast CPU (Central Processing
Unit---the brain
of a computer) with many slower ones (called cores) to avoid overheating
the chip. Even though each core is a slower but we get more of them and
could get more done if we can arrange the work properly. For instance, a
strong worker can lift 100 bricks a minute and a normal worker can only
lift 34 bricks. Three normal workers can outperform one strong worker
even though they are much slower individually. This is the idea of
parallel processing.

Traditionally computer program has been written to describe sequential
processes, which means the steps can only be carried out one at a time
and one after another in a sequence. This type of program works fine on
a computer with a single processor because the computer can perform one
symbol manipulation at a time any ways. In fact we have been reaping the
benefit of Moore\'s law: every two computer hardware double it speed
causing our program run twice as fast without us doing anything. This
trend has stopped. Each individual processor (core) is not getting
faster but we have more of them in a computer. As a result our existing
sequential program will run slower even though the hardware\'s capacity
has become larger. Before the next generation of computers are invented
we can parallel
computing/processing
to solve problems faster computationally.

The idea of parallel processing is not new. For example, a car assembly
line allows multiple cars to be built at the same time. Even though
different parts of the car are being assembled at a given time this
assembly line keeps all the workers busy increasing the throughput
(number of cars built per unit time) of the whole system. We can make
the workers work faster to further increase the throughput or we could
add another assembly and hire more workers. This is one form of parallel
processing - pipelining. Another form of parallelism divides the whole
computing task into parts that can be computed simultaneously and run
them physically on different CPU (computers). This is similar to putting
a jigsaw puzzle together with friends. As you can imagine having some
extra help will definitely help solve the puzzle faster, but do it mean
the more the better. The answer is no. As the number of helpers increase
the amount of coordination and communication increases faster. When you
have too many people they may start stepping on each other\'s toes and
competing with each other for resources (space and puzzle pieces). This
is known as the overhead of parallel processing, which causes the
diminishing return on investment. We can see this pattern clearly when
we measure the improvement in performance as a function of the workers
involved.

In the context of parallel processing/computing we use a metric called
speedup to measure the
improvement in performance. The achieved speedup equals the
solution/execution time of a program with out parallel processing
divided by the execution time of the same task with parallel processing.

$$S = \frac{T_{old}}{T_{new}}$$ **where:**

-   $S \$ is the speedup.
-   $T_{old} \$ is the old execution time without the parallel
    processing.
-   $T_{new} \$ is the new execution time with the parallel processing.

If parallel processing makes a program run twice as fast the speedup is
two (a.k.a two-fold speedup). Theoretically as we double the number of
workers or resources we can expect a two-fold speed up. Practically it
is hard to achieve this optimal speedup because some tasks are not
always parallelizable. For example you can not usually lay the carpet
before the floor of house is constructed and you cannot always add more
painters to get the painting job down faster. Computational tasks often
have similar dependency and resources constraints to keep us from fully
utilize the parallel processing systems (e.g. multi-core computers) we
have.

Exercise:

With a washing machine and a dryer you could work on one load of laundry
at time. You wash it first and then put it into the dryer. Assume the
whole task takes an hour. This works perfectly when you have only one
load to do and there is nothing you can do to make it go faster. What if
you have many loads of laundry to do? You can at least at one load done
every hour. Can you \"speed it up\"? If the number of loads can be
arbitrary larger what is shortest average per load laundry time you can
achieve?

