von LSB bis führendes bit auf 1 setzen.

[fpga-freund (Gast)]

Hallo,

Ich habe einen 256 bit breiten Vector und ich möchte das ab der ersten 
vorkommenden 1 (aus MSB Richtung betrachtet) alle anchfolgenden Stellen 
auf 1 gesetzt werden.
Was währe denn unter berücksichtigung von geringen Taktzyklen und 
Durchlafszeiten eine gute Möglichkeit?

Bisher sieht mein Ansatz so aus, dass ich von MSB nach LSB N-Bit breit 
verodert prüfe ob ein oder mehrere bits auf 1 stehen.
Wenn nicht dann shift ansonsten werden bis zu N Takte benötigt um 
festzustellen welche stelle die erste eins hat.
Danach benötige ich wieder einige taktzyklen um die niederen bits  auf 1 
zu legen.

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

fpga-freund wrote:
> Was währe denn unter berücksichtigung von geringen Taktzyklen und
> Durchlafszeiten eine gute Möglichkeit?
Wie schnell muss das gehen? Der Ressourcenverbrauch ist egal?

> Ich habe einen 256 bit breiten Vector und ich möchte das ab der ersten
> vorkommenden 1 (aus MSB Richtung betrachtet) alle anchfolgenden Stellen
> auf 1 gesetzt werden.
Also eigentlich ein Monstermultiplexer.

> Wenn nicht dann shift
Schieberegister... hmmmm...ich weiß nicht so recht, ob das schneller 
ist. Auf jeden Fall musst du dann den Zugriff auf dieses Register 
arbitrieren und verwalten.

Ich würde darauf basierend mal was aufbauen:
http://www.lothar-miller.de/s9y/archives/55-Finde-das-MSB.html
Eine Strategie wäre z.B. sowas das 8 mal aufzubauen und dann nach Finden 
der "ersten" 1 alle "darunterliegenden" 32-Bit-Worte auf xffffffff zu 
legen...

[ElKo (Gast)]

You are in the english part of the forum. Would be nice to write english 
then, or post in mikrocontroller.net.

How about doing it in one clock cycle? Costs a lot of logic, but should 
be fast. Just check all 256 cases and use the result of the highest.

Untested Pseudocode:

input in[255:0];
output out[255:0];
integer i;

for (i=255; i>0; i=i-1) begin
    if ( (in >> i) == 1 ) begin
        out = (0!) >> i;
        break;
    end
end

If the break is not working properly you can also make a big or-gate for 
the result. This will keep only the highest result.

out = 0;
for (i=255; i>0; i=i-1) begin
    if ( (in >> i) >= 1 ) begin
        out = out | ((0!) >> i);
    end
end

Or you write it straight forward as a big switch-case.

I think this is the fastest regarding speed.

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

ElKo wrote:
> You are in the english part of the forum.
Ja, danke für den Tipp. Ich habe das korrigiert..

Wo ich die Antwort da so sehe befällt mich die Frage: welche 
Beschreibungssprache? Oder geht es lediglich um ein prinzipielles 
Verfahren?

[ElKo (Gast)]

Lothar M. schrieb:
> Ja, danke für den Tipp. Ich habe das korrigiert..
Habs gesehen. Danke. Du warst ein klein wenig schneller. :)

Sprache: An Verilog angelehnt. Wie gesagt, als Anregung. Müsste so 
ähnlich aber umsetzbar sein. Meiner Erfahrung nach liegt der Teufel im 
Detail. Ich bin mir zum Beispiel nicht sicher, wie das break in den 
Tools wirklich umgesetzt werden würde.

[Gustl B. (-gb-)]

Da gibt es doch den Prioritätsencoder. Der liefert die rein 
kombinatorisch den Index des höchstwertigen gesetzten Bits zurück.

[Sigi (Gast)]

fpga-freund schrieb:
> Ich habe einen 256 bit breiten Vector und ich möchte das ab der ersten
> vorkommenden 1 (aus MSB Richtung betrachtet) alle anchfolgenden Stellen
> auf 1 gesetzt werden.
> Was währe denn unter berücksichtigung von geringen Taktzyklen und
> Durchlafszeiten eine gute Möglichkeit?

