[Kopart 0]

Может кто подскажет варианты как это сделать, или где можно почитать.

 

Для примера: нужно из 20-ти 5-ти битных векторов выбрать минимальный по десятичному значению.

 

Подскажите хорошо синтезируемый(150МГц) алгоритм, также реализующий маштабируемость(многократное использование).

Спасибо.

[oval 0]

Может кто подскажет варианты как это сделать, или где можно почитать.

 

Для примера: нужно из 20-ти 5-ти битных векторов выбрать минимальный по десятичному значению.

 

Подскажите хорошо синтезируемый(150МГц) алгоритм, также реализующий маштабируемость(многократное использование).

Спасибо.

 

Подсказать к сожалению нечего. Если речь идет о ПЛИС, то 150МГц вряд-ли достижимо. Встречалась подобная задача, частота получалась значительно ниже, вычисляли результат за несколько тактов, ничего более толкового в голову не пришло. Как вариант, можно попытаться заранее подготавливать данные для данного вычисления, сортировать их.

 

З.Ы. Если удасться найти по данному вопросу что-нибудь толковое, дайте знать, пожалуйста. Тоже интересно.

[daemonDX 0]

Так нужно, чтобы просто развелось на 150, или чтобы еще и на каждом такте весь массив обрабатывало ?

Реализация зависит от условий. Так, если данные подаются по одному за такт, то тут пожалуй, особого пространства для фантазии и нет.

Если все сразу - можно сравнивать попарно, а на следующий этап передавать результат. И так до получения одного числа на выходе. Т.е. организовать дерево компараторов. Ресурсов будет есть прилично, зато конвейер :).

Можно сохранить весь результат в блок регистров, снабженных мультиплексорами 2 в 1. Один вход задействовать для данных, а другой - для выхода с предыдущего регистра - преобразователь параллельных данных в последовательные :) . И на конечном регистре вычислять min/max. Этот вариант подойдет, если между моментами прихода данных есть достаточное количество тактов.

[Loki5000 0]

Для примера: нужно из 20-ти 5-ти битных векторов выбрать минимальный по десятичному значению.

А что подразумевается под "выбрать минимальный"? На выходе должно быть само минимальное значение или индекс вектора содержащего минимальное значение?

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

Более быстрых схем придумать не удалось. При работе на больших частотах на вычисление приходится тратить несколько тактов.

[Kopart 0]

2 daemonDX и Loki5000

 

Примерный алгоритм я понял, но я так понимаю, что все зависит от конкретной задачи. Поэтому сформулирую ее подробнее.

 

На входе есть сразу 20 векторов in[19..0] [4..0] - нужно на выход выдать min значение из 19 векторов(за исключением i-того) те

 

Например

out[0][4..0] = min(из in[19..1][4..0] те за искл in[0][4..0])

...

out[4..0] = min(из in[19..0][4..0] те за искл in[4..0])

...

out[19][4..0] = min(из in[18..0][4..0] те за искл in[19][4..0])

 

Я так понимаю, что за 1 такт на частоте больше 100МГц - это получить не реально(не взирая на количество ресурсов)?

[daemonDX 0]

А результат критично получить на следующий такт, после подачи данных ? Или же задержка в несколько тактов после подачи данных допустима ? Если нет, на 100 МГц за один такт, пожалуй нереально. По крайней мере, пока в голову ничего не приходит.

Если же задержка допустима запустите конвейер. Данные можно подавать каждый такт, первый результат получите через 5-6 тактов, затем - на каждом такте для последующих данных. То есть задержка между подачей данных на вход, и снятием результата будет как раз эти самые 5-6 тактов.

По условию - наверное можно пооптимизить, но на первый взгляд будут нужны 20 конвейерных компонент на базе дерева компараторов :) (один компонент на 19 входов х 20 инстансов)

[Kopart 0]

А результат критично получить на следующий такт, после подачи данных ? Или же задержка в несколько тактов после подачи данных допустима ? Если нет, на 100 МГц за один такт, пожалуй нереально. По крайней мере, пока в голову ничего не приходит.

Если же задержка допустима запустите конвейер. Данные можно подавать каждый такт, первый результат получите через 5-6 тактов, затем - на каждом такте для последующих данных. То есть задержка между подачей данных на вход, и снятием результата будет как раз эти самые 5-6 тактов.

По условию - наверное можно пооптимизить, но на первый взгляд будут нужны 20 конвейерных компонент на базе дерева компараторов :) (один компонент на 19 входов х 20 инстансов)

 

Те Вы также предлагаете сравнивать попарно?

А если такой вариант [4..0] это 32 десятичных значения - следовательно организовать сравнивание с константой снизу вверх 19-ти (20-1) векторов.

Как вариант вложенные if - и размножить их на 20 входных сигналов. Я думаю, после этого синтезатор их сможет оптимизировать (найдя повторения)?!

 

