Question bank — Network-on-Chip (NoC) topologies

T/F — A torus always halves the latency of the same-size mesh. False ::: It roughly halves the diameter (worst hops), but its wraparound wires are physically long, so each hop can cost more cycles and more power — end-to-end latency is not simply halved. Latency and Throughput Trade-offs makes this precise: latency = (hops) × (per-hop cost) + queueing, and only the first factor shrinks.

T/F — A hypercube always beats a mesh because its diameter is ${\log }_{2}N$. False ::: Diameter is only one axis. Hypercube degree grows as ${\log }_{2}N$ (each new dimension adds a port to every node), so routers get more ports (area, power, wiring), and the graph is non-planar — hard to lay out on flat silicon. "Better diameter" is not "better chip".

T/F — A ring has terrible bisection bandwidth no matter how many nodes it has. True ::: Cut a ring anywhere and you always sever exactly two links, so $B_b=2B_{\text{link}}$ regardless of $N$ — the throat never widens as you add nodes, which is why it chokes.

T/F — Adding more links to a topology can only help performance. False ::: Every extra link is an extra router port costing area, power, and control complexity; a 16-port router is far larger than a 4-port one. Past a point, the power/area budget is better spent on cache or cores.

T/F — In a mesh, every node behaves identically. False ::: Interior nodes have degree 4, but edges have 3 and corners only 2 — this asymmetry means edge nodes have fewer paths and different congestion, so performance is not uniform.

T/F — A torus fixes the mesh's node-asymmetry problem. True ::: Wraparound links give every node degree 4, so all nodes are topologically equal — that uniformity is a real advantage for evenly-spread traffic.

T/F — A fat-tree removes the classic tree's root bottleneck. True ::: A plain tree funnels all cross-network traffic through one thin root link. A fat-tree widens links toward the root so every horizontal cut carries the same bandwidth — that is the entire point of "fat".

T/F — Bisection bandwidth and diameter measure the same thing. False ::: Diameter is a latency quantity (worst-case hop count for one packet); bisection bandwidth $B_b$ is a throughput quantity (aggregate data across a cut). A ring has small-ish diameter yet dreadful bisection — they can disagree sharply.

T/F — The hypercube's bisection bandwidth of $N/2$ links makes it wire-cheap. False ::: High bisection means lots of wires must cross the midline — that is bandwidth-rich but wire- and power-expensive, the opposite of cheap. High bisection is a cost, not a discount.

"An $8\times 8$ mesh has diameter $\lfloor 8/2\rfloor +\lfloor 8/2\rfloor =8$." Error ::: That is the torus formula. A mesh has no wraparound, so its diameter is $(N-1)+(M-1)=(8-1)+(8-1)=14$; the $\lfloor N/2\rfloor$ shortcut only exists when you can wrap around.

"A ring of 8 nodes has diameter 8 because there are 8 nodes." Error ::: You can travel either direction around the ring, so worst case is only half-way: $\lfloor 8/2\rfloor =4$ hops. Forgetting the two-directions option double-counts the distance.

"In a hypercube, routing from node 3 to node 12 takes as many hops as the numeric difference $12-3=9$." Error ::: Distance is the number of differing bits (Hamming distance), not numeric subtraction. $0011\oplus 1100=1111$ → 4 bits differ → 4 hops, not 9. Choosing which bit to flip when several differ is exactly what Routing Algorithms decide.

"A fat-tree's leaves and root should use the same link width to keep it simple." Error ::: Equal widths recreate the root bottleneck a fat-tree exists to remove. Link bandwidth must grow toward the root (doubling per level in a binary fat-tree) to keep every cut equally wide.

"Bisection bandwidth of a $4\times 4$ torus equals the mesh's, since both cut 4 columns." Error ::: The torus also cuts the wraparound links, so a bisection severs $2\times \min (N,M)$ links — double the mesh, giving $B_b=2\min (N,M)B_{\text{link}}$. Torus bisection is twice, not equal to, the mesh's.

"Because a hypercube needs $2^k$ nodes, a 12-node system just uses the nearest hypercube." Error ::: A hypercube of dimension $k$ has exactly $N=2^k$ nodes; 12 is not any power of two. You either pad to 16 (wasting ports) or pick a topology like mesh/torus that accepts arbitrary $N$.

