F. C. Langbein, Teilweise Asynchrone Algorithmen [Partially Asynchronous Algorithms]. Parallel Computing Seminar, Second Chair, Mathematical Institute A, Stuttgart University, February 1996. [PDF] [LaTeX (tar.gz)]
There are several issues related to classical (as opposed to quantum parallelism) parallel computing that do not apply to serial computing. One is task allocation, i.e. the splitting of the total workload into smaller tasks which are then solved sequentially. Another one is the communication of interim results between processors. Both issues largely determine the speed of parallel algorithms. A third issue is the synchronisation between computations on different processors. We can either completely synchronise the processors such that they have to wait at predetermined points for the results of certain computations or we can construct the algorithms such that no explicit synchronisation is necessary (lock-free algorithms). A third option is to run the processors asynchronously without waiting for the results from other processors. This issue is related to the convergence of parallel methods and the correctness of the results. In particular if the delays have an upper limit, this rises interesting algorithmic problems.
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.