Подсчет нулей или единиц Опции

[Egel]

Подскажите алгоритм подсчета нулей или единиц в 64 разрядном числе за один такт. И что можно почитать поглубже по поводу создания АЛУ


Спасибо огромное заранее

[Oldring]

Подскажите алгоритм подсчета нулей или единиц в 64 разрядном числе за один такт. И что можно почитать поглубже по поводу создания АЛУ


Спасибо огромное заранее

Многое зависит от длительности такта и от способностей синтезатора по оптимизации. Напишите простой цикл в процессе с переменной-счетчиком для начала.

[SM]

assign temp_a = (in_data & 64'h5555555555555555) + ((in_data >> 1) & 64'h5555555555555555);
assign temp_b = (temp_a & 64'h3333333333333333) + ((temp_a >> 2) & 64'h3333333333333333);
assign temp_c = (temp_b & 64'h0707070707070707) + ((temp_b >> 4) & 64'h0707070707070707);
assign temp_d = (temp_c & 64'h000F000F000F000F) + ((temp_c >> 8) & 64'h000F000F000F000F);
assign temp_e = (temp_d & 64'h0000001F0000001F) + ((temp_d >> 16) & 64'h0000001F0000001F);
assign temp_f = (temp_e & 64'h000000000000003F) + ((temp_e >> 32) & 64'h000000000000003F);

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

[Egel]

На одном сумматоре вообще абсурдно пытаться сделать??

[SM]

На одном сумматоре вообще абсурдно пытаться сделать??

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

А эффективнее всего это делать на дереве полных сумматоров с использованием их входов переносов, подавая везде на перенос один бит входных данных. Таким образом первый уровень будет принимать 3*N бит данных и состоять из однобитных сумматоров, второй - состоять из двухбитных, и принимать N/2 бит (по кол-ву входов переносов сумматоров), и так далее. Проверено, синтезаторы (Quartus, DC и Synplify) не умеют оптимизировать такую структуру в такое дерево.

[des333]

assign temp_a = (in_data & 64'h5555555555555555) + ((in_data >> 1) & 64'h5555555555555555);
assign temp_b = (temp_a & 64'h3333333333333333) + ((temp_a >> 2) & 64'h3333333333333333);
assign temp_c = (temp_b & 64'h0707070707070707) + ((temp_b >> 4) & 64'h0707070707070707);
assign temp_d = (temp_c & 64'h000F000F000F000F) + ((temp_c >> 8) & 64'h000F000F000F000F);
assign temp_e = (temp_d & 64'h0000001F0000001F) + ((temp_d >> 16) & 64'h0000001F0000001F);
assign temp_f = (temp_e & 64'h000000000000003F) + ((temp_e >> 32) & 64'h000000000000003F);

119 элементов против 193 следующей реализации:

Код

always @(*)
  begin
    temp_f = 0;
    for(int i=0; i<64; i++)
      if(in_data[i])
        temp_f++;
  end

Синтезатор еще далек от идеала  


Но, зато, судя по времянке быстродействие второго способа не намного хуже, чем первого.

Надо бы для проверки в TQA загнать.


P.S. Пока проверял - не заметил сообщения выше

Сообщение отредактировал des333 - May 13 2009, 10:52

[PeterD]

А так?
always @(posedge clk) begin
one [7:0] = input_number[63] + input_number[62] + input_number[61] +...+input_number[0]
zero[7:0] = 8'd64 - (input_number[63] + input_number[62] + input_number[61] +...+input_number[0])
end

Сообщение отредактировал PeterD - May 13 2009, 10:54

[Egel]

Но какие частоты будут с 180 разрядным сумматором? Про дерево не совсем понял)

Надо все АЛУ сделать на одном сумматоре)
Это конечно лучший вариант с поразрядным сложением. мне тоже так больше нравится.

Кстати это не есть та схема, о которой вы говорили, SM?

[SM]

Но какие частоты будут с 180 разрядным сумматором? Про дерево не совсем понял)

Точно те же, как и в остальных схемах. Так как как этот зад раком не крути, а для решения задачи нучно 180 одноразрядных сумматоров (примерное количество, плюс минус от реализации и задействования их переносов). А как их расставить - как один 180-битный, или как 180 однобитных - это вам решать и это сути дела не меняет.
Про дерево - для 8 бит так:

wire [1:0] stage_0_0, stage_0_1;
wire [2:0] stage_1_0;
wire [3:0] stage_2_0;

assign stage_0_0 = data[0]+data[1]+data[2];
assign stage_0_1 = data[3]+data[4]+data[5];
assign stage_1_0 = stage_0_0 + stage_0_1 + data[6];
assign stage_2_0 = stage_1_0 + data[7];

до 64 бит сами расширяйте, долго и муторно. А цикл generate продумывать мне влом.

[Egel]

Всем огромное спасибо. Очень сильно помогли

[SM]

Надо все АЛУ сделать на одном сумматоре)

Это сильно завернуто... Из всех букв аббревиатуры АЛУ - останется пожалуй только АУ

[des00]

Проверено, синтезаторы (Quartus, DC и Synplify) не умеют оптимизировать такую структуру в такое дерево.

вот тут проверяли %)

http://electronix.ru/forum/index.php?showtopic=59528

[Postoroniy_V]

2 Admin
ИМХО популярная тема у народа, может того её..пристегнуть?

[Artem_Petrik]

А эффективнее всего это делать на дереве полных сумматоров с использованием их входов переносов, подавая везде на перенос один бит входных данных.

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

[SM]

Как раз с полными сумматорами здесь не очень-то получается, по крайней мере на Альтере.

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

[des00]

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

а можно пример ? для наглядности пусть будет 64-х битный вектор и сравните результат синтеза с http://electronix.ru/forum/index.php?showt...st&p=549588

вопрос возник не просто так. простой оценочный расчет для альетры схемы на полусуматорах 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6 = 120 ячеек, схемы на "нечестных" полных сумматорах 16*2 + 8*4 + 4*5 + 2*6 + 1*7 = 103 ячейки. Сделал как вы предлагаете (если я вас правильно понял) и квартус со мной согласился

[Artem_Petrik]

вопрос возник не просто так. простой оценочный расчет для альетры схемы на полусуматорах 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6 = 120 ячеек, схемы на "нечестных" полных сумматорах 16*2 + 8*4 + 4*5 + 2*6 + 1*7 = 103 ячейки.

Да, вы правы, полные сумматоры лучше. Просто показалось что будет лучше на двух LE сложить 4 бита вместо трех, а оказалось, что все не так просто. Виноват, был неправ.

и квартус со мной согласился

Ага, так вы с ним заодно!

[SM]

двух LE сложить 4 бита

на двух LE сложить 4 бита низзя, так как это три выхода, т.е. 3 LE, а арифметический режим там вряд-ли будет применим из-за особенностей разводки переносов.

[Maverick]

В книге Shevkoplias "Microprocessornye Structury" (стр 479) предлагают такой алгоритм. Вырезка этого алгоритма во вложении

Когда-то давно я реализовал на VHDL логический элемент, который считает число единиц во входных данных так
(он реализован на сумматорах)
Описание портов:
data – N разрядный вход
add – N разрядный выход

Код

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;

entity Vcnt1s is
    Port ( data : in std_logic_vector(15 downto 0);
           add : out std_logic_vector(4 downto 0));
end Vcnt1s;

architecture Behavioral of Vcnt1s is
begin

process (data)
variable S : std_logic_vector(4 downto 0);
begin
S := "00000";
for i in 0 to 15 loop
if data(i) = '1' then S := S + "00001";
end if;
end loop;
add <= S;
end process;

end Behavioral;

Прикрепленные файлы

 Shevkoplias.MicroprocessornyeStructury.pdf ( 45.13 килобайт ) Кол-во скачиваний: 89

 

[SM]

Вырезка этого алгоритма во вложении

Эту схему давал уже des333 где-то в самом начале. Она, пожалуй, самая неэффективная по ресурсам.

[Oldring]

Она, пожалуй, самая неэффективная по ресурсам.

Ваше утверждение неверно. Эта схема самая эффективная по таким ресурсам, как мыслительные усилия и время, затрачиваемые разработчиком на её проектирование с нуля

[SM]

по таким ресурсам, как мыслительные усилия и время

Ну это да, не поспоришь

[Leka]

