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

 
 
 
Reply to this topicStart new topic
> Возможно ли ускорить данный алгоритм?
count_enable
сообщение Sep 27 2016, 13:04
Сообщение #1


Местный
***

Группа: Свой
Сообщений: 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 МГц. Неужели такую простую арифметику нельзя ускорить? Наверняка я где-то накосячил. Длина конвеера не особо критична, но должна быть одинакова для любых значений Х.
Go to the top of the page
 
+Quote Post
Maverick
сообщение Sep 27 2016, 13:40
Сообщение #2


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

Группа: Модераторы
Сообщений: 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.

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


Знающий
****

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



Цитата(Maverick @ Sep 27 2016, 20:40) *
если нужна скорость то
по одной ветви
такт - вычисление модуля Х,
следующий такт - сравнение,
следующий такт - присвоение значений B, S и т.д.

по другой ветви
такт вычисление знака Х ,
затем pipeline регистры для выравнивания с первой веткой, чтобы в конце правильно получить значение Y, с учетом такта для сравнения Х с нулем

В итоге будет конвеер...

Всё так, но если входные данные текущего вычисления зависят от результата предыдущего - конвеер не поможет. А название задачи какбэ намекает на итеративный характер вычислений...
Go to the top of the page
 
+Quote Post
alexadmin
сообщение Sep 28 2016, 08:54
Сообщение #4


Знающий
****

Группа: Свой
Сообщений: 572
Регистрация: 17-11-05
Из: СПб, Россия
Пользователь №: 10 965



Про конвейер все правильно, но меня больше всего в вашей реализации пугает последовательный набор сравнений - это 8 компараторов друг за другом. Надо смотреть репорт по таймингам, но если хочется скорости - или раскладывать этапы сравнения по отдельным тактам или делать таблицей на памяти. Хотя для WIDTH=18 табличка получится знатной wink.gif
Go to the top of the page
 
+Quote Post
count_enable
сообщение Sep 28 2016, 09:17
Сообщение #5


Местный
***

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



Это да, как я посмотрел то затык именно в сравнении величин. Но как это сделать конвеером я пока не придумал, получается или неравное время вычисления от 2 до 9 тактов, или минимум 9 тактов на вход неконвееризируемых. Оба варианта в конечном итоге гораздо хуже медленного но детерминированого пайплайна. Когда придумаю как ускорить сравнение, задача и будет решена. Остальное довольно банально.
Go to the top of the page
 
+Quote Post
AlexRayne
сообщение Sep 28 2016, 09:50
Сообщение #6


Местный
***

Группа: Участник
Сообщений: 319
Регистрация: 27-09-07
Пользователь №: 30 877



Цитата(Bad0512 @ Sep 28 2016, 06:01) *
Всё так, но если входные данные текущего вычисления зависят от результата предыдущего - конвеер не поможет. А название задачи какбэ намекает на итеративный характер вычислений...

а почему не поможет?
Go to the top of the page
 
+Quote Post
alexadmin
сообщение Sep 28 2016, 10:47
Сообщение #7


Знающий
****

Группа: Свой
Сообщений: 572
Регистрация: 17-11-05
Из: СПб, Россия
Пользователь №: 10 965



Цитата(count_enable @ Sep 28 2016, 12:17) *
Это да, как я посмотрел то затык именно в сравнении величин. Но как это сделать конвеером я пока не придумал, получается или неравное время вычисления от 2 до 9 тактов, или минимум 9 тактов на вход неконвееризируемых. Оба варианта в конечном итоге гораздо хуже медленного но детерминированого пайплайна. Когда придумаю как ускорить сравнение, задача и будет решена. Остальное довольно банально.


Ну как? Сравниваете с boundary(0), результат с дополнительным флагом передаете на следующий шаг. Если флага нет, сравниваете с boundary(1). Если есть - просто передаете выбранное значение дальше. И так далее. Если аккуратно написать, то получится честный конвейер, который на каждом такте сможет принимать данные.
Go to the top of the page
 
+Quote Post
Bad0512
сообщение Sep 29 2016, 05:05
Сообщение #8


Знающий
****

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



Цитата(AlexRayne @ Sep 28 2016, 16:50) *
а почему не поможет?

В случае конвеера предполагается что каждый новый такт вы даёте на вход вычислителя новые данные. В случае если этими данными являются результаты предыдущего вычисления вам придется ждать до тех пор пока конвеер не выплюнет результат, и только потом давать ему новую порцию данных. Таким образом общая производительность системы падает.
Go to the top of the page
 
+Quote Post
AlexRayne
сообщение Sep 29 2016, 06:55
Сообщение #9


Местный
***

Группа: Участник
Сообщений: 319
Регистрация: 27-09-07
Пользователь №: 30 877



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

это будет если ваш "конвеер" имеет память текущего состояния (и то с натяжкой), или связи обратные от следующих звеньев - это уже не конвеер.
скорее всего вы описываете ситуацию обратной связи - когда на каждое входное воздействие ваш контур должен успеть отработать и устаканить решение. и тут ситуация неразрешима - скорость ОС должна быть на порядок быстрее скорости входного возмущения.
Возможно получится чделать чтото вширь: обычный делитель это конвеерная развертка собственно звена с обратной связью. В том смысле что делитель можно делать 2мя путями - большой и громоздкий конвеер, или маленький и простой - последовательного приближения.
думаю Вы можете просто последовательно (в конвеер) поставить много звеньев одинаковых, так чтобы заводить выходной сигнал не на вход текущего звена, а на вход следующего по конвееру. соответственно входной сигнал - тоже надо задержать в регистрах и пробросить на вход слежующего звена в конвеере. количество звеньев в таком конвеере должно быть достаточно для выхода на стабильное решение.

Go to the top of the page
 
+Quote Post
RobFPGA
сообщение Sep 29 2016, 09:00
Сообщение #10


Профессионал
*****

Группа: Свой
Сообщений: 1 214
Регистрация: 23-12-04
Пользователь №: 1 643



Приветствую!

У Вас же "жирный" чип вот и растите в ширину!
Делайте 9 параллельных ветки в каждой со своим сдвигом и коэффициентами + 9 сравнений.
А на выходе выбираете нужную ветку в зависимости от результата сравнения.

Удачи! Rob.


Go to the top of the page
 
+Quote Post

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

 


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


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