Next: Routing Potential Problems
Up: Routing in Message Passing
Previous: Routing in Message Passing
Contents
Routing for Broadcasting and Multicasting
- There are two types of communication operations in message passing systems,
- one-to-one (point-to-point or unicast), a node is allowed to communicate a message to only a single destination, which may
be its immediate neighbors.
- collective communications, a number of routing operations are defined under collective communication.
- Among these, broadcast and multicast are the most widely
used.
- In broadcast, also known as the one-to-all operation, one node sends the same message to all other nodes. Broadcast is mainly used to distribute data from one node to others during computation
of a distributed memory program.
- In multicast, also known as the one-to-many operation, one node sends its messages to
distinct destinations. Multicast has several uses in large-scale multiprocessors, including parallel search algorithms and single program multiple data (SPMD) computation.
- Practical broadcast and multicast routing algorithms must be deadlock-free and should transmit the message to each destination
node in as little time and using as short a path as possible.
- One technique to achieve this is to deliver the message along a common path to as many destinations as possible
- and then replicate the message and forward each copy on a different channel band for a unique set of destination nodes.
- The path followed by each copy may further branch in this manner until the message is delivered to every destination node.
- In such a tree-based communication model, the destination set is partitioned at the source and separate copies are sent on one or more outgoing links.
- A message may be replicated at intermediate nodes and forwarded along multiple outgoing links towards disjoint subsets of destinations.
Figure 6.3:
Hypercube broadcast tree-based communication.
|
- Another method to implement a multicast operation uses separate addressing.
- In this case, a separate copy of the message is sent directly from the source to every destination. Clearly, this is an inefficient
technique.
A hypercube broadcast tree-based nearest-neighbor communication is shown in Fig. 6.3.
Next: Routing Potential Problems
Up: Routing in Message Passing
Previous: Routing in Message Passing
Contents
Cem Ozdogan
2006-12-27