Умножение 64 бит на константу с переполнением. Опции

[count_enable]

Вопрос конечно ламерский, но что-то не решается.

Делаю конгруэнтный генератор. В С проблемный кусок выглядит так:

Код

uint64_t state;  // это состояние генератора, оно раз инициализируется.
uint64_t штс;  // это шаг генератора, оно раз инициализируется.
....
//в цикле:
uint64_t oldstate =state;
// Advance internal state
state = oldstate * 6364136223846793005ULL;
state=state + (inc|1);

То есть код исползует переполнение, что и надо реализовать в VHDL. Как мне кажется, умножение на константу и операция модуло не должны создать проблем при синтезе. Симуляция работает корректно в ISim. Но...

Вот мой код:

CODE

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;


entity state_change is
Port ( CLK : in STD_LOGIC;
RST : in STD_LOGIC;
outstate : out STD_LOGIC_VECTOR (63 downto 0));
end state_change;

architecture Behavioral of state_change is
function decimal_string_to_unsigned(decimal_string: string; wanted_bitwidth: positive) return unsigned is
variable tmp_unsigned: unsigned(wanted_bitwidth+3 downto 0) := (others => '0'); -- 4 extra bits to detect overflow
variable character_value: integer;
begin
for string_pos in decimal_string'range loop
case decimal_string(string_pos) is
when '0' => character_value := 0;
when '1' => character_value := 1;
when '2' => character_value := 2;
when '3' => character_value := 3;
when '4' => character_value := 4;
when '5' => character_value := 5;
when '6' => character_value := 6;
when '7' => character_value := 7;
when '8' => character_value := 8;
when '9' => character_value := 9;
when others => report("Illegal number") severity failure;
end case;
tmp_unsigned := tmp_unsigned(wanted_bitwidth-1 downto 0) * to_unsigned(10, 4);
tmp_unsigned := tmp_unsigned + character_value;
if tmp_unsigned(wanted_bitwidth+3 downto wanted_bitwidth) /= "0000" then
report("Too large number") severity failure;
end if;
end loop;
return tmp_unsigned(wanted_bitwidth-1 downto 0);
end decimal_string_to_unsigned;
constant MUL_CONST_str: string := "6364136223846793005";
constant max_64bit_string: string:="18446744073709551615";
constant M: unsigned(63 downto 0) := decimal_string_to_unsigned(MUL_CONST_str, 64); -- вот на это надо умножить
constant max_64bit: unsigned(63 downto 0) := decimal_string_to_unsigned(max_64bit_string, 64);

constant inc: unsigned:=x"34";

signal istate: unsigned (63 downto 0);
signal istate1: unsigned (127 downto 0);

begin

