Forum: FPGA, VHDL & Co. Vergleichsoperator "<" benötigt weniger Logikelemente als "!=" ?


von Emil G. (balsamico)


Lesenswert?

Uns wurde im Digitaltechnikkurs gesagt, wir sollen als 
Vergleichsoperator wenn möglich != anstelle von < bzw. > verwenden, weil 
es Ressourcen sparen würde.

In einem Frequenzteiler habe ich beide Varianten ausprobiert und Quartus 
gibt im Compilation Report für die Variante mit "<" 88 und für die 
Variante mit "!=" 97 Logikelemente verwenden zu müssen. Ist es nicht 
weniger aufwändig, nur auf Ungleichheit zu überprüfen?

1
module Freqteiler #(n=5999999)(output clockout, input clockin);
2
reg [63:0] counter=0;
3
reg c=0;
4
assign clockout = c;
5
always@(posedge clockin) begin
6
7
  if(counter!=n) begin     // ....(counter < n) wirtschaftlicher?
8
9
    counter <= counter + 1;
10
  end else begin
11
    counter <= 0;
12
    c <= ~c;
13
  end
14
end
15
endmodule


Ich verwende ein MAX1000-Board mit dem MAX10-FPGA -falls das zur Sache 
tut.

Soll ich mir das Gegenteil einprägen? -immer besser wenn möglich < bzw. 
> anstelle von != verwenden?

Danke!

: Bearbeitet durch User
von J. S. (engineer) Benutzerseite


Lesenswert?

Ob das weniger benötigt, hängt von der realen Implementierung ab. So, 
wie man es "natürlich" implementieren würde, nämlich mit einem 
verundeten Bitvergleich, ist die Forderung einleuchtend.

Ich kann aber immer nur wieder darauf hinweisen, dass FPGAs eben nicht 
so funktionieren, wie es die Logikgatter, die wir uns ersatzweise 
vorstellen, andeuten.

Alles wird auf LUTs heruntergebrochen und mit anderen Schaltungsteilen 
verknüpft, von daher ist das Ergebnis mit zunehmender Restschaltung 
immer weniger deterministisch.

Solche Regeln galten für die ersten GALs und PALs.

: Bearbeitet durch User
von C. A. Rotwang (Gast)


Lesenswert?

Emanuel G. schrieb:
> Uns wurde im Digitaltechnikkurs gesagt, wir sollen als
> Vergleichsoperator wenn möglich != anstelle von < bzw. > verwenden, weil
> es Ressourcen sparen würde.
>
> In einem Frequenzteiler habe ich beide Varianten ausprobiert und Quartus
> gibt im Compilation Report für die Variante mit "<" 88 und für die
> Variante mit "!=" 97 Logikelemente verwenden zu müssen. Ist es nicht
> weniger aufwändig, nur auf Ungleichheit zu überprüfen?
>
>
>
1
module Freqteiler #(n=5999999)(output clockout, input clockin);
2
> reg [63:0] counter=0;
3
> reg c=0;
4
> assign clockout = c;
5
> always@(posedge clockin) begin
6
> 
7
>   if(counter!=n) begin     // ....(counter < n) wirtschaftlicher?
8
> 
9
>     counter <= counter + 1;
10
>   end else begin
11
>     counter <= 0;
12
>     c <= ~c;
13
>   end
14
> end
15
> endmodule
>
>
> Ich verwende ein MAX1000-Board mit dem MAX10-FPGA -falls das zur Sache
> tut.
>
> Soll ich mir das Gegenteil einprägen? -immer besser wenn möglich < bzw.
>> anstelle von != verwenden?

Weder noch, du solltest dir aber mal anschauen in welche Logik ein 
Vergleich umgesetzt wird. Vielleicht mal ne gute Idee das händisch zu 
machen also Logictabelle aufschreiben und optimieren (Karnough).

ein n-bit vergleich == sollte n/LUT_fanin LUTS benötigen, (!= ebenso, 
nur halt mit negierten LUT-Content)
ein x<a dagegen wird in a == Vergleiche aufgetrödelt die OR verknüpft 
sind.

