//
// Copyright 2018 Ettus Research, A National Instruments Company
//
// SPDX-License-Identifier: LGPL-3.0-or-later
//
// Module: kv_map
module kv_map #(
parameter KEY_WIDTH = 16,
parameter VAL_WIDTH = 32,
parameter SIZE = 6
) (
// Clock and reset
input wire clk,
input wire reset,
// Insert port
input wire insert_stb,
input wire [KEY_WIDTH-1:0] insert_key,
input wire [VAL_WIDTH-1:0] insert_val,
output wire insert_busy,
// Find port
input wire find_key_stb,
input wire [KEY_WIDTH-1:0] find_key,
output wire find_res_stb,
output wire find_res_match,
output wire [VAL_WIDTH-1:0] find_res_val,
// Count
output reg [SIZE-1:0] count = {SIZE{1'b0}}
);
//-------------------------------------------------
// Instantiate a CAM and a RAM
//-------------------------------------------------
// The CAM serves as a "set" and the RAM serves as a
// random addressable "array". Using thse two data structures
// we can build a map. The role of the CAM is to compress
// the key to an address that can be used to lookup data
// stored in the RAM
wire cam_wr_en, cam_wr_busy, cam_rd_match;
wire [SIZE-1:0] cam_wr_addr, cam_rd_addr;
wire [KEY_WIDTH-1:0] cam_wr_data, cam_rd_key;
wire ram_wr_en;
wire [SIZE-1:0] ram_wr_addr;
reg [SIZE-1:0] ram_rd_addr;
wire [VAL_WIDTH-1:0] ram_wr_data, ram_rd_data;
cam #(
.DATA_WIDTH (KEY_WIDTH),
.ADDR_WIDTH (SIZE),
.CAM_STYLE (SIZE > 8 ? "BRAM" : "SRL"),
.SLICE_WIDTH (SIZE > 8 ? 9 : 5)
) cam_i (
.clk (clk),
.rst (reset),
.write_addr (cam_wr_addr),
.write_data (cam_wr_data),
.write_delete(1'b0),
.write_enable(cam_wr_en),
.write_busy (cam_wr_busy),
.compare_data(cam_rd_key),
.match_addr (cam_rd_addr),
.match (cam_rd_match),
.match_many (),
.match_single()
);
ram_2port #(
.DWIDTH(VAL_WIDTH),
.AWIDTH(SIZE)
) mem_i (
.clka (clk),
.ena (ram_wr_en),
.wea (1'b1),
.addra (ram_wr_addr),
.dia (ram_wr_data),
.doa (/* Write port only */),
.clkb (clk),
.enb (1'b1),
.web (1'b0),
.addrb (ram_rd_addr),
.dib (/* Read port only */),
.dob (ram_rd_data)
);
// Pipeline read address into RAM
always @(posedge clk)
ram_rd_addr <= cam_rd_addr;
//-------------------------------------------------
// Find state machine
//-------------------------------------------------
// The lookup process has three cycles of latency
// - CAM lookup has a 1 cycle latency
// - The lookup address into the RAM is delayed by 1 cycle for timing
// - The RAM takes 1 cycle to produce data
localparam FIND_CYC = 3;
reg [FIND_CYC-1:0] find_key_stb_shreg = {FIND_CYC{1'b0}};
reg [FIND_CYC-2:0] find_match_shreg = {(FIND_CYC-1){1'b0}};
reg find_pending = 1'b0;
wire find_busy = find_pending | find_key_stb;
// Delay the find valid signal to account for the latency
// of the CAM and RAM
always @(posedge clk) begin
find_key_stb_shreg <= reset ? {FIND_CYC{1'b0}} :
{find_key_stb_shreg[FIND_CYC-2:0], find_key_stb};
end
assign find_res_stb = find_key_stb_shreg[FIND_CYC-1];
// Latch the find signal to compute pending
always @(posedge clk) begin
if (find_key_stb)
find_pending <= 1'b1;
else if (find_pending)
find_pending <= ~find_res_stb;
end
// Delay the match signal to account for the latency of the RAM
always @(posedge clk) begin
find_match_shreg <= reset ? {(FIND_CYC-1){1'b0}} :
{find_match_shreg[FIND_CYC-3:0], cam_rd_match};
end
assign find_res_match = find_match_shreg[FIND_CYC-2];
//-------------------------------------------------
// Insert state machine
//-------------------------------------------------
localparam [2:0] ST_IDLE = 3'd0;
localparam [2:0] ST_WAIT_FIND = 3'd1;
localparam [2:0] ST_CAM_READ = 3'd2;
localparam [2:0] ST_CAM_CHECK_MATCH = 3'd3;
localparam [2:0] ST_CAM_RAM_WRITE = 3'd4;
localparam [2:0] ST_CAM_WRITE_WAIT = 3'd5;
localparam [2:0] ST_RAM_WRITE = 3'd6;
reg [2:0] ins_state = ST_IDLE;
reg [KEY_WIDTH-1:0] ins_key_cached;
reg [VAL_WIDTH-1:0] ins_val_cached;
reg [SIZE-1:0] write_addr = {SIZE{1'b0}};
reg [SIZE-1:0] next_addr = {SIZE{1'b0}};
always @(posedge clk) begin
if (reset) begin
ins_state <= ST_IDLE;
next_addr <= {SIZE{1'b0}};
end else begin
case (ins_state)
// Idle and waiting for an insert transaction
//
ST_IDLE: begin
// Cache insertion parameters
if (insert_stb) begin
ins_key_cached <= insert_key;
ins_val_cached <= insert_val;
// Wait for find to finish
ins_state <= find_busy ? ST_WAIT_FIND : ST_CAM_READ;
end
end
// Wait for a find transaction to finish
//
ST_WAIT_FIND: begin
// Wait for find to finish
if (~find_busy)
ins_state <= ST_CAM_READ;
end
// Read the CAM to check if the key to insert already exists
//
ST_CAM_READ: begin
// Ensure that find always has priority
if (~find_key_stb)
ins_state <= ST_CAM_CHECK_MATCH;
end
// Look at the CAM match signal to evaluate if we skip writing the CAM
//
ST_CAM_CHECK_MATCH: begin
// If the CAM already has this key, then overwrite it
if (cam_rd_match) begin
ins_state <= ST_RAM_WRITE;
write_addr <= cam_rd_addr;
end else if (~cam_wr_busy) begin
ins_state <= ST_CAM_RAM_WRITE;
write_addr <= next_addr;
next_addr <= next_addr + 1'b1;
end
end
// Write the specified key to the CAM and value to the RAM
//
ST_CAM_RAM_WRITE: begin
ins_state <= ST_CAM_WRITE_WAIT;
end
// Wait for CAM write to finish
//
ST_CAM_WRITE_WAIT: begin
if (~cam_wr_busy) begin
ins_state <= ST_IDLE;
count <= next_addr;
end
end
// Write the specified value to the RAM
//
ST_RAM_WRITE: begin
ins_state <= ST_IDLE;
count <= next_addr;
end
default: begin
// We should not get here
ins_state <= ST_IDLE;
end
endcase
end
end
// CAM Read Port:
// - Find has priority so it can interrupt an insert
assign cam_rd_key =
(ins_state != ST_CAM_READ || find_key_stb) ? find_key : ins_key_cached;
// RAM Write Port:
// - The RAM write enable is held high for 1 cycle
// - The address may come from a CAM lookup or could generated
assign ram_wr_en = (ins_state == ST_RAM_WRITE || ins_state == ST_CAM_RAM_WRITE);
assign ram_wr_addr = write_addr;
assign ram_wr_data = ins_val_cached;
// CAM Write Port:
// - The CAM write enable is held high for 1 cycle
// - The address may come from a CAM lookup or could generated (same as RAM)
assign cam_wr_en = (ins_state == ST_CAM_RAM_WRITE);
assign cam_wr_addr = write_addr;
assign cam_wr_data = ins_key_cached;
// Outputs
assign insert_busy = (ins_state != ST_IDLE);
assign find_res_val = ram_rd_data;
endmodule