Unit II — Parallel Architecture

Interconnection Networks

Session 04 • 2311CSC501J — Parallel Processing

What You'll Learn

Why communication, not computation, becomes the bottleneck
Static (direct) vs dynamic (switched) networks
Bus, crossbar, mesh, torus, hypercube
Degree, diameter & bisection bandwidth

"You can hire the fastest workers in the world — but if they're stuck in traffic reaching each other, they get nothing done. Today we design the roads."

— the whole session in one line

Computation Is Cheap; Communication Is Expensive

A core does billions of adds a second. An add of two numbers already in registers is basically free. Moving data is not — and it costs more the farther the data must travel.

Operation	Relative cost
Add two numbers already in registers	1
Read from L1 cache	~3–4
Read from main memory	~100
Message to a core on another chip	~1,000+
Message to another machine	~10,000+

Past a certain scale, your machine's speed isn't set by how fast the cores compute — it's set by how fast they can talk. The interconnection network is the bottleneck.

Two Families: Static vs Dynamic

Static (direct)

Nodes wired directly to each other with fixed links. A node's neighbors never change — the map is baked into the hardware.

Mesh, torus, hypercube. A fixed road map between towns.

Dynamic (switched)

Nodes connect through switches that can be reconfigured to route any input to any output. Paths are set up on demand.

Bus, crossbar, Omega. A telephone exchange.

   STATIC (direct)                     DYNAMIC (switched)
   nodes wired to nodes                nodes wired to switches

   ( P )---( P )---( P )               ( P )   ( P )   ( P )
     |       |       |                    \      |      /
   ( P )---( P )---( P )                 [ switching fabric ]
     |       |       |                    /      |      \
   ( P )---( P )---( P )               ( P )   ( P )   ( P )

Bus — One Shared Line

   ( P1 )   ( P2 )   ( P3 )   ( P4 )
      |        |        |        |
   ===+========+========+========+===   <- one shared bus

Pros

Minimal wiring, dead simple, cheap. Easy to add a node — just tap the wire.

Cons

Only one talker at a time. Everyone contends for the same wire — it does not scale.

Analogy: one microphone passed around a room. Only one person speaks; everyone else waits. (In systems: a single shared message queue or one database everyone hits.)

Crossbar — Every Input to Every Output

          out1   out2   out3   out4
   in1 ----X------X------X------X----
   in2 ----X------X------X------X----
   in3 ----X------X------X------X----
   in4 ----X------X------X------X----
        (each X is a switch that can connect)

Pros

Non-blocking and fast. Many pairs communicate at once with no waiting.

Cons

Cost grows as N². 1,000 nodes = a million switches. Doesn't scale economically.

Analogy: an old telephone switchboard — any caller patched straight to any line. (In systems: a full service mesh where everything talks directly to everything.)

Multistage (Omega) — The Compromise

Instead of one giant N² crossbar, build log₂(N) stages of tiny 2×2 switches. A message is routed by its destination address, one bit per stage.

   Omega network, N = 8  (3 stages of 2x2 switches)

   in0 --[S]--[S]--[S]-- out0
   in1 --[S]--[S]--[S]-- out1
   in2 --[S]--[S]--[S]-- out2
   in3 --[S]--[S]--[S]-- out3
   in4 --[S]--[S]--[S]-- out4
   in5 --[S]--[S]--[S]-- out5
   in6 --[S]--[S]--[S]-- out6
   in7 --[S]--[S]--[S]-- out7
        stage1 stage2 stage3   (log2(8) = 3 stages)

About (N/2)·log₂(N) switches instead of N² — far cheaper. The catch: it's blocking, so some simultaneous messages collide inside the fabric. A middle path between the cheap-slow bus and the fast-expensive crossbar.

Mesh — A 2D Grid

   ( P )--( P )--( P )--( P )
     |      |      |      |
   ( P )--( P )--( P )--( P )
     |      |      |      |
   ( P )--( P )--( P )--( P )
     |      |      |      |
   ( P )--( P )--( P )--( P )

Pros

Scales beautifully. Wiring grows linearly; every link is short (easy to etch in silicon). The workhorse of Network-on-Chip.

Cons