Ausser man verwendet statt der LUT's einen Adder/Subtractor, dann 
sollten beide Vergleiche gleichviel resourcen verbrauchen.

Und spätestens an dieser Stelle solltest du deine "Messergebnisse" auf 
Plausibilität prüfen, theoretisch kann die Logik für > nicht kleiner 
sein als '=='. Möglicherweise hast du 'dead code' fabriziert, also der > 
Vergleich ist immer true oder false und dann wird der ganze Vergleich 
wegoptimiert. Das kann gerne bei signed/unsigned passieren.

Also ich würde ==  bevorzugen, wenn == verlangt ist, schon wegen der 
einfacher Testbarkeit wegen.

von C. A. Rotwang (Gast)


Lesenswert?

Emanuel G. schrieb:
BTW, üblicherweise schreibt man einen Zähler geringfügig anders, mit 
high prioren reset und dem Zählen im else Zweig. Verhaltensmäßig mag der 
Unterschied gering sein, kann aber das Syntheseergebniss erheblich 
beeinflußen.

 https://www.altera.com/support/support-resources/design-examples/design-software/verilog/ver_behav_counter.html

1
module Freqteiler #(n=5999999)(output clockout, input clockin);
2
reg [63:0] cnt_q = 0;
3
reg        c_q   = 0;
4
5
assign clockout = c_q;
6
7
always@(posedge clockin) begin
8
    if (cnt_q == n) begin     // sync reset by wrap around
9
       cnt_q   <= 0;
10
       c_q     <= ~c_q;             //toggle output
11
    end else begin
12
       cnt_q   <= cnt_q + 1;
13
   end
14
 end
15
 endmodule

von daniel__m (Gast)


Lesenswert?

Emanuel G. schrieb:
> if(counter!=n) begin     // ....(counter < n) wirtschaftlicher?

Das könnte ganz einfach daran liegen, dass counter deutlich mehr 
Bitbreite hat als die Konstante n. Bei = (!=) werden u.u. alle Bits 
verglichen, bei <, <=, >, >=, etc. nur die Benötigten. In diesem Falls 
sind viele MSBs nicht entscheidungerelevant.

von C. A. Rotwang (Gast)


Lesenswert?

daniel__m schrieb:
> Bei = (!=) werden u.u. alle Bits
> verglichen, bei <, <=, >, >=, etc. nur die Benötigten. In diesem Falls
> sind viele MSBs nicht entscheidungerelevant.

??Du meinst LSB??

Also nur bei Vergleichen mit Zweier-Potenzen tritt der Fall ein ,das 
nicht alle bits zum Vergleich herangezogen werden müßen.

Also um bei einem 8 bit unsigned Wert zu entscheiden ob er kleiner als 
128 ist muss man nur das oberste (MSB) bit prüfen, die unteren sind in 
diesem Fall irrelevant. ist cnt_q[7] == '0' , dann ist der Vergleich 
"cnt_q < 128" true



Bei einem Vergleich auf kleiner 127 muss man dagegen die LSB mit 
einbeziehen, um den Fall cnt_q != "0111_1111" als zweite Teilbedingung 
mitzuprüfen.

5999999 in dem Beispiel ist nun aber keine 2erpotenz, also kann das 
nicht die Erklärung sein.

von Sigi (Gast)


Lesenswert?

Emanuel G. schrieb:
> Uns wurde im Digitaltechnikkurs gesagt, wir sollen als
> Vergleichsoperator wenn möglich != anstelle von < bzw. > verwenden, weil
> es Ressourcen sparen würde.

Solche Aussagen müssen immer im Kontext gesehen werden.
Meisst soll hier auf die Umsetzung/Ergebnisse der
Std.Tools hingewiesen werden, und die sind oft alles
andere als optimal.

Wenn du dich selber dranmachst und die Vergleichsoperatoren
für FPGAs in LUTs/CarryChains manuelll giesst, dann wirst
du feststellen, dass der Resourcenverbrauch +/- identisch
ist.