Хотя 32 вложеных if'a... Ваше мнение?

[Kopart 0]

но на первый взгляд будут нужны 20 конвейерных компонент на базе дерева компараторов :) (один компонент на 19 входов х 20 инстансов)

 

Можете привести пример описания конвеерной компоненты на базе дерева компараторов, о котором вы написали(лучше на Veriloge).

Просто не очень ясно "дерево компараторов" или я в предыдущем посте, примерно это и описал?

[Gate 0]

2 daemonDX и Loki5000

 

Примерный алгоритм я понял, но я так понимаю, что все зависит от конкретной задачи. Поэтому сформулирую ее подробнее.

 

На входе есть сразу 20 векторов in[19..0] [4..0] - нужно на выход выдать min значение из 19 векторов(за исключением i-того) те

 

Например

out[0][4..0] = min(из in[19..1][4..0] те за искл in[0][4..0])

...

out[4..0] = min(из in[19..0][4..0] те за искл in[4..0])

...

out[19][4..0] = min(из in[18..0][4..0] те за искл in[19][4..0])

 

Я так понимаю, что за 1 такт на частоте больше 100МГц - это получить не реально(не взирая на количество ресурсов)?

 

Компараторы синтезируются в lut'ы, и оптимизировать там нечего, поэтому Вам надо рассмотреть обратную задачу - сколько 5-битных компараторов поместится в 100 Мгц. Предположим, их будет 5, тогда Вы берете 4 таких блока - это первая стадия конвейера (выходы - на тактируемый регистр), выходы этих четырех подаются на 4-входовый компаратор - это 2-я стадия конвейера. Если не хватит - то вводите еще стадии.

Компаратор на N входов пишется примерно так:

  
temp=5'b11111;
for (i=0; i<N; i=i+1) if (in[i]<=temp) temp=in[i];

На выходе цикла в temp - минимум .

Что касается Вашей задачи, то вижу 2 пути:

1. Тупой - поставить 20 19-входовых компараторов.

2. Оптимизированный - написать 20-входовый компаратор, который бы выдавал минимум и его индекс и следующее за минимумом число. А Ваши 19 выходов формируются так - если индекс минимума совпадает с индексом, который надо выкинуть, то берете следующее за минимумом число. Если нет - берете минимум. Совпадающие по значению минимумы должны рассматриваться как разные числа. Я долго не думал, но похоже по ресурсам это будет примерно 4 20-вх. компаратора.

Изменено 24 апреля, 2006 пользователем Gate

[sazh 8]

По совету Gate попробовал, нужен конвейер.

module min_max

(

input [4:0] a,b,c,d,

output [4:0] q

);

 

wire [4:0] in [3:0];

 

assign in[0] = a;

assign in[1] = b;

assign in[2] = c;

assign in[3] = d;

 

integer temp;

 

always @(*)

begin: block

integer i;

 

temp = -1;

for (i = 0; i < 4; i = i + 1)

if (in <= temp)

temp = in;

end

 

assign q = temp;

 

endmodule

[des00 25]

Компараторы синтезируются в lut'ы, и оптимизировать там нечего, поэтому Вам надо рассмотреть обратную задачу - сколько 5-битных компараторов поместится в 100 Мгц. Предположим, их будет 5, тогда Вы берете 4 таких блока - это первая стадия конвейера (выходы - на тактируемый регистр), выходы этих четырех подаются на 4-входовый компаратор - это 2-я стадия конвейера. Если не хватит - то вводите еще стадии.

 

ИМХО вы не правы, да компараторы вида == синтезируються на лютах, а вот вида <, <= и противоположные на суматорах,

вот простой пример

 

entity test is
    port(  
        a : in unsigned(7 downto 0);
        b : in unsigned(7 downto 0);
        
        result : out std_logic;
        c : out unsigned(7 downto 0)
        );
end entity test;

architecture rtl of test is 
    signal res : std_logic;
begin

    result <= res;
    
    res <= '1' when (a <= b) else '0';
    
    process (res, a, b) is
    begin
        if (res = '1') then 
            c <= a;
        else 
            c <= b;
        end if;
    end process;

end architecture  rtl;

в прикрепленом файле то, что изображает симплифай 8.4

 

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

поэтому ИМХО я бы сделал так :

собираем блок - компаратор 4-х чисел, в котором сравниваем a,b, bc, c,d на первом такте, на втором такте муксим нужные задержаные(если нужен поток)/незадержаные данные на выход.

далее возможны варианты:

если нужен поток : таких блоков берем 5, их выхлопы подаем на 1 блок компаратор 4-х чисел, и остаеться только 1 последний просто компаратор.

если можно подождать, и данные были скапчурены то на вход компаратора ставим муксер 2в1/4в1,

