L11: Interconnection Network

Sorting a Linear Array

Odd-Even Transposition Sort (1D)

Shear Sort Algorithm (2D)

1. Row Sorting:
   • Odd Rows sort in ascending order
   • Even Rows sort in descending order
2. Column Sorting: All columns sort in ascending order (top to bottom)
3. Repeat until sorted

Step 0

Step 1

Step 2

Step 3

Step 4

Step 5 - Sorted (snake-like arrangement)

Complexity: $O(n^\frac{1}{2} (\log_2 {n + 1}))$

Interconnection Network Impact

• System scalability – size and extensibility
• System performance and energy efficiency
  • Communication speed
  • Latency to memory
  • Energy spent to communicate

Topology

Direct Interconnection

Indirect Interconnection

Direct Interconnection

• Also known as Static or Point-to-Point
• Usually endpoints are of the same type (core, memory)

Indirect Interconnection:

• Also known as Dynamic Interconnect is formed by switches
• Topology can be modeled as a Graph: G = (V, E), V = vertices; E = edges
• Metrics: Diameter, Degree, Bisection Width, Connectivity

Direct Interconnection

Diameter: Diameter $\delta(G)$: maximum distance between any pair of nodes

$$\delta(G) = \max_{u,v \in V}(\min_{\substack{\phi\text{ path from u to v}}} \set{k | k \text{ is the length of the path from u to v}})$$

• Usefulness: Small diameter ensures small distances for message transmission

Degree:

• Degree g(v): number of direct neighbour nodes of node v
• Degree g(G): maximum degree of a node in a network G

$$g(G) = max\set{g(v) | g(v) \text{ degree of } v\in V}$$

• Usefulness: Small node degree reduces the node hardware overhead

Bisection Width:

• Bisection width B(G): minimum number of edges that must be removed in to divide the network into two equal halves

$$B(G) = \min_{\substack{U_1,U_2\text{ partition of V}\\[2px] |\left|U_1| - |U_2|\right| \leq 1}} \left| \set{(u, v)\in E | u \in U_1, v\in U_2} \right|$$

• Bisection bandwidth BW(G): Total bandwidth available between the two bisected portion of the network
• Usefulness: a measure for the capacity of a network when transmitting messages simultaneously

Connectivity:

• Node connectivity: nc(G) – minimum number of nodes that must fail to disconnect the network

  $$nc(G) = \min_{M\subset V}\set{\lvert M\rvert | \exists u, v\in V, s.t.; \nexists\text{ path in } G_{V\setminus M}\text{ from $u$ to $v$}}$$
  • Usefulness: Determine the robustness of the network

• Edge connectivity: ec(G) – minimum number of edges that must fail to disconnect the network

  $$ec(G) = \min_{F\subset E}\set{\lvert F\rvert | \exists u, v\in V, s.t.; \nexists\text{ path in } G_{E\setminus F}\text{ from $u$ to $v$}}$$
  • Usefulness: Determine number of independent paths between any pair of nodes

Basic Networks

Mesh Networks - d-dimension: #nodes n = r^d

Complete Binary Tree

Hypercube Networks

Cube-Connected-Cycles (CCC):

Cube-Connected-Cycles (CCC)

• From a k-dimensional hypercube (k ≥ 3), substitute each node with a cycle of k-nodes
  • Each of the k-nodes take one of the original k links
  • Total nodes = $k2^k$

Metrics of Cube-Connected-Cycles (CCC)

• Each node in a k-dimensional CCC is labeled as (X, Y)
  • X = the corresponding node index in hypercube
  • Y = the position in the cycle, i.e. 0…k-1
• Node (X, Y) is connected to:
  • $(X, (Y+1)\mod k)$
  • $(X, (Y-1)\mod k)$
  • $(X\oplus2^Y, Y)$, where $\oplus$ is bitwise XOR (flip the ith significant bit)

Summary of Metrics

Indirect Interconnection

