mikrocontroller.net

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


Autor: Hans-Werner (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: A. F. (artur-f) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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...

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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
    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
brauchst du in einem FPGA kein Zwischenregister.
Das könntest du in einem FPGA einfach so beschreiben:
  process (clk) begin
     if rising_edge(clk) then
        if (exchange='1') then
           a(i)=a(j);
           a(j)=a(i);
        end if;
     end if;
  end process;
Hier dient das frei erfundene Signal "exchange" der Synchronisation mit 
der "aufrufenden" Statemachine.

Autor: rtz (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da hat man C und VHDl syntax vermischt...
...
if exchange = '1' then
   a(i)<=a(j);
   a(j)<=a(i);
end if;
...

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
rtz wrote:
> Da hat man C und VHDl syntax vermischt...
>
>
> ...
> if exchange = '1' then
>    a(i)<=a(j);
>    a(j)<=a(i);
> end if;
> ...
> 
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 ;-)

Autor: Klaus Falser (kfalser)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Hans-Werner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schönen Dank für alle Antworten.
Habe mich bisher nur an einzelnen Zustandsmaschinen versucht.
Siehe unten.
Das wird jetzt etwas grösseres.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity power is
  generic
  (
     -- Input and output size is 8 bit
    size : positive := 8
  );
  port
  (
    clock              : in   std_logic;
    base              : in   std_logic_vector(size-1 downto 0);
    exponent                : in   std_logic_vector(size-1 downto 0);
    result                  : out std_logic_vector(size-1 downto 0);
    enable                  : in  std_logic;
    ready                   : out std_logic;
    valid                   : out std_logic
  );    
end power;

-- The square & multiply algorithmus as a state machine
-- for calculation of a^b mod (2 ** m)
architecture power_rtl of power is
  -- The states for the state machine
  type states is (zero, first, second, third, forth);
  -- The state machine starts at the left state
  signal state     : states := zero;
  subtype long is natural range 2 ** size - 1 downto 0;

  signal res, exp         : long;
  signal res_temp, exp_temp   : long;
  subtype index is natural range size-1 downto 0;
  signal i             : index;
begin  
  

  square_and_multiply : process (clock)
  begin
     if rising_edge(clock)
    then   
      case state is
        -- The output is not valid, but the machine is ready
         when zero  =>  valid <= '0';
                  ready  <= '1';
                  if enable = '1'
                  then
                    ready <= '0';
                    state <= first;
                  end if;
        -- The machine is enabled and running
        when first =>  i   <= exponent'right;
                  res <= 1;
                  exp <= to_integer(unsigned(base));
                  state <= second;
        -- The machine is calculating inside a loop
        when second => if i <= exponent'left
                  then
                    if exponent(i) = '1'
                    then
                       -- It´s possible to eliminate mod here
                      res_temp <= (res * exp) mod 2**size;                    
                    else
                      res_temp <= res;
                    end if;
                    -- It´s possible to eliminate mod here
                    exp_temp <= (exp * exp) mod 2**size;                    
                  end if;
                  state <= third;
        -- Loop again or end the calculation ?
        when third =>  if i < exponent'left
                  then
                    res <= res_temp;
                    exp <= exp_temp;                    
                     i <= i + 1;
                    state <= second;
                  else
                    state <= forth;
                  end if;
        -- The result is valid and the machine goes back to wait state
        when forth =>   result <= std_logic_vector(to_unsigned(res,size));
                  ready <= '0';
                  valid <= '1';
                  state <= zero;
      end case;
    end if; -- rising_edge
  end process square_and_multiply;

end architecture power_rtl;

Autor: Hans-Werner (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Klaus Falser (Gast)
Datum:

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

Autor: daniel (Gast)
Datum:

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

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Hans-Werner (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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 ?

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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)
  process (clk) begin
     if rising_edge(clk) then
        a(i)<=a(j);
        a(j)<=a(i);
     end if;
  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:
   .-------------------------------------.
   |                                     |
   |     a(i)                  a(j)      |
   |   .-----.               .-----.     |
   '---|D   Q|---------------|D   Q|-----'
       |     |               |     |
     .-|>    |             .-|>    |
     | '-----'             | '-----'
     |                     |
  ---'---------------------'
Wenn sich die Zieladressen (i, j) ändern, dann bleibt der Ablauf selbst 
trotzdem parallel.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.