Forum: FPGA, VHDL & Co. C in VHDL umsetzen


von Hans-Werner (Gast)


Lesenswert?

Habe mir folgendes aus dem Internet (FH Flensburg) gefischt.
Mein Problem bei der Umsetzung in VHDL (Synthetisierbar) ist folgendes:
Wie modelliere ich die einzelnen Methoden bzw. Prozeduren/Funktionen ?
Da ich hier Zustandsmaschinen brauche muß ich entweder jede Methode in 
einen Prozess umsetzen oder für jede Methode eine eigene Entity 
definieren und in diesen dann die Prozesse umsetzen.
Bzw. anders gefragt, wie gehe ich mit der Parameteübergabe um ?
Das ganze ist rein iterativ und setzt auf einem Array auf, sollte also 
(mit viel Arbeit) umsetzbar sein. Es werden nur integer als Indizes 
verwendet also keine Pointer.


public class BottomupHeapSorter
{
    private int[] a;
    private int n;

    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        bottomupheapsort();
    }

    private void bottomupheapsort()
    {
        int x, u;
        buildheap();
        while (n>1)
        {
            n--;
            x=a[n];    // Markierung des letzten Blatts
            a[n]=a[0];
            u=holedownheap();
            upheap(u, x);
        }
    }

    private void buildheap()
    {
        for (int v=n/2-1; v>=0; v--)
            downheap (v);
    }

    private void downheap(int v)
    {
        int w=2*v+1;         // erster Nachfolger von v
        while (w<n)
        {
            if (w+1<n)       // gibt es einen zweiten Nachfolger?
                if (a[w+1]>a[w]) w++;
            // w ist der Nachfolger von v mit maximaler Markierung

            if (a[v]>=a[w]) return;  // v hat die Heap-Eigenschaft
            // sonst
            exchange(v, w);  // vertausche Markierungen von v und w
            v=w;             // fahre mit v=w fort
            w=2*v+1;
        }
    }

    private int holedownheap()
    {
        int v=0, w=2*v+1;

        while (w+1<n)     // zweiter Nachfolger existiert
        {
            if (a[w+1]>a[w]) w++;
            // w ist der Nachfolger von v mit maximaler Markierung
            a[v]=a[w];
            v=w; w=2*v+1;
        }

        if (w<n)    // einzelnes Blatt
        {
            a[v]=a[w];
            v=w;
        }
        // frei­gewordene Position ist an einem Blatt angekommen
        return v;
    }

    private void upheap(int v, int x)
    {
        int u;
        a[v]=x;
        while (v>0)
        {
            u=(v-1)/2;    // Vorgänger
            if (a[u]>=a[v]) return;
            // sonst
            exchange(u, v);
            v=u;
        }
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

}    // end class BottomupHeapSorter

von A. F. (artur-f) Benutzerseite


Lesenswert?

Und wo ist dein VHDL Code?
> wie gehe ich mit der Parameteübergabe um
in VHDL sind es Signale.

Keiner wird dir sagen, wie genau du das in VHDL umsetzt, denn dazu 
müssten wir wissen worum es geht. Mit dem Quellcode kann man nicht viel 
anfangen, wenn es nicht dokumentiert ist...

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


Lesenswert?

> Es werden nur integer als Indizes verwendet also keine Pointer
Indizierte Zugriffe auf "Irgendwas" sind Pointer-Zugriffe.
Sowas
>> int t=a[i];
ist das selbe wie
>> int t=*a+i;
und das ist ein Pointer.
Und das hier sowieso:
>> this.a=a;

Nachdem das geklärt ist, kommen wir zu deiner Aufgabe:
Dieses kleine C-Programm ist dafür vorgesehen, auf einer großen 
State-Machine (sagen wir mal Prozessor dazu) abzulaufen.
Du machst es am einfachsten auch so. Also mehrere SM, am einfachsten für 
jede Funktion eine. Die werden dann über jeweils ein Signal getriggert 
und melden zurück, wenn sie fertig sind. Das wird schnell zu 
implementieren sein, ist aber sicher nicht zeitoptimal. Denn es wird 
parallele Hardware implementiert, die meistens nur darauf wartet, dass 
eine andere SM mit irgendwas fertig ist... :-(

Zumindest für einen elementaren Tausch wie
1
    private void exchange(int i, int j)
2
    {
3
        int t=a[i];
4
        a[i]=a[j];
5
        a[j]=t;
6
    }
brauchst du in einem FPGA kein Zwischenregister.
Das könntest du in einem FPGA einfach so beschreiben:
1
  process (clk) begin
2
     if rising_edge(clk) then
3
        if (exchange='1') then
4
           a(i)=a(j);
5
           a(j)=a(i);
6
        end if;
7
     end if;
8
  end process;
Hier dient das frei erfundene Signal "exchange" der Synchronisation mit 
der "aufrufenden" Statemachine.

von rtz (Gast)


Lesenswert?

Da hat man C und VHDl syntax vermischt...
1
...
2
if exchange = '1' then
3
   a(i)<=a(j);
4
   a(j)<=a(i);
5
end if;
6
...

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


Lesenswert?

rtz wrote:
> Da hat man C und VHDl syntax vermischt...
>
>
1
> ...
2
> if exchange = '1' then
3
>    a(i)<=a(j);
4
>    a(j)<=a(i);
5
> end if;
6
> ...
7
>
Oh, schlags kaputt, die Signalzuweisungen wieder mal...
Aber das mit dem if() mache ich immer so (in beiden Sprachen).

Trotzdem glaube ich fest, dass das  Hans-Werner's kleinstes Problem sein 
wird ;-)

