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;
}
// freigewordene 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
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...
> 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
privatevoidexchange(inti,intj)
2
{
3
intt=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
ifrising_edge(clk)then
3
if(exchange='1')then
4
a(i)=a(j);
5
a(j)=a(i);
6
endif;
7
endif;
8
endprocess;
Hier dient das frei erfundene Signal "exchange" der Synchronisation mit
der "aufrufenden" Statemachine.
rtz wrote:
> Da hat man C und VHDl syntax vermischt...>>
1
>...
2
>ifexchange='1'then
3
>a(i)<=a(j);
4
>a(j)<=a(i);
5
>endif;
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 ;-)
> 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
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.
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?
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.
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 ?
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
ifrising_edge(clk)then
3
a(i)<=a(j);
4
a(j)<=a(i);
5
endif;
6
endprocess;
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.