Parallel algorithm

A parallel algorithm, as opposed to a traditional serial algorithm, is one which can be executed a piece at a time in many different processing devices, and then put back together again at the end to get the correct result.

Some algorithms are easy to divide up into pieces like this. For example, splitting up the job of checking all of the numbers from one to a hundred to see if it is divisible by seven could be done by assigning a subset of the numbers to each available processor, and then putting the list of positive results back together.

Most of the available algorithms to compute Pi, on the other hand, could not be easily split up into parallel portions. Most of them require the results from a preceding step to effectively carry on with the next step.

Parallel algorithms are valuable because it is far easier to execute large computing tasks via a parallel algorithm than it is via a serial (non-parallel) algorithm, because of the way all modern processors work. It is, in general, far cheaper to buy twice as many processors than it is to buy a single processor which is twice as fast. There are also certain theoretical limits to the potential of serial processors.

(Someone please add appropriate links.) (Or, for that matter, replace it with a good one.)