von Klaus F. (kfalser)


Lesenswert?

> Das ganze ist rein iterativ und setzt auf einem Array auf, sollte also
> (mit viel Arbeit) umsetzbar sein.
Wie kommst Du dazu?
Gerade iterative Algorithmen sind in Hardware schwierig umzusetzen. Auf 
einem Prozessor hat man einen Stack, von dem das Betriebssystem (fast) 
beliebig viel zur Verfügung stellt und der mit jeder Iterationsstufe 
wächst. Dadurch kann der Algorithmus fast beliebig viele Zustände 
zwischenspeichern und bei der Rückkehr von der Funktion weiterarbeiten.

Bei einem FPGA ist das nicht der Fall, dort sind die Resourcen fest 
vergeben. Im idealsten Fall kann man vielleicht über den Takt iterieren 
und das Ergebnis steht erst nach einer variablen Anzahl vom Taktzyklen 
fest, aber dazu muß man den Algorithmus so schreiben können, dass ein 
Abspeichern der Vorgeschichte nicht notwendig ist.

Klaus

von Hans-Werner (Gast)


Lesenswert?

Schönen Dank für alle Antworten.
Habe mich bisher nur an einzelnen Zustandsmaschinen versucht.
Siehe unten.
Das wird jetzt etwas grösseres.
1
library ieee;
2
use ieee.std_logic_1164.all;
3
use ieee.numeric_std.all;
4
5
entity power is
6
  generic
7
  (
8
     -- Input and output size is 8 bit
9
    size : positive := 8
10
  );
11
  port
12
  (
13
    clock              : in   std_logic;
14
    base              : in   std_logic_vector(size-1 downto 0);
15
    exponent                : in   std_logic_vector(size-1 downto 0);
16
    result                  : out std_logic_vector(size-1 downto 0);
17
    enable                  : in  std_logic;
18
    ready                   : out std_logic;
19
    valid                   : out std_logic
20
  );    
21
end power;
22
23
-- The square & multiply algorithmus as a state machine
24
-- for calculation of a^b mod (2 ** m)
25
architecture power_rtl of power is
26
  -- The states for the state machine
27
  type states is (zero, first, second, third, forth);
28
  -- The state machine starts at the left state
29
  signal state     : states := zero;
30
  subtype long is natural range 2 ** size - 1 downto 0;
31
32
  signal res, exp         : long;
33
  signal res_temp, exp_temp   : long;
34
  subtype index is natural range size-1 downto 0;
35
  signal i             : index;
36
begin  
37
  
38
39
  square_and_multiply : process (clock)
40
  begin
41
     if rising_edge(clock)
42
    then   
43
      case state is
44
        -- The output is not valid, but the machine is ready
45
         when zero  =>  valid <= '0';
46
                  ready  <= '1';
47
                  if enable = '1'
48
                  then
49
                    ready <= '0';
50
                    state <= first;
51
                  end if;
52
        -- The machine is enabled and running
53
        when first =>  i   <= exponent'right;
54
                  res <= 1;
55
                  exp <= to_integer(unsigned(base));
56
                  state <= second;
57
        -- The machine is calculating inside a loop
58
        when second => if i <= exponent'left
59
                  then
60
                    if exponent(i) = '1'
61
                    then
62
                       -- It´s possible to eliminate mod here
63
                      res_temp <= (res * exp) mod 2**size;                    
64
                    else
65
                      res_temp <= res;
66
                    end if;
67
                    -- It´s possible to eliminate mod here
68
                    exp_temp <= (exp * exp) mod 2**size;                    
69
                  end if;
70
                  state <= third;
71
        -- Loop again or end the calculation ?
72
        when third =>  if i < exponent'left
73
                  then
74
                    res <= res_temp;
75
                    exp <= exp_temp;                    
76
                     i <= i + 1;
77
                    state <= second;
78
                  else
79
                    state <= forth;
80
                  end if;
81
        -- The result is valid and the machine goes back to wait state
82
        when forth =>   result <= std_logic_vector(to_unsigned(res,size));
83
                  ready <= '0';
84
                  valid <= '1';
85
                  state <= zero;
86
      end case;
87
    end if; -- rising_edge
