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

[Egel]

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


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

[Egel]

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

[SM]

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

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

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

[Artem_Petrik]

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

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

[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