Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Умножение 64 бит на константу с переполнением.
Форум разработчиков электроники ELECTRONIX.ru > Программируемая логика ПЛИС (FPGA,CPLD, PLD) > Работаем с ПЛИС, области применения, выбор
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

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

Krys
Цитата(count_enable @ Sep 18 2015, 01:22) *
Делаю конгруэнтный генератор.
У меня тоже ламерский вопрос: посоветуйте, пожалуйста, где простым языком написано про этот генератор и как сделать умножение переполнением.
count_enable
Со своим "ламерским вопросом" я разобрался - теперь синтезирует как надо.

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

У меня теперь более серьезный вопрос: мне надо умножать на 64-битную константу. Если синтезировать с DSP48, скорость получается под 155 МГц, если без DSP48- 166 МГц.
Понятно, что надо давать конвеер. Ведь умножение на константу можно разбить на сдвиг и сложение. Как правильно разбить на этапы умножение на 6364136223846793005ULL ?
Bad0512
Цитата(count_enable @ Sep 18 2015, 00:22) *
Так как xilinx не воспринимает числа больше 32 бит

Не вздумайте им об этом сообщить - они очень обидятся...
А по сабжу - не пробовали для константы явно разрядность указать? Это по умолчанию константы 32-битные, но никто не запрещает сделать и с большей разрядностью.
Golikov A.
ну это просто

( A + B ) * ( C + D ) = AC+BC+AD+BD.
вот и делите свое число 64 бита на несколько частей 32 или вообще 16 бит, перемножаете, выравниваете порядки и все... можно на одном 32 битном умножителе за 4-6 тактов перемножать 64 на 64
Krys
Цитата(Golikov A. @ Sep 18 2015, 16:31) *
ну это просто

( A + B ) * ( C + D ) = AC+BC+AD+BD.
вот и делите свое число 64 бита на несколько частей 32 или вообще 16 бит, перемножаете, выравниваете порядки и все... можно на одном 32 битном умножителе за 4-6 тактов перемножать 64 на 64

Добавлю: теория есть на стр. 28 вот тут: http://www.xilinx.com/support/documentatio...uides/ug389.pdf

Цитата(count_enable @ Sep 18 2015, 16:18) *
Со своим "ламерским вопросом" я разобрался - теперь синтезирует как надо.
А как решили проблему?

Цитата(count_enable @ Sep 18 2015, 16:18) *
Делаю я это: http://www.pcg-random.org/ . Переполнение там не для умножения, а просто как часть алгоритма, как я понял
А LFSR не устраивает по степени "случайности"?
Maverick
Цитата(count_enable @ Sep 18 2015, 12:18) *
Как правильно разбить на этапы умножение на 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-битные множить.
Golikov A.
будет лучше сделать

Код
s1 <= (64'd1<<61);
s2 <= (64'd1<<59) + s1;
s3 <= (64'd1<<58) + s2;
....

только сдается мне что это константу так набирать всяко хуже...
Maverick
Цитата(count_enable @ Sep 18 2015, 14:00) *

посмотрите и это
тут можно скачать xapp211.zip

Просто можно использовать несколько LSFR - думаю тогда случайность улучшится, в xapp211 используется 2 LSFR , но думаю если по копать то можно и больше сделать и приблизиться к случайности...
Хотя уверенности в этом нет - не знаю...

dm.pogrebnoy
Цитата(Maverick @ Sep 18 2015, 14:14) *
Просто можно использовать несколько LSFR - думаю тогда случайность улучшится, в xapp211 используется 2 LSFR , но думаю если по копать то можно и больше сделать и приблизиться к случайности...
Хотя уверенности в этом нет - не знаю...
.


Дык вроде XORSHIFT оно и есть. И качество хорошее.

http://xorshift.di.unimi.it/
blackfin
Цитата(Maverick @ Sep 18 2015, 14:14) *
Просто можно использовать несколько LSFR - думаю тогда случайность улучшится, в xapp211 используется 2 LSFR ...

Путаетесь в показаниях? -> LFSR.. rolleyes.gif
Maverick
Цитата(blackfin @ Sep 18 2015, 14:49) *
Путаетесь в показаниях? -> LFSR.. rolleyes.gif

опечатка вышла blush.gif

просто скопипастил отсюда:

Цитата(count_enable @ Sep 18 2015, 14:00) *
От себя добавлю что LSFR хоть и простейший...
count_enable
Пока гуру занимаются правописанием sm.gif, я быстренько набросал сумматор с шифтером. Получилось 1276 slice regs, и 498 МГц для Виртекса 7. Можно ли сделать лучше? Скорость на втором месте, размер на первом.

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
constant inc: unsigned:=x"34";
signal state:unsigned (63 downto 0);
type istate_type is array (0 to 33) of unsigned (127 downto 0);
signal istate: istate_type;
signal counter: integer range 0 to 33;

--- Multiplication constant: 101100001010001111101000010110101001100100101010111111100101101
begin

process(CLK)
begin
if(rising_edge(CLK)) then
if(RST='1') then

istate(0)<=to_unsigned(integer(1),istate(0)'length); -- init seed
else
istate(0)(63 downto 0)<=state;
istate(1)<=istate(0)+(istate(0) sll 2);
istate(2)<=istate(1)+(istate(0) sll 3);
istate(3)<=istate(2)+(istate(0) sll 5);
istate(4)<=istate(3)+(istate(0) sll 8);
istate(5)<=istate(4)+(istate(0) sll 9);

istate(6)<=istate(5)+(istate(0) sll 10);
istate(7)<=istate(6)+(istate(0) sll 11);
istate(8)<=istate(7)+(istate(0) sll 12);
istate(9)<=istate(8)+(istate(0) sll 13);

istate(10)<=istate(9)+(istate(0) sll 14);
istate(11)<=istate(10)+(istate(0) sll 16);
istate(12)<=istate(11)+(istate(0) sll 18);
istate(13)<=istate(12)+(istate(0) sll 20);

istate(14)<=istate(13)+(istate(0) sll 23);
istate(15)<=istate(14)+(istate(0) sll 26);
istate(16)<=istate(15)+(istate(0) sll 27);
istate(17)<=istate(16)+(istate(0) sll 30);

istate(18)<=istate(17)+(istate(0) sll 32);
istate(19)<=istate(18)+(istate(0) sll 34);
istate(20)<=istate(19)+(istate(0) sll 35);
istate(21)<=istate(20)+(istate(0) sll 37);

istate(22)<=istate(21)+(istate(0) sll 42);
istate(23)<=istate(22)+(istate(0) sll 44);
istate(24)<=istate(23)+(istate(0) sll 45);
istate(25)<=istate(24)+(istate(0) sll 46);

istate(26)<=istate(25)+(istate(0) sll 47);
istate(27)<=istate(26)+(istate(0) sll 48);
istate(28)<=istate(27)+(istate(0) sll 52);
istate(29)<=istate(28)+(istate(0) sll 54);

istate(30)<=istate(29)+(istate(0) sll 59);
istate(31)<=istate(30)+(istate(0) sll 60);
istate(32)<=istate(31)+(istate(0) sll 62);
end if;
end if;
end process;
------------------------------------- blocking state refresh until we finish the pipeline once
process (CLK, RST)
begin
if(rising_edge(CLK)) then
if(RST='1') then
counter<=0;
state<=to_unsigned(integer(1),state'length);
else
if (counter/=32) then
counter<=counter+1;
else
state<=istate(32)(63 downto 0)+inc;
end if;
end if;
end if;
end process;
outstate<=std_logic_vector(state);
end Behavioral;

count_enable
Переписал код с использованием 1 сдвигового регистра, на котором в цикле и сдвигается вся портянка. Как МАС, только SAC - shift-add accumulator. 390Regs /340 LUT, но почему-то скорость упала до 370 МГц. Учитывая что теперь вычисление нового состояния занимает 34 цикла, эффективная скорость в районе 12 Мегачисел. Совсем не радужно sad.gif. Вроде конвееризировал правильно..

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

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

architecture Behavioral of small_pcg is
component SHIFT_ADD
Port ( CLK : in STD_LOGIC;
RST: in STD_LOGIC;
A : in STD_LOGIC_VECTOR (63 downto 0);
B : in STD_LOGIC_VECTOR (63 downto 0);
SHIFT : in STD_LOGIC_VECTOR (5 downto 0);
OUTPUT : out STD_LOGIC_VECTOR (63 downto 0));
end component;

type integer_arrray is array (0 to 33) of integer;
constant shift_values: integer_arrray:=(0,2,3,5,8,9,10,11,12,13,14,16,18,20,23,26,27,30,32,34,35,37,42,
44,45,46,47,48,52,54,59,60,62,0); -- соответствует "1" в константе, последний 0 - заглушка
signal inA,inB,shifter_out: STD_LOGIC_VECTOR (63 downto 0);
signal SHIFT:STD_LOGIC_VECTOR (5 downto 0);
signal state,state1,state2:unsigned(127 downto 0);
signal oldstate:unsigned(63 downto 0);
signal counter: integer range 0 to 32;
signal save:std_logic;
begin
process(CLK)
begin
if(rising_edge(CLK)) then
if(RST='1') then
state<=(to_unsigned(integer(1),state'length));
state1<=(to_unsigned(integer(0),state1'length));
state2<=(to_unsigned(integer(0),state2'length));
oldstate<=(to_unsigned(integer(1),oldstate'length));
counter<=0;
else
if (counter/=32) then
state(63 downto 0)<=oldstate;
state1<=(state sll shift_values(counter)); -- вот здесь в цикле мы сдвигаем...
state2<=state1+state2; -- вот здесь в цикле и суммируем...
counter<=counter+1;
else
counter<=0;
oldstate<=state2(63 downto 0); -- новое состояние вычислено
end if;

end if;
end if;
end process;
OUTPUT<=std_logic_vector(oldstate);
end Behavioral;
andrew_b
Цитата(count_enable @ Sep 18 2015, 21:45) *
Код
            state1<=(state sll shift_values(counter)); -- вот здесь в цикле мы сдвигаем...

А не получился ли тут у вас мультиплексор 32 сдвинутых state? Может, вы хотите что-то типа

Код
            state1<=(state1 sll 1); -- вот здесь в цикле мы сдвигаем...
count_enable
Да, сдвиг на 1 куда "дешевле", но тогда надо 64 такта. Получается в районе 270 блоков и 500 МГц. Т.е. в 4 раза меньше и 64 медленнее комбинаторного решения. Ну что ж, как говорил великий философ Мик Джаггер, "You can't always get what you want". Зато все мыслимые тесты на рандомность проходит, хоть в NSA отдавай.
Krys
Цитата(count_enable @ Sep 18 2015, 18:00) *
Это НИОКР
А в чём же здесь буква "Н" кроется, если, как Вы говорите, "всё уже украдено до нас"? )))

andrew_b
Цитата(count_enable @ Sep 20 2015, 12:29) *
Да, сдвиг на 1 куда "дешевле", но тогда надо 64 такта. Получается в районе 270 блоков и 500 МГц. Т.е. в 4 раза меньше и 64 медленнее комбинаторного решения.
Не понял, откуда в 64 раза медленнее? Как процесс занимал 32 такта, так и будет занимать. Предлагается только вместо того, чтобы для каждого такта использовать сдвинутое число state, использовать сдвинутое число state1 из предыдущего такта.
count_enable
Цитата(Krys @ Sep 20 2015, 12:40) *
А в чём же здесь буква "Н" кроется, если, как Вы говорите, "всё уже украдено до нас"? )))
Реализация в железе с оптимизацией под это самое железо - еще не украдены sm.gif. Этот генератор к тому же имеет возможность делать т.н. "party tricks", т.е. возможно так задавать зерно, что он будет генерировать заданные последовательности. Это можно использовать как цифровой водяной знак. Но это уже в дальнейшей перспективе.
Krys
Цитата(count_enable @ Sep 21 2015, 16:03) *
Реализация в железе с оптимизацией под это самое железо
Ну это всё же инженерия, а не "Н". Если Эйнштейн (условно) придумал формулу, а я её запрограммировал, это же не значит, что открытие сделал я. Открытие сделал Эйнштейн. Я лишь это открытие реализовал.
count_enable
С точки зрения фундаментальных дисциплин в электронике вообще практически нету "науки" - прочитал идею, спаял девайс и подгоняй результат под теорию. Поэтому мне больше нравится английский термин R&D - Research and Development. Исследовательско-конструкторская работа.
Krys
Цитата(count_enable @ Sep 21 2015, 18:18) *
С точки зрения фундаментальных дисциплин в электронике вообще практически нету "науки" - прочитал идею, спаял девайс и подгоняй результат под теорию
Не согласен. "Идею" нужно придумать самому. Наука - не обязательно сделать открытие. И слово Research тоже к науке относится: нужно исследовать неисследованное. Т.е. вывести формулу зависимости, описать её и т.д.
Так что я бы не стал говорить, что инженерия = Research. Под Research всё же подразумевается наука. И я не стал бы выдавать инженерию за науку, ссылаясь на то, что в радиоэлектронике вообще нет науки. В электронике можно найти и инженерию, и науку.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.