Und: was meinst du genau mit Logikelementen? LUTs?
Wenn ich einen Vergleich bei 64 Bits mache, dann liegt
der Verbrauch bei einfacher Optimierung/Implementierung
etwa 64 LUTs, bei besserer Optimierung nur 16 LUTs.

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

Emanuel G. schrieb:
> if(counter!=n) begin     // ....(counter < n) wirtschaftlicher?
Alle Jahre wieder... ;-)
Siehe den Beitrag "Re: Logikverbrauch Vergleichsoperatoren"
und die verlinkten Threads. Da beziehen sich die fragen zwar auf VHDL, 
die Logik und die Zielplattform "FPGA" ist aber die selbe...  ;-)

> Ist es nicht weniger aufwändig, nur auf Ungleichheit zu überprüfen?
Prinzipiell ist ein Vergleich auf "ungleich" das selbe wie ein Vergleich 
auf "gleich". Das eine ist lediglich eine Negation des Anderen. Und beim 
Vergleich auf Gleichheit muss jedes Bit in Betracht gezogen werden, 
während beim < oder auch <= oder > oder >= ganze Bereiche wegoptimiert 
werden können.

> Uns wurde im Digitaltechnikkurs gesagt, wir sollen als
> Vergleichsoperator wenn möglich != anstelle von < bzw. > verwenden, weil
> es Ressourcen sparen würde.
Wobei man natürlich beachten muss, dass da gar nichts "verglichen", 
sondern nur eine Kombinatorik berechnet wird, die für den Reset 
zuständig ist.
Nehmen wir mal einen Vergleicher, der ein 6-Bit-Wort auf "101001" 
vergleichen und dann einen Zähler zurücksetzen soll. der "Vergleicher" 
wird dann in einer 6er LUT realisiert, in der alles 0 ist, bis auf die 
Adresse 41, die eine 1 enthält.

Es kann für das Beispiel hier also gut sein, dass der 
Ressourcenverbrauch beim "Vergleich" auf 5999998 oder 6000000 zugunsten 
des = bzw. /= ausfällt. Tendenziell habe ich aber die Erfahrung gemacht, 
dass "Vergleiche" gegen Konstanten mit < und > besser implementiert 
werden können.

: Bearbeitet durch Moderator
von Yalu X. (yalu) (Moderator)


Lesenswert?

Lothar M. schrieb:
> Und beim
> Vergleich auf Gleichheit muss jedes Bit in Betracht gezogen werden,
> während beim < oder auch <= oder > oder >= ganze Bereiche wegoptimiert
> werden können.

Ein Beispiel:

Bei den Vergleichen

  x ≥ k · 2^n  bzw.
  x < k · 2^n

haben die niederwertigsten n Bits von x keinen Einfluss auf das
Ergebnis, bei

  x == k · 2^n  bzw,
  x != k · 2^n

hingegen schon.

So entspricht bspw. der 8-Bit-Vergleich x[7:0] < 80 dem 4-Bit-Vergleich
x[7:4] < 5 und kann (bei einer LUT-Breite < 8) mit etwa dem halben
Aufwand von x[7:0] != 80 realisiert werden.


> module Freqteiler #(n=5999999)(output clockout, input clockin);
> ...
>   if(counter!=n) begin     // ....(counter < n) wirtschaftlicher?
>
>     counter <= counter + 1;

  counter != n

entspricht

  counter[63:0] != 5999999

Es müssen also alle 64 Bits von counter ausgewertet werden.

  counter < 5999999

kann zwar nicht direkt optimiert werden. Da aber sowieso ein
Inkrementierer benötigt wird, kann der Vergleich auch so aussehen:

  counter + 1 < 6000000

was

  (counter + 1)[63:7] < 46875

entspricht. Dazu müssen nur 57 statt 64 Bits ausgewertet werden.

