Parallel algorithm
|
|
In computer science, 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. Technically, it is far more difficult to construct a fast single processor than have many but slow processors with the same throughput. There are also certain theoretical limits to the potential of serial processors.
A subtype of parallel algorithms, distributed algorithms are algorithms designed to work in cluster computing and distributed computing environments where additional concerns over "classical" parallel algorithms need to be addressed.
See also: multiple agent system (MAS), neural network
External links
- Parallel Algorithm Design (http://www.dcs.ed.ac.uk/home/stg/pub/P/par_alg.html)
- Designing and Building Parallel Programs page at the US Argonne National Laboratories (http://www-unix.mcs.anl.gov/dbpp/)