Search code examples
vhdlramlookup-tables

VHDL - How to compare two bit_vectors for dynamic table lookup

I'm storing two tables in two signals. One table keeps the key (address) and the other keeps the value corresponding to the key. I need to compare an input to the key and, if they match, return the value stored.

The reason why I need this is for a dynamic lookup table for branch instruction prediction. In the fetch stage of a processor I get the input Instruction_Address and I return a branch_To_Address and a branch_Prediction. Initially I want to store 16 predictions/branch addresses and use a circular buffer ring to overwrite as needed.

I've been trying to use a FOR with a nested IF to search for the key inside keyTable.

The whole module seems to work fine, except when I compare two bit_vectors with the IF statement. I need this twice (one on read and another on write) and hence I need to "sweep" the keysTable so I can see if the address that is being looked up has an entry.

I noticed the error upon simulation, where the ELSE clause is being called always regardless of the keysTable having the right entries.

Verifiable example:

library IEEE;
use ieee.numeric_bit.all;

entity branch_prediction_table is
generic (
    addrSize    : NATURAL   := 4;
    tableSize   : NATURAL   := 4);
port (
    clock : in bit;
    input_addr: in bit_vector(addrSize-1 downto 0);
    return_value : out bit );
end branch_prediction_table;

architecture branch_table of branch_prediction_table is

    signal keysTable : bit_vector(addrSize*tableSize-1 downto 0) := ( others => '0');
    signal valuesTable : bit_vector(tableSize*2-1 downto 0) := ( others => '0');

begin

    tableProc: process(clock) is

        variable valueFromTable : bit;
    begin
        if rising_edge(clock) then

            search_table: for iR in (tableSize-1) to 0 loop

                if (keysTable(addrSize*(iR+1)-1 downto addrSize*iR) = input_addr) then
                    valueFromTable := valuesTable((iR+1)*2-1);
                    EXIT search_table;
                else
                    valueFromTable := '0';
                end if;

            end loop search_table;

            return_value <= valueFromTable;

        end if; -- rising_edge(clock)
    end process tableProc;
end branch_table;

with verifiable testbench simulation TCL:

add wave -position insertpoint  \
sim:/branch_prediction_table/addrSize \
sim:/branch_prediction_table/clock \
sim:/branch_prediction_table/input_addr \
sim:/branch_prediction_table/keysTable \
sim:/branch_prediction_table/return_value \
sim:/branch_prediction_table/tableSize \
sim:/branch_prediction_table/valuesTable
force -freeze sim:/branch_prediction_table/valuesTable 11111111 0
force -freeze sim:/branch_prediction_table/keysTable 1111101001100011 0
force -freeze sim:/branch_prediction_table/clock 0 0, 1 {5000 ps} -r {10 ns}
run 10 ns
force -freeze sim:/branch_prediction_table/input_addr 1010 0
run 20 ns
force -freeze sim:/branch_prediction_table/input_addr 1111 0
run 10 ns

and testbench simulation result showing that error is indeed in the IF: Verifiable Testbench Simulation

I have tried converting them with to_integer(unsigned(bit_vector1)) = to_integer(unsigned(bit_vector2)) with no avail

Solution

  • As user1155120 pointed out:

    The problem lies within search_table: for iR **in** (tableSize-1) to 0 loop

    It should've been "down to" as L > R. Since I used "in" with L>R, that produces a null range and the for loop iteration is said to be complete.

    (IEEE Std 1076-2008 5.2 Scalar types, "A range specifies a subset of values of a scalar type. A range is said to be a null range if the specified subset is empty. The range L to R is called an ascending range; if L > R, then the range is a null range. The range L downto R is called a descending range; if L < R, then the range is a null range.").

    10.10 Loop statement "For the execution of a loop with a for iteration scheme, the discrete range is first evaluated. If the discrete range is a null range, the iteration scheme is said to be complete, ..."