Introduction to Multiprocessors - Fundamentals of Computer Organization and Architecture - page 250

introduced. The cosmic cube message-passing multiprocessor was designed at
Caltech during the period 1981-1985. It represented the first hypercube multi-
processor system that was made to work. Wormhole routing in message
passing was introduced in 1987 as an alternative to the traditional store-and-
forward routing in order to reduce the size of the required buffers and to
decrease the message latency. In wormhole routing, a packet is divided into
smaller units that are called flits (flow control bits) such that flits move in a
pipeline fashion with the header flit of the packet leading the way to the
destination node. When the header flit is blocked due to network congestion, the
remaining flits are blocked as well (see Chapter 5 of our topic on Advanced
Computer Architecture and Parallel Processing (see reference list) in Volume II
for more details).
The elimination of the need for a large global memory, which is usually a reason
for a slowdown of the overall system, together with its asynchronous nature, give
message-passing schemes an edge over shared-memory schemes. Similar to
shared-memory multiprocessors, application programs are divided into smaller
parts; each can be executed by an individual processor in a concurrent manner.
A simple example of a message-passing multiprocessor architecture is shown in
Figure 11.11. As can be seen from the figure, processors use local bus (internal chan-
nels) to communicate with their local memories while communicating with other
processors via an interconnection networks (external channels). Processes running
on a given processor use internal channels to exchange messages among themselves.
Processes running on different processors use external channels to exchange mess-
ages. Such a scheme offers a great deal of flexibility in accommodating a large
number of processors and being readily scalable. It should be noted that the process
and the processor, which executes it, are considered as two separate entities. The
size of a process is determined by the programmer and can be described by its granu-
larity, given by:

computation time
communication time

Granularity ¼

P 1 M 1 P n M n

Interconnection Network

Figure 11.11 Example of a message-passing multiprocessor architecture