www.mikrocontroller.net

Forum: FPGA, VHDL & Co. Frage zu Pipeline


Autor: Rene B. (themason) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe mal eine Theoriefrage.

Es geht sich um folgendes :

Ich habe mich mit Pipelines ein wenig beschäftigt und da habe ich mal 
eine Frage zu :

Beim klassischen Pipelining wird ja davon ausgegangen das pro Takt ein 
Befehl in die Pipeline geschubst wird.
Aber wenn ich nun externen Speicher habe den ich mit Steuersignalen (der 
Einfachheit halber CS, RW, OE, Adresse und Daten, also ein ganz 
ordinäres SRAM) fütter so brauche ich ja beim Umschalten zw. Read und 
Write (wenn ich beispielsweise ein STORE gemacht habe) mehrere Takte 
(ich muß ja das OE zurücknehmen, RW setzen, Daten & Adresse anlegen und 
warten). Hätte ich in dem Falle einen Pipeline Stall ?! Eigentlich ja 
schon oder ?
Der Extremfall, das man bei jedem Befehl zw. STORE und Fetch umschalten 
muß wird sicherlich nicht vorkommen, aber wäre in dem Falle die Pipeline 
dann nicht fürn Eimer, da ich ja jedesmal x-NOPs (Bubbles) einfügen muß 
um die Operation ausführen zu können.
Wie wird sowas im Normalfalle gelöst (abgesehen davon zu sagen : 
Verwende gefälligst Harvard bzw getrennte Daten/Adress/Steuerleitungen 
für Programm/Daten-Speicher) ?

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dazu hat man Caches eingeführt.

Prinzipiell ist eine Pipeline so schnell wie das langsamste Glied, d.h. 
wenn du immer auf den Speicher zugreifst müssen auch alle anderen 
Glieder die zig Takte abwarten bis es weiter geht. Man schiebt aber 
keine NOPs rein

Autor: Rene B. (themason) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@grotesk

Dann könnte man das im Prinzip ja auch so sagen/machen :

Wenn jeder Zugriff auf den Speicher meinetwegen 3 Takte dauert, wäre der 
Pipelinetakt ein Drittel meines Systemtakts (mit dem der Speicher 
angesprochen wird). Also quasi wie bei den alten 8051'ern die 12 Takte 
für einen Zyklus gebraucht haben. Das man im Prinzip einen "Vorteiler" 
(der dann über eine Statemachine beispielsweise die Leitungen zum SRAM 
hin zappeln lässt, um dann nach einer festen Zeit der Pipeline ein neues 
Datenwort zu fressen geben kann. Sehe ich das richtig ?

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ja

Autor: Rene B. (themason) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke schön für die Info.

Ich hoffe es ist ok wenn ich noch weitere Fragen stelle :-))

Und zwar hab ich mir beim TecChannel den Artikel über die 
RISC-Architektur durchgelesen (sehr Interessant und gut erklärt wie ich 
finde), und es stellt sich mir die Frage wie die (m.M. nach der 
Pferdefuß bzw. Haken an dem RISC-Prinzip mit jedem Takt einen Befehl neu 
in die Pipeline zu schubsen) Branch-Prediction bei kleineren Prozessoren 
realisiert ist. Z.B. AVR, Microblaze (gerade auf einem FPGA dürfte 
Branch-Prediction ja nicht ohne sein, wenn mans sich nicht gerade 
einfach macht), MSP usw.

Hintergrund des ganzen ist das ich immer noch "plane" mir mal eine CPU 
selbst zu bauen ;-P.
Im ersten Schritt ohne Pipelining, im zweiten mit.
Aber auch so ist es mal interessant zu wissen wie das funktioniert, bzw 
wie sowas konkret (auf die Eingangsfrage hin) aussehen kann.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Beim Microblaze/NiosII ist die Branchprediction im Datenblatt 
beschrieben. Der Microblaze nutzt hier aber eine andere Technik nennt 
sich Delayslots, hat also keine Prediction "drin".
Auch AVRs haben keine Prediction drin da sie keine Pipeline im 
klassichem Sinne besitzen.

