Forum: FPGA, VHDL & Co. Division in VHDL


You were forwarded to this site from EmbDev.net. Back to EmbDev.net
von Knut (Gast)


Lesenswert?

Gibt es die Möglichkeit durch einen Operatoren (z.B. / ) in VHDL zu 
dividieren? Vor allem 2 verschiedene std_logic_vector durcheinander? 
Wenn ja, in welcher Libray ( ieee... ) ist dieser zu finden? MfG

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


Lesenswert?

> Gibt es die Möglichkeit durch einen Operatoren (z.B. / ) in VHDL zu
> dividieren?
Klar kann VHDL das. Du schreibst einfach:
1
  :
2
  use IEEE.numeric_std.ALL;
3
  :
4
  signal wert1: std_logic_vector(15 downto 0) := x"1234";
5
  signal wert2: std_logic_vector(7 downto 0)  := x"56";
6
  signal result: std_logic_vector(7 downto 0);
7
  :
8
  result <= std_logic_vector(unsigned(wert1)/unsigned(wert2));

Nur blöd, dass dein Synthesizer das nicht kann...  :-o
Für eine Division in einem FPGA brauchst du etwas mehr Aufwand:
http://www.lothar-miller.de/s9y/archives/29-Division-in-VHDL.html


BTW:
> Gibt es die Möglichkeit durch einen Operatoren (z.B. / ) in VHDL zu
> dividieren? Vor allem 2 verschiedene std_logic_vector durcheinander?
Man rechnet nicht mit Vektoren. Dafür gibt es die Datentypen signed, 
unsigned und integer...

von Nobbi (Gast)


Lesenswert?

Also ich kann nur den bereits aufgeführten Divisionalgorithmus von 
lkmiller empfehlen, hab ich auch schon selbst verwendet. Du musst 
allerdings beachten dass die Division länger als einen Zyklus braucht, 
nämlich genausoviele Zyklen wie dein Datentyp Bits besitzt.
Willst du allerdings nur eine Division in der Simulation verwenden, 
kannst du ruhig den "/" Operator nehmen.
Wenn sich die Möglichkeit gibt, dann berechne die Divisionen lieber im 
vorraus und rechne mit den Ergebnissen als konstanten weiter.
Gruß Nobbi

von Michael (Gast)


Lesenswert?

Derl läuft aber zyklisch, oder?

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


Lesenswert?

Michael schrieb:
> Derl läuft aber zyklisch, oder?
Der ist getaktet.
Oder was meinst du mit "zyklisch"?

von Michael (Gast)


Lesenswert?

Ich meine, ob er voll gepipelined ist.

von dito (Gast)


Lesenswert?

Michael schrieb:
> Ich meine, ob er voll gepipelined ist.

Meinst du mit "voll gepipelined", dass man oben mit jedem Takt zwei neue 
Operanden anlegt und unten (nach einer gewissen Latenz) mit jedem Takt 
ein Ergebnis erhält? Das ist nicht der Fall!
Wenn du sowas willst, dann musst du mehrere Divisions-Komponenten 
parallel schalten und multiplexen.

von Michael (Gast)


Lesenswert?

Ach stimmt, das wäre ein Option. Dann schaue ich mal wegen der Latenz. 
Vermutlich braucht der aber je Bit einen Clock.

Ein Divider aus der CoreLib von Xilinx ist da halt schneller.

von dito (Gast)


Lesenswert?

Michael schrieb:
> Ein Divider aus der CoreLib von Xilinx ist da halt schneller.

Der Xilinx-Core kann sogar als "voll gepipelined" (nach deiner 
Definition ;-) ) konfiguriert werden.

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


Lesenswert?

Michael schrieb:
> Ein Divider aus der CoreLib von Xilinx ist da halt schneller.
Wie definierst du "schneller"?
Dass du das Ergebnis sofort hast, oder dass du schneller wieder neue 
Operanden eingeben kannst oder dass du eine höhere Taktfrequenz 
verwenden kannst?

> Ein Divider aus der CoreLib von Xilinx ist da halt schneller.
Der Divider ist dann ganz einfach aufwendiger, weil mehrere Schritte 
parallelisiert werden. Das ist kein Hexenwerk, es ist nur die Abwägung 
Ressourcen gegen Zeitbedarf.

> Vermutlich braucht der aber je Bit einen Clock.
Ja, dann ist in der Simulation schön zu sehen und nachvollziehbar. 
Dadurch kann man sich irgendwelche Vermutungen sparen. Wenn du kapiert 
hast, wie die Division funktioniert, kannst du auch über eine 
Geschwindigkeitsoptimierung nachdenken.

von J. S. (engineer) Benutzerseite


Lesenswert?

>Der Xilinx-Core kann sogar als "voll gepipelined" (nach deiner
>Definition ;-) ) konfiguriert werden.
Ja,ja - dann läuft er auf 17 MHz :-)

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


Lesenswert?

Juergen S. schrieb:
> Ja,ja - dann läuft er auf 17 MHz
Mit Multi-Cycles liesse sich da was machen... ;-)

