Bits in Wort zählen

[Bronco (Gast)]

Hallo,

ich habe ein 16Bit-paralleles Interface am FPGA, über das ich Datenwort 
empfange und dann in ein RAM speichere.
Zum Debuggen wäre es interessant, die Anzahl der gesetzten Bits 
mitzuzählen, die an meinem Interface reinkommen. Allerdings kommen die 
Worte mit voller Taktrate rein, d.h. ich müßte die Anzahl der gesetzten 
Bits im Wort in einem Takt erfassen.
Ich könnte natürlich mit einem "for"-Konstrukt jede Menge parallele 
Vergleicher erzeugen...
Oder gibt es da vielleicht noch einen Trick 17?

[Ottmar (Gast)]

Wozu benötigt man da Vergleicher?

d0 ---\
      |
d1 --(+)--\
          |
d2 ------(+)--\
              |
d3 ----------(+)--\
...
                      |
d1 ------------------(+)--> Sum

Wenn die synthese inteligent ist dann macht sie was performantes draus.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Bronco schrieb:
> Ich könnte natürlich mit einem "for"-Konstrukt jede Menge parallele
> Vergleicher erzeugen...
Du wirst sowieso nicht drumrum kommmen...
Aber halb so schlimm: es werden nicht "jede Menge Vergleicher" 
herauskommen, sondern nur ein relativ simples Logikkonstrukt mit 16 
Eingängen und 5 Ausgängen, weil mehr als 16 Zustände sowieso nicht 
vorkommen können.


BTW: War alles schonmal da...
https://www.mikrocontroller.net/search?query=einsen+zählen&forums[]=9

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Ich hätte da dann mal was ausprobiert:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity CountOnes is
    Port ( i : in  STD_LOGIC_VECTOR (15 downto 0);
           o : out  STD_LOGIC_VECTOR (4 downto 0));
end CountOnes;

architecture Behavioral of CountOnes is

begin
  -- Spartan 3
  -- Number of Slices       42
  -- Number of 4 input LUTs 73
  process (i) 
  variable cnt : integer range 0 to 16 := 0;
  begin
     cnt := 0;
     for c in 0 to 15 loop
       if i(c)='1' then 
         cnt:=cnt+1; 
       end if;
     end loop;
     o <= std_logic_vector(to_unsigned(cnt,5));
  end process;

  -- Spartan 3
  -- Number of Slices       16
  -- Number of 4 input LUTs 28
  process (i) 
  variable cnt : unsigned (4 downto 0);
  begin
     cnt := "00000";
     for c in 0 to 15 loop
       cnt:=cnt+unsigned'("0000"&i(c)); 
     end loop;
     o <= std_logic_vector(cnt);
  end process;

end Behavioral;

Die erste Variante gibt einen recht aufwendigen Multiplexer und braucht 
27ns, die zweite Variante die gewünschten Addierer mit 19ns 
Durchlaufzeit (incl. IO-Pads Treiber!)...

[Bronco (Gast)]

Lothar Miller schrieb:

cnt:=cnt+1;

Das klingt ja zu schön, um wahr zu sein!
Baut die Synthese da etwa einen Addierer mit 16 Eingängen?

[Ottmar (Gast)]

Lothar Miller schrieb:
> variable cnt : integer range 0 to 16 := 0;

Interessanter Unterschied im synthese Ergebnis. Vielleicht käme die 
synthese mit einem range 0 to 31 besser zurecht.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Bronco schrieb:
> Baut die Synthese da etwa einen Addierer mit 16 Eingängen?
Nein, die baut 16 Addierer...

Ottmar schrieb:
> Interessanter Unterschied im synthese Ergebnis. Vielleicht käme die
> synthese mit einem range 0 to 31 besser zurecht.
Das ist der Synthese schnuppe.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Lothar Miller schrieb:
> Die erste Variante gibt einen recht aufwendigen Multiplexer und braucht
> 27ns, die zweite Variante die gewünschten Addierer mit 19ns
> Durchlaufzeit (incl. IO-Pads Treiber!)...
Die dritte Variante ist noch schneller (16.444ns):

  process (i) 
  variable c0  : unsigned (2 downto 0);
  variable c1  : unsigned (2 downto 0);
  variable c2  : unsigned (2 downto 0);
  variable c3  : unsigned (2 downto 0);
  variable cnt : unsigned (4 downto 0);
  begin
     cnt := "00000";
     c0  := "000";
     c1  := "000";
     c2  := "000";
     c3  := "000";
     for c in 0 to 3 loop
       c0 := c0+unsigned'("00"&i(c)); 
       c1 := c1+unsigned'("00"&i(c+4)); 
       c2 := c2+unsigned'("00"&i(c+8)); 
       c3 := c3+unsigned'("00"&i(c+12)); 
     end loop;
     cnt:= unsigned'("00"&c0) + unsigned'("00"&c1) + unsigned'("00"&c2) + unsigned'("00"&c3);
     o <= std_logic_vector(cnt);
  end process;