Schau dir mal als Beispiel die Carry-Chain einer
Spartan3/VirtexII/Virtex4-Logikzelle an. Du fütterst
diese ganz Unten mit 0, sobald eine 1 auftaucht, wird
eine 1 ausgegeben und eine 1 in die Chain eingespeisst.
Da du von MSB an abwärts arbeitest musst du nur noch
den Vektor "umgekehrt" an die Chain legen.

Bei 256 Bit schätze ich (+Datasheet-Specs) beim Virtex4
bist du bei 40MHz.

[ElKo (Gast)]

Ok, das Break wollte Modelsim nicht. Keine Ahnung wieso. SystemVerilog 
soll das eigentlich können.
> ** Error: (vsim-3043) compare.v(36): Unresolved
>      reference to 'break'.

Mit der richtigen Bedingung im if geht es aber auch ohne. Ergebnis siehe 
Anhang. Hier für 16 Bit. Für 256 einfach den Parameter hoch setzen. 
Synthesefähigkeit nicht geprüft.

module compare(
        din,
        dout
    );
    
    parameter len = 16;
    
    // Inputs, Outputs
        input   [len-1:0] din;
        output  [len-1:0] dout;
        
    // variables
        integer i;
        reg [len-1:0] temp;
    
    assign dout = temp;
    
    // multiplexer
    always @(din) begin
        temp = 16'h0;
        for (i=len-1; i>=0; i=i-1) begin
            if ( (din >> i) == 1 ) begin
                temp = (16'hFFFF) >> (len-i-1);
            end
        end
    end

endmodule

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

ElKo schrieb:
> Synthesefähigkeit nicht geprüft.
Mit VHDL geht es komplett kombinatorisch. Auf dem alten S3 laut 
Synthesizer mit knapp 50ns, ein V5 macht 30ns daraus...

EDIT: mal genauer untersucht: der lügt sich da irgendwas in die 
Tasche... :-/

Ich würde mir auch mal die Sache mit der Carry-Chain genauer anschauen, 
ob sich da nicht was machen lässt.

[bitwurschtler (Gast)]

fpga-freund schrieb:
>Ich habe einen 256 bit breiten Vector und ich möchte das ab der ersten
>vorkommenden 1 (aus MSB Richtung betrachtet) alle anchfolgenden Stellen
>auf 1 gesetzt werden.
>Was währe denn unter berücksichtigung von geringen Taktzyklen und
>Durchlafszeiten eine gute Möglichkeit?

RS-FF, das high aktive S mit Q des FF davor verbinden.

[Sigi (Gast)]

Lothar M. schrieb:
> Ich würde mir auch mal die Sache mit der Carry-Chain genauer anschauen,
> ob sich da nicht was machen lässt.

Dein Code macht im Prinzip schon dass, was ich mit der
CarryChain erreichen möchte, ISE mapped es aber nicht
perfekt in die CLBs/Slices. Von daher ist es ein wenig
(wirklich nur wenig!) langsamer als die CarryChain.

Im Anhang/Bildern sieht man eine einzelne Zelle, einen
Teil der Kette und beide Testbenches.

Wenn man noch zusätzlich bedenkt, dass die verwendeten
LUT4 4 Eingänge besitzen und per Tabelle eine Art
Priority-Encoder implementiert werden kann, dann kann
man damit die Kettenlänge nochmal durch 4 teilen und
erreicht durch entsprechende Location-Constraints
Taktraten um die 400-500MHz (auf Virtex5 sogar bis
700MHz). Allerdings wird das Weitertransportieren bei
diesen Taktraten schnell sehr aufwendig.

[Sigi (Gast)]

bitwurschtler schrieb:
> RS-FF, das high aktive S mit Q des FF davor verbinden.

Kann man machen, man muss aber bedenkten, dass
dadurch eine sehr langsame Kette generiert wird
(geschätzt ca. 5-10 mal langsamer als eine CarryChain).

Eine CarryChain hat z.B. per V4-Slice 0.09ns
(256/2*0.09ns = 11.52ns) und per V5-Slice 0.11ns
(256/4*0.11ns = 7.04ns) Durchlaufzeit. Durch geschicktes
Verwenden dieser Ketten können z.B. 16KBit-Vektoren
mit >=50MHz auf V5 mit einer Konstanten/Variablen
verglichen werden.