ABSTRACT
On distributed memory computers, the memory of a node is directly accessible only to the processes running on that node, and message-passing is the primary means for exchanging data between processes running on different nodes. Most parallel algorithms for distributed memory computers therefore use a programming model, the message-passing paradigm, in which processes exchange data by explicitly sending and receiving messages. Except for trivially parallel computational problems in which the processes can work completely independently of each other, parallel applications involve some data exchange between processes, and often a significant amount of communication is required. For instance, data needed by a process may have to be retrieved from a remote memory location associated with another process, or a manager process in charge of distributing and scheduling work will need to communicate with other processes to do so. The use of message-passing in a parallel program may affect the parallel performance in several ways. For example, the communication overhead (the time required to perform the communication) may be significant and may grow as the number of processes increases, and the presence of communication steps may require synchronization of all processes, which forces some processes to be idle while waiting for other processes to catch up.