[Ottmar (Gast)]

Mit Synplify Pro bekomme ich für die Variante 1 ein ganz anderers 
Ergebnis.
V1: 25 LUT
V2: 28 LUT
V3: 28 LUT

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Ottmar schrieb:
> Mit Synplify Pro bekomme ich für die Variante 1 ein ganz anderers
> Ergebnis.
Und was kommt dabei heraus?
Anscheinend erkennt dieser Synthesizer, dass das if nicht wirklich 
eine Abfrage ist, und generiert keine Multiplexer wie XST 13.2 das tut. 
Kurz: es ist schon sinnvoll, wenn man das Verhalten "seines" 
Synthesetools ab und an mal auf Eigenarten abklopft...

[Ottmar (Gast)]

V1: Siehe Anhang.
V2: Ein Adder mit 16 eingängen.

Nach dem mappen:
V1 benutzt einige MUXCY und reduziert damit den LUT count.
V2 besteht nur aus LUT's

[Detlef _. (detlef_a)]

einsen zählen kann man auch ohne Schleife, siehe angehängten C-Code. Das 
ist nur Bitfummelei, auch die Multiplikation, das sollte sich leicht in 
VHDL umsetzen lassen, wozu ich (leider leider) nicht in der Lage bin.

Cheers
Detlef

/*******************************************************************/
uint8_t cntbits(uint32_t a)
/*******************************************************************/
{uint32_t mask=011111111111ul;
a=(a-((a&~mask)>>1))-((a>>2)&mask);
a+=a>>3;
a=(a&070707)+((a>>18)&070707);
a*=010101;
return ((a>>12)&0x3f);

}

[Roberto (Gast)]

Ich frage mich, warum er bei der Adderlösung II etwas anderes 
rausbekommt, da die Adder ja auch nur über LUTs abgebildetet werden und 
am Ende zu dem selben Resultat führen müssten, wie die MUX-Version.

Offenbar sind die Tools dann doch nicht intelligent, wie man denkt.

Was kommt denn raus, wenn man bei beiden "restucture MUX" anwrift?

Auch "register retimg" sollte das tool veranlassen, die Struktur 
auzzubrechen.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Roberto schrieb:
> Offenbar sind die Tools dann doch nicht intelligent, wie man denkt.
Sie haben ihre eigene "Intelligenz", die sich von Version zu Version 
ändert, aber nicht zwingend weiterentwickelt...  ;-)

Detlef _a schrieb:
> Das ist nur Bitfummelei, auch die Multiplikation, das sollte sich
> leicht in VHDL umsetzen lassen, wozu ich (leider leider) nicht in
> der Lage bin.
Da sind ja nun einige Rechenoperationen drin, da muss der Synthesizer 
schon schlau sein, um die in Logik umzubiegen...

[Bronco (Gast)]

Detlef _a schrieb:
> einsen zählen kann man auch ohne Schleife, siehe angehängten C-Code.

Bekommt das Dein C-Code auch in einem einzigen Takt hin?

[Detlef _. (detlef_a)]

Die Anforderung für einen Takt hatte ich überlesen. Der Code braucht 
vier Takte, die kannst Du allerdings pipelinen, sodass für jeden Takt 
ein Ergebnis kommt, allerdings 4 Takte zeitverzögert.

Aber: Geht auch in einem Takt :-)))) , und zwar mit dem angehängten 
Code. Dort habe ich die sequentiellen Rechnungen durch defines ersetzt, 
braucht mehr Resourcen aber nur einen Takt, also quasi parallelisiert. 
Die Multiplikation habe ich durch Addition von drei Summanden ersetzt. 
Das ganze ist für 32Bit, bei 16 wird das noch bißchen übersichtlicher. 
Bitte auch beachten, dass bei C Zahlen mit führender 0 als Oktalzahlen 
interpretiert werden.

Danke, war Spaß gewesen.
Cheers
Detlef

P.S. So sieht das expandierte Makro aus: :-))))