Wenn du wirklich mal deine "eigene" CPU bauen möchtest gibt es da 
verschiedene "Lernvorlagen" angefangen beim Picoblaze (da gibt es ein 
PDF wie der entworfen wurde) über z.B. den DLX, in "Andrew S. Tanenbaum, 
Structured Computer Organization, Fourth Edition" ist der Bau einer 
Microcode basierten Architektur beschrieben und auch sehr gut wie dort 
Pipelinestufen eingefügt werden. Das hab ich mal begonnen in VHDL 
umzusetzen ist aber nicht ganz ohne.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das freut mich dass du gerade deine eigene CPU bauen willst.
Ich höre im Moment diese Vorlesung:

http://www3.informatik.uni-erlangen.de/Lehre/CPU/S...

Die Folien und Übungsblätter sind frei, d.h. rein theoretisch kannst du 
die zur Übung auch mitmachen ;)
Ziel ist eine gecachete, gepipelinede CPU mit ein paar Befehlen. (Wie 
aufwändig die CPU wird hängt unter anderem davon ab wie geschickt man 
die Befehle codiert)
Zur Branch Prediction gibts verschiedene Ansätze:

- Am einfachsten ist ein statischer Ansatz wie z.B.: rückwärts immer, 
vorwärts nimmer, also dass man bei Rückwertssprüngen (z.B. Schleifen) 
immer springt und sonst nicht

- ein dynamischer Ansatz, der normalerweise mit einer Branch Prediction 
Table realisiert wird. Dort merkt man sich für Sprungadressen ob man da 
schon in der Vergangenheit gesprungen ist oder nicht. Dies kann man nun 
mit 1 oder 2 bit kodieren und anhanddessen entscheiden (0/100% oder 
0/25/75/100) und nach einem Muster vorgehen (0->25->75->100, 
100->75->25->0, 0->75->100, 100->25->0), dies kann man noch 
weitertreiben in dem man sich Sprungmuster zu einer Adresse merkt z.B. 
0111011, dann ist es z.b. sehr wahrscheinlich dass man nächstes mal 
wieder springt und danach nicht (z.b. eine innere Schleife die 3 mal 
ausgeführt wird). Branch Prediction ist ein Thema welches man sehr 
auswälzen kann, weil man damit viel Perfomanz gewinnen und verlieren 
kann. Neben Branchprediction gibt es noch Konstrukte wie Delayslots, 
d.h. man füllt hinter den Sprung Befehle ein die so oder so hätten 
ausgeführt werden müssen, das ist dann Sache von Compiler und 
funktioniert nur bei kleinen Pipelines (4-5 Stufen) gut.

Autor: Rene B. (themason) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
@Läubi und Grotesk

Erstmal danke für die Antworten.
Das der AVR in dem Sinne kein Pipelining nutzt wusste ich nicht (hab 
mich bisher immer nur die Datenblätter mit den Registerbelegungen 
beschäftigt :-))
Beim Microblaze müsste ich mir das auch mal nachlesen, habe aber nicht 
vor mit dem Dingen was zu machen, da ich kein geld für das teure EDK 
ausgeben möchte. Picoblaze wiederrum wäre schon interessant zum lernen, 
aber da bin ich am VHDL-Code verzweifelt, weil der so dermaßen 
ultra-kompakt ist (und eben auf die Xilinxe optimiert ist) das ich 
hinter die einzelnen Blöcke nicht hintergestiegen bin. Also die 
einzelnen Blöcke waren bei der ersten durchsicht des Codes nicht so 
wirklich zu erkennen.
Aber nach der Entstehungsgeschichte des Picoblaze (und dessen genauen 
Aufbau) werd ich mal suchen.

@Grotessk

