Fifo ID Tracker

Introduction

In this PPA challenge, you are given a first-in first-out buffer (fifo) of requests and need to report which request IDs are currently stored in it. Each request is a packed struct with an ID, a write-or-read bit, an address and data. Alongside the fifo's usual push and pop interface, the module drives valid_id_o, a bit vector with one bit per possible ID: valid_id_o[k] must be asserted whenever at least one request with ID k is in the fifo.

For example, if the fifo holds requests with IDs 3, 5 and 7 (in any order, and even if an ID appears more than once), then valid_id_o[3], valid_id_o[5] and valid_id_o[7] are asserted and every other bit is low.

The boilerplate code works but is slow and large: it reads the fifo's whole storage at once, rotates it by the read pointer so the oldest request comes first, and then marks the ID of each stored request. Your task is to keep the same behaviour while improving the timing and area of the design. The synthesis and timing report after each run shows how your design compares with the reference solution.

All the flops should be positive edge triggered with active high resets (if any).

Interface Definition

DEPTH       => Number of entries in the fifo
ID_W        => Width of the request ID; there are 2**ID_W possible IDs
ADDR_W      => Width of the request address
DATA_W      => Width of the request data

push_i      => Push a request into the fifo
push_req_i  => The request to push: {id, write_or_read, addr, data}, id in the MSBs

pop_i       => Pop the oldest request from the fifo
pop_req_o   => The oldest request in the fifo

count_o     => Number of requests currently in the fifo
valid_id_o  => valid_id_o[k] is high when at least one request with ID k is in the fifo

The request layout, as used in the boilerplate:

typedef struct packed {
  logic [ID_W-1:0]   id;
  logic              write_or_read;   // 1: write, 0: read
  logic [ADDR_W-1:0] addr;
  logic [DATA_W-1:0] data;
} req_t;

Interface Requirements

• The fifo must keep requests in first-in first-out order
• Push and pop can happen in the same cycle
• pop_req_o must show the oldest request whenever the fifo isn't empty
• count_o and valid_id_o must reflect the requests stored in the fifo at the start of the cycle (they update the cycle after a push or pop)
• An ID stays valid until the last request with that ID is popped
• push_i will only be asserted when the fifo isn't full (count_o < DEPTH)
• pop_i will only be asserted when the fifo isn't empty (count_o > 0)

Shared Modules

You are allowed to use the following shared module in your RTL:

module qs_fifo_broadside #(
  parameter DATA_W = 4,
  parameter DEPTH  = 4
)(
  input   logic                           clk,
  input   logic                           reset,

  input   logic                           push_i,
  input   logic [DATA_W-1:0]              push_data_i,

  input   logic                           pop_i,
  output  logic [DATA_W-1:0]              pop_data_o,

  output  logic [DEPTH-1:0][DATA_W-1:0]   fifo_data_o,   // Storage slot i (not the i-th oldest entry)
  output  logic [$clog2(DEPTH+1)-1:0]     count_o,       // Number of stored entries
  output  logic [$clog2(DEPTH)-1:0]       rd_ptr_o,      // Slot of the oldest entry
  output  logic [$clog2(DEPTH)-1:0]       wr_ptr_o       // Slot the next push writes
);