Corner-to-corner takes many hops — the diameter grows as √N. Edge nodes have fewer links.

Analogy: city blocks on a grid — to cross town you drive block by block.

Torus — A Mesh with Wrap-Around

   Torus = mesh + wrap-around links

    +--( P )--( P )--( P )--( P )--+
    |    |      |      |      |    |   <- top wraps to bottom
    +--( P )--( P )--( P )--( P )--+
    |    |      |      |      |    |
    +--( P )--( P )--( P )--( P )--+
         (left column wraps to right column)

Join the opposite edges. Now every node has the same degree, and the longest path is roughly halved. Shorter average distance, no lonely edge nodes.

Real machines: Cray, IBM Blue Gene (3D/5D torus), Fujitsu's K computer and Fugaku (6D torus). Analogy: Pac-Man — walk off the right edge, reappear on the left.

Hypercube — An n-Dimensional Cube

Give each node an n-bit label. Connect two nodes if and only if their labels differ in exactly one bit. That single rule gives 2ⁿ nodes, each with n neighbors.

   3-D hypercube (n = 3, 2^3 = 8 nodes)

        110 ------- 111
        /|          /|
     100 ------- 101 |
      |  |        |  |
      | 010 ------|- 011
      |/          |/
     000 ------- 001

   Route 000 -> 111: flip one bit at a time
   000 -> 001 -> 011 -> 111   (3 hops = n)

Pros

Very low diameter (only log₂N hops), high bisection, elegant bit-flip routing.

Cons

Node degree = n grows with the machine. A 1,024-node cube needs 10 links per node.

How We Compare Networks: The Metrics

Degree

Links per node. Lower = cheaper, simpler node.

Diameter

Worst-case hops between the two farthest nodes. The headline latency number.

Bisection bandwidth

Min links cut to split the network in half. The number for all-to-all traffic.

There is no free network. Low diameter & high bisection cost you either money (the crossbar) or node degree (the hypercube). Cheap, buildable networks (bus, mesh) pay with a bigger diameter.

The Comparison Table (Know This Cold)

For N nodes (mesh/torus as a √N × √N grid; hypercube as n = log₂N dimensions):

Topology	Degree	Diameter	Bisection	Scales?
Bus	1	1	1	No — one talker
Crossbar	N/side	1	N/2	No — N² cost
Mesh	2–4	2(√N − 1)	√N	Yes
Torus	4	2·⌊√N/2⌋	2√N	Yes
Hypercube	log₂N	log₂N	N/2	Yes, to a limit

A bus looks great on diameter but bisection 1 kills it. A crossbar is perfect but N². Mesh & torus trade a growing diameter for cheap wiring. Hypercube buys a tiny diameter with growing degree.

Where This Shows Up in Real Machines

Network-on-Chip

Many-core CPUs & GPUs wire cores as a mesh or ring on the silicon, with a tiny router at each core. A shared bus would choke.

Supercomputers

Fugaku — 6D torus. Blue Gene — 3D/5D torus. Crays — torus & Dragonfly. At 100,000+ nodes, the topology is the machine.

Data centers

Google, Meta, Amazon build fat-tree / Clos fabrics so any server reaches any other at full bandwidth. Bisection is the metric they obsess over.

Core-to-core on a chip → chip-to-chip in a server → server-to-server in a rack → rack-to-rack in a data center. The same problem at every level — how do the workers reach each other without the network becoming the bottleneck?

Recap & What's Next

Key Takeaways

Past a certain scale, communication — not computation — is the bottleneck.
Networks are static (direct: mesh, torus, hypercube) or dynamic (switched: bus, crossbar, Omega).
Compare them with degree, diameter, and bisection bandwidth.
No free network: low diameter/high bisection costs money (crossbar) or node degree (hypercube).
Same idea from NoC on a chip → torus in a supercomputer → fat-tree in a data center.

Homework

Look up one TOP500 supercomputer's interconnect; write 3–4 sentences on it.
Draw a 3D hypercube with binary labels; mark a 3-hop route 000 → 111.
Come ready: "Two cores each cache the same variable; one changes it — how does the other find out?"

Next session: Memory Hierarchy & Cache Coherence

Shared memory sounds simple — until every core caches its own copy of the same variable.