Loading files
This file is pinned to the selected release. Download the original to open it in your design tool.
e73baaec2This file is pinned to the selected release. Download the original to open it in your design tool.
// Copyright 2018 ETH Zurich and University of Bologna.
// Copyright and related rights are licensed under the Solderpad Hardware
// License, Version 0.51 (the "License"); you may not use this file except in
// compliance with the License. You may obtain a copy of the License at
// http://solderpad.org/licenses/SHL-0.51. Unless required by applicable law
// or agreed to in writing, software, hardware and materials distributed under
// this License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
// CONDITIONS OF ANY KIND, either express or implied. See the License for the
// specific language governing permissions and limitations under the License.
// ID Queue
//
// In an ID queue, every element has a numeric ID. Among all elements that have the same ID, the ID
// queue preserves FIFO order.
//
// This ID queue implementation allows to either push (through the `inp_*` signals) or pop (through
// the `oup_*` signals) one element per clock cycle (depending on the _FULL_BW_ operating mode
// descibed below). The `inp_` port has priority and grants a request iff the queue is not full. The
// `oup_` port dequeues an element iff `oup_pop_i` is asserted during an `oup_` handshake;
// otherwise, it performs a non-destructive read. `oup_data_o` is valid iff `oup_data_valid_o` is
// asserted during an `oup_` handshake. If `oup_data_valid_o` is not asserted, the queue did not
// contain an element with the provided ID.
//
// The queue can work in two bandwidth modes:
// * !FullBw: Input and output cannot be performed simultaneously (max bandwidth: 50%).
// * FullBw: Input and output can be performed simultaneously and a popped cell can be reused
// immediately in the same clock cycle. Area increase typically 5-10%.
//
// This ID queue additionally provides the `exists_` port, which searches for an element anywhere in
// the queue. The comparison performed during the search can be masked: for every bit that is
// asserted in `exists_mask_i`, the corresponding bit in the queue element and in `exists_data_i`
// must be equal for a match; the other bits are not compared. If masking is not required, tie
// `exists_mask_i_ to `'1` and the synthesizer should simplify the comparisons to unmasked ones. The
// `exists_` port operates independently of the `inp_` and `oup_` ports. If the `exists_` port is
// unused, tie `exists_req_i` to `1'b0` and the synthesizer should remove the internal comparators.
//
// This ID queue can store at most `Capacity` elements, independent of their ID. Let
// - C = `Capacity`
// - B = $bits(data_t)
// - I = 2**`IdWidth`
// Then
// - the queue element storage requires O(C * (B + log2(C))) bit
// - the ID table requires O(H * log2(C)) bit, where H = min(C, I)
//
// Maintainers:
// - Andreas Kurth <akurth@iis.ee.ethz.ch>
`include "common_cells/assertions.svh"
`include "common_cells/registers.svh"
module cc_id_queue #(
parameter int unsigned IdWidth = 1,
parameter int unsigned Capacity = 1,
parameter bit FullBw = 0,
parameter bit CutOupPopInpGnt = 0,
parameter int unsigned NumCmpPorts = 1,
parameter type data_t = logic[31:0],
// Dependent parameters, DO NOT OVERRIDE!
localparam type id_t = logic[IdWidth-1:0]
) (
input logic clk_i, // Clock
input logic rst_ni, // Asynchronous reset active low
input logic clr_i, // Synchronous clear active high
input id_t inp_id_i,
input data_t inp_data_i,
input logic inp_req_i,
output logic inp_gnt_o,
input data_t [NumCmpPorts-1:0] exists_data_i,
input data_t [NumCmpPorts-1:0] exists_mask_i,
input logic [NumCmpPorts-1:0] exists_req_i,
output logic [NumCmpPorts-1:0] exists_o,
output logic [NumCmpPorts-1:0] exists_gnt_o,
input id_t oup_id_i,
input logic oup_pop_i,
input logic oup_req_i,
output data_t oup_data_o,
output logic oup_data_valid_o,
output logic oup_gnt_o,
output logic full_o,
output logic empty_o
);
// Capacity of the head-tail table, which associates an ID with corresponding head and tail
// indices.
localparam int unsigned NIds = 2**IdWidth;
localparam int unsigned HtCapacity = (NIds <= Capacity) ? NIds : Capacity;
localparam int unsigned HtIdxWidth = cc_pkg::idx_width(HtCapacity);
localparam int unsigned LdIdxWidth = cc_pkg::idx_width(Capacity);
// Type for indexing the head-tail table.
typedef logic [HtIdxWidth-1:0] ht_idx_t;
// Type for indexing the lined data table.
typedef logic [LdIdxWidth-1:0] ld_idx_t;
// Type of an entry in the head-tail table.
typedef struct packed {
id_t id;
ld_idx_t head,
tail;
logic free;
} head_tail_t;
// Type of an entry in the linked data table.
typedef struct packed {
data_t data;
ld_idx_t next;
logic free;
} linked_data_t;
head_tail_t [HtCapacity-1:0] head_tail_d, head_tail_q;
linked_data_t [Capacity-1:0] linked_data_d, linked_data_q;
logic empty,
full,
match_in_id_valid,
match_out_id_valid,
no_in_id_match,
no_out_id_match;
logic [HtCapacity-1:0] head_tail_free,
idx_matches_in_id,
idx_matches_out_id;
logic [NumCmpPorts-1:0][Capacity-1:0] exists_match;
logic [Capacity-1:0] linked_data_free;
id_t match_in_id, match_out_id;
ht_idx_t head_tail_free_idx,
match_in_idx,
match_out_idx;
ld_idx_t linked_data_free_idx,
oup_data_free_idx;
logic oup_data_popped,
oup_ht_popped;
// Find the index in the head-tail table that matches a given ID.
for (genvar i = 0; i < HtCapacity; i++) begin: gen_idx_match
assign idx_matches_in_id[i] = match_in_id_valid && (head_tail_q[i].id == match_in_id) &&
!head_tail_q[i].free;
assign idx_matches_out_id[i] = match_out_id_valid && (head_tail_q[i].id == match_out_id) &&
!head_tail_q[i].free;
end
assign no_in_id_match = !(|idx_matches_in_id);
assign no_out_id_match = !(|idx_matches_out_id);
cc_onehot_to_bin #(
.OnehotWidth ( HtCapacity )
) i_id_ohb_in (
.onehot_i ( idx_matches_in_id ),
.bin_o ( match_in_idx )
);
if (FullBw) begin : gen_ohb_out
cc_onehot_to_bin #(
.OnehotWidth ( HtCapacity )
) i_id_ohb_out (
.onehot_i ( idx_matches_out_id ),
.bin_o ( match_out_idx )
);
end else begin : gen_ohb_out_tie
assign match_out_idx = '0;
end
// Find the first free index in the head-tail table.
for (genvar i = 0; i < HtCapacity; i++) begin: gen_head_tail_free
assign head_tail_free[i] = head_tail_q[i].free;
end
cc_lzc #(
.Width ( HtCapacity ),
.Mode ( cc_pkg::LZC_TRAILING_ZERO_CNT )
) i_ht_free_lzc (
.in_i ( head_tail_free ),
.cnt_o ( head_tail_free_idx ),
.empty_o ( )
);
// Find the first free index in the linked data table.
for (genvar i = 0; i < Capacity; i++) begin: gen_linked_data_free
assign linked_data_free[i] = linked_data_q[i].free;
end
cc_lzc #(
.Width ( Capacity ),
.Mode ( cc_pkg::LZC_TRAILING_ZERO_CNT )
) i_ld_free_lzc (
.in_i ( linked_data_free ),
.cnt_o ( linked_data_free_idx ),
.empty_o ( )
);
// The queue is full if and only if there are no free entries in the linked data structure.
assign full = !(|linked_data_free);
// The queue is empty if and only if all entries in the linked data structure are free.
assign empty = &linked_data_free;
// Data potentially freed by the output.
assign oup_data_free_idx = head_tail_q[match_out_idx].head;
// Data can be accepted if the linked list pool is not full, or if some data is simultaneously
// popped (given FullBw & !CutOupPopInpGnt).
assign inp_gnt_o = ~full || (oup_data_popped && FullBw && ~CutOupPopInpGnt);
always_comb begin
match_in_id = '0;
match_out_id = '0;
match_in_id_valid = 1'b0;
match_out_id_valid = 1'b0;
head_tail_d = head_tail_q;
linked_data_d = linked_data_q;
oup_gnt_o = 1'b0;
oup_data_o = data_t'('0);
oup_data_valid_o = 1'b0;
oup_data_popped = 1'b0;
oup_ht_popped = 1'b0;
if (!FullBw) begin
if (inp_req_i && !full) begin
match_in_id = inp_id_i;
match_in_id_valid = 1'b1;
// If the ID does not yet exist in the queue, add a new ID entry.
if (no_in_id_match) begin
head_tail_d[head_tail_free_idx] = '{
id: inp_id_i,
head: linked_data_free_idx,
tail: linked_data_free_idx,
free: 1'b0
};
// Otherwise append it to the existing ID subqueue.
end else begin
linked_data_d[head_tail_q[match_in_idx].tail].next = linked_data_free_idx;
head_tail_d[match_in_idx].tail = linked_data_free_idx;
end
linked_data_d[linked_data_free_idx] = '{
data: inp_data_i,
next: '0,
free: 1'b0
};
end else if (oup_req_i) begin
match_in_id = oup_id_i;
match_in_id_valid = 1'b1;
if (!no_in_id_match) begin
oup_data_o = data_t'(linked_data_q[head_tail_q[match_in_idx].head].data);
oup_data_valid_o = 1'b1;
if (oup_pop_i) begin
// Set free bit of linked data entry, all other bits are don't care.
linked_data_d[head_tail_q[match_in_idx].head] = '0;
linked_data_d[head_tail_q[match_in_idx].head].free = 1'b1;
if (head_tail_q[match_in_idx].head == head_tail_q[match_in_idx].tail) begin
head_tail_d[match_in_idx] = '{free: 1'b1, default: '0};
end else begin
head_tail_d[match_in_idx].head =
linked_data_q[head_tail_q[match_in_idx].head].next;
end
end
end
// Always grant the output request. If there was no match, the default, invalid entry
// will be returned.
oup_gnt_o = 1'b1;
end
end else begin
// FullBw
if (oup_req_i) begin
match_out_id = oup_id_i;
match_out_id_valid = 1'b1;
if (!no_out_id_match) begin
oup_data_o = data_t'(linked_data_q[head_tail_q[match_out_idx].head].data);
oup_data_valid_o = 1'b1;
if (oup_pop_i) begin
oup_data_popped = 1'b1;
// Set free bit of linked data entry, all other bits are don't care.
linked_data_d[head_tail_q[match_out_idx].head] = '0;
linked_data_d[head_tail_q[match_out_idx].head].free = 1'b1;
if (head_tail_q[match_out_idx].head
== head_tail_q[match_out_idx].tail) begin
oup_ht_popped = 1'b1;
head_tail_d[match_out_idx] = '{free: 1'b1, default: '0};
end else begin
head_tail_d[match_out_idx].head =
linked_data_q[head_tail_q[match_out_idx].head].next;
end
end
end
// Always grant the output request. If there was no match, the default, invalid entry
// will be returned.
oup_gnt_o = 1'b1;
end
if (inp_req_i && inp_gnt_o) begin
match_in_id = inp_id_i;
match_in_id_valid = 1'b1;
// If the ID does not yet exist in the queue or was just popped, add a new ID entry.
if (oup_ht_popped && (oup_id_i==inp_id_i)) begin
// If output data was popped for this ID, which lead the head_tail to be popped,
// then repopulate this head_tail immediately.
head_tail_d[match_out_idx] = '{
id: inp_id_i,
head: oup_data_free_idx,
tail: oup_data_free_idx,
free: 1'b0
};
linked_data_d[oup_data_free_idx] = '{
data: inp_data_i,
next: '0,
free: 1'b0
};
end else if (no_in_id_match) begin
// Else, if no head_tail corresponds to the input id.
if (oup_ht_popped) begin
head_tail_d[match_out_idx] = '{
id: inp_id_i,
head: oup_data_free_idx,
tail: oup_data_free_idx,
free: 1'b0
};
linked_data_d[oup_data_free_idx] = '{
data: inp_data_i,
next: '0,
free: 1'b0
};
end else begin
if (oup_data_popped) begin
head_tail_d[head_tail_free_idx] = '{
id: inp_id_i,
head: oup_data_free_idx,
tail: oup_data_free_idx,
free: 1'b0
};
linked_data_d[oup_data_free_idx] = '{
data: inp_data_i,
next: '0,
free: 1'b0
};
end else begin
head_tail_d[head_tail_free_idx] = '{
id: inp_id_i,
head: linked_data_free_idx,
tail: linked_data_free_idx,
free: 1'b0
};
linked_data_d[linked_data_free_idx] = '{
data: inp_data_i,
next: '0,
free: 1'b0
};
end
end
end else begin
// Otherwise append it to the existing ID subqueue.
if (oup_data_popped) begin
linked_data_d[head_tail_q[match_in_idx].tail].next = oup_data_free_idx;
head_tail_d[match_in_idx].tail = oup_data_free_idx;
linked_data_d[oup_data_free_idx] = '{
data: inp_data_i,
next: '0,
free: 1'b0
};
end else begin
linked_data_d[head_tail_q[match_in_idx].tail].next = linked_data_free_idx;
head_tail_d[match_in_idx].tail = linked_data_free_idx;
linked_data_d[linked_data_free_idx] = '{
data: inp_data_i,
next: '0,
free: 1'b0
};
end
end
end
end
end
// Exists Lookup
for (genvar k = 0; k < NumCmpPorts; k++) begin: gen_lookup_port
for (genvar i = 0; i < Capacity; i++) begin: gen_lookup
// For a match, the entry needs to be occupied AND
// the masked slot data needs to match the masked query data.
assign exists_match[k][i] = ~linked_data_q[i].free &
((linked_data_q[i].data & exists_mask_i[k]) ==
(exists_data_i[k] & exists_mask_i[k]));
end
always_comb begin
exists_gnt_o[k] = 1'b0;
exists_o[k] = '0;
if (exists_req_i[k]) begin
exists_gnt_o[k] = 1'b1;
exists_o[k] = (|exists_match[k]);
end
end
end
// Registers
for (genvar i = 0; i < HtCapacity; i++) begin: gen_ht_ffs
`FFARNC(head_tail_q[i],
head_tail_d[i],
clr_i,
head_tail_t'{free: 1'b1, default: '0},
clk_i,
rst_ni)
end
for (genvar i = 0; i < Capacity; i++) begin: gen_data_ffs
`FFARNC(linked_data_q[i],
linked_data_d[i],
clr_i,
linked_data_t'{free: 1'b1, default: '0},
clk_i,
rst_ni)
end
// Status interface
assign full_o = full;
assign empty_o = empty;
// Validate parameters.
`ifndef COMMON_CELLS_ASSERTS_OFF
`ASSERT_INIT(id_width_0, IdWidth >= 1, "The ID must at least be one bit wide!")
`ASSERT_INIT(capacity_0, Capacity >= 1, "The queue must have capacity of at least one entry!")
`endif
endmodule