Reference : Introduction to Parallel Computing, Edition Second by Vipin Kumar et al

Routing and Communication Costs

Routing Mechanism - path msg takes

• minimal: shortest path, Non-minimal: not shortest, for avoid network congestion.
• Deterministic Routing: Unique path determined solely on the source and destination processor - ignore the state of the network.
• Adaptive Routing : use information on the state of the network.

Review of SF and CT

Store and Forward (SF)

• Common on early parallel
• Forwards msg after the entire msg has been received and stored.
• t_h is substantially less.

$$t_c = t_s + (m * t_w + t_h) * l \approx t_s * mt_w * l$$

Cut-Through Routing

• msg is sent in fixed-length segments called flow-control digits or flits
• Wormhole routing pipelines the flits through the network.
• Uses less memory at the intermediate processor
• msg header = l * t_h to arrive.

$$t_c = t_s + l * t_h * tw$$

• cost is O(m+l) while O(m*l) for SF.

One-To-All Broadcast (OTAB) All-To-One Reduction (ATOR)

Ring or Linear Array

Recursive Doubling = 한곳으로 보내고 2명 2명이 2명에게 4명 4명이 4명에게….

Hence msg cab be broadcast in lg(p)

The destination node to each step to be sent must be carefully chosen to utilise the resources (avoid congestion on the network).

Reduction can be performed by reversing the direction and the sequence of communication —> will lead to the beginning node 0.

Mesh

• Can regard each row and col of a square mesh of p nodes as a linear array or sqrt(p) nodes.
• Perform like linear array on rows first, and do the same thing on the cols.
• Hence 16 nodes (4*4) will be sqrt(16) = 4 phases in one-to-all broadcast. In 3D —> p^(1/3)
• Reduction = same as linear array.

HyperCube

• 2^d hypercube = d-dimension mesh with two nodes in each d.
• Steps: d steps. 8 nodes (222) —> 3 steps.
• The dimension is identified by the MSB, while the order of visiting dimension does not affect the communication —> Means no congestion.

Balanced Binary Tree

• Hypercube OTA broadcast maps naturally onto it.

All-to-All Broadcast (ATAB) and Reduction (ATAR)

• Used in matrix operations.
• can be performed by p * OTAB or can be concatenated into one large message while traversing the network.

Linear Array and Ring

• Each node = initial node. Use one way and pass it to the neighbour. First send urs then start to send the latest msg u got from the neighbour. Hence takes p-1 steps (need to receive 7 info in 8 nodes)

Mesh

• Same as linear. Perform linear ATAB for rows and do cols.

Hypercube

• hypercube = extension of mesh to log(p) dimensions. takes log (p) steps.