FlooNoC Notes

1 Concept

1). Wormhole Routing (The Flow Control Method)

Think of a long, narrow pipeline. Wormhole routing is a switching technique - it determines how a packet is broken down and moved from one router to the next. It's the dominant method in NoCs because it balances low latency with low buffer requirements.

The Core Idea: A packet is divided into smaller units called flits (flow control digits). Typically, there are three types of flits:

• Head Flit: Contains the path/routing information and the packet's destination.
• Body Flit/s: Contains the actual payload data.
• Tail Flit: Marks the end of the packet.

How it works (The Analogy): Imagine a convoy of cars (flits) driving through a series of tunnels (routers and links).

1. The head car leads the way. It decides which tunnel to take at each intersection.
2. Once the head car enters a tunnel, the body cars follow closely behind, without any gaps.
3. The convoy (the whole packet) gets "wormed" through the network. Different parts of the same packet can be in different routers simultaneously.
4. The tunnel is blocked for any other convoy until the tail car has passed through.

Key Characteristics:

• Low Buffer Requirement: Routers only need to store a few flits, not a whole packet.
• Low Latency: The head flit experiences routing delay, but following flits proceed at link speed (pipeline latency).
• Blocking: If the head flit is blocked (its next router is busy), all trailing flits stop in place, blocking the path for others. This is called head-of-line (HoL) blocking, a major disadvantage.

2). XY Routing (The Routing Algorithm)

Think of a grid of city streets. XY routing is a deterministic routing algorithm – it answers the question: "Given the current node and the destination, which output port should I use?"

The Core Idea: It's a simple, deadlock-free algorithm for a 2D mesh topology (the most common NoC layout). A node's address is its coordinates (X, Y). The rule is:

1. Route first in the X dimension (horizontal) until the packet's X-coordinate matches the destination's X-coordinate.
2. Then route in the Y dimension (vertical) until the Y-coordinate matches.

How it works: Let's say a packet at node (2, 1) needs to go to destination (5, 4).

• Step 1 (X-routing): Compare X (2 vs 5). Destination is to the East. Go East.
  • Path: (2,1) → (3,1) → (4,1) → (5,1)
• Step 2 (Y-routing): Now at X=5 (match). Compare Y (1 vs 4). Destination is to the North. Go North.
  • Path: (5,1) → (5,2) → (5,3) → (5,4)

Key Characteristics:

• Simple: Requires very little hardware (just a comparator).
• Deterministic: The path is always the same for a given source-destination pair.
• Deadlock-Free: By restricting turns (no turning from Y back to X, or cycles), it avoids deadlock.
• Not Adaptive: It cannot route around congested or faulty routers. If the direct path is blocked, the packet has no alternative and will be stuck.
• Not Optimal for All Traffic: It can lead to hotspots and load imbalance (e.g., traffic in the center of the chip is heavier).

3). How They Work Together

Wormhole routing is how you send flits. XY-routing is which way you send the head flit.

Imagine a NoC using both:

1. The source processor creates a packet destined for (5,4). It breaks it into Head, Body, and Tail flits.
2. The Head flit arrives at the first router (2,1). The router uses the XY routing logic. It compares coordinates, sees X differs, and chooses the East output port.
3. The router then uses wormhole routing to start sending the Head flit East. It reserves the East port and the link to the next router for the entire packet.
4. Immediately, the Body flits begin following the Head flit through the reserved path, one per cycle.
5. At the next router (3,1), the process repeats. The Head flit again selects the East port based on XY-routing, and the rest of the wormhole convoy follows.
6. This continues until (5,1), where the Head flit's XY logic chooses North.
7. Finally, at (5,4), the Tail flit passes through, releasing all the reserved resources along the path.

4). Summary Table

Feature	Wormhole Routing	XY-Routing
Category	Switching Technique (Flow Control)	Routing Algorithm (Path Selection)
Question it Answers	How is the packet moved?	Which way does it go at each hop?
Key Benefit	Low router buffer size	Extremely simple, deadlock-free hardware
Key Drawback	Head-of-Line (HoL) blocking	Not adaptive; creates congestion hotspots
Works on	Flits (Head, Body, Tail)	Coordinates (X, Y) in a 2D mesh

In short: XY-routing tells the head flit of a wormhole-routed packet the path to take through the 2D mesh NoC.

2 Reading

[50] G. Paulin, P. Scheffler et al., “Occamy: A 432-core 28.1 dp-gflop/s/w $83 \%$ fpu utilization dual-chiplet, dual-hbm2e risc-v-based accelerator for stencil and sparse linear algebra computations with 8-to-64-bit floatingpoint support in 12nm finfet,” VLSI Symposium, 2024.

[51] M. Jung, C. Weis, and N. Wehn, “Dramsys: A flexible dram subsystem design space exploration framework,” IPSJ Transactions on System and LSI Design Methodology, vol. 8, pp. 63–74, 2015.