Parallel computing

Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain faster results.

Algorithms

It should not be imagined that successful parallel computing is a matter of obtaining the required hardware and connecting it suitably. The difficulty of cooperative problem solving is aptly demonstrated by the following dubious reasoning:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:If it takes one man one minute to dig a post-hole then sixty men can dig it in one second.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In practice, linear speedup (i.e., speedup proportional to the number of processors) is very difficult to achieve. This is because many algorithms are essentially sequential in nature (Amdahl's law states this more formally).

Related Topics:
Speedup - Amdahl's law

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Up to a certain point, certain workloads can benefit from pipeline parallelism when extra processors are added. This uses a factory assembly line approach to divide the work. If the work can be divided into n stages where a discrete deliverable is passed from stage to stage, then up to n processors can be used. However, the slowest stage will hold up the other stages so it is rare to be able to fully use n processors.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Most algorithms must be redesigned in order to make effective use of parallel hardware. Programs which work correctly in a single CPU system may not do so in a parallel environment. This is because multiple copies of the same program may interfere with each other, for instance by accessing the same memory location at the same time. Therefore, careful programming is required in a parallel system.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Superlinear speedup - the effect of a N processor machine completing a task more than N times faster than a machine with a single processor similar to that in the multiprocessor has at times been a controversial issue (and lead to much benchmarking) but can be brought about by such effects as

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

the multiprocessor machine having not just N times the processing power but also N times cache and memory thus flattening the cache-memory-disk hierarchy, more efficient use of memory by the individual processors due to partitioning of the problem and a number of other effects. Similar boosted efficiency claims are sometimes aired for the use of a cluster of cheap computers as a replacement of a large multiprocessor, but again the actual results depend much on the problem at hand and the ability to partition the problem in a way that is conductive to clustering.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~