Editing Parallel algorithm (section)

==Issues==

===Communication===
The cost or complexity of serial algorithms is estimated in terms of the space (memory) and time (processor cycles) that they take. Parallel algorithms need to optimize one more resource, the communication between different processors. There are two ways parallel processors communicate, shared memory or message passing.

[[Shared memory]] processing needs additional [[lock (computer science)|locking]] for the data, imposes the overhead of additional processor and bus cycles, and also serializes some portion of the algorithm.

[[Message passing]] processing uses channels and message boxes but this communication adds transfer overhead on the bus, additional memory need for queues and message boxes and latency in the messages. Designs of parallel processors use special [[bus (computing)|buses]] like [[crossbar switch|crossbar]] so that the communication overhead will be small but it is the parallel algorithm that decides the volume of the traffic.

If the communication overhead of additional processors outweighs the benefit of adding another processor, one encounters [[parallel slowdown]].

===Load balancing===
{{main|Load balancing (computing)}}
Another problem with parallel algorithms is ensuring that they are suitably [[load balancing (computing)|load balanced]], by ensuring that ''load'' (overall work) is balanced, rather than input size being balanced. For example, checking all numbers from one to a hundred thousand for primality is easy to split among processors; however, if the numbers are simply divided out evenly (1–1,000, 1,001–2,000, etc.), the amount of work will be unbalanced, as smaller numbers are easier to process by this algorithm (easier to test for primality), and thus some processors will get more work to do than the others, which will sit idle until the loaded processors complete.