А я поспорю
Весь проект написаный в таком стиле, окажется неконкурентноспособным, и пойдет в корзину --> эффективность "по таким ресурсам, как мыслительные усилия и время, затрачиваемые разработчиком" ,окажется равной нулю.

[Oldring]

А я поспорю
Весь проект написаный в таком стиле, окажется неконкурентноспособным, и пойдет в корзину --> эффективность "по таким ресурсам, как мыслительные усилия и время, затрачиваемые разработчиком" ,окажется равной нулю.

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

[sazh]

Эту схему давал уже des333 где-то в самом начале. Она, пожалуй, самая неэффективная по ресурсам.

Что интересно. Показал девушкам - программистам различные реализации полемики
http://electronix.ru/forum/index.php?showt...=59528&st=0
Они в Вашу реализацию за раз въехали. Взяли на заметку.

[Leka]

То есть проект "может оказаться неконкурентоспособен" но утверждение что "окажется неконкурентоспособен" - неверно.

Ок.

[Maverick]

Эту схему давал уже des333 где-то в самом начале. Она, пожалуй, самая неэффективная по ресурсам.

Чтобы спора не было надо бы кому-то просто реализовать по данному алгоритму. Потом произвести сравнение результатов синтеза Можно ссылку на предложенную схему des333, которая реализована по данному алгоритму (я что-то ее не увидел, может плохо смотрел ).

[SM]

Чтобы спора не было надо бы кому-то просто реализовать по данному алгоритму. Потом произвести сравнение результатов синтеза Можно ссылку на предложенную схему des333, которая реализована по данному алгоритму (я что-то ее не увидел, может плохо смотрел ).

Сообщение №6 в этой ветке. Сразу вместе со сравнением результатов синтеза с вариантом неоптимального дерева.

[des333]

Эту схему давал уже des333 где-то в самом начале. Она, пожалуй, самая неэффективная по ресурсам.

Я думаю, Maverick писал про схему, указанную в pdf, а не про тот код, который написан в его посте. 




Насчет неэффективности согласен, я ее синтезировал именно с целью выявить, насколько "плохую" схему синтезирует Quartus по ресурсоемкости и быстродействию (до анализа в TQA руки никак не дойдут)  

[SM]

Я думаю, Maverick писал про схему, указанную в pdf, а не про тот код, который написан в его посте.   

А, если так, то тогда да, на этой основе никто алгоритма подсчета не предлагал. Я имел в виду именно схему, представленную кодом из поста. Однако в этом алгоритме понадобится на выходе кодер экспоненты (вычисление положения старшей 1), что тоже не сказать, что ресурсов не занимает. Да и эти вот блочки на пересечениях - в лучшем случае 1 блок 1 LUT в арифметическом режиме (или в режиме CASCADE, который был в свое время в ацексах), в худшем - 1 блок 2 LUT, и кол-во блоков пропорционально квадрату разрядности, что не выглядит эффективным.

[Maverick]

Я думаю, Maverick писал про схему, указанную в pdf, а не про тот код, который написан в его посте. 

Вы правы Именно ее я и имел ввиду

Сообщение №6 в этой ветке. Сразу вместе со сравнением результатов синтеза с вариантом неоптимального дерева.

Спасибо посмотрел и все таки, реализация не по предложенному мною алгоритму (описанный в pdf файле).
PS это только мое мнение

[SM]

реализация не по предложенному мною алгоритму (описанный в pdf файле).

Исходя из текста Вашего поста, я пришел к однозначному выводу, что в pdf предложен тот код, который приведен был в тексте сообщения на VHDL, ну и в pdf даже и заглядывать не стал... Оказывается, был не прав. Сорри.

[Maverick]

Исходя из текста Вашего поста, я пришел к однозначному выводу, что в pdf предложен тот код, который приведен был в тексте сообщения на VHDL, ну и в pdf даже и заглядывать не стал... Оказывается, был не прав. Сорри.

Извините меня плиз, если что не так сказал , но я скорее привел описание которое обсуждалось, т.е. на сумматорах. В pdf приведен пример реализации с помощью цепочки логики "И" и "ИЛИ", и описания на VHDL его не делал (руки как-то не доходили, хотя хочу это как-то реализовать и посмотреть/сравнить эти реализации).