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.)

Worked Example: The Moment the Bus Saturates

A shared bus delivers 10 GB/s in total. Each core needs 2 GB/s to run at full speed. Watch what happens as we add cores.

Cores	Bandwidth wanted	Each core actually gets	Each runs at	Total useful work
1	2 GB/s	2 GB/s	100%	1.0×
4	8 GB/s	2 GB/s	100%	4.0×
5	10 GB/s	2 GB/s	100%	5.0× — exactly saturated
8	16 GB/s	1.25 GB/s	63%	5.0×
16	32 GB/s	0.63 GB/s	31%	5.0×
64	128 GB/s	0.16 GB/s	8%	5.0× — still

Read the last column downwards. After 5 cores it never changes again. Cores 6 through 64 contribute exactly zero. You are paying for 64 cores and running at the speed of 5.

Notice the shape of that flatline. It is Amdahl's Law wearing a hardware costume — a single shared resource that everything must pass through caps the whole system, no matter how much you add around it. In Session 01 the bottleneck was un-splittable code; here it's a wire.

This is why the bus died. It worked beautifully for 2 and 4 cores in the 1990s. It cannot be made to work for 64. And it's why every network after this slide is an attempt to escape the single shared line.

Where you meet this today: a single database that every microservice talks to. Same graph, same flatline, same fix — stop making everything cross one shared thing.

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.

Worked Example: Routing Through a Hypercube

In a hypercube, two nodes are neighbours exactly when their addresses differ in one bit. That one rule gives you the entire routing algorithm for free.

Send from node 0110 to node 1011 in a 16-node (4-dimensional) hypercube.

Step 1 — XOR the two addresses to find what must change:

        source       0110
        destination  1011
        XOR          1101     <-- bits 3, 2 and 0 differ

Step 2 — the number of 1s is the distance:  3 hops. Done. No map needed.

Step 3 — walk it, flipping one differing bit per hop (lowest first):

        0110  --flip bit 0-->  0111
        0111  --flip bit 2-->  0011
        0011  --flip bit 3-->  1011   arrived

Look at what a router has to store to do this: nothing. No routing table, no map of the network, no coordination. Every node computes my_address XOR destination, flips the lowest set bit, and forwards. That is the whole algorithm, and it works for a 4-node cube or a 4-million-node cube.

Why this is such a big deal — and why we still don't use it

1,024 nodes, arranged as…	Worst-case hops	Links per node
A single bus	1	1 — but zero parallelism
A 32×32 mesh	62	4 — always 4
A 32×32 torus	32	4 — always 4
A 10-dimensional hypercube	10	10 — and it grows

The hypercube wins on hops by 6× — and loses on buildability. Its degree is log₂N, so it changes as the machine grows: a million-node hypercube needs 20 cables out of every node. You cannot design one board and mass-produce it, and you cannot add a node without rewiring.

A mesh or torus has degree 4, forever. One board design, buy 100,000 of them, bolt them together. That is why the machines on the Top500 list are meshes, tori and dragonflies — and why hypercubes, which are prettier, lost.

Exam note: "given source and destination in a hypercube, give the route and the number of hops" is a standard question. The answer is always: XOR, count the 1s, flip them one at a time.

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.

Your Turn: Pick the Network

In pairs, 6 minutes. Which topology, and which metric drove your answer? The second half is the real question.

1. Connect 8 GPUs on one server board

Crossbar. N is tiny, so N² = 64 is cheap, and you want zero blocking. This is literally what an NVSwitch is.

2. Connect 100,000 nodes in a supercomputer

Torus (or dragonfly). Degree drives it: you need a node design that stays the same at any scale. Diameter is bad and you accept that.

3. A weather simulation where each cell only ever talks to its 4 neighbours

Mesh — and here's the point: diameter doesn't matter at all. No message ever travels more than one hop. Match the topology to the communication pattern, not to the leaderboard.

4. A sort where every node sends data to every other node

Whatever maximises bisection width — fat tree or hypercube. All-to-all traffic is exactly the case bisection width measures, and a mesh will choke.

5. The one worth arguing about: 4 microservices, all reading one Postgres database

You have built a bus — and it will saturate exactly like slide 6. Read replicas = adding paths. Sharding = moving to a distributed topology. You have been designing interconnection networks your whole career; nobody called them that.

The takeaway, if you remember one line from today: there is no best topology. There is only the cheapest topology whose weak metric your traffic pattern happens not to care about.

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.