// Associative memory implemented with a linear search.
// For use in LSU EE 4702 Spring 2000.
// Intended to show how an implicit state machine description can be
// transformed into an explicit state machine description. A
// practical associative memory would not use a sequential linear
// search.
// All modules pass the testbench (amt.v). All but the first module
// are synthesizable by Leonardo 1999.1f and the synthesized Verilog
// passes the testbench. (The synthesized implicit state machine will
// only work if the flip-flop primitives are redefined so they
// initialize to state zero. This is due to a shortcoming of Leonardo
// or the Leonardo documentation.)
// The costs and clock frequencies of the modules appear at the
// end of this file.
// Testbench is in file amt.v
// Uncomment one of the AM_foo macros below.
// Non-synthesizable version.
//`define AM_NOT_SYN
// Implicit state machine.
//`define AM_SYN_ISM
// Explicit state machine based on explicit state machine.
//`define AM_SYN_ESM_1
// Streamlined explicit state machine
//`define AM_SYN_ESM_2
`define AM_SYN_ISM_SH
`define dsize 8
`define dbits `dsize-1:0
`define ksize 8
`define kbits `ksize-1:0
`define size_lg 5
`define sbits (`size_lg-1):0
`define size (1<<`size_lg)
`define srange `size-1:0
`ifdef AM_NOT_SYN
module am(data_out,found,ready,full,data_in,key,op,clk);
input data_in, key, op, clk;
output data_out, found, ready, full;
parameter op_reset = 0;
parameter op_insert = 1;
parameter op_remove = 2;
parameter op_lookup = 3;
parameter op_nop = 4;
wire [`dbits] data_in;
wire [`kbits] key;
wire [2:0] op;
wire clk;
reg [`dbits] data_out;
reg found, ready;
wire full;
reg [`size_lg:0] occ;
reg [`dbits] data [`srange];
reg [`kbits] keys [`srange];
reg valid [`srange];
reg [`sbits] ptr;
reg ptr_empty_valid;
reg [`sbits] ptr_empty;
assign full = occ[`size_lg];
always @( posedge clk )
case( op )
op_reset:
begin
ptr = 0; occ = 0;
ready = 0; found = 0;
begin:RESET_SEARCH
forever begin
valid[ptr] = 0;
ptr = ptr + 1;
if( !ptr ) disable RESET_SEARCH;
end
end
@( negedge clk ) ready = 1;
end
op_insert:
begin
ptr = 0; ready = 0; ptr_empty_valid = 0;
begin:INSERT_SEARCH
forever begin
if( !valid[ptr] && !ptr_empty_valid ) begin
ptr_empty_valid = 1;
ptr_empty = ptr;
end
if( valid[ptr] && keys[ptr] === key ) begin
found = 1;
data[ptr] = data_in;
data_out = data_in;
disable INSERT_SEARCH;
end
ptr = ptr + 1;
if( !ptr ) begin // Loop Exit
found = 0;
if( ptr_empty_valid ) begin
keys[ptr_empty] = key;
data[ptr_empty] = data_in;
valid[ptr_empty] = 1;
occ = occ + 1;
end
disable INSERT_SEARCH;
end
end // forever begin
end // block: INSERT_SEARCH
@( negedge clk ) ready = 1;
end // case: op_insert
op_remove, op_lookup:
begin
ptr = 0; ready = 0;
begin:REMOVE_SEARCH
forever begin
if( valid[ptr] && keys[ptr] == key ) begin
if( op == op_remove ) begin
valid[ptr] = 0;
occ = occ - 1;
end
data_out = data[ptr]; found = 1;
disable REMOVE_SEARCH;
end
ptr = ptr + 1;
if( !ptr ) begin found = 0; disable REMOVE_SEARCH; end
end
end
@( negedge clk ) ready = 1;
end // case: op_remove
// Do nothing.
op_nop: @( negedge clk ) ready = 1;
default: begin
$display("Invalid operation: %d",op);
$stop;
end
endcase // case( op )
endmodule // am
`endif // ifdef AM_NOT_SYN
//
// Using an implicit state machine.
//
`ifdef AM_SYN_ISM
// Note: For simulation of synthesized module, zero must be a valid
// state of the implicit state variable and so binary or gray coding
// must be used. This is a bug workaround.
//
// exemplar encoding binary
//
module am(data_out,found,ready,full,data_in,key,op,clk);
input data_in, key, op, clk;
output data_out, found, ready, full;
parameter op_reset = 0;
parameter op_insert = 1;
parameter op_remove = 2;
parameter op_lookup = 3;
parameter op_nop = 4;
wire [`dbits] data_in;
wire [`kbits] key;
wire [2:0] op;
wire clk;
reg [`dbits] data_out;
reg found, ready;
wire full;
reg [`size_lg:0] occ;
reg [`dbits] data [`srange];
reg [`kbits] keys [`srange];
reg valid [`srange];
reg [`sbits] ptr;
reg ptr_empty_valid;
reg [`sbits] ptr_empty;
assign full = occ[`size_lg];
always @( posedge clk ) begin
// State 0: ready
case( op )
op_reset:
begin
ptr = 0; occ = 0;
ready = 0; found = 0;
begin:RESET_SEARCH
forever @( posedge clk ) begin
// State 1: reset_item
valid[ptr] = 0;
ptr = ptr + 1;
if( !ptr ) disable RESET_SEARCH;
end
end
ready = 1;
end
op_insert:
begin
ptr = 0; ready = 0; ptr_empty_valid = 0;
begin:INSERT_SEARCH
forever @( posedge clk ) begin
// State 2: insert
if( !ptr_empty_valid && !valid[ptr] ) begin
ptr_empty_valid = 1;
ptr_empty = ptr;
end
if( valid[ptr] && keys[ptr] === key ) begin
found = 1;
data[ptr] = data_in;
data_out = data_in;
disable INSERT_SEARCH;
end
ptr = ptr + 1;
if( !ptr ) begin
found = 0;
if( ptr_empty_valid ) begin
keys[ptr_empty] = key;
data[ptr_empty] = data_in;
valid[ptr_empty] = 1;
occ = occ + 1;
end
disable INSERT_SEARCH;
end
end // forever begin
end // block: INSERT_SEARCH
ready = 1;
end // case: op_insert
op_remove, op_lookup:
begin
ptr = 0; ready = 0;
begin:REMOVE_SEARCH
forever @( posedge clk ) begin
// State 3: rem_look
if( valid[ptr] && keys[ptr] === key ) begin
if( op == op_remove ) begin
valid[ptr] = 0;
occ = occ - 1;
end
data_out = data[ptr]; found = 1;
disable REMOVE_SEARCH;
end
ptr = ptr + 1;
if( !ptr ) begin
found = 0;
disable REMOVE_SEARCH;
end
end
end
ready = 1;
end // case: op_remove
// Do nothing.
op_nop: @( posedge clk ) ready = 1;
default: begin
// exemplar translate_off
$display("Invalid operation: %d",op);
$stop;
// exemplar translate_on
end
endcase // case( op )
end // block: MAIN
endmodule // am
`endif
`ifdef AM_SYN_ISM_SH
// Note: For simulation of synthesized module, zero must be a valid
// state of the implicit state variable and so binary or gray coding
// must be used. This is a bug workaround.
//
// exemplar encoding binary
//
module am(data_out,found,ready,full,data_in,key,op,clk);
input data_in, key, op, clk;
output data_out, found, ready, full;
parameter op_reset = 0;
parameter op_insert = 1;
parameter op_remove = 2;
parameter op_lookup = 3;
parameter op_nop = 4;
wire [`dbits] data_in;
wire [`kbits] key;
wire [2:0] op;
wire clk;
reg [`dbits] data_out;
reg found, ready;
wire full;
reg [`size_lg:0] occ;
reg [`dbits] data [`srange], temp_data;
reg [`kbits] keys [`srange], temp_keys;
reg valid [`srange], temp_valid;
reg [`sbits] ptr;
reg ptr_empty_valid;
reg [`sbits] ptr_empty;
assign full = occ[`size_lg];
integer i;
task shift;
begin
temp_data = data[0]; temp_keys = keys[0]; temp_valid = valid[0];
for(i=0; i<`size-1; i=i+1) begin
data[i] = data[i+1]; keys[i] = keys[i+1]; valid[i] = valid[i+1];
end
data[`size-1] = temp_data;
keys[`size-1] = temp_keys;
valid[`size-1] = temp_valid;
end
endtask // shift
always @( posedge clk ) begin
// State 0: ready
case( op )
op_reset:
begin
ptr = 0; occ = 0;
ready = 0; found = 0;
begin:RESET_SEARCH
forever @( posedge clk ) begin
// State 1: reset_item
valid[0] = 0;
shift;
ptr = ptr + 1;
if( !ptr ) disable RESET_SEARCH;
end
end
ready = 1;
end
op_insert:
begin
ptr = 0; ready = 0; ptr_empty_valid = 0;
begin:INSERT_SEARCH
begin:REPLACE_SEARCH forever @( posedge clk ) begin
// State 2: insert
if( valid[0] && keys[0] === key ) begin
found = 1;
data[0] = data_in;
data_out = data_in;
disable INSERT_SEARCH;
end
ptr = ptr + 1;
if( !ptr ) disable REPLACE_SEARCH;
shift;
end end
ptr = 0; found = 0;
forever @( posedge clk ) begin
if( !valid[0] ) begin
keys[0] = key;
data[0] = data_in;
valid[0] = 1;
occ = occ + 1;
disable INSERT_SEARCH;
end
ptr = ptr + 1;
if( !ptr ) disable INSERT_SEARCH;
shift;
end
end // block: INSERT_SEARCH
ready = 1;
end // case: op_insert
op_remove, op_lookup:
begin
ptr = 0; ready = 0;
begin:REMOVE_SEARCH
forever @( posedge clk ) begin
// State 3: rem_look
if( valid[0] && keys[0] === key ) begin
if( op == op_remove ) begin
valid[0] = 0;
occ = occ - 1;
end
data_out = data[0]; found = 1;
disable REMOVE_SEARCH;
end
ptr = ptr + 1;
shift;
if( !ptr ) begin
found = 0;
disable REMOVE_SEARCH;
end
end
end
ready = 1;
end // case: op_remove
// Do nothing.
op_nop: @( posedge clk ) ready = 1;
default: begin
// exemplar translate_off
$display("Invalid operation: %d",op);
$stop;
// exemplar translate_on
end
endcase // case( op )
end // block: MAIN
endmodule // am
`endif
//
// Using an explicit state machine, first attempt.
//
// Similar to code above (to show how code was modified). The description
// does simulate and synthesize correctly.
//
`ifdef AM_SYN_ESM_1
// exemplar encoding binary
module am(data_out,found,ready,full,data_in,key,op,clk);
input data_in, key, op, clk;
output data_out, found, ready, full;
parameter op_reset = 0;
parameter op_insert = 1;
parameter op_remove = 2;
parameter op_lookup = 3;
parameter op_nop = 4;
wire [`dbits] data_in;
wire [`kbits] key;
wire [2:0] op;
wire clk;
reg [`dbits] data_out;
reg found, ready;
wire full;
reg [`size_lg:0] occ;
reg [`dbits] data [`srange];
reg [`kbits] keys [`srange];
reg valid [`srange];
reg [`sbits] ptr;
reg ptr_empty_valid;
reg [`sbits] ptr_empty;
parameter st_ready = 0,
st_reset = 1,
st_insert = 2,
st_rem_look = 3;
reg [1:0] state, next_state;
assign full = occ[`size_lg];
// Note: It would be foolish--and Leonardo won't stand in your way
// or even warn you--to update clk on the positive edge because
// next_state is also updated on the positive edge.
always @( negedge clk ) state <= next_state;
always @( posedge clk ) begin
case( state )
st_ready:
// State 0: ready
case( op )
op_reset:
begin
ptr = 0; occ = 0;
ready = 0; found = 0;
next_state = st_reset;
// begin:RESET_SEARCH
// forever @( posedge clk ) begin
// // State 1: reset
// valid[ptr] = 0;
// ptr = ptr + 1;
// if( !ptr ) disable RESET_SEARCH;
// end
// end
// ready = 1;
end
op_insert:
begin
ptr = 0; ready = 0; ptr_empty_valid = 0;
next_state = st_insert;
// begin:INSERT_SEARCH
// forever @( posedge clk ) begin
// // State 2: insert
// if( !ptr_empty_valid && !valid[ptr] ) begin
// ptr_empty_valid = 1;
// ptr_empty = ptr;
// end
// if( valid[ptr] && keys[ptr] === key ) begin
// found = 1;
// data[ptr] = data_in;
// data_out = data_in;
// disable INSERT_SEARCH;
// end
// ptr = ptr + 1;
// if( !ptr ) begin
// found = 0;
// disable INSERT_SEARCH;
// end
// end // forever begin
// end // block: INSERT_SEARCH
// if( !found && ptr_empty_valid ) begin
// keys[ptr_empty] = key;
// data[ptr_empty] = data_in;
// valid[ptr_empty] = 1; occ = occ + 1;
// end
// ready = 1;
end // case: op_insert
op_remove, op_lookup:
begin
ptr = 0; ready = 0;
next_state = st_rem_look;
// begin:REMOVE_SEARCH
// forever @( posedge clk ) begin
// // State 3: rem_look
// if( valid[ptr] && keys[ptr] == key ) begin
// if( op == op_remove ) begin
// valid[ptr] = 0;
// occ = occ - 1;
// end
// data_out = data[ptr]; found = 1;
// disable REMOVE_SEARCH;
// end
// ptr = ptr + 1;
// if( !ptr ) begin
// found = 0;
// disable REMOVE_SEARCH;
// end
// end
// end
// ready = 1;
end // case: op_remove
// Do nothing.
op_nop: ready = 1;
default: begin
// exemplar translate_off
$display("Invalid operation: %d",op);
$stop;
// exemplar translate_on
end
endcase // case( op )
st_reset: begin
begin:RESET_SEARCH
// forever @( posedge clk ) begin
// State 1: reset
valid[ptr] = 0;
ptr = ptr + 1;
if( !ptr ) begin
// disable RESET_SEARCH;
next_state = st_ready;
ready = 1;
end
end
end
st_insert: begin
begin:INSERT_SEARCH
//forever @( posedge clk ) begin
// State 2: insert
if( !ptr_empty_valid && !valid[ptr] ) begin
ptr_empty_valid = 1;
ptr_empty = ptr;
end
if( valid[ptr] && keys[ptr] === key ) begin
found = 1;
data[ptr] = data_in;
data_out = data_in;
ready = 1;
next_state = st_ready;
disable INSERT_SEARCH;
end
ptr = ptr + 1;
if( !ptr ) begin
found = 0;
ready = 1;
if( ptr_empty_valid ) begin
keys[ptr_empty] = key;
data[ptr_empty] = data_in;
valid[ptr_empty] = 1;
occ = occ + 1;
end
next_state = st_ready;
disable INSERT_SEARCH;
end
// end // forever begin
end // block: INSERT_SEARCH
end // case: st_insert
st_rem_look: begin
begin:REMOVE_SEARCH
// forever @( posedge clk ) begin
// State 3: rem_look
if( valid[ptr] && keys[ptr] == key ) begin
if( op == op_remove ) begin
valid[ptr] = 0;
occ = occ - 1;
end
data_out = data[ptr]; found = 1;
ready = 1; next_state = st_ready;
disable REMOVE_SEARCH;
end
ptr = ptr + 1;
if( !ptr ) begin
found = 0;
ready = 1; next_state = st_ready;
disable REMOVE_SEARCH;
end
// end
end // block: REMOVE_SEARCH
end // case: st_rem_look
// exemplar translate_off
// Still need an explicit reset.
2'bxx: next_state = st_ready;
// exemplar translate_on
default: begin
// exemplar translate_off
$display("Invalid state."); $stop;
// exemplar translate_on
end
endcase // case( state )
end // always @ ( posedge clk )
endmodule // am
`endif
//
// Using an explicit state machine, second attempt.
//
// Based on the code above, but reorganized and streamlined.
//
`ifdef AM_SYN_ESM_2
// exemplar encoding binary
module am(data_out,found,ready,full,data_in,key,op,clk);
input data_in, key, op, clk;
output data_out, found, ready, full;
parameter op_reset = 0;
parameter op_insert = 1;
parameter op_remove = 2;
parameter op_lookup = 3;
parameter op_nop = 4;
wire [`dbits] data_in;
wire [`kbits] key;
wire [2:0] op;
wire clk;
reg [`dbits] data_out;
reg found;
wire ready;
wire full;
reg [`size_lg:0] occ;
reg [`dbits] data [`srange];
reg [`kbits] keys [`srange];
reg valid [`srange];
reg [`sbits] ptr;
reg ptr_empty_valid;
reg [`sbits] ptr_empty;
parameter /* exemplar enum states */ st_ready = 0,
st_reset = 1,
st_insert = 2,
st_rem_look = 3;
reg [1:0] /* exemplar enum states */ state, next_state;
assign full = occ[`size_lg];
assign ready = state == st_ready;
// Note: It would be foolish--and Leonardo won't stand in your way
// or even warn you--to update clk on the positive edge because
// next_state is also updated on the positive edge.
always @( negedge clk ) state <= next_state;
always @( posedge clk ) begin
// Note: The directives below are needed despite the fact that
// state is an enumerated type and all states appear. (Leonardo 1999.1f)
// exemplar parallel_case
// exemplar full_case
case( state )
st_ready: // State 0: ready
// exemplar parallel_case
// exemplar full_case
case( op )
op_reset: begin
ptr = 0; occ = 0; found = 0;
next_state = st_reset;
end
op_insert: begin
ptr = 0; ptr_empty_valid = 0;
next_state = st_insert;
end
op_remove, op_lookup: begin
ptr = 0;
next_state = st_rem_look;
end
// Do nothing.
op_nop:;
default: begin
// exemplar translate_off
$display("Invalid operation: %d",op);
$stop;
// exemplar translate_on
end
endcase // case( op )
st_reset: begin // State 1: reset
valid[ptr] = 0;
ptr = ptr + 1;
if( !ptr ) next_state = st_ready;
end
st_insert: begin // State 2: insert
if( !valid[ptr] && !ptr_empty_valid ) begin
ptr_empty_valid = 1;
ptr_empty = ptr;
end
if( valid[ptr] && keys[ptr] === key ) begin
data[ptr] = data_in;
data_out = data_in;
found = 1;
next_state = st_ready;
end else begin
ptr = ptr + 1;
if( !ptr ) begin
if( ptr_empty_valid ) begin
keys[ptr_empty] = key;
data[ptr_empty] = data_in;
valid[ptr_empty] = 1;
occ = occ + 1;
end
found = 0;
next_state = st_ready;
end
end
end // case: st_insert
st_rem_look: begin
// State 3: rem_look
if( valid[ptr] && keys[ptr] == key ) begin
if( op == op_remove ) begin valid[ptr] = 0; occ = occ - 1; end
data_out = data[ptr]; found = 1;
next_state = st_ready;
end else begin
ptr = ptr + 1;
if( !ptr ) begin
found = 0;
next_state = st_ready;
end
end // else: !if( valid[ptr] && keys[ptr] == key )
end // case: st_rem_look
// exemplar translate_off
// Still need an explicit reset.
2'bxx: next_state = st_ready;
// exemplar translate_on
// exemplar translate_off
default: begin
$display("Invalid state."); $stop;
end
// exemplar translate_on
endcase // case( state )
end // always @ ( posedge clk )
endmodule // am
`endif
// Cost and Performance of Linear Search Associative Memory Variations
// Run with "quick" optimization and set to optimize delay. Synthesized
// for the sample ASIC.
// Implicit State Machine
// Number of ports : 31
// Number of nets : 1594
// Number of instances : 1556
// Number of references to this view : 0
// Number of gates : 10806
// clk : 120.7 MHz
// Explicit State Machine 1
// Number of ports : 31
// Number of nets : 1602
// Number of instances : 1565
// Number of references to this view : 0
// Number of gates : 10800
// clk : 128.2 MHz
// Explicit State Machine 2
// Number of ports : 31
// Number of nets : 1563
// Number of instances : 1531
// Number of references to this view : 0
// Number of gates : 10710
// clk : 120.2 MHz