Parallel Asynchronous Algorithms I. Modelling and Analysis

The first computers were essentially made up of a memory for storing computer programs and the data they required, an arithmetic and logic unit for performing these types of operations, and exchange units for peripheral devices (disks, printers, etc.). Because of the presence of a single arithmetic and logic unit, on this type of architecture, a calculation code is executed in sequential mode on this single resource; this corresponds to the execution of instructions one after the other, so only one at a time, even if the operations to be performed are independent. This type of sequential execution has rapidly reached its performance limits when the calculation does not allow results to be obtained within a reasonable timeframe, and requires significant memory storage. Thus, for calculations required to handle large applications, such as meteorology, this type of sequential programming is no longer suitable, and calculation performance is not satisfactory for obtaining simulation results in relatively short times.

To overcome these limitations, parallel computing has emerged as a solution. To improve computer performance, this solution involves making the best possible use of computing and memory resources. The solution adopted is to parallelize codes, i.e. to perform several calculations simultaneously on different resources, each consisting of an arithmetic and logic unit, also known as a processor, so that a greater number of operations can be performed in a minimum amount of time. To parallelize a calculation code, the user has to break down the overall problem into several smaller, coupled sub-problems. In this way, several computational tasks can be processed simultaneously on these processors, with the coupling between sub-problems being effected by exchanges of results between the processes cooperating in parallel. In this way, provided the parallelized calculation codes are optimized, execution times can be significantly reduced, enabling larger problems to be solved and larger volumes of data to be processed.

This new computing mode requires us to question the architecture of early computers, to adapt the computing program to a parallel execution mode, and to learn new programming languages and tools.

The architectures of these supercomputers have therefore evolved firstly by building machines with common memory, where all processors have access to the latter. However, this type of machine is both expensive to build and doesn't offer the massive parallelism required for large-scale applications. Manufacturers have therefore designed machines with distributed memory, where each processor has its own local memory, with links between these processors via an interconnection network; the latter enables messages to be exchanged between...