Efficient modular arithmetic in VHDL

Question

I'm building some modules in VHDL for handling modular arithmetic and want to make sure it's well-designed for timing and somewhat efficient when scaling up. This will need to work with 128-bit or 256-bit arithmetic when complete, but I'm testing it currently with small 16-bit numbers currently. There are two modules: mod_add for the basic modular arithmetic and mod_mul for the multiplication built on top of modular addition.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity mod_add is
 generic(
 bits : positive := 16;
 modulo : positive := 15
 );
 port(
 clk : in std_logic;
 rst : in std_logic;
 a : in std_logic_vector(bits-1 downto 0);
 b : in std_logic_vector(bits-1 downto 0);
 q : out std_logic_vector(bits-1 downto 0) := (others => '0')
 );
end entity;
architecture behavior of mod_add is
 constant modulo_c : std_logic_vector(bits-1 downto 0) := std_logic_vector(to_unsigned(modulo, bits));
 signal q_int : std_logic_vector(bits downto 0) := (others => '0');
 signal q_out : std_logic_vector(bits downto 0) := (others => '0');
begin
 process(clk)
 begin
 if rising_edge(clk) then
 if rst = '1' then
 q_int <= (others => '0');
 q_out <= (others => '0');
 else
 q_int <= std_logic_vector(unsigned("0" & a) + unsigned("0" & b));
 if unsigned(q_int) >= unsigned("0" & modulo_c) then
 q_out <= std_logic_vector(unsigned(q_int) - unsigned(modulo_c));
 else
 q_out <= q_int;
 end if;
 end if;
 end if;
 end process;
 q <= q_out(bits-1 downto 0);
end architecture behavior;
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity mod_mul is
 generic(
 bits : positive := 16;
 modulo : positive := 15
 );
 port(
 clk : in std_logic;
 rst : in std_logic;
 load : in std_logic;
 ready : out std_logic := '0';
 a : in std_logic_vector(bits-1 downto 0);
 b : in std_logic_vector(bits-1 downto 0);
 q : out std_logic_vector(bits-1 downto 0) := (others => '0')
 );
end entity;
architecture behavior of mod_mul is
 component mod_add
 generic(
 bits : positive := 16;
 modulo : positive := 15
 );
 port(
 clk : in std_logic;
 rst : in std_logic;
 a : in std_logic_vector(bits-1 downto 0);
 b : in std_logic_vector(bits-1 downto 0);
 q : out std_logic_vector(bits-1 downto 0)
 );
 end component mod_add;
 constant p_c : std_logic_vector(bits-1 downto 0) := std_logic_vector(to_unsigned(modulo, bits));
 signal q_int : std_logic_vector(bits downto 0) := (others => '0');
 signal q_out : std_logic_vector(bits downto 0) := (others => '0');
 constant b_zero : std_logic_vector(bits-1 downto 0) := (others => '0');
 signal b_shift : std_logic_vector(bits-1 downto 0) := (others => '0');
 signal culm : std_logic_vector(bits-1 downto 0) := (others => '0');
 signal val : std_logic_vector(bits-1 downto 0) := (others => '0');
 signal culm_add_val : std_logic_vector(bits-1 downto 0) := (others => '0');
 signal val_double : std_logic_vector(bits-1 downto 0) := (others => '0');
 signal counter : std_logic_vector(1 downto 0) := "00";
begin
 culm_add_val_proc: mod_add generic map(
 bits => bits,
 modulo => modulo
 ) port map(
 clk => clk,
 rst => rst,
 a => culm,
 b => val,
 q => culm_add_val
 );
 val_double_proc: mod_add generic map(
 bits => bits,
 modulo => modulo
 ) port map(
 clk => clk,
 rst => rst,
 a => val,
 b => val,
 q => val_double
 );
 process(clk)
 begin
 if rising_edge(clk) then
 if rst = '1' then
 counter <= (others => '0');
 elsif load = '1' then
 counter <= (others => '0');
 else
 counter <= std_logic_vector(unsigned(counter) + 1);
 end if;
 end if;
 end process;
 process(clk)
 begin
 if rising_edge(clk) then
 if rst = '1' then
 culm <= (others => '0');
 val <= (others => '0');
 elsif load = '1' then
 culm <= (others => '0');
 val <= a;
 b_shift <= b;
 elsif counter = "10" then
 if b_shift(0) = '1' then
 culm <= culm_add_val;
 end if;
 val <= val_double;
 b_shift <= "0" & b_shift(bits-1 downto 1);
 end if;
 end if;
 end process;
 q <= culm;
 ready <= '1' when b_shift = b_zero else '0';