88
  end process square_and_multiply;
89
90
end architecture power_rtl;

von Hans-Werner (Gast)


Lesenswert?

Umgangssprachlich gesehen hast du recht.
Ein Index ist soetwas wie ein Pointer.
Aus Sicht der Programmierung bzw. Informatik ist es eher anders.
Ein Pointer ist eine Speicheradresse; ein Index ist ein ganzzahliger 
Wert aus dem durch Multiplikation mit dem Speicherplatz des 
entsprechenden Elementes (Je nach Datentyp) die Speicheradresse 
berechnet wird.

von Andreas S. (andreas) (Admin) Benutzerseite


Lesenswert?

Klaus Falser wrote:
>> Das ganze ist rein iterativ und setzt auf einem Array auf, sollte also
>> (mit viel Arbeit) umsetzbar sein.
> Wie kommst Du dazu?
> Gerade iterative Algorithmen sind in Hardware schwierig umzusetzen. Auf
> einem Prozessor hat man einen Stack, von dem das Betriebssystem (fast)
> beliebig viel zur Verfügung stellt und der mit jeder Iterationsstufe
> wächst. Dadurch kann der Algorithmus fast beliebig viele Zustände
> zwischenspeichern und bei der Rückkehr von der Funktion weiterarbeiten.

Verwechselst du da iterativ und rekursiv?

von Klaus Falser (Gast)


Lesenswert?

Ja, leider.
Manchmal scheint der Kopf nicht mehr ganz zu funktionieren.

von daniel (Gast)


Lesenswert?

gibt es denn irgendeine möglichkeit auch (nicht allzu ausartende)
rekursivität in einem fpga nachzubilden?

von Jörg (Gast)


Lesenswert?

Ja, gibt es: Du musst statt eines endlichen Automat einen Stack-Automat
verwenden. Im Prinzip funktioniert dieser wie der endl. Automat, ist
aber um zusätzliche Opertionen PUSH und POP (gepusht/gepopt werden
Zustand und evtl. weitere Werte) sowie einem Stack (z.B. internes RAM
bzw. BlockRam). Ist aber nicht so schwer zu implementieren, alledings
wegen der zusätzlichen Komponenten wesentlich aufwendiger, z.B. weil
ja auch ein Stack überlaufen kann.

von Hans-Werner (Gast)


Lesenswert?

Wieso kann a(i) = a(j) gefolgt von a(j) = a(i) funktionieren ?
Auch mit Zwischenvariable t sollte es nicht funktionieren.
Ich denke es wird alles in parallele Hardwarestrukturen umgesetzt, 
sofern ich keine Zustandsmaschine verwende.
Wieso kann ich also a(i) = a(j) und a(j) = a(i) parallel ausführen ?

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


Lesenswert?

Hans-Werner wrote:
> Wieso kann a(i) = a(j) gefolgt von a(j) = a(i) funktionieren ?
Ja, endlich.
Ich musste lange auf die Frage warten, aber sie kam noch ;-)
Hier folgt nichts, es wird gleichzeitig ausgeführt, das ist der Trick.

> Wieso kann ich also a(i) = a(j) und a(j) = a(i) parallel ausführen ?
In einem rudimentären FPGA gibt es nur FFs, Kombinatorik (in LUTs: Und, 
Oder, Nicht, Xor...) und Verdrahtung. Moderne FPGA-Designs haben als 
Gimmick noch fertige RAM-Blöcke, Multiplizierer, Prozessor-Cores, 
Kommunikations-Einheiten... mit drauf, die sind aber fest eingebaut und 
nicht programmierbar, sondern "nur" konfigurierbar.

Also, wir verwenden FFs um Zustände zu speichern. Und mit einem Takt 
wird in ein FF der neue Zustand, der vorher schon am Eingang anlang, 
eingetaktet. In der Beschreibung (zur Einfachheit ohne Enable)
1
  process (clk) begin
2
     if rising_edge(clk) then
3
        a(i)<=a(j);
4
        a(j)<=a(i);
5
     end if;
6
  end process;
ist ein Takt, mit dem die beteiligten FF die Daten am Eingang auf den 
Ausgang übernehmen. Also übernimmt a(i) den (jetzigen) Wert von a(j), 
und a(j) übernimmt zeitgleich den (jetzigen) Wert von a(i).

In der Praxis sähe das dann so aus, wenn z.B. i und j immer konstant 
wären:
1
   .-------------------------------------.
2
   |                                     |
3
   |     a(i)                  a(j)      |
4
   |   .-----.               .-----.     |
5
   '---|D   Q|---------------|D   Q|-----'
6
       |     |               |     |
7
     .-|>    |             .-|>    |
8
     | '-----'             | '-----'
9
     |                     |
10
  ---'---------------------'
Wenn sich die Zieladressen (i, j) ändern, dann bleibt der Ablauf selbst 
trotzdem parallel.

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.