Перейти к содержанию
Поиск
    

Возможно ли ускорить данный алгоритм?

Ответить

count_enable    0

count_enable
Опубликовано · Жалоба

Кусково-линейная аппроксимация логистической ф-ции. Множители подобраны из степеней двойки, из операций только сдвиг и сумма.

 

Y=kx+b; b-массив из 9 значений.

 

Схема алгоритма:

 

ei17ur.png

 

Код алгоритма 

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 МГц. Неужели такую простую арифметику нельзя ускорить? Наверняка я где-то накосячил. Длина конвеера не особо критична, но должна быть одинакова для любых значений Х.

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Maverick_    15

Maverick_
Опубликовано · Жалоба
Кусково-линейная аппроксимация логистической ф-ции. Множители подобраны из степеней двойки, из операций только сдвиг и сумма.

 

Y=kx+b; b-массив из 9 значений.

 

 

Цель: 6 и 7 Виртексы изначально. Синтез показывает 280 МГц. Если сделать сдвиг и сумму отдельно (сначала вычислять X_shifted, потом суммировать с Y_abs), скорость возрастает до 293 МГц. Неужели такую простую арифметику нельзя ускорить? Наверняка я где-то накосячил. Длина конвеера не особо критична, но должна быть одинакова для любых значений Х.

 

если нужна скорость то

по одной ветви

такт - вычисление модуля Х,

следующий такт - сравнение,

следующий такт - присвоение значений B, S и т.д.

 

по другой ветви

такт вычисление знака Х ,

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

 

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

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Bad0512    2

Bad0512
Опубликовано · Жалоба
если нужна скорость то

по одной ветви

такт - вычисление модуля Х,

следующий такт - сравнение,

следующий такт - присвоение значений B, S и т.д.

 

по другой ветви

такт вычисление знака Х ,

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

 

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

Всё так, но если входные данные текущего вычисления зависят от результата предыдущего - конвеер не поможет. А название задачи какбэ намекает на итеративный характер вычислений...

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

alexadmin    0

alexadmin
Опубликовано · Жалоба

Про конвейер все правильно, но меня больше всего в вашей реализации пугает последовательный набор сравнений - это 8 компараторов друг за другом. Надо смотреть репорт по таймингам, но если хочется скорости - или раскладывать этапы сравнения по отдельным тактам или делать таблицей на памяти. Хотя для WIDTH=18 табличка получится знатной ;)

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

count_enable    0

count_enable
Опубликовано · Жалоба

Это да, как я посмотрел то затык именно в сравнении величин. Но как это сделать конвеером я пока не придумал, получается или неравное время вычисления от 2 до 9 тактов, или минимум 9 тактов на вход неконвееризируемых. Оба варианта в конечном итоге гораздо хуже медленного но детерминированого пайплайна. Когда придумаю как ускорить сравнение, задача и будет решена. Остальное довольно банально.

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

AlexRayne    7

AlexRayne
Опубликовано · Жалоба
Всё так, но если входные данные текущего вычисления зависят от результата предыдущего - конвеер не поможет. А название задачи какбэ намекает на итеративный характер вычислений...

а почему не поможет?

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

alexadmin    0

alexadmin
Опубликовано · Жалоба
Это да, как я посмотрел то затык именно в сравнении величин. Но как это сделать конвеером я пока не придумал, получается или неравное время вычисления от 2 до 9 тактов, или минимум 9 тактов на вход неконвееризируемых. Оба варианта в конечном итоге гораздо хуже медленного но детерминированого пайплайна. Когда придумаю как ускорить сравнение, задача и будет решена. Остальное довольно банально.

 

Ну как? Сравниваете с boundary(0), результат с дополнительным флагом передаете на следующий шаг. Если флага нет, сравниваете с boundary(1). Если есть - просто передаете выбранное значение дальше. И так далее. Если аккуратно написать, то получится честный конвейер, который на каждом такте сможет принимать данные.

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Bad0512    2

Bad0512
Опубликовано · Жалоба
а почему не поможет?

В случае конвеера предполагается что каждый новый такт вы даёте на вход вычислителя новые данные. В случае если этими данными являются результаты предыдущего вычисления вам придется ждать до тех пор пока конвеер не выплюнет результат, и только потом давать ему новую порцию данных. Таким образом общая производительность системы падает.

 

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

AlexRayne    7

AlexRayne
Опубликовано · Жалоба
В случае конвеера предполагается что каждый новый такт вы даёте на вход вычислителя новые данные. В случае если этими данными являются результаты предыдущего вычисления вам придется ждать до тех пор пока конвеер не выплюнет результат, и только потом давать ему новую порцию данных. Таким образом общая производительность системы падает.

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

скорее всего вы описываете ситуацию обратной связи - когда на каждое входное воздействие ваш контур должен успеть отработать и устаканить решение. и тут ситуация неразрешима - скорость ОС должна быть на порядок быстрее скорости входного возмущения.

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

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

 

 

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

RobFPGA    27

RobFPGA
Опубликовано · Жалоба

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

 

У Вас же "жирный" чип вот и растите в ширину!

Делайте 9 параллельных ветки в каждой со своим сдвигом и коэффициентами + 9 сравнений.

А на выходе выбираете нужную ветку в зависимости от результата сравнения.

 

Удачи! Rob.

 

 

 

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
×
  • Создать...