Packets, Flits and Layers
Split a large interconnect into layers and cut packets into flits. Give each message class its own virtual channel, and see the deadlock that sharing one causes.
You Will Be Able To
- Name the protocol, network and link layers and the unit each one moves.
- Explain how flits, virtual channels and credits share one physical link.
- Find the cycle of waiting that deadlocks requests and responses on one virtual channel.
- Lesson
- P1.13
- Time
- 30 min
- Runs on
- Your browser
- Check
- 5 questions
A network-on-chip passed every test with light traffic. Under a benchmark that sent reads in both directions at once, it froze after a few hundred cycles. No flit was corrupt and no handshake rule broke. Requests had filled every buffer, so no response could get through, and without responses no request would ever leave.
- I/O
The slots are B's buffer for the one shared VC. Requests fill it; responses then have no room to get through.
- Cycle 0
A sends a request to B. Requests and responses share one virtual channel and its two-flit buffer.
- Cycle 1
A response flit follows, on the same channel and the same credits.
- Cycle 7
B's buffer starts to hold requests that B cannot answer yet: its own response queue is full.
- Cycle 11
B's buffer is full of requests and A has no credit left. B is stuck in the same way.
- Cycle 15
Nothing moves again. Each node waits for room that only the other can make: a deadlock.
Two requests answered of six each way. No rule of the link was broken: the cycle of waiting is in the protocol.
Three Layers
A bus with a few wires can carry a whole transaction in one place. A large chip cannot. Its interconnect is a network, and it splits the work into layers, each with its own unit and its own job.
| Layer | Unit | Its job |
|---|---|---|
| Protocol | Transaction, made of messages: requests, responses, snoops | Which messages a transaction needs, and protocol-level flow control |
| Network | Packet: a message with source and target node IDs | Packetizing messages and routing them to the right node |
| Link | Flit: one slot of a buffer | Flow control between neighbours, and channels that keep switching deadlock-free |
AMBA CHI is built this way: protocol, network and link layers, with flits and credits at the bottom.
Each layer trusts the one below. The protocol layer asks for a message to reach a node. The network picks the route. The link layer moves it hop by hop, a flit at a time.
Packets into Flits
A packet starts with a header: its destination, its type and a tag to match the answer. A data payload follows. The link cuts the packet into flits, short for flow-control units. A flit is the amount one buffer slot holds and one credit pays for.
In the bench a request is one flit and a response is two: a header and the data. Credits count flits, not packets, so a response needs two credits to cross. A long packet may hold a channel from its head flit to its tail flit, so other packets wait behind it.
Virtual Channels
One wire can carry several virtual channels. Each has its own buffer at the far end and its own credits. A flit carries its channel number, and it may go only with a credit for that channel. So a full channel blocks only itself.
That is exactly what requests and responses need. A node takes a request only when it can queue the response. If both share one channel, requests can fill every buffer, and responses then have nowhere to go. Each node waits for the other: a protocol deadlock. With a separate channel for responses, they always get through, and every request drains.
Real protocols give each message class its own channel for this reason. CHI has separate request, response, snoop and data channels, and its link layer exists partly to keep switching deadlock-free.
Where You Will Meet It
Asked in interviews: packets, flits and deadlock
What is a flit?
A flow-control unit: the piece of a packet one buffer slot holds and one credit pays for. A packet is one or more flits.
Why do networks use virtual channels?
So that one blocked class of traffic cannot block another on the same wire. Each channel has its own buffer and credits.
How can a network deadlock when every rule is kept?
Through a cycle of waiting. Requests fill the buffers a response needs, and the requests cannot drain until their responses leave.
How do you avoid a protocol deadlock?
Put requests and responses on separate channels, and let a node always accept a response. Then responses always drain.
Why did light traffic not find it?
Buffers never filled. A deadlock needs enough load to close the cycle, so tests must push every class at once.
Try It
Both nodes send six read requests at the same time. Requests travel on virtual channel 0 and responses on channel 1, so a full request buffer never blocks a response. Every request is answered.
Remove the // in front of shared_vc = 1; and run again. Now the line reads A got 2 of 6 answers, B got 2 of 6, and the run stops when nothing has moved for 30 cycles. Try three requests each way with the shared channel: the buffers never fill and all of them are answered.
A got 6 of 6 answers, B got 6 of 6Read included file: noc_link.sv
// noc_link.sv: two nodes, a link each way, flits on virtual channels with credits (read-only).
// Protocol layer: a node sends n_req read requests (6 unless the bench sets it) to the other node and answers every request it
// receives with a response. A request is one flit; a response is two flits (a header and the data).
// Link layer: one flit per cycle per direction, sent only with a credit for its virtual channel
// (VC). Each node buffers DEPTH flits per VC on its input and returns a credit when it frees one.
// A node takes a request off its input only when it has room to queue the whole response.
// shared_vc = 0: requests travel on VC 0 and responses on VC 1, each with its own buffer;
// shared_vc = 1 (the twin): everything shares VC 0 and its buffer.
// Flit: {type[1:0], vc, tag[4:0]}, type 1 request, 2 response header, 3 response data.
module noc_node #(parameter int DEPTH = 2) (
input logic clk,
input logic rst_n,
input logic shared_vc,
output logic tx_valid,
output logic [7:0] tx_flit,
input logic [1:0] tx_crd, // a credit returned for VC 0 / VC 1
input logic rx_valid,
input logic [7:0] rx_flit,
output logic [1:0] rx_crd,
output int sent, answered, done // requests sent, requests answered, responses received
);
logic [7:0] ib [2][DEPTH]; // input buffers per VC
int ih [2], in_n [2];
logic [7:0] oq [2][4]; // output queues: 0 requests, 1 responses
int oh [2], on_ [2];
int crd [2], turn, k, v, q;
logic [7:0] f;
bit picked;
int n_req = 6; // requests this node sends; the bench may change it before reset ends
function automatic int vc_of(input int queue);
return shared_vc ? 0 : queue;
endfunction
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
for (int i = 0; i < 2; i++) begin ih[i] = 0; in_n[i] = 0; oh[i] = 0; on_[i] = 0; crd[i] = DEPTH; end
sent = 0; answered = 0; done = 0; turn = 0; tx_valid <= 0; rx_crd <= 0;
end else begin
rx_crd <= 0;
for (int i = 0; i < 2; i++) if (tx_crd[i]) crd[i]++; // credits that came back
if (rx_valid) begin // a flit arrives
v = rx_flit[5];
ib[v][(ih[v] + in_n[v]) % DEPTH] = rx_flit; in_n[v]++;
end
// consume input heads: a response flit always, a request only with room for its response
for (int i = 0; i < 2; i++) if (in_n[i] > 0) begin
f = ib[i][ih[i]];
if (f[7:6] != 2'd1) begin
if (f[7:6] == 2'd3) done++;
ih[i] = (ih[i] + 1) % DEPTH; in_n[i]--; rx_crd[i] <= 1;
end else if (on_[1] <= 2) begin
oq[1][(oh[1] + on_[1]) % 4] = {2'd2, 1'(vc_of(1)), f[4:0]}; on_[1]++;
oq[1][(oh[1] + on_[1]) % 4] = {2'd3, 1'(vc_of(1)), f[4:0]}; on_[1]++;
answered++;
ih[i] = (ih[i] + 1) % DEPTH; in_n[i]--; rx_crd[i] <= 1;
end
end
// the protocol layer: issue the next request
if (sent < n_req && on_[0] < 4) begin oq[0][(oh[0] + on_[0]) % 4] = {2'd1, 1'(vc_of(0)), 5'(sent)}; on_[0]++; sent++; end
// the link layer: one flit, from the queues in turn, only with a credit for its VC
tx_valid <= 0; picked = 0;
for (int j = 0; j < 2; j++) begin
q = (turn + j) % 2;
if (!picked && on_[q] > 0 && crd[vc_of(q)] > 0) begin
tx_flit <= oq[q][oh[q]]; tx_valid <= 1; crd[vc_of(q)]--; picked = 1;
oh[q] = (oh[q] + 1) % 4; on_[q]--; turn = 1 - q;
end
end
end
end
endmodule
Check Yourself
Common Mistakes
Wrong Count credits per packet.
A buffer slot holds a flit, so a multi-flit packet sent on one credit overflows the receiver.
Fix Spend one credit per flit, on the flit's own virtual channel.
Wrong Put responses on the same virtual channel as requests to save buffers.
Requests can then fill every buffer that responses need, and the network deadlocks under load.
Fix Give each message class its own channel, and always accept responses.
Wrong Trust a network that passed light-traffic tests.
A protocol deadlock appears only when buffers fill, so light traffic cannot reach it.
Fix Run every message class at full rate in both directions, and check that traffic always drains.
Remember
- A large interconnect has layers: messages in the protocol layer, packets in the network layer, flits in the link layer.
- A flit is what one buffer slot holds and one credit pays for. A packet is one or more flits.
- Virtual channels share a wire but not their buffers or credits, so one full channel blocks only itself.
- Requests and responses on one channel can deadlock: requests fill the buffers responses need.
- A deadlock needs load to close its cycle. Tests that never fill buffers never see it.