|
|
  |
Возможно ли ускорить данный алгоритм? |
|
|
|
Sep 27 2016, 13:04
|
Местный
  
Группа: Свой
Сообщений: 310
Регистрация: 28-01-13
Из: Лондон
Пользователь №: 75 384

|
Кусково-линейная аппроксимация логистической ф-ции. Множители подобраны из степеней двойки, из операций только сдвиг и сумма. Y=kx+b; b-массив из 9 значений. Схема алгоритма:  Код алгоритма CODE library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.NUMERIC_STD.ALL; use ieee.math_real.all;
entity logistic is generic ( FRAC_WIDTH: integer := 13; DATA_WIDTH :integer :=18); Port ( CLK: in STD_LOGIC; DIN : in STD_LOGIC_VECTOR (DATA_WIDTH-1 downto 0); DOUT : out STD_LOGIC_VECTOR (DATA_WIDTH-1 downto 0)); end logistic;
architecture Behavioral of logistic is -- Ax+b;
type i_bound_t is array (0 to 8) of std_logic_vector(DATA_WIDTH-1 downto 0); constant boundary: i_bound_t:=( std_logic_vector(to_signed(integer(real(7.236)*real(2**FRAC_WIDTH)),DATA_WIDTH)) , std_logic_vector(to_signed(integer(real(5.846)*real(2**FRAC_WIDTH)),DATA_WIDTH)) , std_logic_vector(to_signed(integer(real(5.147)*real(2**FRAC_WIDTH)),DATA_WIDTH)) , std_logic_vector(to_signed(integer(real(4.442)*real(2**FRAC_WIDTH)),DATA_WIDTH)) , std_logic_vector(to_signed(integer(real(3.724)*real(2**FRAC_WIDTH)),DATA_WIDTH)) , std_logic_vector(to_signed(integer(real(2.977)*real(2**FRAC_WIDTH)),DATA_WIDTH)) , std_logic_vector(to_signed(integer(real(2.164)*real(2**FRAC_WIDTH)),DATA_WIDTH)) , std_logic_vector(to_signed(integer(real(1.065)*real(2**FRAC_WIDTH)),DATA_WIDTH)) , std_logic_vector(to_signed(integer(real(0)*real(2**FRAC_WIDTH)),DATA_WIDTH)) ); constant B: i_bound_t:=( std_logic_vector(to_signed(integer(real(7.236)*real(2**FRAC_WIDTH)),DATA_WIDTH)) , std_logic_vector(to_signed(integer(real(0.984375)*real(2**FRAC_WIDTH)),DATA_WIDT H)), std_logic_vector(to_signed(integer(real(0.97265625)*real(2**FRAC_WIDTH)),DATA_WI DTH)), std_logic_vector(to_signed(integer(real(0.953125)*real(2**FRAC_WIDTH)),DATA_WIDT H)), std_logic_vector(to_signed(integer(real(0.91796875)*real(2**FRAC_WIDTH)),DATA_WI DTH)), std_logic_vector(to_signed(integer(real(0.859375)*real(2**FRAC_WIDTH)),DATA_WIDT H)), std_logic_vector(to_signed(integer(real(0.765625)*real(2**FRAC_WIDTH)),DATA_WIDT H)), std_logic_vector(to_signed(integer(real(0.6328125)*real(2**FRAC_WIDTH)),DATA_WID TH)), std_logic_vector(to_signed(integer(real(0.5)*real(2**FRAC_WIDTH)),DATA_WIDTH)) );
signal X_abs:std_logic_vector(DATA_WIDTH-1 downto 0); signal X_shifted:std_logic_vector(DATA_WIDTH-1 downto 0); signal Y_abs:std_logic_vector(DATA_WIDTH-1 downto 0); signal sDIN,ssDIN:std_logic; -- pipeline sign begin process(CLK) begin if(rising_edge(CLK)) then X_abs<=std_logic_vector(abs(signed(DIN))); sDIN<=DIN(DATA_WIDTH-1); ssDIN<=sDIN; if(X_abs>boundary(0)) then Y_abs<=std_logic_vector(to_signed(integer(2**FRAC_WIDTH),DOUT'length)); elsif X_abs>boundary(1) then -- X_shifted<=std_logic_vector(signed(X_abs) srl 9); Y_abs<=std_logic_vector((signed(X_abs) srl 9)+signed(B(1))); elsif X_abs>boundary(2) then -- X_shifted<=std_logic_vector(signed(X_abs) srl 8); Y_abs<=std_logic_vector((signed(X_abs) srl 8)+signed(B(2))); elsif X_abs>boundary(3) then -- X_shifted<=std_logic_vector(signed(X_abs) srl 7); Y_abs<=std_logic_vector((signed(X_abs) srl 7)+signed(B(3))); elsif X_abs>boundary(4) then -- X_shifted<=std_logic_vector(signed(X_abs) srl 6); Y_abs<=std_logic_vector((signed(X_abs) srl 6)+signed(B(4))); elsif X_abs>boundary(5) then -- X_shifted<=std_logic_vector(signed(X_abs) srl 5); Y_abs<=std_logic_vector((signed(X_abs) srl 5)+signed(B(5))); elsif X_abs>boundary(6) then -- X_shifted<=std_logic_vector(signed(X_abs) srl 4); Y_abs<=std_logic_vector((signed(X_abs) srl 4)+signed(B(6))); elsif X_abs>boundary(7) then -- X_shifted<=std_logic_vector(signed(X_abs) srl 3); Y_abs<=std_logic_vector((signed(X_abs) srl 3)+signed(B(7))); else -- X_shifted<=std_logic_vector(signed(X_abs) srl 2); Y_abs<=std_logic_vector((signed(X_abs) srl 2)+signed(B(8))); end if; if((ssDIN)='1') then -- negative number DOUT<=std_logic_vector(to_signed(integer(2**FRAC_WIDTH),DOUT'length)-signed(Y_abs)); else DOUT<=Y_abs; end if; end if; end process; end Behavioral;
Цель: 6 и 7 Виртексы изначально. Синтез показывает 280 МГц. Если сделать сдвиг и сумму отдельно (сначала вычислять X_shifted, потом суммировать с Y_abs), скорость возрастает до 293 МГц. Неужели такую простую арифметику нельзя ускорить? Наверняка я где-то накосячил. Длина конвеера не особо критична, но должна быть одинакова для любых значений Х.
|
|
|
|
|
Sep 27 2016, 13:40
|

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

