Topology

Stephen M. Reaves

2024-10-29

Notes about Lecture 7 for CS-6220

Required Readings

Diameter
Take all pairs of nodes, compute the shortest path, then find the longest shortest path.

Type	Links ( $\lambda$ )	Diameter ( $\Delta$ )
Linear	$P-1$	$P-1$
Mesh	$2\left( \sqrt{P} - 1 \right) \sqrt{P} \approx 2P$	$2\left(\sqrt{P} - 1\right)$
Fully connected	$\frac{P\left(P-1\right)}{2}$	$1$

You care about the number of links because its a proxy for cost

Diameter is a proxy for the longest distance any message may travel in the absense of network contention

bisection width
Minimum number of links to remove to cut network in half

In all-to-all personalized exchanges, all communication will go through bisection.

bisection bandwidth
Assuming all links have equal speed, bisection bandwidth is the product of bisection width and link speed.

What happens when you design an algorithm for a linear topology but it runs on something like a mesh?

If the links of the physical network are a superset of the logical network, there will be no (extra) contention caused by the mapping

congestion
Maximum number of logical edges that map to a physical edge

A lower bound of congestion is the logical bisection width divided by physical bisection width.