Erstmal vielen Dank für den Link. Sehr schön erklärt (wenn auch nur 
grob, aber mit dem Vorwissen aus dem TecChannel findet sich ja schon 
einiges wieder)

In dem Sinne hab ich mir ja schon ne CPU (wenn auch keine gepipelinte) 
gebaut. Allerdings hatte die nen SRBFOOSP-ISC (Super Reduced, But For 
Only One Purpose)-Instruction Set Computing Befehlssatz hat.
Ist im klassischen Sinne ein Prozessor aber gleichzeitig auch nicht. Es 
ist eher ein komfortabel zu programmierendes Rechenwerk.

Hatte vergessen zu erwähnen das Branch-Prediction ja nicht das einzige 
ist. Das hatte ich in dem Artikel auf dem TecChannel schon rausgelesen, 
aber ich denke ich würde es mir erstmal wirklich einfach machen, weil 
egal ob Delay-Slots, Branch-Prediciton oder was es da sonst noch gibt 
bräuchten meiner Meinung nach seehr viel Chip-Fläche, die beim FPGA ja 
begrenzt ist. Und um ein Erfolgserlebnis zu haben würde ich da erstmal 
weniger Performance in Kauf nehmen, als mir die Finger an der 
Branch-Problematik zu brechen.

Anbei mal mein Wenn geplanter Befehlssatz. (muß noch verbessert werden, 
erstmal nur die erste Fassung)
Ich habe vor eine 16Bit CPU zu bauen mit 16x16Bit General Purpose 
Register. Die meisten Befehle sind 2-Register-Befehle, und es wird noch 
wür zwischenergebnisse einen Akku geben mit dem sich die Ergebnisse (bei 
bedarf) wieder in die Register zurückschreiben lassen sollen.
Separater Akku deshalb weil ich beispielsweise bei einer Multiplikation 
von 2 16 Bit Werten ja 1 32 Bit Wert erhalte, und auch mit 32 Bit 
arbeiten können möchte (evtl bohr ich die Alu noch etwas auf um zum 
aktuellen Akkuinhalt noch weitere Operationen ausführen zu können 
(Feedback, Shifting usw).
Weiterhin soll das Teil bedingte Befehlsausführung haben und 
SW-Interrupts.
Na ja. Mal schauen. Erstmal ohne Pipelining und dann im zweiten Schritt 
redesignen mit Pipelining dann.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Rene Böllhoff schrieb:
> Aber nach der Entstehungsgeschichte des Picoblaze (und dessen genauen
> Aufbau) werd ich mal suchen.
http://www.dc.uba.ar/materias/disfpga/2010/c1/desc...
Gibt es vieleicht noch andere Versionen von.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Rene Böllhoff schrieb:

> Wenn jeder Zugriff auf den Speicher meinetwegen 3 Takte dauert, wäre der
> Pipelinetakt ein Drittel meines Systemtakts

Nur wenn ein Speicherzugriff unbedingt in einem Takt abgeschlossen 
werden muss. Weder bei externem noch bei interem Speicher (z.B. Cache) 
ist das selbstverständlich.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Läubi .. schrieb:

> Auch AVRs haben keine Prediction drin da sie keine Pipeline im
> klassichem Sinne besitzen.

Eine 2-stufige Pipeline, in der fetch und execute getrennt sind, ist
auch eine Pipeline. Nur eben eine kurze.

Es ist daher auch nicht richtig, allein Cores mit Sprungvorhersage eine 
Pipeline zuzugestehen. Es gibt allerdings einen Zusammenhang zwischen 
der Länge einer Pipeline, und der Notwendigkeit einer zunehmend 
präziseren Sprungvorhersage (wobei man eine nicht vorhandene Vorhersage 
gerne als Vorhersage "predicted not taken" einsortiert ;-).

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Rene Böllhoff schrieb:

> Beim klassischen Pipelining wird ja davon ausgegangen das pro Takt ein
> Befehl in die Pipeline geschubst wird.

Das bezieht sich auf den internen Zustand des Cores, nicht auf das 
Speicherinterface.

> Aber wenn ich nun externen Speicher habe den ich mit Steuersignalen (der
> Einfachheit halber CS, RW, OE, Adresse und Daten, also ein ganz
> ordinäres SRAM) fütter so brauche ich ja beim Umschalten zw. Read und
> Write

Wobei man Adresse und Daten nicht gleichzeitig aktivieren muss. Wenn man 
auf effizienten Betrieb mit externem Speicher Wert legt, dann kann es 
sich sehr wohl lohnen, die Phasen von Adresse und Daten zu trennen. D.h. 
die Adresse vom nachfolgenden Speicherzyklus wird bereits gegen Ende des 
laufenden Zyklus aktiv. Die Daten kommen später, wenn Schreibzugriff. 
Viel Umschaltzeit entsteht so nicht. Bei direkt angebundenem SRAM ohne 
Adresslatch mag das ungeeignet sein, bei anderen Speichertypen hingegen 
kann es den Speicher effizienter nutzen.

Im Extremfall bei komplexen Bus- und Speichersystemen sind die Request- 
und Reponse-Phasen der Speicherzugriffe weitgehend bis vollständig 
voneinander getrennt und es sind etliche solcher Zugriffe gleichzeitig 
am laufen. Erst bei solchen Interfaces ist das oben suggerierte Ziel, 
pro (Bus-)Taktzyklus einen Zugriff initiieren zu können, wieder in 
Reichweite.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Rene Böllhoff schrieb:

> Separater Akku deshalb weil ich beispielsweise bei einer Multiplikation
> von 2 16 Bit Werten ja 1 32 Bit Wert erhalte, und auch mit 32 Bit
> arbeiten können möchte

Sowas fand sich bei realen Architekturen häufiger, aber eher 
spezialisiert als MQ-Register für ebensolche Doppelwortoperationen wie 
Multiplikation und Division (daher das Q), ggf. auch manche 
Schiebeoperationen.

Als die Chipdesigner später anfingen, solche Operationen zu pipelinen 
(*), haben sie sich allerdings selbst in den Allerwertesten gebissen, 
denn dabei ist dieses Register doch sehr hinderlich ;-). Aber das wird 
dich sicherlich nicht stören.

