Principles of Message-Passing Programming

Posted By on March 19, 2016

Download PDF
Other Scalability Metrics
The Building Blocks: Send and Receive Operations
  • There are two key attributes that characterize the message-passing programming paradigm.
  • The first is that it assumes a partitioned address space and the second is that it supports only explicit parallelization.
  • The logical view of a machine supporting the message-passing paradigm consists of p processes, each with its own exclusive address space.
  • Instances of such a view come naturally from clustered workstations and non-shared address space multicomputers.
  • There are two immediate implications of a partitioned address space.
  • First, each data element must belong to one of the partitions of the space; hence, data must be explicitly partitioned and placed.
  • This adds complexity to programming, but encourages locality of access that is critical for achieving high performance on non-UMA architecture, since a processor can access its local data much faster than non-local data on such architectures.
  • The second implication is that all interactions (read-only or read/write) require cooperation of two processes – the process that has the data and the process that wants to access the data.
  • This requirement for cooperation adds a great deal of complexity for a number of reasons.
  • The process that has the data must participate in the interaction even if it has no logical connection to the events at the requesting process.
  • In certain circumstances, this requirement leads to unnatural programs. In particular, for dynamic and/or unstructured interactions the complexity of the code written for this type of paradigm can be very high for this reason.
  • However, a primary advantage of explicit two-way interactions is that the programmer is fully aware of all the costs of non-local interactions, and is more likely to think about algorithms (and mappings) that minimize interactions.
  • Another major advantage of this type of programming paradigm is that it can be efficiently implemented on a wide variety of architectures.
  • The message-passing programming paradigm requires that the parallelism is coded explicitly by the programmer.
  • That is, the programmer is responsible for analyzing the underlying serial algorithm/application and identifying ways by which he or she can decompose the computations and extract concurrency.
  • As a result, programming using the message-passing paradigm tends to be hard and intellectually demanding.
  • However, on the other hand, properly written message-passing programs can often achieve very high performance and scale to a very large number of processes.
  • Structure of Message-Passing Programs Message-passing programs are often written using the asynchronous or loosely synchronous paradigms.
  • In the asynchronous paradigm, all concurrent tasks execute asynchronously.
  • This makes it possible to implement any parallel algorithm.
  • However, such programs can be harder to reason about, and can have non-deterministic behavior due to race conditions.
  • Loosely synchronous programs are a good compromise between these two extremes.
  • In such programs, tasks or subsets of tasks synchronize to perform interactions.
  • However, between these interactions, tasks execute completely asynchronously.
  • Since the interaction happens synchronously, it is still quite easy to reason about the program.
  • Many of the known parallel algorithms can be naturally implemented using loosely synchronous programs.
  • In its most general form, the message-passing paradigm supports execution of a different program on each of the p processes.
  • This provides the ultimate flexibility in parallel programming, but makes the job of writing parallel programs effectively unscalable.
  • For this reason, most message-passing programs are written using the single program multiple data (SPMD) approach.
  • In SPMD programs the code executed by different processes is identical except for a small number of processes (e.g., the “root” process).
  • This does not mean that the processes work in lock-step. In an extreme case, even in an SPMD program, each process could execute a different code (the program contains a large case statement with code for each process).
  • But except for this degenerate case, most processes execute the same code. SPMD programs can be loosely synchronous or completely asynchronous.
Other Scalability Metrics
The Building Blocks: Send and Receive Operations

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby