реклама на сайте
подробности

 
 
2 страниц V   1 2 >  
Reply to this topicStart new topic
> Умножение 64 бит на константу с переполнением.
count_enable
сообщение Sep 17 2015, 18:22
Сообщение #1


Местный
***

Группа: Свой
Сообщений: 310
Регистрация: 28-01-13
Из: Лондон
Пользователь №: 75 384



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

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

Код
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

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

Go to the top of the page
 
+Quote Post
Krys
сообщение Sep 18 2015, 08:32
Сообщение #2


Гуру
******

Группа: Свой
Сообщений: 2 002
Регистрация: 17-01-06
Из: Томск, Россия
Пользователь №: 13 271



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


--------------------
Зная себе цену, нужно ещё и пользоваться спросом...
Go to the top of the page
 
+Quote Post
count_enable
сообщение Sep 18 2015, 09:18
Сообщение #3


Местный
***

Группа: Свой
Сообщений: 310
Регистрация: 28-01-13
Из: Лондон
Пользователь №: 75 384



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

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

У меня теперь более серьезный вопрос: мне надо умножать на 64-битную константу. Если синтезировать с DSP48, скорость получается под 155 МГц, если без DSP48- 166 МГц.
Понятно, что надо давать конвеер. Ведь умножение на константу можно разбить на сдвиг и сложение. Как правильно разбить на этапы умножение на 6364136223846793005ULL ?
Go to the top of the page
 
+Quote Post
Bad0512
сообщение Sep 18 2015, 09:30
Сообщение #4


Знающий
****

Группа: Свой
Сообщений: 802
Регистрация: 11-05-07
Из: Томск
Пользователь №: 27 650



Цитата(count_enable @ Sep 18 2015, 00:22) *
Так как xilinx не воспринимает числа больше 32 бит

Не вздумайте им об этом сообщить - они очень обидятся...
А по сабжу - не пробовали для константы явно разрядность указать? Это по умолчанию константы 32-битные, но никто не запрещает сделать и с большей разрядностью.
Go to the top of the page
 
+Quote Post
Golikov A.
сообщение Sep 18 2015, 09:31
Сообщение #5


Гуру
******

Группа: Свой
Сообщений: 4 256
Регистрация: 17-02-06
Пользователь №: 14 454



ну это просто

( A + B ) * ( C + D ) = AC+BC+AD+BD.
вот и делите свое число 64 бита на несколько частей 32 или вообще 16 бит, перемножаете, выравниваете порядки и все... можно на одном 32 битном умножителе за 4-6 тактов перемножать 64 на 64
Go to the top of the page
 
+Quote Post
Krys
сообщение Sep 18 2015, 10:04
Сообщение #6


Гуру
******

Группа: Свой
Сообщений: 2 002
Регистрация: 17-01-06
Из: Томск, Россия
Пользователь №: 13 271



Цитата(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 не устраивает по степени "случайности"?


--------------------
Зная себе цену, нужно ещё и пользоваться спросом...
Go to the top of the page
 
+Quote Post
Maverick
сообщение Sep 18 2015, 10:30
Сообщение #7


я только учусь...
******

Группа: Модераторы
Сообщений: 3 447
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(count_enable @ Sep 18 2015, 12:18) *
Как правильно разбить на этапы умножение на 6364136223846793005ULL ?

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

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

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

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


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
count_enable
сообщение Sep 18 2015, 11:00
Сообщение #8


Местный
***

Группа: Свой
Сообщений: 310
Регистрация: 28-01-13
Из: Лондон
Пользователь №: 75 384



Цитата
А как решили проблему?
Было: 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-битные множить.
Go to the top of the page
 
+Quote Post
Golikov A.
сообщение Sep 18 2015, 11:13
Сообщение #9


Гуру
******

Группа: Свой
Сообщений: 4 256
Регистрация: 17-02-06
Пользователь №: 14 454



будет лучше сделать

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

только сдается мне что это константу так набирать всяко хуже...
Go to the top of the page
 
+Quote Post
Maverick
сообщение Sep 18 2015, 11:14
Сообщение #10


я только учусь...
******

Группа: Модераторы
Сообщений: 3 447
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(count_enable @ Sep 18 2015, 14:00) *

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

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



--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
dm.pogrebnoy
сообщение Sep 18 2015, 11:45
Сообщение #11


Знающий
****

Группа: Свой
Сообщений: 747
Регистрация: 11-04-07
Пользователь №: 26 933



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


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

http://xorshift.di.unimi.it/


--------------------
Go to the top of the page
 
+Quote Post
blackfin
сообщение Sep 18 2015, 11:49
Сообщение #12


Гуру
******

Группа: Свой
Сообщений: 3 106
Регистрация: 18-04-05
Пользователь №: 4 261



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

Путаетесь в показаниях? -> LFSR.. rolleyes.gif
Go to the top of the page
 
+Quote Post
Maverick
сообщение Sep 18 2015, 11:58
Сообщение #13


я только учусь...
******

Группа: Модераторы
Сообщений: 3 447
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



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

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

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

Цитата(count_enable @ Sep 18 2015, 14:00) *
От себя добавлю что LSFR хоть и простейший...


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
count_enable
сообщение Sep 18 2015, 14:57
Сообщение #14


Местный
***

Группа: Свой
Сообщений: 310
Регистрация: 28-01-13
Из: Лондон
Пользователь №: 75 384



Пока гуру занимаются правописанием 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;

Go to the top of the page
 
+Quote Post
count_enable
сообщение Sep 18 2015, 17:45
Сообщение #15


Местный
***

Группа: Свой
Сообщений: 310
Регистрация: 28-01-13
Из: Лондон
Пользователь №: 75 384



Переписал код с использованием 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;
Go to the top of the page
 
+Quote Post

2 страниц V   1 2 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 7th July 2025 - 03:12
Рейтинг@Mail.ru


Страница сгенерированна за 0.01688 секунд с 7
ELECTRONIX ©2004-2016