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.

One Virtual Channel for Requests and Responses: The Link FreezesThe link from A to B in the twin, edges 3 to 18. R is a request flit, H and D the two flits of a response. B to A looks the same.
  • I/O
flitNode Asends requests, owes responsesNode Binput buffer of 2 flits
flit→ Node BNode Asends requests, owes responsesNode Binput buffer of 2 flits

The slots are B's buffer for the one shared VC. Requests fill it; responses then have no room to get through.

0123456789101112131415clkflit_validflitRHRDRHRD-RH-creditsb_buffer01012
Scroll horizontally ↔
  1. Cycle 0

    A sends a request to B. Requests and responses share one virtual channel and its two-flit buffer.

  2. Cycle 1

    A response flit follows, on the same channel and the same credits.

  3. Cycle 7

    B's buffer starts to hold requests that B cannot answer yet: its own response queue is full.

  4. Cycle 11

    B's buffer is full of requests and A has no credit left. B is stuck in the same way.

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

LayerUnitIts job
ProtocolTransaction, made of messages: requests, responses, snoopsWhich messages a transaction needs, and protocol-level flow control
NetworkPacket: a message with source and target node IDsPacketizing messages and routing them to the right node
LinkFlit: one slot of a bufferFlow 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
  1. 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.

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

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

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

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

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: A got 6 of 6 answers, B got 6 of 6
Read 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

Predict the outputRequests and responses share one virtual channel, but each node sends only three requests. The bench runs until nothing moves. What does it print?
`timescale 1ns/1ps
module tb;
  logic clk = 0, rst_n = 0, shared_vc = 0;
  always #5 clk = ~clk;                  // rising edges at 5, 15, 25, ...
  wire       ab_v, ba_v;                 // a flit on the link from A to B, and from B to A
  wire [7:0] ab_f, ba_f;
  wire [1:0] a_crd, b_crd;               // credits returned, one bit per VC
  int a_sent, a_ans, a_done, b_sent, b_ans, b_done;
  noc_node a (.clk(clk), .rst_n(rst_n), .shared_vc(shared_vc), .tx_valid(ab_v), .tx_flit(ab_f), .tx_crd(b_crd),
    .rx_valid(ba_v), .rx_flit(ba_f), .rx_crd(a_crd), .sent(a_sent), .answered(a_ans), .done(a_done));
  noc_node b (.clk(clk), .rst_n(rst_n), .shared_vc(shared_vc), .tx_valid(ba_v), .tx_flit(ba_f), .tx_crd(a_crd),
    .rx_valid(ab_v), .rx_flit(ab_f), .rx_crd(b_crd), .sent(b_sent), .answered(b_ans), .done(b_done));
  int cycle = -1, last_move = 0;
  always @(posedge clk) begin cycle++; if (ab_v || ba_v) last_move = cycle; end
  initial begin
    repeat (2) @(posedge clk); #1 rst_n = 1;
    shared_vc = 1;              // one VC for everything
    a.n_req = 3; b.n_req = 3;
    // Run until no flit has moved for 30 cycles.
    while (cycle - last_move < 30 && cycle < 300) @(posedge clk);
    #1 $display("A got %0d of %0d answers, B got %0d of %0d", a_done, a_sent, b_done, b_sent);
    $finish;
  end
endmodule
Read 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
ConceptWhat does one credit pay for on a link with flits?
ConceptWhich layer decides which node a packet goes through next?
Read the waveformTwo nodes share one virtual channel. B's two-flit input buffer and A's credits are shown. From which cycle is the link deadlocked?
A's credits and B's buffer
0123456flit_validcreditsb_buffer012
Scroll horizontally ↔

Cycles 0 to 6. B's buffer holds only requests from cycle 3 on.

ConceptWhy must a node be able to accept a response at any time, while it may refuse a request?

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.

Practice

Report a problem with this page