• Why: Reduce hardware costs by sharing switches and links
• How: Switches provide indirect connection between nodes and can be configured dynamically
• Metric: Cost (number of switches / links), Concurrent connections

Bus Network:

Bus Network

• A set of wires to transport data from a sender to a receiver
• Only one pair of devices can communicate at a time
  • A bus arbiter is used for the coordination
  • Typically used for a small number of processors

Crossbar Network:

Crossbar Network

• A n × m crossbar network has n inputs and m outputs
• 2 states of a switch: straight or direction change
• Hardware is costly (n x m switches) → small number of processors

Multistage Switching Network

Multistage Switching Network

• Several intermediate switches with connecting wires between neighbouring stages
• Goal: obtain a small distance for arbitrary pairs of input and output devices

Omega Network:

Omega Network

• One unique path for every input to output

• An n × n Omega network has log n stages

  • n/2 switches per stage, each switch has 2 input and 2 output links
  • Connections between stages are regular
  • Also known as (lg n – 1) – dimension Omega Network

• A switch position: (α, i)

  • α: position of a switch within a stage; i: stage number

• Has an edge from node (α, i) to two nodes (β,i + 1) where

  • β = α by a cyclic left shift
  • β = α by a cyclic left shift + inversion of the LSBit

Omega Network Example

• Omega Network vs Crossbar Switches: To connect 16 processor nodes to 16 memory nodes
  • Crossbar = 16 x 16 = 256 switches
  • Omega: n=16 and using 2x2 switches
    • Total number of switches = n/2 switches per stage * log n stages
    • 32 switches

Butterfly Network:

Butterfly Network

• Node (α, i) connects to
  • (α, i+1), i.e. straight edge
  • (α’, i+1), α and α’ differ in the (i + 1)th bit from the left, i.e. cross edge

Baseline Network: k stages

Baseline Network

• Node (α, i) to two nodes (β, i + 1) where
  • β = cyclic right shift of last (k-i) bits of α
  • β = inversion of the LSBit of α + cyclic right shift of last (k - i) bits

Other networks: Beneš network, Clos network, Fat-Tree, Folded Butterfly, etc

Routing

Note

💡 Routing algorithm determines path(s) from source to destination within a given interconnection topology

Classification:

• Based on path length: Minimal or Non-minimal routing: whether the shortest path is always chosen
• Based on adaptivity:
  • Deterministic: Always use the same path for the same pair of (source, destination) node
  • Adaptive: May take into account of network status and adapt accordingly, e.g. avoid congested path, avoid dead nodes etc

XY Routing for 2D Mesh

XY Routing for 2D Mesh

(X_src, Y_src) to (X_dst, Y_dst):

• Move in X direction until X_src == X_dst
• Move in Y direction until Y_src == Y_dst

E-Cube Routing for Hypercube

E-Cube Routing for Hypercube

Let $(\alpha_{n-1}\alpha_{n-2}\dots\alpha_1\alpha_0)$ and $(\beta_{n-1}\ \beta_{n-2}\dots\beta_1\beta_0)$ be the bit representations of source and destination node address respectively:

• Number of bits difference in source and target node address → number of hops (i.e. hamming distance)

• Start from MSB to LSB (or LSB to MSB)

  • Find the first different bit

  • Go to the neighboring node with the bit corrected

    → At most n hops

XOR-Tag Routing for Omega Network

XOR-Tag Routing for Omega Network

• Let T = Source Id ⊕ Destination Id
• At stage-k:
  • Go straight if bit k of T is 0
  • Crossover if bit k of T is 1

Current Trends

Ethernet

• Support point-to-point and broadcast
• Commonly-used topologies: physical bus, physical star with a logical bus, etc

Bus Topology

Star Topology

InfiniBand

• Support point-to-point and multicast (on top of point-to-point capabilities)
• Commonly-use topologies: Fat tree , torus, etc.

Fat Tree Topology

Torus Topology