*: Obacht, anderer Begriffskontext. Hier ist ein Multiplier gemeint, der 
zwar mehrere Takte braucht, aber pro Takt eine neue Operation 
akzeptiert.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Am einfachsten (hardwaremäßig) ist es komplett auf den Sprungkrempel zu 
verzichten und im Code entsprechend viele NOPs einzufügen (z.b. hinter 
jeden Sprung 3 NOPs, ist halt Pipelinelängen abhängig). Die Performanz 
ist dann zwar im Arsch aber man will ja auch nicht Intel toppen.

Das nächstschwierigere wäre die Pipeline zu stallen bis das Ergebnis 
bekannt ist.

Danach kommen Delay Slots

Und Königsklasse ist dann Prediction, wobei dynamisch nochmal haariger 
wie statisch ist

Autor: Rene B. (themason) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@A.K. und grotesque

Erstmal vielen Dank für die Hintergrundinfos.
Also ich mach mich erstmal an den Prozessor ohne Pipelining. Später 
foglt dann Pipelining, allerdings werd ich auf Branch prediction 
verzichten und NOPs einfügen. Je nachdem wie gut die Anweisungen 
sortiert sind dürfte sich ja schon ein Geschwindigkeitsvorteil ergeben.
Ich habe den Befehlssatz auch nochmal etwas überarbeitet und erweitert. 
Die meisten Befehle (bis auf 2 Kategorien) sind nun bedingt ausführbar.
Ich denke selbst ohne Pipelining bietet das genug Möglichkeiten zum 
"spielen". Vllt bekomme ich ja auch einen Hochsprachencompiler 
programmiert (am liebsten wär mir natürlich C :-))), aber erstmal 
abwarten.
Als erstes den Prozessor fertigstellen.
Da werde ich wahrscheinlich mit einem Prescaler arbeiten (2 oder 4) der 
in den Zwischentakten dann meine Speicher/ALU Operationen macht, sodass 
jeder Befehl eine konstante Zeit benötigt. Auf dieser Basis ist es vllt 
einfacher Pipelining zu realiseren.