end architecture behavior;

And the test bench for mod_mul:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity test_mod_mul is
end entity test_mod_mul;
architecture behavioral of test_mod_mul is
 component mod_mul
 generic(
 bits : positive := 16;
 modulo : positive := 15
 );
 port(
 clk : in std_logic;
 rst : in std_logic;
 load : in std_logic;
 ready : out std_logic;
 a : in std_logic_vector(bits-1 downto 0);
 b : in std_logic_vector(bits-1 downto 0);
 q : out std_logic_vector(bits-1 downto 0)
 );
 end component mod_mul;
 constant clk_period : time := 20 ns;
 signal halt : boolean := false;
 signal clk : std_logic := '0';
 signal rst : std_logic := '0';
 signal load : std_logic := '0';
 signal a, b : std_logic_vector(15 downto 0);
 signal a_in, b_in : integer := 0;
 signal ready : std_logic;
 signal q : std_logic_vector(15 downto 0);
 signal q_out : integer;
begin
 uut: mod_mul port map(
 clk => clk,
 rst => rst,
 load => load,
 ready => ready,
 a => a,
 b => b,
 q => q
 );
 a <= std_logic_vector(to_unsigned(a_in, a'length));
 b <= std_logic_vector(to_unsigned(b_in, b'length));
 q_out <= to_integer(unsigned(q));
 process
 begin
 clk <= '1';
 wait for clk_period/2;
 clk <= '0';
 wait for clk_period/2;
 if halt then
 wait;
 end if;
 end process;
 process
 procedure check_multiply(
 constant a, b : in integer;
 constant q : in integer) is
 begin
 wait until falling_edge(clk);
 a_in <= a;
 b_in <= b;
 load <= '1';
 wait for clk_period;
 load <= '0';
 wait until rising_edge(clk) and ready = '1';
 assert q_out = q report "Failed mod multiplication" severity error;
 end procedure check_multiply;
 begin
 rst <= '1';
 wait for 10*clk_period;
 rst <= '0';
 wait for clk_period;
 assert ready = '1' report "Not ready" severity error;
 assert q_out = 0 report "Failed mod multiplication" severity failure;
 check_multiply(2, 2, 4);
 check_multiply(2, 3, 6);
 check_multiply(3, 3, 9);
 check_multiply(4, 4, 1);
 check_multiply(6, 5, 0);
 check_multiply(6, 7, 12);
 wait for 1000 ns;
 halt <= true;
 wait;
 end process;
end architecture behavioral;

• JHBonarius: Can I ask what you are designing? ASIC? FPGA? What synthesis tools are you using? What arithmetic functions do you want to realize (in equations)?

Answer 1

Layout

The code is laid out very well, with consistent indentation and structure. This makes the code very easy to understand.

Partitioning

You did a good job of splitting the design code into different files/entities with hierarchy, making the code easy to reuse for other purposes. The clear separation between design and testbench code also makes the design easy to test.

Scale

You mentioned efficiency with scaling the design up as a goal, and I think you succeeded there with the generic parameters.

Testbench

It is superb that you made the testbench code self-checking. You made the code modular with the check_multiply procedure, again making the code easy to understand and maintain.

Naming

The entity names are a bit cryptic. If "mod" is short for "modulo", I recommend using the full word:

modulo_multiply
modulo_add

The signal name q is not very descriptive. In the adder code, consider naming it sum, and in the multiply code, consider result. The same goes for signals like q_int, q_out, etc. It's not clear what is meant by "int". Maybe you meant "internal", but it could be read as "integer", etc.

Documentation

It would be good to add header comments to each design file summarizing the features of each design.

Test

You could simplify the testbench further by calculating the expected value inside check_multiply instead of passing it into the procedure.

You could elaborate on the failure message by also printing out the input values and expected and actual result values.

Add checks of larger values, especially trying the maximum input values.

In addition to the directed checks, add checks for random input values. You could add a loop to cycle through hundreds of values, which should not take much simulation time.