Parallel algorithms for asynchronous multiprocessors

The work presented in this thesis is mainly involved in the design and analysis of asynchronous parallel algorithms that can be run on MIMD type parallel computers, in particular the NEPTUNE system at Loughborough University. Initially, different types of existing parallel computers including the Data-Flow computers and VLSI technology are described from both the hardware and implementation points of view. Basic ideas of programming such computers are also outlined. Also, the main characteristics of the NEPTUNE MIMD-system are presented together with the principles of synchronisation, the resource demands and the overhead costs of the parallel control structures. Such information is measured frequently in the performance analysis of the algorithms presented in this thesis in order to exploit the potentiality of the NEPTUNE system and parallel computers in general. The Speed-up and Efficiency factors are calculated and the optimum number of processors and processes is suggested in most of the algorithms presented...