Effizienter popcount

[Dominik N. (dzo_pf)]

Hallo,
ich brauche für eine Transformation (FPGA Bildverarbeitung) ein 
Popcount, welches aus einem 80-bit-Array die Einsen zählt und als Stream 
ausgibt (II=1). Ich verpacke das ganze in AXI4-Streams (Input: 80-bit, 
Output 7-bit).

Mein bisheriger Ansatz bestand aus dem folgenden Snippet:

            for idx in 0 to FILTER_WIDTH*FILTER_HEIGHT-1 loop
                if in_data_i(idx) then
                    v.count := v.count + 1;
                end if;
            end loop;

Dies ist zwar ein sehr einfacher Ansatz, führt für mich jedoch logisch 
zu einem unanständig komplexen kaskadierten Addierer, ohne die LUTs 
richtig auszureizen. Habt ihr eine andere Idee? Falls Pipelining 
notwendig, wäre das auch kein Problem (sollte aber möglichst generisch 
erfolgen können, um flexibel zu bleiben). Gibt es eine Lösung, die LUTs 
zu verwenden, und möglichst wenig kombinatorische Pfade zu erhalten 
(Ziel: 300 MHz auf Cyclone 10 GX).

Viele Grüße,
der zopf

[Duke Scarring (Gast)]

Wie schnell bist Du denn jetzt mit dem 80-Bit Adder?

[Dominik N. (dzo_pf)]

280 MHz, unter sehr idealen Zuständen (direkte Pin-IOs). Im Anhang die 
RTL der langen Adder-Chain (chain, chain, chain...). Die Timing Closure 
Recommendations empfehlen genau diesen kombinatorischen Datenpfad zu 
verkleinern, um schneller zu werden.

[Duke Scarring (Gast)]

D. Z. schrieb:
> 280 MHz
Ok. Dann muß man es ja mit dem Pipelinen nicht gleich übertreiben:
Wenn Du in der ersten Stufe jeweils 16 Eingänge summierst, bleiben in 
der zweiten Stufe noch 5 Additionen übrig. Die erste Stufe ist dann 
schon wieder für neue Daten frei.

Duke

[Dominik N. (dzo_pf)]

Meine Frage bezog sich auch nicht darauf, wie es anders mit Addierern zu 
lösen ist, sondern wie man eventuell LUTs nutzen kann, um Popcount 
generisch kombinatorisch simpler zu machen. Mir ist schon klar, dass mit 
mehreren Pipeline-Stufen das ganze Design schneller laufen kann.

[Tobias F. (analrapist)]

Das wird wohl schwierig. In der ersten Stufe kannst du die 2-Output LUTs 
nur nutzen um 3 Inputs zusammenzufassen. Das gibt dann 27 2Bit Zahlen 
die du zusammenfassen musst. Davon kannst du mit je 4 6-Input LUTs eben 
3 Stueck verarbeiten. Damit hast du 2 Logic Levels und es bleiben dir 9 
4Bit Zahlen. Spaetestens hier musst du richtige Addierer mit Carry 
Chains benutzen.

[Dominik N. (dzo_pf)]

Okay, habe schon befürchtet, dass eine der optimalen Lösungen ist, 
händisch die LUT-Hierarchie zu definieren. Da ich mich jetzt nicht auf 
80-bit festlegen möchte, hatte ich die Hoffnung, dass hier jemand einen 
sehr generischen Algo preisgibt, der von Quartus ziemlich effizient in 
Hardware umgesetzt wird. Ich verbleibe erstmal bei dem aktuellen Design, 
und werde mich dann wohl in naher Zukunft mit der händischen Optimierung 
beschäftigen - vielleicht findet sich ja noch jemand (Herr Miller?), der 
ne gute Idee hat. Trotzdem danke für den Input.

[Sigi (Gast)]

Ich würd's fast so wie Tobias machen, nur in der
ersten Stufe fasse ich 6 Bits per 3xLUT6 zu einer
ersten Summe zusammen (eiglich 14 Summen).
Danach wird mit CarryChain-Adder weitergefahren:
1.Stufe: 14X 6*LUT6 => 14X 3-Bit-Sums
2.Stufe:  7x Adder  =>  7x 4-Bit-Sums
3.Stufe:  4x Adder  =>  4x 5-Bit-Sums
4.Stufe:  2x Adder  =>  2x 6-Bit-Sums
5.Stufe:  1x Adder  =>  1x 7-Bit-Sums
d.h. 109 LEs (55 ALMs)

Da dir Pipelining egal ist, je Stufe eine
Registerbank (keine zusätzlichen LEs).

Bleibt nur noch die Frage nach einer "guten"
Implementierung:
Ich würd's wie bei einer rekursiven Definition
machen, implementiert durch eine Komponente,
relativ leicht runterzuschreiben.

[Tobias F. (analrapist)]

Sigi schrieb:
> Ich würd's fast so wie Tobias machen, nur in der
> ersten Stufe fasse ich 6 Bits per 3xLUT6 zu einer
> ersten Summe zusammen (eiglich 14 Summen).
> Danach wird mit CarryChain-Adder weitergefahren:

Ja klar, hab uebersehen dass man dafuer auch mehrere 6-input LUTs nehmen 
kann. Trotzdem wird die Architektur mehr als 5 Logic Levels haben. Stufe 
1 hat einen, Stufe 2 ebenfalls, Stufe 3 hat aber dann schon zwei.

[Weltbester FPGA-Pongo (Gast)]

D. Z. schrieb:
> ibt es eine Lösung, die LUTs
> zu verwenden, und möglichst wenig kombinatorische Pfade zu erhalten
> (Ziel: 300 MHz auf Cyclone 10 GX).

Es ist ziemlich egal, wie du das beschreibst. Wenn es rein 
kombinatorisch ist, verteilt er die LUTs wie er es braucht.

[Vancouver (Gast)]

Wenn Du bereit bist, den Begriff LUT etwas weiter zu fassen, kannst Du 
in der ersten Stufe passend initialisierte BlockROMs statt 
1-Bit-Additionen verwenden. Mit 1k-ROMS kannst Du z.B. alle Ergebnisse 
für 10-Bit-Popcounts speichern. Dann brauchst du 8 solcher ROMs, alle 
mit dem gleichen Inhalt, und in der nächsten Stufe machst Du einen 
klassischen Adder-Tree mit 8 Operanden. Das ganze skaliert auch relativ 
leicht für größere oder kleinere Eingangs-Operanden.