Vielen Dank nochmal ...
... ich werde bestimmt noch Beizeiten nerven :-))

Was haltet ihr von dem Befehlssatz (vom ersten drübergucken mein ich) ? 
Bei Bedarf poste ich den neuen Befehlssatz auch mal.


>aber man will ja auch nicht Intel toppen.

Nicht ? Hatte ich eigentlich vorgehabt ... ööhmz ;-P

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

Bewertung
0 lesenswert
nicht lesenswert
>> aber man will ja auch nicht Intel toppen.
> Nicht ? Hatte ich eigentlich vorgehabt ... ööhmz ;-P
Probiers doch. Wenn du eine schöne neue Idee hast, wirst du entweder 
untergebuttert oder sie wird dir abgekauft oder erst das eine und dann 
das andere  ;-)

Autor: Rene B. (themason) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Probiers doch. Wenn du eine schöne neue Idee hast,

Leider nicht :-))
Aber vllt fällt sie mir ja aufm Klo ein ;-P, glaub aber eher nicht ...

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn man bedenkt was die Intelarchitektur eigentlich alles so für 
Schmutz betreibt die das Leben unnötig schwer machen wundert mich nix 
mehr :D Haben das wahrscheinlich zum Selbstzweck so gemacht

Autor: ein_unwissender (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hab mal was mit Branch prediction gemacht, das ist nicht ohne... vor 
allem gibts nicht DIE dynamische prediction, es gibt sehr viele Ansätze, 
ich schätze mal weniger als 10 Grundansätze und dann gibts für manche 
Ansätze zig Variationen...

Wie die Leute das bei Intel und AMD machen, das bleibt deren Geheimnis. 
Es gibt allerdings im Netz ein paar Infos und bei manchen älteren 
Prozessoren (Pentium I und Pro usw) wurde sogar herausgefunden wie sie 
funktioniert. Die heutigen sind da doch etwas komplexer.

Das größte Problem ist aber nicht der Algorithmus, den kann man sich 
nämlich noch einigermaßen selber überlegen wenn man ein paar Wochen Zeit 
reinsteckt. Das größte Problem ist imho die Cache-Anbindung bzw. die 
SRAM-Anbindung um die zur Prediction benötigten Tabellen zu lesen und zu 
schreiben. Auch ein Cache hat nämlich nie nur 1 Takt Zugriffszeit, vor 
allem wenn man sich im Bereich >>100 Mhz aufhält...

Ebenfalls bewundernswert ist die Pipeline bei Intel und AMD für 
Frequenzen bei 3GHz. Da bekommt man mit den gängigen modernen 
IC-Bibliotheken NICHTS mehr hin. Anscheinend haben die bei Intel extrem 
geniale Technologen was die Logikprozesse und Bibliotheken angeht!

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ein_unwissender schrieb:

>
> Ebenfalls bewundernswert ist die Pipeline bei Intel und AMD für
> Frequenzen bei 3GHz. Da bekommt man mit den gängigen modernen
> IC-Bibliotheken NICHTS mehr hin. Anscheinend haben die bei Intel extrem
> geniale Technologen was die Logikprozesse und Bibliotheken angeht!

Und das bei Pipelines mit ueber 20 Stufen, Out Of Order Execution, 
ALU-Splitting und dann noch CISC Befehle. In x86 steckt jeder Schmutz 
drin den man sich nur vorstellen kann, das ist wirklich uebel

Autor: Ein Zuschauer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
...wobei man da ja mal ein Einsehn hatte und die Pipelinelänge wieder 
etwas geschrumpft hat (seit P4 Zeiten)...

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.