可合成的 VHDL 递归，Vivado：模拟器以意外方式终止

Question

我想实现一个 count min sketch 更新和访问时间最少的系统。

基本上，一个输入样本由多个 (d) 散列函数散列，每个散列函数都会在它命中的桶中增加一个计数器。查询一个样本时，比较一个样本对应的所有桶的counter，返回最小的counter的值。

我正在尝试使用以下代码在 log_2(d) 时间内找到计数器的最小值：

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;

当我运行上述代码时，出现以下错误：

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.

我找不到任何名为 xsim.log 的文件并且 xvhdl.log 是空的，但是 elaborate.log 有一些内容：

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

删除以下行可解决上述错误：

output <= min(0, depth - 1, sample);

我的问题：

为什么我无法模拟这段代码？
此代码运行后是否可以合成？
是否有更好（and/or 更快）的方法来获取所有相关哈希桶中的最小值？

Answer 1

并不是说我能够找到递归在现实世界中的任何用途，只是让@EML 感到惊讶（如上面评论中所要求的）：您实际上可以定义递归硬件VHDL 中的结构。

至少在 Quartus 中，这仅在您为编译器提供最大递归深度的明确指示时才有效，否则它会尝试将递归展开到任何可能的输入，最终死于堆栈溢出：

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;

MAX_RECURSION_DEPTH 为 6，这会生成一个具有超过 500 个 LE 的组合电路（因此实际使用可能非常有限），但至少它有效。

Answer 2

VHDL 中可以递归吗？

我会说，是的，但不是我们所知道的递归。这是简短的回答。我有代码（如果有人对实现 Quicksort 感兴趣的话），它会非常愉快地合成。如果有人知道 Quicksort，它通常不会出现在综合的上下文中。但是我做到了。

诀窍（这是无理取闹且难以理解的）是在将“状态”推入（硬件）堆栈后，用一个奇怪的状态机模拟递归，该状态机回溯到起始状态。如果你愿意，你可以很容易地合成这种数据结构。

我记得 Thatcher、Goguen 和 Wright 写的一些有趣的文章，内容涉及从一种编码域到其他编码域（简而言之，不同的计算模型）的语义转换。

我确实觉得这可能是更一般意义上的实际递归表达式的起源点。但请注意，这非常困难。

可合成的 VHDL 递归，Vivado：模拟器以意外方式终止

Synthesizable VHDL recursion, Vivado: simulator has terminated in an unexpected manner

simulation

synthesis

vhdl

vivado