|
Умножение 64 бит на константу с переполнением. |
|
|
|
Sep 17 2015, 18:22
|
Местный
  
Группа: Свой
Сообщений: 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
=========================================================================
|
|
|
|
|
Sep 18 2015, 09:18
|
Местный
  
Группа: Свой
Сообщений: 310
Регистрация: 28-01-13
Из: Лондон
Пользователь №: 75 384

|
Со своим "ламерским вопросом" я разобрался - теперь синтезирует как надо. Делаю я это: http://www.pcg-random.org/ . Переполнение там не для умножения, а просто как часть алгоритма, как я понял. У меня теперь более серьезный вопрос: мне надо умножать на 64-битную константу. Если синтезировать с DSP48, скорость получается под 155 МГц, если без DSP48- 166 МГц. Понятно, что надо давать конвеер. Ведь умножение на константу можно разбить на сдвиг и сложение. Как правильно разбить на этапы умножение на 6364136223846793005ULL ?
|
|
|
|
|
Sep 18 2015, 09:30
|
Знающий
   
Группа: Свой
Сообщений: 802
Регистрация: 11-05-07
Из: Томск
Пользователь №: 27 650

|
Цитата(count_enable @ Sep 18 2015, 00:22)  Так как xilinx не воспринимает числа больше 32 бит Не вздумайте им об этом сообщить - они очень обидятся... А по сабжу - не пробовали для константы явно разрядность указать? Это по умолчанию константы 32-битные, но никто не запрещает сделать и с большей разрядностью.
|
|
|
|
|
Sep 18 2015, 10:04
|

Гуру
     
Группа: Свой
Сообщений: 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 не устраивает по степени "случайности"?
--------------------
Зная себе цену, нужно ещё и пользоваться спросом...
|
|
|
|
|
Sep 18 2015, 10:30
|

я только учусь...
     
Группа: Модераторы
Сообщений: 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.
"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
|
|
|
|
|
Sep 18 2015, 11:00
|
Местный
  
Группа: Свой
Сообщений: 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-битные множить.
|
|
|
|
|
Sep 18 2015, 11:14
|

я только учусь...
     
Группа: Модераторы
Сообщений: 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.
"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
|
|
|
|
|
Sep 18 2015, 14:57
|
Местный
  
Группа: Свой
Сообщений: 310
Регистрация: 28-01-13
Из: Лондон
Пользователь №: 75 384

|
Пока гуру занимаются правописанием  , я быстренько набросал сумматор с шифтером. Получилось 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;
|
|
|
|
|
Sep 18 2015, 17:45
|
Местный
  
Группа: Свой
Сообщений: 310
Регистрация: 28-01-13
Из: Лондон
Пользователь №: 75 384

|
Переписал код с использованием 1 сдвигового регистра, на котором в цикле и сдвигается вся портянка. Как МАС, только SAC - shift-add accumulator. 390Regs /340 LUT, но почему-то скорость упала до 370 МГц. Учитывая что теперь вычисление нового состояния занимает 34 цикла, эффективная скорость в районе 12 Мегачисел. Совсем не радужно  . Вроде конвееризировал правильно.. 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;
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|