|
Цитата(count_enable @ Sep 27 2016, 16:04)  Кусково-линейная аппроксимация логистической ф-ции. Множители подобраны из степеней двойки, из операций только сдвиг и сумма.
Y=kx+b; b-массив из 9 значений.
Цель: 6 и 7 Виртексы изначально. Синтез показывает 280 МГц. Если сделать сдвиг и сумму отдельно (сначала вычислять X_shifted, потом суммировать с Y_abs), скорость возрастает до 293 МГц. Неужели такую простую арифметику нельзя ускорить? Наверняка я где-то накосячил. Длина конвеера не особо критична, но должна быть одинакова для любых значений Х. если нужна скорость то по одной ветви такт - вычисление модуля Х, следующий такт - сравнение, следующий такт - присвоение значений B, S и т.д. по другой ветви такт вычисление знака Х , затем pipeline регистры для выравнивания с первой веткой, чтобы в конце правильно получить значение Y, с учетом такта для сравнения Х с нулем В итоге будет конвеер...
--------------------
If it doesn't work in simulation, it won't work on the board.
"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
|
|
|
|
|
Sep 28 2016, 09:50
|
Местный
  
Группа: Участник
Сообщений: 319
Регистрация: 27-09-07
Пользователь №: 30 877

|
Цитата(Bad0512 @ Sep 28 2016, 06:01)  Всё так, но если входные данные текущего вычисления зависят от результата предыдущего - конвеер не поможет. А название задачи какбэ намекает на итеративный характер вычислений... а почему не поможет?
|
|
|
|
|
Sep 28 2016, 10:47
|
Знающий
   
Группа: Свой
Сообщений: 572
Регистрация: 17-11-05
Из: СПб, Россия
Пользователь №: 10 965

|
Цитата(count_enable @ Sep 28 2016, 12:17)  Это да, как я посмотрел то затык именно в сравнении величин. Но как это сделать конвеером я пока не придумал, получается или неравное время вычисления от 2 до 9 тактов, или минимум 9 тактов на вход неконвееризируемых. Оба варианта в конечном итоге гораздо хуже медленного но детерминированого пайплайна. Когда придумаю как ускорить сравнение, задача и будет решена. Остальное довольно банально. Ну как? Сравниваете с boundary(0), результат с дополнительным флагом передаете на следующий шаг. Если флага нет, сравниваете с boundary(1). Если есть - просто передаете выбранное значение дальше. И так далее. Если аккуратно написать, то получится честный конвейер, который на каждом такте сможет принимать данные.
|
|
|
|
|
Sep 29 2016, 06:55
|
Местный
  
Группа: Участник
Сообщений: 319
Регистрация: 27-09-07
Пользователь №: 30 877

|
Цитата(Bad0512 @ Sep 29 2016, 08:05)  В случае конвеера предполагается что каждый новый такт вы даёте на вход вычислителя новые данные. В случае если этими данными являются результаты предыдущего вычисления вам придется ждать до тех пор пока конвеер не выплюнет результат, и только потом давать ему новую порцию данных. Таким образом общая производительность системы падает. это будет если ваш "конвеер" имеет память текущего состояния (и то с натяжкой), или связи обратные от следующих звеньев - это уже не конвеер. скорее всего вы описываете ситуацию обратной связи - когда на каждое входное воздействие ваш контур должен успеть отработать и устаканить решение. и тут ситуация неразрешима - скорость ОС должна быть на порядок быстрее скорости входного возмущения. Возможно получится чделать чтото вширь: обычный делитель это конвеерная развертка собственно звена с обратной связью. В том смысле что делитель можно делать 2мя путями - большой и громоздкий конвеер, или маленький и простой - последовательного приближения. думаю Вы можете просто последовательно (в конвеер) поставить много звеньев одинаковых, так чтобы заводить выходной сигнал не на вход текущего звена, а на вход следующего по конвееру. соответственно входной сигнал - тоже надо задержать в регистрах и пробросить на вход слежующего звена в конвеере. количество звеньев в таком конвеере должно быть достаточно для выхода на стабильное решение.
|
|
|
|
|
  |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|