Prinzipiell können auch die höchstwertigen 41 Bits unberücksichtigt
bleiben, da der tatsächlich genutzte Wertebereich von counter nur 23
Bits umfasst. Diese Optimierung ist aber auch für den Vergleich mit !=
anwendbar.

: Bearbeitet durch Moderator
von Emil G. (balsamico)


Angehängte Dateien:

Lesenswert?

Wow. So simpel dieses Forum aufgemacht ist, so gewaltig ist was seine 
User hier an Wissen, Erfahrung und Hilfsbereitschaft mitbringen. Das 
wird mir gerade immer klarer.

Ich habe mich bis jetzt 2 Mal durch die Posts gearbeitet und schon 
vieles verstanden. Vielen Dank euch allen!


Sigi schrieb:
> Und: was meinst du genau mit Logikelementen? LUTs?

Flip-Flops denke ich, oder eben das, wovon der Max10 8000 hat und was 
wohl der beschränkende Faktor bezüglich der Kapazität für Schaltungen im 
FPGA ist. (siehe Bild) Ich muss mir das alles erst noch aneignen, so 
tief sind wir in das Thema leider nicht eingestiegen (Elektrotechnik, 
Hochschule). Aber jetzt habe ich ja euch :)


/edit
Flip-Flops ist natürlich Blödsinn, 88 FFs für das ganze Ding kann nicht 
wirklich sein, ist klar...

: Bearbeitet durch User
von C. A. Rotwang (Gast)


Lesenswert?

Emanuel G. schrieb:


> Flip-Flops denke ich, oder eben das, wovon der Max10 8000 hat und was
> wohl der beschränkende Faktor bezüglich der Kapazität für Schaltungen im
> FPGA ist. (siehe Bild) Ich muss mir das alles erst noch aneignen, so
> tief sind wir in das Thema leider nicht eingestiegen (Elektrotechnik,
> Hochschule).

Die "Kaüazität" wird von verschiedenen Ressorucen beschränkt, FF, 
Kombinatorik, Taktnetzwerke, routing resources, pins, DSP-slices, carry 
chain,... . Logigelemente (LE) enthalten einige FF, LUT's und kleinkram 
also mehrere Resourcen verschiedenster Art. Um die resourcenauslastung 
zu bestimmen, muss man also sich auch vergewissern wie "ausgelastet das 
LE ist. manchmal entsteht übermässige Belastung.
https://www.altera.com/en_US/pdfs/literature/hb/max-10/m10_architecture.pdf 
S.8


>Aber jetzt habe ich ja euch :)

Du hast die Dokus, User Guides,Online Hilfe, manuals, AppNotes, WP vom 
FPGA-Hersteller, etc. pp. aber nicht uns. Zumindest ich weise jede 
Vereinnahmung von mir.


PS:
IMHO ist die Frage falsch zum Beispieldesign formuliert, da das design 
kein Comparator sondern ein Freq-teiler ist.
Ein clock divider ist nicht notwendigerweise mit einem dedizierten 
comperator-block aufgebaut, zum Vergleich können interne Signale der 
(Zähler-) Logik benutzt werden.
Optimalerweise lässt man das Zählwerk eines Freq-dividers auf 0 laufen 
und nutzt zum Wraparound  höchstwertige Carry-sig. Das carry-signal muss 
nicht im Verilog/VHDL-Code expizit ausformuliert sein, normalerweise 
genügt eine codezeile mit dem passenden bedingung, damit das 
Synthesetool erkennt, welches "Macro" es zu benutzen hat.
Die Zählgrenze wird als Load-value benutzt aber nicht als Vergleich, das 
erwähnte carry-sig wird als load signal des Zählwerkes genutzt.

Der Synthesis style guide des jeweiligen FPGA-Herstellers sollte das 
passende Template dafür zeigen:

https://www.altera.com/en_US/pdfs/literature/hb/qts/qts_qii51008.pdf
https://www.altera.co.jp/content/dam/altera-www/global/en_US/pdfs/literature/hb/qts/qts_qii51006.pdf

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.