I would like to implement a count min sketch with minimal update and access times.
Basically an input sample is hashed by multiple (d) hash functions and each of them increments a counter in the bucket that it hits. When querying for a sample, the counters of all the buckets corresponding to a sample are compared and the value of the smallest counter is returned as a result.
I am trying to find the minimum value of the counters in log_2(d) time with the following code:
entity main is
Port ( rst : in STD_LOGIC;
a_val : out STD_LOGIC_VECTOR(63 downto 0);
b_val : out STD_LOGIC_VECTOR(63 downto 0);
output : out STD_LOGIC_VECTOR(63 downto 0);
. .
. .
. .
CM_read_ready : out STD_LOGIC;
clk : in STD_LOGIC);
end main;
architecture Behavioral of main is
impure function min( LB, UB: in integer; sample: in STD_LOGIC_VECTOR(long_length downto 0)) return STD_LOGIC_VECTOR is
variable left : STD_LOGIC_VECTOR(long_length downto 0) := (others=>'0');
variable right : STD_LOGIC_VECTOR(long_length downto 0) := (others=>'0');
begin
if (LB < UB)
then
left := min(LB, ((LB + UB) / 2) - 1, sample);
right := min(((LB + UB) / 2) - 1, UB, sample);
if (to_integer(unsigned(left)) < to_integer(unsigned(right)))
then
return left;
else
return right;
end if;
elsif (LB = UB)
then
-- return the counter's value so that it can be compared further up in the stack.
return CM(LB, (to_integer(unsigned(hasha(LB)))*to_integer(unsigned(sample))
+ to_integer(unsigned(hashb(LB)))) mod width);
end if;
end min;
begin
CM_hashes_read_log_time: process (clk, rst)
begin
if (to_integer(unsigned(instruction)) = 2)
then
output <= min(0, depth - 1, sample);
end if;
end if;
end process;
end Behavioral;
When I run the above code, I get the following errors:
The simulator has terminated in an unexpected manner. Please review the simulation log (xsim.log) for details.
[USF-XSim-62] 'compile' step failed with error(s). Please check the Tcl console output or '/home/...sim/sim_1/behav/xsim/xvhdl.log' file for more information.
[USF-XSim-62] 'elaborate' step failed with error(s). Please check the Tcl console output or '/home/...sim/sim_1/synth/func/xsim/elaborate.log' file for more information.
I was not able to find any file called xsim.log and xvhdl.log was empty, but elaborate.log had some content:
Vivado Simulator 2018.2
Copyright 1986-1999, 2001-2018 Xilinx, Inc. All Rights Reserved.
Running: /opt/Xilinx/Vivado/2018.2/bin/unwrapped/lnx64.o/xelab -wto c199c4c74e8c44ef826c0ba56222b7cf --incr --debug typical --relax --mt 8 -L xil_defaultlib -L secureip --snapshot main_tb_behav xil_defaultlib.main_tb -log elaborate.log
Using 8 slave threads.
Starting static elaboration
Completed static elaboration
INFO: [XSIM 43-4323] No Change in HDL. Linking previously generated obj files to create kernel
Removing the following line solves the above errors:
output <= min(0, depth - 1, sample);
My questions:
not that I was able to find any real world use for recursion, but just to surprise @EML (as requested in the comments above): you actually can define recursive hardware structures in VHDL.
In Quartus at least, this only works if you give the compiler a clear indication of the maximum recursion depth, otherwise it will try to unroll the recursion to any possible input, eventually dying from a stack overflow:
entity recursive is
generic
(
MAX_RECURSION_DEPTH : natural
);
port
(
clk : in std_ulogic;
n : in natural;
o : out natural
);
end recursive;
architecture Behavioral of recursive is
function fib(max_depth : natural; n : natural) return natural is
variable res : natural;
begin
if max_depth <= 1 then
res := 0;
return res;
end if;
if n = 0 then
res := 0;
elsif n = 1 or n = 2 then
res := 1;
else
res := fib(max_depth - 1, n - 1) + fib(max_depth - 1, n - 2);
end if;
return res;
end function fib;
begin
p_calc : process
begin
wait until rising_edge(clk);
o <= fib(MAX_RECURSION_DEPTH, n);
end process;
end Behavioral;
With a MAX_RECURSION_DEPTH of 6, this generates one single combinational circuit with more than 500 LEs (so the pracical use is probably very limited), but at least it works.