// Testbench for associative memory module.
// For use in LSU EE 4702 Spring 2000.
// Tested modules are in file am.v
`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
// The number of rounds is the number of times a particular key
// is used in a test. In each round of a test a particular operation
// is applied to a key. For example, in a particular test the first
// time any key is used it will be "insert"ed into the am, the
// second time (round) any key is used it will be "remove"d. These
// operations are specified by strings passed to the do_test task.
`define maxrounds 20
// The shadow arrays hold three more elements than the associative array
// can. The idea is to try to insert something when the am is full.
`define size_plus (`size+3)
`define srange_plus (`size_plus-1):0
// Works for size_lg >= 2
`define sbits_plus `size_lg:0
module am_test();
wire [`dbits] dout;
wire found, rdy, full;
reg [`dbits] din;
reg [`kbits] key;
reg [2:0] op;
reg clk;
am am1(dout,found,rdy,full,din,key,op,clk);
// States for the shadow array.
parameter st_never_used = 0;
parameter st_in = 1;
parameter st_removed = 2;
// Parameters from am duplicated because Leonardo does not preserve
// them in synthesized modules.
parameter op_reset = 0;
parameter op_insert = 1;
parameter op_remove = 2;
parameter op_lookup = 3;
parameter op_nop = 4;
// Shadow registers keep track of test data. They do not exactly
// duplicate the similarly named registers in the module.
reg [`dbits] shadow_data [`srange_plus], exp_data;
reg [`kbits] shadow_key [`srange_plus];
reg [2:0] shadow_state [`srange_plus];
integer shadow_round [`srange_plus];
integer shadow_occ;
integer round_op[`maxrounds-1:0];
// Expected outputs of module.
reg exp_full, exp_found;
integer test_index [`size_plus*`maxrounds-1:0];
integer test_size;
time timeout;
reg valid;
integer i;
function [31:0] randi;
input [31:0] limit;
randi = ( $random >> 1 ) % limit;
endfunction // randi
// Perform a test specified by a string. (See comment near maxrounds, above.)
task do_test;
input [(`maxrounds+1)*8-1:0] rts_po;
reg [(`maxrounds+1)*8-1:0] op_str;
integer rounds, r;
begin
$display("Starting test %s",rts_po);
// Determine number of rounds and reverse string.
rounds = 0;
while( rts_po[7:0] )
begin
op_str = op_str << 8;
op_str[7:0] = rts_po[7:0];
rts_po = rts_po >> 8;
rounds = rounds + 1;
end
// Initialize round_op array based on characters in string.
for(r=0; r<rounds; r=r+1) begin
case( op_str[7:0] )
"r": round_op[r] = op_remove;
"i": round_op[r] = op_insert;
"l": round_op[r] = op_lookup;
"n": round_op[r] = op_nop;
default: begin
$display("Unexpected op in test string.");
$stop;
end
endcase // case( op_str[7:0] )
op_str = op_str >> 8;
end
// Prepare the array of key indices.
init_test(rounds);
// Perform the actual tests.
execute_test;
end
endtask // parse_test
task init_test;
input [31:0] rounds;
integer i, j, r, temp, pos;
begin
test_size = `size_plus * rounds;
// Set array test_index to:
// 0 1 2 ... `size_plus-1 0 1 2 ... `size_plus-1 0 1 ...
j = 0;
for(r=0; r<rounds; r=r+1) for(i=0; i<`size_plus; i=i+1) begin
test_index[j] = i;
j = j + 1;
end
// Randomly rearrange the elements of test_index.
for(j=0; j<test_size; j=j+1) begin
pos = randi(test_size);
temp = test_index[j]; test_index[j] = test_index[pos];
test_index[pos] = temp;
end
// Initialize the array keeping track of the round for a key.
for(i=0; i<`size_plus; i=i+1) shadow_round[i] = 0;
end
endtask // init_test
task execute_test;
integer i, j, new_data;
begin
@( negedge clk );
if( !rdy ) begin $display("Expected module to be ready."); $stop; end
for(i=0; i<test_size; i=i+1) begin
// j is the element number in shadow_foo to use.
j = test_index[i];
// Command the am to perform the indicated operation, and
// determine the expected outputs. Update shadow_foo.
// Note that the (correct) current outputs are different
// than the expected outputs so expected outputs use
// delayed assignments.
case( round_op[shadow_round[j]] )
op_insert: begin
new_data = $random;
op = op_insert;
key = shadow_key[j];
din = new_data;
exp_found <= @( negedge rdy ) shadow_state[j] === st_in;
exp_data <= @( negedge rdy ) new_data;
if( shadow_state[j] !== st_in && !full ) begin
shadow_occ <= @( negedge rdy ) shadow_occ + 1;
if( shadow_occ === `size - 1) exp_full <= @( negedge rdy ) 1;
shadow_state[j] = st_in;
end
shadow_data[j] = new_data;
end
op_lookup: begin
op = op_lookup;
key = shadow_key[j];
din = $random;
exp_found <= @( negedge rdy ) shadow_state[j] === st_in;
exp_data <= @( negedge rdy ) shadow_data[j];
end
op_remove: begin
op = op_remove;
key = shadow_key[j];
din = $random;
exp_found <= @( negedge rdy ) shadow_state[j] === st_in;
exp_data <= @( negedge rdy ) shadow_data[j];
if( shadow_state[j] === st_in ) begin
shadow_occ <= @( negedge rdy ) shadow_occ - 1;
exp_full <= @( negedge rdy ) 0;
shadow_state[j] = st_removed;
end
end // case: op_remove
op_nop: begin
op = op_nop;
key = shadow_key[j];
din = $random;
exp_found <= @( negedge rdy ) 0;
end
endcase // case( round_op[shadow_round[j]] )
shadow_round[j] = shadow_round[j] + 1;
if( !rdy ) begin
$display("Should be ready.");
$stop;
end
// A nop does not cause rdy to go low.
if( op !== op_nop ) @( posedge rdy );
end // for(i=0;
op = op_nop;
end
endtask // execute_test
always #10 clk = !clk;
// Display an error message if rdy does not go high after a certain
// amount of time.
always @( valid or negedge rdy )
fork:WATCHDOG
#(timeout) begin
$display("Module did not respond in time.");
$stop;
end
@( posedge rdy ) disable WATCHDOG;
join
// Check the outputs at appropriate times.
always @( posedge rdy or found or dout or full or valid )
if( valid && rdy ) #1 begin
if( found !== exp_found ) begin
$display("Disagreement on found"); $stop;
end
if( found && dout !== exp_data ) begin
$display("Disagreement on data."); $stop;
end
if( full !== exp_full ) begin
$display("Disagreement on full."); $stop;
end
end // if ( valid && rdy )
initial begin
// Testbench can't test modules with less than four items.
if( `size_lg < 2 ) begin
$display("Testbench cannot handle size_lg less than 2."); $stop;
end
// Set to 1 when valid output expected.
valid = 0;
clk = 0;
timeout = `size * 20 * 3;
// Initialize shadow structures.
for(i=0;i<`size_plus;i=i+1) begin
shadow_state[i] = st_never_used;
shadow_data[i] = $random;
shadow_key[i] = {$random,i[`sbits_plus]};
end
shadow_occ = 0;
exp_full = 0; exp_found = 0; exp_data = 0;
// Reset module.
op = op_nop;
wait( rdy );
op = op_reset;
wait( !rdy );
valid = 1;
op = op_nop;
wait( rdy );
// Do the tests.
//
// Test coding: "i", insert; "r", remove; "l", lookup; "n", nop.
do_test("ir"); // Partially fill and empty.
do_test("l"); // Make sure it's still empty.
do_test("i"); // Make sure it's still empty, and fill it...
do_test("r"); // ... and empty it ...
do_test("iri"); // ... and fill it once again, though not monotonically.
do_test("li"); // Make sure it's still full.
do_test("r"); // Empty again.
do_test("inrlirlirnirliri"); // Slowly fill.
do_test("r"); // Quickly empty.
$display("Completed all tests successfully.");
$stop;
end // initial begin
endmodule // am_test