Introduction to Message Passing

• A message passing architecture is used to communicate data among a set of processors without the need for a global memory.
• The elimination of the need for a large global memory together with its synchronization requirement, gives message passing schemes an edge over shared memory schemes.
• Each processor has its own address space. Nodes communicate with each other by
  • links (called external channels)
  • via an interconnection network, normally a static-type network.
    • In particular, hypercubes and the nearest-neighbor two-dimensional and three-dimensional mesh interconnection networks have received considerable attention over the years.
    • Two important factors must be considered in designing message passing interconnection networks:
      • link bandwidth; defined as the number of bits that can be transmitted per unit of time (bits/s).
      • network latency; defined as the time to complete a message transfer through the network.
• In executing a given application program, the program is divided into concurrent processes; each is executed on a separate processor.
• If the number of processes is larger than the number of processors, then more than one process will have to be executed on a processor in a time-shared fashion.
• Processes running on a given processor use what is called internal channels to exchange messages among themselves.
• Processes running on different processors use the external channels to exchange messages (see Fig. 2, in this figure, a horizontal line represents the execution of each process and lines extended among processes represent messages exchanged among these processes.).
• An important advantage of this form of data exchange is the elimination of the need for synchronization constructs, such as semaphores, which results in performance improvement.
• In addition, a message passing scheme offers flexibility in accommodating a large number of processors in addition to being readily scalable.

  Figure 2: An example of a message passing system.

  
• A message is defined as a logical unit for internode communication; it is considered as a collection of related information that travels together as an entity. A message can be
  • an instruction,
  • data,
  • synchronization,
  • interrupt signals.
• A message passing system interacts with the outside world by receiving input message(s) and/or outputting message(s). It is essential that the outside world perceives a consistent behavior of a given message passing system.
• Process Granularity; The size of a process in a message passing system can be described by a parameter called process granularity.
  
  $$Process~Granularity=\frac{computation~time}{communication~time}$$
  
  
  Three types of granularity can be distinguished. These are:
  1. Coarse granularity: Each process holds a large number of sequential instructions and takes a substantial amount of time to execute.
  2. Medium granularity: Since the process communication overhead increases as the granularity decreases, medium granularity describes a middle ground where communication overhead is reduced.
  3. Fine granularity: Each process contains a few sequential instructions (as few as just one instruction).
  Message passing multiprocessors uses mostly medium or coarse granularity.