von D. I. (Gast)


Lesenswert?

Juergen S. schrieb:
>>Der Xilinx-Core kann sogar als "voll gepipelined" (nach deiner
>>Definition ;-) ) konfiguriert werden.
> Ja,ja - dann läuft er auf 17 MHz :-)

nicht voll kombinatorisch ;)

Bei den Floating-Point teilen ist das ja auch so. Die Division braucht 
zwar 28 Takte Latenz, aber ich kann mit jedem Takt was neues 
reinschieben und bekomme dann eben nach 28 Takten jeden Takt ein 
Ergebnis

von Michael (Gast)


Lesenswert?

Das läuft aber doch alles wieder darauf hinaus, daß man ein voll 
gepipelinetes Design hat/braucht. Ergo CoreGen.

von Harald D (Gast)


Lesenswert?

Hätte bitte jemand so einen divider core, der in einem Takt rechnen kann 
und auch effektiv ist?

von KIT (Gast)


Lesenswert?

Hallo Leute,
ich versuche zu verstehen wie die Division in VHDL funktioniert.
ich kapiere dieses Code von Miller immer noch nicht richtig. kann mir 
bitte jmnd erklären was mit dem Code hier gemeint ist:

http://www.lothar-miller.de/s9y/archives/29-Division-in-VHDL.html

hier wird die bit vom vector r von b-2 bis 0 nach b-1 bis 1 verschoben 
oder und wieso wird alle bit vom vector dd(von b-2 bis 0) durch 0 
ersetzt??

ich bitte um erklärung danke
1
 when shift =>
2
            -- erst mal die beiden Operanden 
3
            -- für die Subtraktion zurechtrücken
4
            if ( (r(b-2 downto 0)&dd(b-1)) < dr ) then
5
               bits <= bits-1;
6
               r    <= r(b-2 downto 0)&dd(b-1);
7
               dd   <= dd(b-2 downto 0)&'0';
8
            else
9
               z    <= sub;
10
            end if;
11
12
         when sub =>
13
            if (bits>0) then
14
               r    <= r(b-2 downto 0)&dd(b-1);
15
               dd   <= dd(b-2 downto 0)&'0';
16
               -- Rest minus Divisor
17
               diff := (r(b-2 downto 0)&dd(b-1)) - dr;  
18
               if (diff(b-1)='0') then                 
19
                  -- wenn kein Unterlauf 
20
                  --> Divisor passt noch rein 
21
                  --> MSB=0 --> 1 in Ergebnis einschieben
22
                  q <= q(b-2 downto 0) & '1';
23
                  r <= diff;
24
               else
25
                  -- wenn Unterlauf 
26
                  --> 0 einschieben, mit altem Wert weiterrechnen
27
                  q <= q(b-2 downto 0) & '0';
28
               end if;
29
               bits <= bits-1;
30
            else
31
               z    <= done;
32
            end if;
33
            
34
         when done =>
35
            busy <= '0';
36
            -- Handshake: wenn nötig warten, bis start='0'
37
            if (start='0') then 
38
               z <= idle; 
39
            end if;
40
      end case;

danke in Voraus

von dorko (Gast)


Lesenswert?

es ist so wie in der 2.ten Klasse. Du kuckst, ob die eine Zahl in die 
andere reinpasst, dh ob du sie dividieren kannst, ohne auf <0 zu kommen. 
Wenn das nicht der Fall ist, rueckst du sie eine zehnerpotenz weiter 
nach rechts und probierst erneut.

Hier hast du halt 2er Potenzen, und die Zahl passt entweder einmal ganz 
rein oder eben nicht, aber nicht zb 2 mal wie im Dezimalsystem sein 
koennte.


Dezimal

   130 / 55
  -110   (-55x2)
 --------
    20
   -55 x 0 (geht nicht)
    20
    -5.5
    -5.5
    -5.5
 --------
     3.5

  usw

sorry etwas unuebersichtlich




binaer

 101010 / 111
 111  passt nicht
  111 passt, rest =

ach so aehnlich halt, sry ist mir grad zu fummelig

von dorko (Gast)


Lesenswert?

dorko schrieb:
> andere reinpasst, dh ob du sie dividieren kannst, ohne auf <0 zu kommen.

sollte subtrahieren heissen

von Ratgeber (Gast)


Lesenswert?

Ich finde es eigentlich antiquiert, immer wieder Divisionsalgorithmen 
implementieren zu müssen. Liesse sich da nichts in der Richtung machen?
Beitrag "FPGAs mit embedded divider erhältlich?"

von Uwe (Gast)


Lesenswert?

Eventuell kannst du ja fixed point Arithmetik benutzen. Die ist schnell 
und einfach

von KIT (Gast)


Lesenswert?

>Ich finde es eigentlich antiquiert, immer wieder Divisionsalgorithmen
>implementieren zu müssen

hallo Ratgeber ich will einfach dieses algorithmus verstehen, da ich es 
in eine andere sprache umsetzen will.

