A Model of Efficient Asynchronous Parallel Algorithms on Multicomputer Systems

This paper describes a methodology for the implementation of asynchronous parallel algorithms on multicomputer systems. The algorithms studied here belong to the class of iterative methods. The proposed methodology is based on the definition of a computational model by which an algorithm is specified as a set of concurrent processes mapped onto a set of processors and communicating by asynchronous message passing. This approach can be appealing and innovative since there is a need to reduce the cost of synchronization that affects synchronous algorithms. As an application of the proposed approach, the implementation on a network of INMOS Transputers of an asynchronous parallel version of the classical Newton method for solving nonlinear optimization problems is described and discussed. In this implementation each computational task of the algorithm is implemented as an Occam process running on a Transputer. The performance results of the numerical experiments are encouraging and show the effectiveness of the proposed approach.