C in VHDL umsetzen

Gast #1023097 
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
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Langsamer Modus Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Melden Danke
Moderator (Firma: Titel) Persönliche Seite 
> 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.
Antwort Zitieren Bearbeiten Löschen Melden Danke
Moderator (Firma: Titel) Persönliche Seite 
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 ;-)
Antwort Zitieren Bearbeiten Löschen Melden Danke 
> 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
Antwort Zitieren Bearbeiten Löschen Melden Danke
Gast 
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;
Antwort Zitieren Bearbeiten Löschen Melden Danke
Gast 
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.
Antwort Zitieren Bearbeiten Löschen Melden Danke
Admin Persönliche Seite 
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?
Antwort Zitieren Bearbeiten Löschen Melden Danke
Gast 
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.
Antwort Zitieren Bearbeiten Löschen Melden Danke
Gast 
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 ?
Antwort Zitieren Bearbeiten Löschen Melden Danke
Moderator (Firma: Titel) Persönliche Seite 
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.
Antwort Zitieren Bearbeiten Löschen Melden Danke
Thread beobachten

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 18 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Dein Name und deine E-Mail-Adresse

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.