и остаеться только сгородить выходную логику (это позволит сэкономить ресурса).

 

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

[sazh 8]

To des00

В Quartuse Ваш пример не пошел. Ошибку выкатывает.

А так как я VHDL не знаю, у меня сумматора не получилось:

library ieee;

use ieee.std_logic_1164.all;

use ieee.std_logic_unsigned.all;

entity test is

port(

a : in std_logic_vector(7 downto 0);

b : in std_logic_vector(7 downto 0);

result : out std_logic;

c : out std_logic_vector(7 downto 0)

);

end entity test;

 

architecture rtl of test is

signal res : std_logic;

begin

 

result <= res;

 

res <= '1' when (a <= B) else '0';

 

process (res, a, B) is

begin

if (res = '1') then

c <= a;

else

c <= b;

end if;

end process;

 

end architecture rtl;

 

 

 

P.S. Эти милые молдашки - не моя работа. Как они получаются, не знаю.

[des00 25]

To des00

В Quartuse Ваш пример не пошел. Ошибку выкатывает.

А так как я VHDL не знаю, у меня сумматора не получилось:

 

 

Хмм интересно, но т.к. у меня квартус не стоит (пока), я воспользовался симпифаем для стратикса второго.

(в тот раз был под виртекс4).

 

вот код который я кормил симплифаю

library ieee;

use ieee.std_logic_1164.all;

use ieee.NUMERIC_STD.all;

 

entity test is

port(

a : in unsigned(7 downto 0);

b : in unsigned(7 downto 0);

 

result : out std_logic;

c : out unsigned(7 downto 0)

);

end entity test;

 

architecture rtl of test is

--######## internal signal declaration ########-----

signal res : std_logic;

--######## end internal signal declaration ########-----

begin

 

 

result <= res;

 

res <= '1' when (a <= B) else '0';

 

process (res, a, B) is

begin

if (res = '1') then

c <= a;

else

c <= b;

end if;

end process;

 

end architecture rtl;

 

в приложении то что показал симплифай

насколько я понимаю структуру ЛЯ стратикса второго, опять же суматор-вычитатель :)

[Kopart 0]

К вопросу о частоте, я тоже попробовал синтезировать пример приведенный "sazh" (Примеры на VHDL, также не пошли - проблема с синтаксисом VHDL, которого я не знаю :( )

 

-----

module min_max

(

input [4:0] a,b,c,d,

input clk,

output [4:0] q

);

 

wire [4:0] in [3:0];

 

assign in[0] = a;

assign in[1] = b;

assign in[2] = c;

assign in[3] = d;

 

integer temp;

 

always @(posedge clk)

begin: block

integer i;

 

temp = -1;

for (i = 0; i < 4; i = i + 1)

if (in <= temp)

temp = in;

end

 

assign q = temp;

 

endmodule

 

Так как у меня сейчас есть только пакет для Actel - я смог проверить во что приведенный выше пример воплощается для разных семейств.

Если я правильно понимаю, разведеная частота "clk" получилась 181, 250 , 455 МГц соответственно для семейств APA, A3P и Axelerator.

В Altere LUT'ы помощнее будут, а вот частота получится больше или там другое определяет.

Просто в оригинале сказано сделать этот модуль на Altera'e, а вот, если поэксперементировать с другими фирмами (в плане конструкции ячейки)?

[des00 25]

К вопросу о частоте, я тоже попробовал синтезировать пример приведенный "sazh" (Примеры на VHDL, также не пошли - проблема с синтаксисом VHDL, которого я не знаю :( )

 

-----

module min_max

(

input [4:0] a,b,c,d,

input clk,

output [4:0] q

);

 

wire [4:0] in [3:0];

 

assign in[0] = a;

assign in[1] = b;

assign in[2] = c;

assign in[3] = d;

 

integer temp;

 

always @(posedge clk)

begin: block

integer i;

 

temp = -1;

for (i = 0; i < 4; i = i + 1)

if (in <= temp)

temp = in;

end

 

assign q = temp;

 

endmodule

 

Так как у меня сейчас есть только пакет для Actel - я смог проверить во что приведенный выше пример воплощается для разных семейств.

Если я правильно понимаю, разведеная частота "clk" получилась 181, 250 , 455 МГц соответственно для семейств APA, A3P и Axelerator.

В Altere LUT'ы помощнее будут, а вот частота получится больше или там другое определяет.

Просто в оригинале сказано сделать этот модуль на Altera'e, а вот, если поэксперементировать с другими фирмами (в плане конструкции ячейки)?

 

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

 

что бы посмотерть как будет реально, пропустите входные сигналы через тригеры и отключите разводку пинов ввода вывода, тогда можно оценить скорострельность на пустом кристале.

 

и мой пример это не послание как делать, а послание к размышлению на тему как делать