Why do shared buses collapse past roughly 8–16 cores while NoCs keep scaling? There is no magic number — the ceiling is where the sum of all cores' bandwidth demand exceeds the one bus's fixed $B_{\text{bus}}=f\cdot w$. With a 128-bit bus at 2 GHz (256 Gb/s) split among cores, ~8–16 cores each get only single-digit Gb/s and stall on contention; a NoC's parallel links add capacity per core instead.

Why is a hypercube's diameter logarithmic while a mesh's grows as $\sqrt{N}$? Each hypercube hop flips one address bit, halving the "remaining difference", so $k={\log }_{2}N$ hops suffice. A mesh only moves one grid-step per hop along a physical axis, so distance grows with the side length — for $N^2$ total nodes the side is $\sqrt{N^2}=N$, i.e. $\sqrt{\text{total}}$.

Why does a fat-tree double link width at each level up but a mesh keeps links uniform? In a tree, traffic concentrates as it climbs toward the shared root, so upper links must be wider to avoid a choke. A mesh has no single funnel point — traffic spreads across many parallel links, so uniform width suffices.

Why might a designer pick a low-bisection ring over a high-bisection hypercube? Rings have degree 2 (tiny routers), minimal wiring, and low power — ideal when traffic is light and the power/area budget is tight. Peak bandwidth is wasted if you never generate the traffic to use it.

Why does wire delay, not gate delay, drive the move to NoCs in modern nodes? Transistors kept shrinking and speeding up, but wires did not scale as well; a long cross-chip wire now costs many cycles to traverse. NoCs break long global wires into short router-to-router hops, keeping each signal path fast. This is a core constraint of System-on-Chip (SoC) Design, where the floorplan, not the logic, sets the timing budget.

Why is a torus harder to physically lay out than a mesh despite the same degree? Its wraparound links must jump from one chip edge all the way to the opposite edge — very long wires that raise delay, power, and routing congestion, unlike the mesh's uniformly short neighbour links.

Why can two topologies with identical diameter still have wildly different real latency? Hop count ignores per-hop cost: a hop over a long wraparound or fat-tree link takes more cycles than a short mesh hop, and congestion adds queueing delay. Diameter counts steps, not time — the very distinction Latency and Throughput Trade-offs is built around.

Why can a topology have huge bisection bandwidth $B_b$ yet still feel slow? $B_b$ is a peak throughput ceiling across a cut; a single packet still pays the full diameter in hops. Throughput and latency are separate axes, so a wide-throat network can still make one lonely packet travel far.

What is the diameter and bisection of a $1\times N$ mesh (a single row)? A single row is a linear array: diameter $=(N-1)+(1-1)=N-1$ (no second dimension to shorten it), and a mid-cut severs just one link, so $B_b=1\cdot B_{\text{link}}$ — essentially a ring cut open.

What happens to a ring's diameter formula when $N=2$? $\lfloor 2/2\rfloor =1$: the two nodes are one hop apart — correct, since a 2-node ring is just a single bidirectional link (the two "directions" coincide).

For a $2\times 2$ mesh, does the "interior degree 4" rule apply? No — every node is a corner in a $2\times 2$ mesh, so all have degree 2. The degree-4 interior only appears once the grid is at least $3\times 3$; small grids are all boundary.

What is a $k=1$ hypercube, and does the ${\log }_{2}N$ diameter still hold? $k=1$ gives $N=2^1=2$ nodes joined by one link; diameter $=k={\log }_{2}2=1$ hop — consistent. The smallest hypercube is just two connected nodes.

In a fat-tree, what carries traffic between two leaves under the same switch — does it ever reach the root? No — such traffic turns around at the lowest common switch, so nearby communication is cheap and never burdens the fat root links. Only cross-subtree traffic climbs high; this locality is why coherence traffic favours locality-aware placement.

What is the bisection bandwidth of a single isolated node (N=1)? There is no cut to make — no two halves exist — so bisection bandwidth is undefined/zero; the metric only becomes meaningful once the network has something to split.

Does an odd-length ring change the diameter formula? No — $\lfloor N/2\rfloor$ still holds; e.g. a 7-node ring has diameter 3, because the floor correctly drops the half-hop that an odd count would otherwise imply.