Queue Design in SystemVerilog:

Entry is stored into the Queue in a certain order. The order could be as simple as find any first vacant entry or find a next vacant entry from previous allocation or find the last entry that became available recently.

Queues are used in Digital design when the Data from a Stream is needed to be stored into a Structure, manipulated and taken out of Order based on a protocol or events in the Design.

The Entry could be taken out of queue (de-allocated) based on a certain protocol. If the protocol involves series of events that are common for each entry then a FSM shown below is used. However, if each entry in the queue needs a separate event then just a Combinational Trigger logic to clear a valid bit maybe sufficient.

Here’s an example of 8 Entry Queue that uses FSM for each Entry manipulation :

Queue FSM
parameter   DEPTH         = 8;
parameter   INVALID_STATE = 4'b0001;
parameter   VALID_STATE   = 4'b0010;
parameter   EVENT1_STATE  = 4'b0100;
parameter   DISABLE_STATE = 4'b1000;

logic [DEPTH-1:0]      state_ps[3:0];
logic [DEPTH-1:0]      state_ns[3:0];  
logic                  queue_empty;
logic                  queue_full;

logic [DATA_WIDTH-1:0] queue_data[DEPTH-1:0];
logic                  queue_valid[DEPTH-1:0];
logic [DATA_WIDTH-1:0] data_out[DEPTH-1:0];

logic [DEPTH-1:0]      new_entry;
logic [DEPTH-1:0]      allocate_entry;
logic                  allocate_new;

logic [DEPTH-1:0]      event1_started;
logic [DEPTH-1:0]      event1_completed;
logic [DEPTH-1:0]      event1_dis;

genvar x, i, j;

always_comb begin
  casez (state_ps[0])
    8'b????_???1 : new_entry = 8'h1;
    8'b????_??10 : new_entry = 8'h2;
    8'b????_?100 : new_entry = 8'h4;
    8'b????_1000 : new_entry = 8'h8;
    8'b???1_0000 : new_entry = 8'h10;
    8'b??10_0000 : new_entry = 8'h20;
    8'b?100_0000 : new_entry = 8'h40;
    8'b1000_0000 : new_entry = 8'h80;
    default      : new_entry = '0;

assign allocate_entry = (~queue_full & allocate_new) ? new_entry : 8'b0;

always_comb begin
  for (int entry = 0; entry < DEPTH; entry++)
    casez (state_ps[entry])
      INVALID_STATE : if(entry_dis[entry])
                        state_ns[entry]   = DISABLE_STATE;
                      else if(allocate_entry[entry])
                         state_ns[entry]  = VALID_STATE;
                         state_ns[entry]  = INVALID_STATE;
     DISABLE_STATE  : if(~entry_dis[entry])
                         state_ns[entry]  = INVALID_STATE;
                        state_ns[entry]   = DISABLE_STATE;                        

      VALID_STATE   : if(event1_started[entry]) 
                         state_ns[entry]  = EVENT1_STATE;
                         state_ns[entry]  = VALID_STATE;

      EVENT1_STATE :  if(event1_completed[entry])
                         state_ns[entry] = INVALID_STATE;
                         state_ns[entry]  = EVENT1_STATE;

      default      :  state_ns[entry] = state_ps[entry]; 

for (x = 0; x < DEPTH; x++)
  always_ff @(posedge clk or negedge reset) begin
      state_ps[x] <= INVALID_STATE;
      state_ps[x] <= state_ns[x];

assign event1_started   = request_sent[DEPTH-1:0]; // From other Module
assign event1_completed = response_ack[DEPTH-1:0]; // From other Module
assign entry_dis        = entry_disable[DEPTH-1:0];// From other Module 

//Queue Data maintenance
for (i = 0; i < DEPTH; i++)
  always_ff @(posedge clk or negedge reset)
    if(~reset | event_completed[i]) begin
      queue_data[i]   <= queue_data[i]; // Can be zero if required 
      queue_valid[i]  <= 1'b0;
    else if (allocate_entry[i]) begin
      queue_data[i]   <= data_in;
      queue_valid[i]  <= 1'b1;
    else begin
      queue_data[i]   <= queue_data[i];
      queue_valid[i]  <= queue_valid[i];

//Queue Data readout of multiple entries.
 for (j = 0; j < DEPTH; j++)  
   assign data_out[j] = (event_completed[j] & queue_valid[j]) 
                         ? queue_data[j] :'0; 

Here request & response could be sent and received from another Design Module. These Events (Started and Completed) could happen one per entry per cycle or multiple entries per cycle. Hence, there are multiple entries getting State updates i.e multiple entries taken out of Queue.

If only single event is expected to complete every cycle then Decoder is needed to extract out single Data element out of queue as shown below:

logic [2:0] entry_dec;
always_comb begin
 unique case (event_completed[7:0])
    8'h0000_0001 : entry_dec = 3'h0;
    8'b0000_0010 : entry_dec = 3'h1;
    8'b0000_0100 : entry_dec = 3'h2;
    8'b0000_1000 : entry_dec = 3'h3;
    8'b0001_0000 : entry_dec = 3'h4;
    8'b0010_0000 : entry_dec = 3'h5;
    8'b0100_0000 : entry_dec = 8'h6;
    8'b1000_0000 : entry_dec = 8'h7;

//Queue Data readout of Single entry
assign data_out = ((|event_completed) & queue_valid[entry_dec]) 
                   ? queue_data[entry_dec] :'0; 

Entry disable is done in order to limit or disable the number of Entries Queue or apply back-pressure on preceding Design module. This programming is usually done via Firmware and used as a effective tool to Test out Corner cases.

Published by


Silicon Design Enthusiast.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s