@ Darko danke es is natürlich so einfach das Ding. Aber was ist 
eingentilch mit dem hier gemeint:
1
 (r(b-2 downto 0)&dd(b-1))
Ist es genau die bit nummer b-2 bis 0 von Vektor r auf die Wert von 
dd(b-1) das vielleicht 0 oder 1 sein kann setzen?? oder bedeutet es was 
anderes??

von Unbekannter (Gast)


Lesenswert?

du solltest das mal simulieren. dann siehst du, was es macht.

dann baust du das ding in excel

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


Lesenswert?

KIT schrieb:
> Aber was ist eingentilch mit dem hier gemeint:
> r  <= r(b-2 downto 0)&dd(b-1);
Das ist eine Concatenation.
Hier wird einfach an die unteren Bits von r ein Bit aus dd angehängt, 
und das Ergebnis dann wieder an r zugewiesen.

In C könnte das so aussehen:
r = (r<<1) | ((dd>>(b-1))&0x1);

von Ratsucher (Gast)


Lesenswert?

Gibt es eigentlich noch andere grundlegende Divisionprinzipien?

Ich hatte mal ein Konzept realisiert, wo mit Multiplikation und 
Ausprobieren der richtige Wert gefunden wurde. Dahert aber im 
Extremmfall auch solange, wie man bits hat.

von A. S. (rava)


Lesenswert?

stimmt: wenn man x = Z/N berechnen möchte, kann man das auch als 
implizites Problem x*N - Z = 0 formulieren und den "Durchprobiervorgang" 
durch Tricks beschleunigen. Hat aber nix mit VHDL jetzt zu tun, da das 
prinzipbedingt sequenziell läuft.

Pseudocode:
1
int Z = 25000;
2
int N = 5;
3
int x = 1;
4
5
if(Z < N) return;
6
while(2*x*N - Z <= 0)
7
{
8
 x*=2;
9
}
10
while(x*N - Z < 0)
11
{
12
 x++;
13
}
14
return x;

das Spart "Ausprobierzeit", da erst grob gesucht wird und dann das 
Ergebnis verfeinert wird. Bei dem Beispiel ist noch nicht viel gewonnen, 
da x erst mal auf 8192 hochzählt und dann wieder runterläuft
Das kann man natürlich noch beliebig ausarbeiten (mehrere 
Zwischenstufen, negative Zahlen, Fließkomma, ...)

von Ratsucher (Gast)


Lesenswert?

Na so würde man das ja nicht machen. Man würde schon immer in die Mitte 
springen und dann halbieren. Ja nach grösser,oder kleiner die obere oder 
untere Hälfte anvisieren. Stichwort binäre Teilung.

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


Lesenswert?

A. S. schrieb:
> auch als implizites Problem x*N - Z = 0 formulieren
Bringt aber leider keinerlei Einsparung beim Ressourcenverbrauch und 
sicher keinen Geschwindigkeitszuwachs. Der Subtrahierer wird auch hier 
gebraucht. Und wenns kein Subtrahierer sein soll, dann ist ein 
Vergleicher nötig. Es ist also gegenüber der "Grundschullösung", wo ja 
nach der Subtraktion nur das Vorzeichen angeschaut wird, keine 
Verbesserung in Sicht.

von J. S. (engineer) Benutzerseite


Lesenswert?

So sieht es aus. Man kann nur mehr Tempo reinbringen, wenn man 
zusätzliche Resourcen einsetzt und parallel rechnet, z.B. über 
vorausschauende Annahmen und dann entscheidet, was nochmal weitere 
Resourcen und Zeit kostet!

Bei der eigentlichen "primitiven" Division in VHDL hat man ja noch den 
Vorteil, dass das jeweilige Hochmultiplizieren und Vergleichen auf 
größer und kleiner zu einem JA/NEIN - Fall degradiert, weil es ein 
einziges Bit ist. Sobald man das anders rechnet, z.B. im Vierersystem, 
wird es aufwändiger, aber kaum schneller. Für einen Vergleich eines 
Quadrupels z.B. braucht man immerhin 16 parallele Vergleiche oder (n 
über k)/2 = 6 geschachelte mit verketteter Kombinatorik (geschachtelte 
"IF"s), um 4 Bits gleichzeitig zu verarbeiten und damit 4 Takte zu 
gewinnen. Der anschließende Vergleich, welches Ergebnis nun stimmt 
(Annahmeneinfluss), verschlingt dann wieder einen Takt. Damit hätte man 
quais 4:2 übersetzt.

Die Rechenpipeline wäre halb so lang aber 6x/16x so breit. Das kommt 
wohl nur in Ausnahmefällen in Betracht.

Die beste Option in Sachen Geschwindigkeit ist eigentlich eine 
vollkombinatorische Lösung, die naturgemäß die minimalste Latenz 
liefert, die in der jeweiligen Technologie machbar ist und danach das 
parallele Instanziieren mehrerer Lines, um den Durchsatz zu schaffen. 
Alles andere sind wieder Optimierungen zu Gunsten des Durchsatzes/der 
Resourcen und zu Lasten der Latenz.

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.