process(CLK)
begin
if(rising_edge(CLK)) then
if(RST='1') then
istate<=to_unsigned(integer(95516),istate'length);
istate1<=to_unsigned(integer(95516),istate1'length);
else
istate1<=(istate*M) ;
istate<=istate1(63 downto 0)+inc;
end if;
end if;
end process;
outstate<=std_logic_vector(istate);
end Behavioral;

Так как xilinx не воспринимает числа больше 32 бит, добавил функцию конверсии числа. Но к сожалению, при синтезе я получаю 64 защёлки и огромную портянку ворнингов:

CODE

=======================================================================
==
* HDL Synthesis *
=========================================================================

Synthesizing Unit <state_change>.
Related source file is "C:\Why\Life\Is\So\Hard\state_change.vhd".
Found 72-bit register for signal <istate1>.
Found 64-bit register for signal <outstate>.
Found 64-bit adder for signal <istate1[63]_GND_4_o_add_1_OUT> created at line 61.
Found 64x63-bit multiplier for signal <n0010> created at line 60.
Summary:
inferred 1 Multiplier(s).
inferred 1 Adder/Subtractor(s).
inferred 136 D-type flip-flop(s).
inferred 1 Multiplexer(s).
Unit <state_change> synthesized.

=========================================================================
HDL Synthesis Report

Macro Statistics
# Multipliers : 1
64x63-bit multiplier : 1
# Adders/Subtractors : 1
64-bit adder : 1
# Registers : 2
64-bit register : 1
72-bit register : 1
# Multiplexers : 1
64-bit 2-to-1 multiplexer : 1

=========================================================================

=========================================================================
* Advanced HDL Synthesis *
=========================================================================

WARNING:Xst:1710 - FF/Latch <istate1_37> (without init value) has a constant value of 0 in block <state_change>. This FF/Latch will be trimmed during the optimization process.
WARNING:Xst:1895 - Due to other FF/Latch trimming, FF/Latch <istate1_38> (without init value) has a constant value of 0 in block <state_change>. This FF/Latch will be trimmed during the optimization process.
WARNING:Xst:1895 - Due to other FF/Latch trimming, FF/Latch <istate1_39> (without init value) has a constant value of 0 in block <state_change>. This FF/Latch will be trimmed during the optimization process.
WARNING:Xst:1895 - Due to other FF/Latch trimming, FF/Latch <istate1_40> (without init value) has a constant value of 0 in block <state_change>. This FF/Latch will be trimmed during the optimization process.
.........................................................................
WARNING:Xst:1895 - Due to other FF/Latch trimming, FF/Latch <istate1_52> (without init value) has a constant value of 0 in block <state_change>. This FF/Latch will be trimmed during the optimization process.
WARNING:Xst:1895 - Due to other FF/Latch trimming, FF/Latch <istate1_53> (without init value) has a constant value of 0 in block <state_change>. This FF/Latch will be trimmed during the optimization process.
WARNING:Xst:1895 - Due to other FF/Latch trimming, FF/Latch <istate1_54> (without init value) has a constant value of 0 in block <state_change>. This FF/Latch will be trimmed during the optimization process.
.........................................................................
Optimizing unit <state_change> ...
WARNING:Xst:1710 - FF/Latch <istate_4> (without init value) has a constant value of 1 in block <state_change>. This FF/Latch will be trimmed during the optimization process.
WARNING:Xst:1710 - FF/Latch <istate1_0> (without init value) has a constant value of 0 in block <state_change>. This FF/Latch will be trimmed during the optimization process.
WARNING:Xst:1895 - Due to other FF/Latch trimming, FF/Latch <istate_0> (without init value) has a constant value of 0 in block <state_change>. This FF/Latch will be trimmed during the optimization process.

Mapping all equations...
Building and optimizing final netlist ...
Found area constraint ratio of 100 (+ 5) on block state_change, actual ratio is 0.
INFO:Xst:2260 - The FF/Latch <istate_3> in Unit <state_change> is equivalent to the following FF/Latch : <istate1_2>

Final Macro Processing ...

=========================================================================
Final Register Report

Macro Statistics
# Registers : 6
Flip-Flops : 6

=========================================================================

[count_enable]

Со своим "ламерским вопросом" я разобрался - теперь синтезирует как надо.

Делаю я это: http://www.pcg-random.org/ . Переполнение там не для умножения, а просто как часть алгоритма, как я понял.

У меня теперь более серьезный вопрос: мне надо умножать на 64-битную константу. Если синтезировать с DSP48, скорость получается под 155 МГц, если без DSP48- 166 МГц.
Понятно, что надо давать конвеер. Ведь умножение на константу можно разбить на сдвиг и сложение. Как правильно разбить на этапы умножение на 6364136223846793005ULL ?

[Maverick]

Как правильно разбить на этапы умножение на 6364136223846793005ULL ?

Это число не простое и состоит из множителей
3
5
415949
1020018675983

т.е. 3*5*415949*1020018675983 = 6364136223846793005

множители в свою очередь уже простые числа.

+ совет от ув. Golikov A.

[count_enable]

А как решили проблему?

Было: istate1<=(istate*M) rem (max_64bit-1); стало istate1<=(istate*M); istate<=istate(63 downto 0) + inc; Писал вечером и котелок не особо варил, поэтому вставил ненужное rem, оно и портило.

А LFSR не устраивает по степени "случайности"?

Это НИОКР, поэтому нету понятия "устраивает". Есть понятие "больше-лучше". От себя добавлю что LSFR хоть и простейший, но случайность его удручающа и даже в простых симуляциях при 32-битном регистре видимы периодические процессы. Плюс распределение не является нормальным.
Данный же генератор по утверждению создательницы лучше существующих. В подтверждение - общепринятые тесты типа TestU01.

т.е. 3*5*415949*1020018675983 = 6364136223846793005

Cпасибо большое. А если сделать что-то типа:

Код

s1<=2**62;
s2<=2**60+s1;
s3<=2**59+s2;
....

Будет лучше, хуже или так же само? Думаю обойтись без DSP48. С множителем понятно, что надо 18-битные множить.

[Krys]

Это НИОКР

А в чём же здесь буква "Н" кроется, если, как Вы говорите, "всё уже украдено до нас"? )))

[count_enable]

А в чём же здесь буква "Н" кроется, если, как Вы говорите, "всё уже украдено до нас"? )))

Реализация в железе с оптимизацией под это самое железо - еще не украдены . Этот генератор к тому же имеет возможность делать т.н. "party tricks", т.е. возможно так задавать зерно, что он будет генерировать заданные последовательности. Это можно использовать как цифровой водяной знак. Но это уже в дальнейшей перспективе.

[Krys]

Реализация в железе с оптимизацией под это самое железо

Ну это всё же инженерия, а не "Н". Если Эйнштейн (условно) придумал формулу, а я её запрограммировал, это же не значит, что открытие сделал я. Открытие сделал Эйнштейн. Я лишь это открытие реализовал.