Friday, 11 January 2019

Unexpected patterns in Verilog $random


I have a Verilog test bench that monitors a 64-bit bus and should randomly schedule a flipped bit (packet corruption) to happen every 1-in-X packets. I was surprised to find it not injecting any corruption, and seemingly this is due to patterns in $random ?


Verilog module, placed inline with bus:


module test_cable  #(
parameter EMPTY_BITS = 3,
parameter DATA_BITS = 64
) (
input wire clk,


input wire [DATA_BITS-1:0] eth_c2cable_data,
input wire eth_c2cable_valid,
input wire eth_c2cable_sop,
input wire [EMPTY_BITS-1:0] eth_c2cable_empty,
input wire eth_c2cable_eop,
input wire eth_c2cable_error,
output wire eth_c2cable_ready,

output wire [DATA_BITS-1:0] eth_cable2s_data,

output wire eth_cable2s_valid,
output wire eth_cable2s_sop,
output wire [EMPTY_BITS-1:0] eth_cable2s_empty,
output wire eth_cable2s_eop,
output wire eth_cable2s_error,
input wire eth_cable2s_ready
);

// Corruption control task
// 2'b00 clean

// 2'b01 corrupt 1 pkt in 2^6
// 2'b10 corrupt 1 pkt in 2^7
// 2'b11 corrupt 1 pkt in 2^8
reg [1:0] ready_control = 2'b00;
reg [31:0] random_next = 0;

task setCorruptControl;
input [1:0] bitf;
begin
ready_control <= bitf;

end
endtask

// ready bit control
reg [7:0] corrupt_at_cycle = 0;
wire [31:0] random_mask = (1'b1 << (6+ready_control))-1;
always @(posedge clk) begin
random_next <= $random;

if ((eth_c2cable_sop && eth_c2cable_valid) && ready_control > 0 && (random_next & random_mask) == 32'b0) begin

// corrupt this packet at some point. we don't know how big packet is, so somewhere in first 16 cycles
// if the packet stops before we corrupt, we'll hit the next one
corrupt_at_cycle <= random_next[24 +: 4];
$display("Scheduling corruption %t for +%d cycles %08x", $time, random_next[24 +: 4], random_next);

end else if (corrupt_at_cycle > 0 && eth_c2cable_valid) begin
corrupt_at_cycle <= corrupt_at_cycle - 1'b1;
end

if (eth_c2cable_corruption != 0) begin

$display("Corrupting wire packet with noise %016x", eth_c2cable_corruption);
end
end

// corrupt by flipping single bit in this cycle
wire [63:0] eth_c2cable_corruption = corrupt_at_cycle == 1 ? { 1'b1 << random_next[24 +: 5] } : 64'b0;

assign eth_cable2s_data = eth_c2cable_data ^ eth_c2cable_corruption;
assign eth_cable2s_valid = eth_c2cable_valid;
assign eth_cable2s_sop = eth_c2cable_sop;

assign eth_cable2s_eop = eth_c2cable_eop;
assign eth_cable2s_empty = eth_c2cable_empty;
assign eth_cable2s_error = eth_c2cable_error;
assign eth_c2cable_ready = eth_cable2s_ready;

endmodule

Looking at the simulation output corruption is always scheduled to occur in zero cycles, so never happens:


...
Scheduling corruption 882531000 for + 0 cycles 40002780

Scheduling corruption 887190000 for + 0 cycles 002edf00
Scheduling corruption 894192000 for + 0 cycles 4049c380
Scheduling corruption 907395000 for + 0 cycles c0270a80
Scheduling corruption 948746000 for + 0 cycles 4010dd80
Scheduling corruption 959389000 for + 0 cycles 40155b80
Scheduling corruption 964957000 for + 0 cycles c0357a80
...
^ ^

This seems to be caused by bits random_next[24 +: 4] and random_next[0 +: 6] being zero coincidently. I arbitrarily chose the bits from 24 hoping they would have no correlation with the low bits. Is this a weakness with the Verilog pseudo-random number algorithm, or a problem with the Icarus Verilog simulator?



After much bug-hunting, I modified occurrences of random_next[24 +: 4] to random_next[28 +: 4] and the test bench works.



Answer



I have written a little testbench that demonstrates the problem stand-alone:


module testbench;

integer i, j = 0;
reg [31:0] randval;

initial begin
for (i = 0; i < 100000; i = i+1) begin

randval = $random;
if (randval[0 +: 6] == 0) begin
$display("%8d %6d: %x -> %d %d", i, j, randval, randval[0 +: 6], randval[24 +: 4]);
if (randval[24 +: 4] != 0) $finish;
j = j + 1;
end
end
$display("IEEE Std 1364-2005 $random (rtl_dist_uniform(seed, LONG_MIN, LONG_MAX)) sucks!");
end


endmodule

The really interesting thing here is that the exact behavior of $random is defined in IEEE Std 1364-2005. There is actually C code in the standard (pages 317 and 318). I don't want to quote it here in full, but a copy of the code can be found for example in Icarus Verilog:


https://github.com/steveicarus/iverilog/blob/master/vpi/sys_random.c


Calling $random in Verilog equals to calling rtl_dist_uniform(&a_seed, INT_MIN, INT_MAX) in this C file.


So what you demonstrated here is not only a weakness in $random of just one particular simulator, but a weakness in $random in general.


One solution would be to simply implement your own random number generator. I often use the Xorshift family of random number generators because they work fairly well and are easy to implement:


http://en.wikipedia.org/wiki/Xorshift


The following example uses a 64 bit xorshift to generate 32 bit numbers:


module testbench;


reg [63:0] xorshift64_state = 64'd88172645463325252;

task xorshift64_next;
begin
// see page 4 of Marsaglia, George (July 2003). "Xorshift RNGs". Journal of Statistical Software 8 (14).
xorshift64_state = xorshift64_state ^ (xorshift64_state << 13);
xorshift64_state = xorshift64_state ^ (xorshift64_state >> 7);
xorshift64_state = xorshift64_state ^ (xorshift64_state << 17);
end

endtask

integer i;
initial begin
for (i = 0; i < 100; i = i+1) begin
xorshift64_next;
$display("%x", xorshift64_state[31:0]);
end
end


endmodule

No comments:

Post a Comment

arduino - Can I use TI&#39;s cc2541 BLE as micro controller to perform operations/ processing instead of ATmega328P AU to save cost?

I am using arduino pro mini (which contains Atmega328p AU ) along with cc2541(HM-10) to process and transfer data over BLE to smartphone. I...