return 
((((((((a-((a&~(011111111111ul))>>1))-((a>>2)&(011111111111ul)))+(((a-(( 
a&~(011111111111ul))>>1))-((a>>2)&(011111111111ul)))>>3))&070707)+(((((a 
-((a&~(011111111111ul))>>1))-((a>>2)&(011111111111ul)))+(((a-((a&~(01111 
1111111ul))>>1))-((a>>2)&(011111111111ul)))>>3))>>18)&070707))+((((((a-( 
(a&~(011111111111ul))>>1))-((a>>2)&(011111111111ul)))+(((a-((a&~(0111111 
11111ul))>>1))-((a>>2)&(011111111111ul)))>>3))&070707)+(((((a-((a&~(0111 
11111111ul))>>1))-((a>>2)&(011111111111ul)))+(((a-((a&~(011111111111ul)) 
>>1))-((a>>2)&(011111111111ul)))>>3))>>18)&070707))<<6)+((((((a-((a&~(01 
1111111111ul))>>1))-((a>>2)&(011111111111ul)))+(((a-((a&~(011111111111ul 
))>>1))-((a>>2)&(011111111111ul)))>>3))&070707)+(((((a-((a&~(01111111111 
1ul))>>1))-((a>>2)&(011111111111ul)))+(((a-((a&~(011111111111ul))>>1))-( 
(a>>2)&(011111111111ul)))>>3))>>18)&070707))<<12))>>12)&0x3f);


/*******************************************************************/
uint8_t cntbits1(uint32_t a)
/*******************************************************************/
{
#define mask (011111111111ul)
#define a0 ((a-((a&~mask)>>1))-((a>>2)&mask))
#define a1 (a0+(a0>>3))
#define a2 ((a1&070707)+((a1>>18)&070707))
//#define a3 (a2*010101)
#define a3 (a2+(a2<<6)+(a2<<12))
return ((a3>>12)&0x3f);
}

[Detlef _. (detlef_a)]

Ähm, bin nicht sicher, ob das ein Takt wird. Muß ich nochmal frischer 
drüber nachdenken.

Cheers
Detlef

[Detlef _. (detlef_a)]

Wenn's denn noch interessiert:

Ja, das geht in einem Takt. Wird aber ne fette kombinatorische Logik mit 
entweder sehr vielen Gattern nebeneinander (viel Resourcen) oder viele 
Gatter hintereinander (lange Laufzeit).

Cheers
Detlef

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Logisch, dass das in einem Takt gehen muss. Denn in dem geposteten 
Rechenwerk sind nur Addierer, Subtrahierer und Schiebeoperatoren 
beteiligt. Aber nichts, was gespeichert werden müsste.

Wenn das Ganze allerdings Teil eines getakteten Systems ist, dann wird 
hier nur eine geringe Taktfrequenz erreicht werden können, weil die 
Durchlaufzeit durch das Rechenwerk recht lang sein wird...

[Detlef _. (detlef_a)]

In meinem ursprüglichen Algorithmus mußte man sehr wohl was abspeichern, 
da brauchte man 4 Takte. Dafür war die Logik einfach.

Die Logik wird komplexer wenn man das Ergebnis in einem Takt braucht, 
aber auch da gibts tradeoffs: entweder langsam (Gatter hintereinander, 
geringe maximale Taktfrequenz) oder Gatter parallel (aufwendig). Am 
schnellsten/auwendigsten wäre es, die 2^16 Quersummen aus einer Tabelle 
zu holen. Am langsamsten/einfachsten ist es, die 16Bit sequentiell durch 
einen Addierer zu schieben. Zwischen den beiden Extremen kann man sich 
beliebig bewegen, kommt drauf an, was man will/muß, aber das ist immer 
so.

Cheers
Detlef

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Detlef _a schrieb:
> In meinem ursprüglichen Algorithmus mußte man sehr wohl was abspeichern
Ja, den Algorithmus kennt ja nun keiner ausser dir...

> Zwischen den beiden Extremen
Interessant wären Zahlen zum Ressourcenverbrauch, zur Durchlaufzeit und 
zur Toolchain. Hast du da was?

[Detlef _. (detlef_a)]

Lothar Miller schrieb:
> Detlef _a schrieb:
>> In meinem ursprüglichen Algorithmus mußte man sehr wohl was abspeichern
> Ja, den Algorithmus kennt ja nun keiner ausser dir...
>

Klar kennen den Algorithmus auch andere, den Algorithmus hatte ich doch 
oben dargestellt. Außerdem stammt der leider nicht von mir sondern ist 
der Standard zum Bits zählen in C, siehe z.B. ersten hit für 'number of 
set bits in a word'. Wenn man den kennen wollen würde, könnte man den 
auch vor meinen Einlassungen schon gekannt haben. Es gibt im übrigen 
nichts, was nur ich alleine wüßte, zumindest auf technischem Gebiet.

>> Zwischen den beiden Extremen
> Interessant wären Zahlen zum Ressourcenverbrauch, zur Durchlaufzeit und
> zur Toolchain. Hast du da was?

Nein, hab nix, kann kein VHDL, naja, so gut wie nicht.

Cheers
Detlef