Autor Thema: Eigene CPU  (Gelesen 68310 mal)

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #120 am: 04. January 2012, 03:48 »
Hallo,


für malloc/free ist nicht das OS zuständig sondern die libc innerhalb der Applikation, also Teil des User-Mode-Codes. Mit malloc/free wird der Heap benutzt und wie dieser intern verwaltet wird ist je nach Realisierung der libc ziemlich unterschiedlich. Da gibt es von ganz simplen verketteten Listen bis hin zu komplexen SLAB-Allocatoren eine ordentlich große Bandbreite ab Möglichkeiten. Letztlich bauen diese aber alle auf den normalen virtuellen Speicher auf den die Applikation vom OS bekommt, zumindest auf einem normalen Flat-Memory-System. In diesem Punkt unterschieden sich Windows und Linux (und auch alle anderen OSe in dieser Klasse) nur marginal von einander.

Was alle aktuellen OSe gemeinsam haben ist die Art mit der sie den virtuellen Speicher den Applikationen zur Verfügung stellen also das Paging, was eben der Grundstein des Flat-Memory-Konzepts darstellt. Paging ist zwar eine tolle Idee aber hat einen erheblichen Nachteil: es kostet bei jedem Speicherzugriff Performance. Das wird zwar mit Dingen wie dem TLB noch einigermaßen gut abgefangen aber spätestens wenn reale Programme mal wirklich ein paar TB an echtem Speicher benötigen und auch benutzen wollen dürfte das Konzept des TLB an seine Grenzen geraten sein und der Performanceverlust fürs Paging enorm werden. Deswegen möchte ich das mit Segmenten machen, die kosten deutlich weniger Performance und das ist auch nicht davon abhängig wie viele Segmente ein Programm insgesamt nutzt oder wie groß diese Segmente sind. Das einzigste was passen muss ist die Anzahl der Segment-Register (wovon x86 leider viel zu wenige hat so das dort Segmentierung nie wirklich zufriedenstellend war, nebst dessen das Segmentierung bei x86 auch nur schlecht im Befehlssatz integriert ist).

Für meine Heap-Implementierung, innerhalb der libc, will ich auch ein paar Segmente benutzen (die per Syscall vom OS geholt und verwaltet werden). Ich denke das ich es schaffe damit eine recht kleine innere Fragmentierung zu erreichen aber dafür habe ich das Risiko einer externen Fragmentierung also die einzelnen Segmente werden den physischen Speicher langsam fragmentieren (wie die Dateien auf einer Festplatte). Vor allem wenn die Speichernutzung sich langsam der Größe des physischen Speichers nähert wird das ein dringenderes Problem. Deswegen möchte ich die Möglichkeit haben für einzelne Segmente individuell Paging aktivieren zu können. Auf diese Art bleibt das Segment aus Sicht der Applikation intakt obwohl es über den physischen Speicher verstreut also fragmentiert ist. Das Paging ermöglicht es dann auch dieses Segment im Hintergrund, also ohne das die Applikation das merkt (vom Performanceverlust mal abgesehen), zu defragmentieren. Sobald das Defragmentieren der Segmente im physischen Speicher abgeschlossen ist kann das Paging wieder deaktiviert werden und die betreffende Applikation läuft wieder mit voller Performance.

Mir ist bewusst das ich mir damit einiges an Problemen aufhalse (z.B. was passiert wenn ein Segment vergrößert werden soll während es defragmentiert wird? gerade in einem SMP-System kann ja theoretisch beides gleichzeitig passieren) aber ich denke das sich das unterm Strich trotzdem lohnt. In den modernen Flat-Memory-OSen versucht man ja auch eine Art Defragmentierung einzubauen damit z.B. viele 4kB-Pages zu einer 2MB-Page zusammengefasst werden können, mit steigendem realen Speicherverbrauch der Applikationen wird das auch immer nötiger werden um den Performanceverlust durchs Paging in Grenzen zu halten.

Für mein System betrachte ich Paging nicht als Mittel gegen Fragmentierung, die wird bei meinen Segmenten zwangsläufig auftreten, sondern eher als Werkzeug um diese Fragmentierung wieder zu beheben. Auch fürs Swapping ist IMHO Paging die einzigst praktikable Lösung. Daneben eröffnet mir das Paging auch Dinge wie Memory-Mapped-File-IO aber das kommt erst sehr viel später dran. Im übrigen werden bei mir Segmente auch immer nur ganze Pages belegen und in jeder Page wird immer nur maximal ein Segment drin sein, so ähnlich wie ein Cluser bei FAT auch immer nur von einer Datei benutzt werden kann. Die Verwaltung des physischen Speichers in meinem OS wird also auch nur mit Pages arbeiten. Der wesentliche Unterschied zwischen Segmentierung und Paging ist der das für Segmentierung eine Basis und eine Größenangabe reicht um jedes Offset das innerhalb des Segments liegt in eine physische Adresse umrechnen zu können wogegen bei Paging riesige Tabellen erforderlich sind um eine virtuelle Adresse in eine physische Adresse umwandeln zu können.

In normalen Programmiersprachen, wie z.B. C, sind lokale Variablen (innerhalb von Funktionen) immer auf dem Stack und nicht auf dem Heap. Bei Java landet alles auf dem Heap, ist dort ein wesentlicher Aspekt des Gesamtkonzepts, und man kann als Programmierer auch nicht explizit zwischen Heap und Stack wählen aber bei vielen anderen Programmiersprachen wird zwischen Heap und Stack klar unterschieden und der Programmierer hat auch die Wahl was er benutzen möchte. Ich vermute Du solltest Dir einfach mal noch ein paar andere Dinge abseits von Java genauer ansehen um einen besseren Überblick über die vielfältigen Möglichkeiten zu bekommen.


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

kevin

  • Administrator
  • Beiträge: 2 767
    • Profil anzeigen
Gespeichert
« Antwort #121 am: 04. January 2012, 12:17 »
Was meinst du mit "schwer tun"? Und auf jeden Fall ist es in beiden Fällen nicht der Kernel, der sich damit schwertut, sondern höchstens die libc.
Thou shalt not follow the NULL pointer, for chaos and madness await thee at its end.

Dimension

  • Beiträge: 155
    • Profil anzeigen
Gespeichert
« Antwort #122 am: 04. January 2012, 15:58 »
Wenn ich mich richtig erinnere, weist libc Speicher ausschließlich im Vielfachen der Größe einer 4kb Page zu.

LittleFox

  • Beiträge: 306
    • Profil anzeigen
    • LF-Net.org
Gespeichert
« Antwort #123 am: 04. January 2012, 16:32 »
Hi,

nein, die LibC ruft beim Betriebssystem ganze Pages ab (bei x86 meistens 4K). Verwaltet wird der Speicher in der LibC Byte-genau - wenn dein Objekt nur 21 Byte groß ist, wird auch nur so viel benötigt.

Grüße,
LittleFox

FreakyPenguin

  • Administrator
  • Beiträge: 301
    • Profil anzeigen
    • toni.famkaufmann.info
Gespeichert
« Antwort #124 am: 04. January 2012, 17:37 »
Ich würde ja mal sagen das hängt sehr stark von der konkreten Implementierung von malloc() ab. Eine gescheites malloc() wird sicher nicht nur ganze Pages rausgeben, aber aufgrund von Verwaltungsdatenstrukturen und allfälligem Padding wird warscheinlich mehr als nur 21 Byte benötigt.

LittleFox

  • Beiträge: 306
    • Profil anzeigen
    • LF-Net.org
Gespeichert
« Antwort #125 am: 04. January 2012, 18:03 »
OK, bin jetzt vom Idealfall ausgegangen :D

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #126 am: 04. January 2012, 18:58 »
Hallo,


OK, bin jetzt vom Idealfall ausgegangen :D
Auch dann wird für ein Objekt mit 21 Bytes sicher mehr als das benötigt, also Verwaltungsinformationen kommen in jedem Fall dazu.

Ansonsten fällt mir gerade ein das bei CPUs die keine unausgerichteten Speicherzugriffe unterstützen, was auf fast alle außer x86 zutrifft, der Pointer der von malloc kommt eigentlich zwangsläufig mindestens auf den größten nativ von der CPU unterstützten Datentyp ausgerichtet sein muss da ansonsten der Compiler gar keinen validen Code erzeugen kann. In einer Struktur werden auf solchen CPUs auch alle Member auf ihre Größe entsprechend ausgerichtet. Aber für x86 ist es auf jeden Fall möglich (wenn auch unperformant) komplett ohne Alignment und Padding auszukommen.


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

Sannaj

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #127 am: 11. January 2012, 18:36 »
Naja ich hab mir auch mal Gedanken bezüglich einer CPU (eigentlich mehrerer CPU's) gemacht. Zwar hab ich kein vollständiges Konzept entwickelt, aber folgende Ideen will ich dann dennoch der Allgemeinheit mitteilen.
Dabei habe ich mich hauptsächlich mit einem Problem beschäftigt, das bei RISC CPU's auftritt, nämlich die Befehlslänge.
Bei einer RISC Architektur stößt man immer auf folgende Probleme:
Wählt man die auf 32bit RISC Maschinen übliche Befehlslänge gleich der Wortlänge ist sie zu kurz um Konstanten und Adressen aller Art ohne großen Aufwand vernünftig laden zu können. (Auch wenn die z.B. bei ARM vorgestellten Möglichkeiten schon gut sind.) Würde man eine länger Befehlslänge nehmen (z.B. 64 bit) verschwendet man Speicher und braucht einen breiteren Bus oder doppelte Ladezyklen. Bei einer kürzeren Wortlänge (z.B. 16 bit) passt der Befehl selber, kaum in den Opcode.
Auf 64 Bit Architekturen verschärft sich das Problem. Verwendet man weiterhin 32 bit Befehlslänge kann der Befehl relativ gesehen nur halb so viele unmittelbare Informationen auf nehmen wie auf einem 32 bit Prozessor. Wält man eine Befehlslänge von 64 bit verbraucht das Programm unverhältnismäßig viel Arbeitsspeicher.
Analysiert man den Befehlssatz, erkennt man das es Befehle gibt, die mit wenig Speicher auskommen (Arithmetik, Flags setzten, Stack) und solche, die viel mehr Speicher brauchen.
Natürlich könnte man hingehen und grundsätzlich mit Variablen Befehlslängen arbeiten, aber das wäre nicht so Praktisch. Also habe ich versucht, nur mit Befehlen einfacher und doppelter Länge (32bit/64bit) zu arbeiten, ohne das Design zu sehr zu beeinträchtigen:

Möglichkeit 1:
In bestimmte Abständen, wird anstelle eines Befehls ein Datenwort geladen, das in einem speziellen Konstantenregister gespeichert wird, das man dann ganz normal auslesen und für seine Berechnungen verwenden kann. Der Prozessorbus wurde so erweitert, das er die Konstante mitläd. Die Informationen werden dann intern gepuffert. (z.B. sind die Befehle jeweils 32 bit lang und nach zwei Befehlen folgt ein 64 bit langes Datenwort. Der Prozessor besitzt einen 64 bit Bus, sodass er für jeden bearbeiteten Befehl 64 Bit einlesen kann.
Bei Befehlszyklus 1 ließt der Fetcher beide Befehle ein und gibt den 1. an den Dekoder und schreibt den 2. in den Puffer. Beim Befehlszyklus 2 liest der Fetcher das Datenwort in das Konstantenregister ein und übergibt den gepufferten Befehl an den Dekoder.

Möglichkeit 2:
Alle Befehlswörter haben doppelte Länge. Alle zwei Befehlszyklen ließt der Prozessor ein Befehlswort ein. An einem Steuerbit kann der Predekoder nun erkennen, ob es sich um einen langen Befehl, oder um zwei kurze Befehl handelt. Die interne Pipe hat immer eine größere Länge (z.B. 65 bit). Bei zwei kurzen Befehle werden diese auf Pipelange vergrößert und nacheinander in die Pipe geschoben. Bei einem langen Befehl, wird dieser gefolgt von einem "nop" Wort auf die Pipe geschoben.

Möglichkeit 3 (Die ich am besten finde):
Alle Befehlswörter haben einfache Länge. Es gibt aber ein Psydoregister, "Next Instruction Register" (nir), mit dem man den nächsten Befehl auf der Pipe ansprechen kann (oder den übernächsten Befehl). Der Lesezugriff erfolgt destruktiv, d.h. der Befehl wird beim lesen durch "nop" ersetzt, oder entsprechend markiert (das geht beim übernächsten Befehl einfacher, weil dieser noch nicht dekodiert wurde.) Der Schreibzugriff ist auch möglich wenn man dadurch den übernächsten Befehl anspricht, wodurch man eine Art selbst modifizierenden Code bauen kann.

Darüber hinaus bin ich dafür, Operatorlastige Befehle zu trennen, z.B favorisiere ich anstatt von konditionalen SprungBefehlen oder Bedingungspräfixe, lieber eine Kombination aus unbedingten Sprungbefehlen und einer "skipp next instruktion if <condition>" - Anweisung.

Eine Weiter Idee, die ich hatte, ist mal eine Stack basierende Architektur zu bauen oder eine Möglichkeit zu finden Registersicherung zu sparen. (Z. B. für einen eigenen Registersatz für den Taskshedule.)

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #128 am: 13. January 2012, 21:59 »
Hallo,


Dabei habe ich mich hauptsächlich mit einem Problem beschäftigt, das bei RISC CPU's auftritt, nämlich die Befehlslänge.
Ja, das ist wohl wahr. Aber es gibt auch interessante Lösungen dafür, schau Dir mal den Itanium an. Auch das Problem mit der bedingten Ausführung ist dort auf sehr interessante Art und Weise gelöst.
(eigentlich könnte hier meine Antwort schon zu Ende sein aber ich hoffe man nimmt es mir bei diesem Thema nicht übel wenn ich das doch mit ein paar Buchstaben mehr erkläre)
Der Itanium benutzt 128 Bit große Befehls-Pakete und in jedem Paket sind 3 Befehle a 41 Bit (die restlichen 5 Bit dienen wimre der Verwaltung der Abhängigkeiten des aktuellen Pakets zu den vorhergehenden Paketen, das muss der Compiler einfügen damit Intel den Decoder etwas einfacher bauen kann) und jeder dieser Befehle kann bedingt ausgeführt werden. Einer dieser 3 Befehle (wimre nur der erste) kann ein Load-Immediate sein der volle 64 Bit in ein beliebiges Register lädt und der benutzt dann einfach den folgenden Befehl mit für die Daten und dieser folgende Befehl ist dann zwangsläufig ein NOP (ob das der Decoder so richtet oder ob das schon so drin sein muss weiß ich jetzt gar nicht mehr genau). Durch diese Pakete kann der Itanium immer 3 Befehle pro Takt decodieren und auch ausführen (eigentlich immer 6 weil alle real existierenden Itaniums immer gleich 2 Pakete pro Takt laden) und die 41 Bit bieten auch für alles wichtige ausreichend Platz (obwohl pro Operand 7 Bit benötigt werden da der Itanium 128 Register hat). Der Nachteil ist natürlich das der Code sehr groß ist (weswegen die Itaniums auch sehr riesige und teure Caches haben) und da die 3 Befehle in einem Paket immer gleichzeitig ausgeführt werden dürfen diese auch nicht von einander abhängig sein was den Compiler schon mal vor ziemliche Schwierigkeiten stellen kann (oft müssen dann nicht belegbare Plätze in den Paketen mit NOPs aufgefüllt werden so das die eh schon schlechte Befehlsdichte noch mehr leidet). Das Ergebnis spricht aber für sich, die Itaniums waren die schnellsten CPUs ihrer Zeit, vor allem in Relation zu ihrer gemächlichen Taktfrequenz. Zumindest für wissenschaftliche/mathematische Programme sind die Itaniums eigentlich eine perfekte Wahl, nur leider waren sie immer viel zu teuer und auch viel zu durstig.

(Auch wenn die z.B. bei ARM vorgestellten Möglichkeiten schon gut sind.)
Ja, der Weg von ARM ist interessant aber er hat auch einen eklatanten Nachteil, er erfordert das der Code immer auch lesbar ist (es werden ja ganz normale Speicherzugriffe nur eben mit IP-relativer Adressierung benutzt). Aus Gründen der Sicherheit ist es aber besser wenn Code nicht lesbar sondern nur ausführbar ist.

Ansonsten gibt es für Deine Version mit den 32Bit Befehlen noch eine Möglichkeit 4:
Um ein NOP zu kodieren sollten nicht mehr als 8 Bit nötig sein so das in jedem NOP immer 24 Bit an Daten enthalten sein können. Wenn Du nun einen Load-Immediate-Befehl baust der selber noch 16 Bits Daten enthält (die restlichen 16 Bits sollten doch reichen um den Befehl ansich und das Zielregister zu kodieren) dann könnte der im Decoder um 2 Takte verzögert werden (es käme eben für 2 Takte kein Befehl aus dem Decoder raus) und der Decoder würde intern aus diesem Befehl und den 2 folgenden NOPs insgesamt einen Load-Immediate mit vollen 64Bit Nutzdaten bauen. (wenn einer der beiden folgenden Befehle kein NOP ist gibt es eben eine Illegal-OpCode-Exception) Das hätte auch den Vorteil das nichts schlimmes passiert wenn mal einer der beiden Daten-NOPs angesprungen wird und auch der Disassembler (im Debugger) hätte keine Probleme was sinnvolles anzuzeigen. Ein weiterer Vorteil ist das diese Variante allein im Decoder passiert und Dein eigentlicher CPU-Kern davon nicht betroffen ist, spätestens wenn Du irgendwann doch mal das simple In-Order-Pipeline-Konzept verlassen möchtest wird es Dir sehr entgegen kommen Dich im CPU-Kern auf die eigentliche Arbeit konzentrieren zu können.


Das mit dem Skip-Befehl ist keine so schlechte Idee aber auch hier solltest Du das gleich im Decoder lösen und dem CPU-Kern nur Befehle übergeben bei denen die Ausführungsbedingung integraler Bestandteil ist. Es sollte auch möglich sein das sich dieses Condition-Präfix mit jedem Befehl kombinieren lässt, damit lassen sich wieder viele Sprünge vermeiden und das bringt einiges an Performance und spart oft auch Code. Im klassischen ARM-Befehlssatz ist auch jeder Befehl bedingt ausführbar aber das kostet bei ARM in jedem Befehl 4 Bit so das die ARM-Befehle nur 28 Bit wirklich zur Verfügung haben und das ist, trotz dessen das die Operanden nur 4 Bit benötigen, schon ziemlich knapp. Falls Du fürchtest mit nur einem Flag-Set irgendwann an Performance-Probleme zu stoßen, und das ist bei so einem Single-Point-of-Dependency sehr wahrscheinlich, solltest Du Dir mal anschauen wie das bei Alpha gelöst ist. Die haben zwar nur bedingte Sprünge (alle anderen Befehle werden immer unbedingt ausgeführt) aber dafür kann Alpha direkt ein beliebiges Register auf bestimmte Eigenschaften prüfen, z.B. == 0 oder != 0, und da es mehrere Register gibt kann zwischen dem Befehl der eine Bedingung ermittelt und dem zugehörigen bedingten Sprung-Befehl noch beliebiger anderer Code stehen solange der das eine bestimmte Register nicht verändert. Das sorgt dafür das der bedingte Sprung nicht erst warten muss bis der unmittelbar vorangegangene Test-Befehl durch die Pipeline gekommen ist sondern weil das eben oft schon einige Befehle her ist gibt es weniger Pipeline-Stalls.


Auch ich habe mir über die beiden Punkte (Befehlsgröße und bedingte Ausführung) einige Gedanken gemacht und (wie ich meine) auch ein paar interessante Lösungsmöglichkeiten gefunden, das ist ganz am Anfang dieses Threads recht gut beschrieben.


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

Sannaj

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #129 am: 14. January 2012, 17:29 »
Hallo,


Dabei habe ich mich hauptsächlich mit einem Problem beschäftigt, das bei RISC CPU's auftritt, nämlich die Befehlslänge.
Ja, das ist wohl wahr. Aber es gibt auch interessante Lösungen dafür, schau Dir mal den Itanium an. Auch das Problem mit der bedingten Ausführung ist dort auf sehr interessante Art und Weise gelöst.
(eigentlich könnte hier meine Antwort schon zu Ende sein aber ich hoffe man nimmt es mir bei diesem Thema nicht übel wenn ich das doch mit ein paar Buchstaben mehr erkläre)[...]
Naja, ganz grob entspricht das meiner Möglickeit 2. Allerdings halte ich so einen Itanium-Befehlssatz für überflüssig, weil diese Art von Parallelität nur selten vorkommt (entweder will man SIMD oder MISD.) Für SIMD ist der Befehlssatz zu mächig und damit zu teuer (Man nutzt die Möglichkeiten nicht richtig aus). MISD lässt sich, da Abhängigkeiten zwischen den Paralellbefehlen verbotenen sind, nicht schnelle als bei einem konservativen Befehlssatz lösen. (Ein MISD Prozessor wäre auch mal interessant.)
Zitat

(Auch wenn die z.B. bei ARM vorgestellten Möglichkeiten schon gut sind.)
Ja, der Weg von ARM ist interessant aber er hat auch einen eklatanten Nachteil, er erfordert das der Code immer auch lesbar ist (es werden ja ganz normale Speicherzugriffe nur eben mit IP-relativer Adressierung benutzt). Aus Gründen der Sicherheit ist es aber besser wenn Code nicht lesbar sondern nur ausführbar ist.

Ansonsten gibt es für Deine Version mit den 32Bit Befehlen noch eine Möglichkeit 4:
Um ein NOP zu kodieren sollten nicht mehr als 8 Bit nötig sein so das in jedem NOP immer 24 Bit an Daten enthalten sein können. Wenn Du nun einen Load-Immediate-Befehl baust der selber noch 16 Bits Daten enthält (die restlichen 16 Bits sollten doch reichen um den Befehl ansich und das Zielregister zu kodieren) dann könnte der im Decoder um 2 Takte verzögert werden (es käme eben für 2 Takte kein Befehl aus dem Decoder raus) und der Decoder würde intern aus diesem Befehl und den 2 folgenden NOPs insgesamt einen Load-Immediate mit vollen 64Bit Nutzdaten bauen. (wenn einer der beiden folgenden Befehle kein NOP ist gibt es eben eine Illegal-OpCode-Exception) Das hätte auch den Vorteil das nichts schlimmes passiert wenn mal einer der beiden Daten-NOPs angesprungen wird und auch der Disassembler (im Debugger) hätte keine Probleme was sinnvolles anzuzeigen. Ein weiterer Vorteil ist das diese Variante allein im Decoder passiert und Dein eigentlicher CPU-Kern davon nicht betroffen ist, spätestens wenn Du irgendwann doch mal das simple In-Order-Pipeline-Konzept verlassen möchtest wird es Dir sehr entgegen kommen Dich im CPU-Kern auf die eigentliche Arbeit konzentrieren zu können.
Das Problem ist, das man dadurch einen großen Teil des möglichen Befehlssatzes blockiert. Bisher hab ich mich außerdem nie mit Befehlen die mit doppelter Datenabhängigkeit funktionieren beschäftigt. Die von dir beschriebene Möglichkeit hatte ich auch schon mal, da sie z.B. bei ARM schon vorbereitet wurde. Die never Kondition entspricht quasi deinem nop. Ein weiterer Nachteil deines Vorschlags ist, das man spezielle Befehle hierfür benötigt. Möglichkeit 3 zeichnete sich ja gerade dadurch aus, das man die Immideate wie ein Register nutzten konnte, weil die Daten allein über einen Registerzugriff aktiviert werden. Bei Dissassemblen hab ich eigentlich keine Schwierigkeiten. Der Dissassembler dekodiert dann halt so was wie add r1, r2, nir(0xABCDEF01) und setzt den abhängigen Befehl in Klammern, oder so.
Zitat
Das mit dem Skip-Befehl ist keine so schlechte Idee aber auch hier solltest Du das gleich im Decoder lösen und dem CPU-Kern nur Befehle übergeben bei denen die Ausführungsbedingung integraler Bestandteil ist. Es sollte auch möglich sein das sich dieses Condition-Präfix mit jedem Befehl kombinieren lässt, damit lassen sich wieder viele Sprünge vermeiden und das bringt einiges an Performance und spart oft auch Code. [...]
Das mit der universellen Zuordnung hatte ich eh so vorgesehen (es hieß ja nicht skip next branch). Überhaupt hab ich mir überlegt, ob ich nicht zwei Dekodierstufen einfügen soll. Das macht die Sache einfacher.
Zitat
... solltest Du Dir mal anschauen wie das bei Alpha gelöst ist.[...]
Die Alpha Methode wäre natürlich auch ne Möglichkeit, allerdings ist die Nutzung eines beliebigen Register natürlich mit viel notwendiger Information verbunden. Dafür ist diese Möglichkeit ziemlich nah an dem System, das auch viele Programmiersprachen anwenden. (von FreeBasic weiß ich, das ein if ausgeführt wir, wenn der Ausdruck ungleich null ist. In C ist es glaub ich genauso.)

Grundsätzlich gibt es drei Konditionsmöglichkeiten.
A) Keine Konditionellen Befehle außer bei Sprüngen. Pro. Keinen Speicherbedarf im Opcode  Kontra: Piplineunfreundlich
B) ARM-artige Konditionen: Pro: mächtig Kontra: Wenig Erweiterungsmöglichkeiten, Koste viel Speicher im Opcode
C) Alpha-artige Konditionen: Pro: Flexible Konditionsverwaltung Kontra: Externen Vergleichsoperatoren nötig. Koste viel Speicher im Opcode und Register
D) if TRUE Flag set Kondition: Pro: Wenig Speicher im Opcode Kontra: Externe Unterstützung nötig.

Ich persönlich könnte mir also eine Möglichkeit vorstellen, bei der der einzelne Befehl keine Kondition trägt. Sprünge hätten dann sowas wie eine erweiterte Alpha-artige Kondition und Skip-Präfixe ein leistungsfähiges Konditionssystem.

Darüber hinaus gibt es natürlich noch Möglichkeiten, den Aufbau zu erweitern, indem man konditionelle Sprungbefehle oder Befehlspräfixe einführt.
Zitat
Auch ich habe mir über die beiden Punkte (Befehlsgröße und bedingte Ausführung) einige Gedanken gemacht und (wie ich meine) auch ein paar interessante Lösungsmöglichkeiten gefunden, das ist ganz am Anfang dieses Threads recht gut beschrieben.
Du weißt aber schon, das du den Decoder damit ziemlich auf blähst, da du eigentlich 3 Instructionsets verwendest. Ich würde den Dekoder in verschiedene Teile aufteilen. Du brauchtest also 1 Meta-Decoder (Trennt das Pakete auf) + 2 60bit-Decoder + 3 42bit-Decoder (39bit+3bit Condition) + 6 20bit Decoder = 12 Teildecoder. Da eigentlich alle Teildecoder das gleiche machen, hättest du ziemlich viele Einzellschaltungen. (zum Vergleich ARM brauch für seine Schaltung nur ein ARM und einen Thumb decoder.) Ich würde mir deshalb überlegen, ob du nicht die kurze Befehle auf den langen Abbilden kannst, z.B. indem du konstante Bits einfügst. Außdem würde ich mich fragen, ob du wirklich 6 20bit Anweisungen simultan ausführen musst, oder ob es reicht, immer nur 3 Befehle gleichzeitig zu bearbeiten und die Pipline entsprechend zu modifizieren, oder die Piplinegeschwindigkeit zu halbieren.

Darüber hinaus sollte dir klar sein, das es schwierig ist für einen VLIW Befehlssatz Code zu schreiben, weil das Design nicht der traditionellen Logik entspricht, weshalb das Compiler Backend ziemlich kompliziert wird. Assemblerprogrammierung für eine solche Plattform ist sogar noch schwieriger. Auch die interne Logik wird aufgebläht, weil viele Baugruppen mehrfach auftreten. Von der Theorie her, mag solch ein Befehlssatz ja interessant sein, in der Praxis implementiert man aber lieber SIMD Instruktionen.

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #130 am: 15. January 2012, 12:14 »
Hallo,


eines vorweg: in meiner CPU gibt es kein EPIC. Das empfinde ich persönlich als fürchterliche Fehlentscheidung von Intel, auch wenn es objektiv dafür wohl keinen Grund gibt da die Itaniums ja durchaus recht schnell sind. In kleinen DSPs mit internem RAM macht EPIC eventuell noch Sinn da hier alle Befehle, auch die Speicherzugriffe, mit kurzer und bekannter Latenz auskommen aber für eine General-Purpose-CPU, wo einzelne Befehle auch mal unvorhersehbar lange dauern können, ist EPIC meiner persönlichen Meinung nach absolut fehl am Platz. Hier ist Out-of-Order-Execution deutlich sinnvoller. Weil im Itanium angestrebt wird das jedes Befehls-Paket für seine Ausführung in der Pipeline immer nur einen Takt benötigt sind da einige ziemlich krasse Design-Entscheidungen getroffen wurden. Es gibt da z.B. keine klassischen Multi-Takt-Befehle wie die Division (bei Integer und Floating-Point) oder überhaupt komplexe mathematische Befehle (die müssen alle händisch vom Compiler gebaut werden), dafür gibt es jeweils spezielle Befehle die die einzelnen Iterationsschritte der benötigten Algorithmen (die normalerweise eine HW-State-Maschine selbstständig erledigt) anbieten und der Compiler muss dann damit zurecht kommen. Der Itanium arbeitet rein In-Order mit einer ziemlich kurzen Pipeline, von daher würde er auch alles blockieren wenn er Befehle hätte die mehrere Takte brauchen. Bei der Division verkauft Intel das sogar als Vorteil weil der Compiler bei der Zusammenstellung der händischen Division zwischen möglichst kurzer Latenz für eine Division und möglichst hohem Durchsatz für viele Divisionen wählen kann. Ja, das ist durchaus ein nettes Feature aber es macht den Compiler ziemlich komplex und langsam und es gibt auch etliche Situationen wo der Compiler diese Entscheidung gar nicht wirklich treffen kann weil er einfach nicht weiß wie sich das Gesamtsystem zur Laufzeit verhält. Bei den Speicherzugriffen arbeitet der Itanium exzessiv mit Prefetch-Befehlen die der Compiler passend einflechten muss, damit wird dem Cache-Controller schon mal mitgeteilt was als nächstes benötigt wird so das schon mal vorgesorgt werden kann damit dann wenn der eigentliche Speicherzugriff passiert dieser auch in möglichst einem Takt direkt vom Cache bedient werden kann. Das Problem ist dass das nicht immer gut funktioniert (es gibt ja z.B. auch Speicherbereiche die gar nicht cachebar sind wie HW-MMIO oder Algorithmen deren als nächstes benötigten Daten nicht so einfach vorhersehbar sind) und der Cache-Controller dadurch auch ziemlich komplex wird da er mit vielen parallelen Prefetch-Jobs umgehen können muss.
Alles in allem muss man sagen das Intel mit dem Itanium eine absolut einzigartige CPU geschaffen hat, etwas wirklich vergleichbares gibt es meines Wissens nach nicht auf diesem Planeten. Das trotz all der potentiellen Schwierigkeiten, die bei allen anderen EPIC-Designs auch voll zuschlagen oder auf Grund bestimmter Randbedingen nicht auftreten die dann aber keine General-Purpose-CPU mehr sind, eine so leistungsfähige CPU bei raus gekommen ist bleibt allein eine Leistung der guten Ingeniöre bei Intel die eben für jedes dieser Probleme eine gute Lösung gefunden haben. Unterm Strich ist damit der Itanium zwar extrem leistungsfähig aber die vielen Extras die Intel braucht um das auch tatsächlich mit EPIC zu schaffen machen den Itanium einfach unwirtschaftlich. Ich hab selber einige Zeit überlegt ob man mit diesem Konzept was ansprechendes erreichen kann bin aber zu dem Schluss gelangt das ich lieber auf eine klassische Out-of-Order-Execution einer seriellen Befehlsfolge setzen möchte. Deswegen benutze ich zwar eine Art VLIW-Kodierung, um eine möglichst hohe Code-Dichte bei trotzdem sehr leistungsfähigen Befehlen zu erreichen, aber jeder Befehl ist für sich eigenständig und wird, aus Sicht des Programmierers/Compilers, seriell abgearbeitet. Trotzdem sollen die Abhängigkeiten zwischen den Befehlen natürlich möglichst klein sein (was bei 60 frei nutzbaren Registern und 4 unabhängigen Flag-Sets auch kein so großes Problem sein sollte) damit der CPU-Kern bei der Befehlsausführung ein möglichst hohes Maß an Instruction-Level-Parallelism schafft und eben auch ein Out-of-Order-Commit der Befehle kein Problem darstellt. Mein Decoder wird mit Sicherheit sehr viel Logik im FPGA belegen, vermutlich mehr als alle ALUs der Verarbeitungspipeline zusammen, aber er wird einen seriellen Strom an (einheitlichen) Befehlen liefern und man wird es den einzelnen Befehlen dann nicht mehr ansehen ob sie mit 20 Bit, 39 Bit oder 60 Bit codiert waren. Ich möchte es erreichen das der Decoder pro Takt 2 bis 6 dekodierte Befehle liefern kann (eben ein komplettes Paket) um für die eigentliche Verarbeitung immer genügend Nachschub zu liefern.


Das Problem ist, das man dadurch einen großen Teil des möglichen Befehlssatzes blockiert.
Hä, was meinst Du? Denkst Du das ein NOP mit nur 8 Bits zu kodieren Verschwendung ist?

Möglichkeit 3 zeichnete sich ja gerade dadurch aus, das man die Immideate wie ein Register nutzten konnte, weil die Daten allein über einen Registerzugriff aktiviert werden.
Ja, aber wenn Du das erst bei der tatsächlichen Ausführung der Befehle machst verhinderst Du damit effektiv jegliche Form von Instruction-Level-Parallelism weil Du den (über)nächsten Befehl erst dann dekodieren kannst wenn der aktuelle Befehl abgearbeitet wird. Ich kann Dir nur dringlichst empfehlen zu versuchen dafür eine Lösung zu finden die nur im Decoder alleine passiert damit Du Dir später nichts verbaust.

Die Alpha Methode wäre natürlich auch ne Möglichkeit, allerdings ist die Nutzung eines beliebigen Register natürlich mit viel notwendiger Information verbunden.
Ja, es wird für die Bedingung nicht nur eine Register-Nummer (die bei Alpha 5 Bit groß ist) benötigt sondern auch die Bedingung als solches (da gibt es auch > 0 oder <= 0 jeweils nach signed und unsigned getrennt, wimre gibt es das bei Alpha auch für Floating-Point) und deswegen gibt es bei Alpha wohl nur bedingte Sprünge und sonst nichts. Wenn man diese Bedingung aber in ein eigenständiges Präfix auslagert, das sich mit jedem Befehl kombinieren lässt, dann hat man ja eigentlich auch genügend Bits zur Verfügung um hier auf möglichst große Flexibilität zu setzen. Wenn das Präfix 32 Bits groß ist könnte man sogar die eigentliche Vergleichsoperation (SUB oder AND) und 2 Register mit hinein kodieren. Aber das bläht die interne Befehlsdarstellung ziemlich auf. Ich benötige 7 Bits für die Bedingung (2 Bits für das benutze Flag-Set und 5 Bits für die eigentliche Bedingung, da sind zum einen die 14 Klassiker und noch einige Floating-Point-Bedingungen) und das auch hinter dem Decoder bei der internen Befehlsdarstellung, was IMHO einen brauchbar guten Kompromiss darstellt.


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

Sannaj

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #131 am: 15. January 2012, 18:35 »
Naja, dein Konzept hört sich schon mal gut an. Das mit dem Fehlen der Division gibt es bei mehren RISC Architekturen. Das hat mit dem entfernen des Microcodes zu tuen der Microcode kann auch wie bei den moderen x86-32 ein interner RISC Code sein. Die Division muss ist ein sehr komplexer Ablauf, der in der Regel durch Microcode gelöst werden muss. Und da EPIC auf RISC basiert und deshalb keinen Mikrocode beherrscht, ist die Implementierung der Division ziemlich aufwändig (und wird auch vergleichsweise selten gebraucht.)

Das Problem ist, das man dadurch einen großen Teil des möglichen Befehlssatzes blockiert.
Hä, was meinst Du? Denkst Du das ein NOP mit nur 8 Bits zu kodieren Verschwendung ist?
Naja wenn ich bedenke, das ich nop ohnehin schon indirekt kodiert mit so befehlen wie add 0reg, 0reg, 0reg. Halte ich es für nicht so praktisch wenn ich ein 256tel der möglichen Instructionswörter für nop's hergebe und dann für viele, zusätzliche Befehle, die dann auch noch Platz für die restlichen Bits reservieren müssen, find ich Problematisch. (Natürlich könnt man einen Bareal Shifter verwende und den shift 0 Funktionen, eine Spezialfunktion zuweisen.

Ja, aber wenn Du das erst bei der tatsächlichen Ausführung der Befehle machst verhinderst Du damit effektiv jegliche Form von Instruction-Level-Parallelism weil Du den (über)nächsten Befehl erst dann dekodieren kannst wenn der aktuelle Befehl abgearbeitet wird. Ich kann Dir nur dringlichst empfehlen zu versuchen dafür eine Lösung zu finden die nur im Decoder alleine passiert damit Du Dir später nichts verbaust.
Wenn ich mal nur vom Lesezugriff ausgehe, baue ich einfach eine Schaltung ein, die die Verarbeitung die die Verarbeitung des Folgebefehls behindert. Führe ich alle Befehle nacheinander aus, weiß ich zwei Takte bevor ich den Befehl ausführe, ob dieser ausgeführt werden soll. Jetzt baue ich einfach eine Flag ein, die die Ausführung des Befehls unterbindet. Du darfst nicht vergessen, das ich einen Befehl auch dann dekodieren kann, wenn ich ihn gar nicht ausführe. (Die Ausführschaltung ist einfach für einen Takt gesperrt). Umgekehrt weiß ich auch schon nach dem dekodieren, ob ich auf das NIR zugreifen werden, und deshalb den nächsten Befehl nicht ausführen darf.
Für den Schreibzugriff hast du recht. Da ich aber Schreibzugriff auf das NIR als ehr wenig gebrauchte Anweisung betrachte, braucht diese Funkion auch keine super effektive Ausführmethode. Das heißt, ich der Schreibzugriff würde halt die Pipline leeren, oder zumindest zurück schieben. Eine sehr lange Pipline halte ich sowieso für unpraktisch.
Ja, es wird für die Bedingung nicht nur eine Register-Nummer (die bei Alpha 5 Bit groß ist) benötigt sondern auch die Bedingung als solches (da gibt es auch > 0 oder <= 0 jeweils nach signed und unsigned getrennt, wimre gibt es das bei Alpha auch für Floating-Point) und deswegen gibt es bei Alpha wohl nur bedingte Sprünge und sonst nichts. Wenn man diese Bedingung aber in ein eigenständiges Präfix auslagert, das sich mit jedem Befehl kombinieren lässt, dann hat man ja eigentlich auch genügend Bits zur Verfügung um hier auf möglichst große Flexibilität zu setzen. Wenn das Präfix 32 Bits groß ist könnte man sogar die eigentliche Vergleichsoperation (SUB oder AND) und 2 Register mit hinein kodieren. Aber das bläht die interne Befehlsdarstellung ziemlich auf. Ich benötige 7 Bits für die Bedingung (2 Bits für das benutze Flag-Set und 5 Bits für die eigentliche Bedingung, da sind zum einen die 14 Klassiker und noch einige Floating-Point-Bedingungen) und das auch hinter dem Decoder bei der internen Befehlsdarstellung, was IMHO einen brauchbar guten Kompromiss darstellt.
Naja ich würde ohnehin nur zwei Konditionale Befehle verwenden: Den primitiven Sprung Befehl mit Registerhilfe (oder über NIR auch mit Immidiate.) und halt das Condition Präfix, sowie der evalFLAGS Befehl (setzt ein Register auf 0 oder -1, entsprechend der FLAGS). Da ich mit Nullregister arbeite, sind die bedingungsfindenden Opcodes nicht so speziell.
Im allgemeinen Sind folgende Optionen für eine Condition notwendig, die aber auch zusammengefasst werden.
1. Setzten der Flags (Arithmetische Befehle die als Rd das Nullregister verwenden.)
2. Evaluation der Bedingung in einen Wahrheitswert. evalFLAGS Befehl
3. Aktivierung der Bedingung (Registerorientierte Conditionspräfixe)
4. Aktion die unter der Bedingung ausgeführt wird.

Sprungbefehle fassen hierbei die Aktionen 2-4 oder 3-4 zusammen. Flagorientierte Konditionspräfixe fassen Aktion 2 und 3 zusammen. In beiden Fällen muss der Wahrheitswert dann nicht in notiert werden.
Im Instruction set, unterscheiden sich  evalFLAGS Befehl und Flagorientierte Konditionspräfixe dadurch, dass bei letzteren der Programm Counter als "Evaluationsziel angegeben wird."
Registerorientierte Conditionspräfixe gleichen den 3-4-Sprungbefehlen, nur das der PC als "Sprungziel" angegeben wird.
Beide Präfixe lassen sich deshalb leicht daran erkennen, das sie das PC adressieren.

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #132 am: 15. January 2012, 21:42 »
Hallo,


Das mit dem Fehlen der Division gibt es bei mehren RISC Architekturen.
Das hat aber nichts mit RISC oder Microcode zu tun, es geht einfach darum sich die Transistoren für die HW-Divisions-Schaltung einzusparen. Bei den CPUs wo es etwas mehr auf Rechenleistung ankommt (also eben nicht die typischen kleinen Micro-Controller) ist für gewöhnliche ein HW-Divisions-Schaltung drin, auch bei RISC. Die braucht halt einfach nur einige Takte bis das Ergebnis anliegt und solange steht eben die Pipe-Line wenn es keine Out-of-Order-Execution gibt, trotzdem ist diese Zeit immer noch deutlich kürzer als wenn der Compiler eine Division händisch baut (außer natürlich beim Itanium da der spezielle Befehle hat die direkt die einzelnen Iterationsschritte der Division anbieten, was wimre keine andere CPU hat). Auch bei der Verarbeitung von Floating-Point-Zahlen ist bei den meisten CPUs (so sie denn Floating-Point überhaupt können) nicht nur Addition/Subtraktion und Multiplikation in HW verfügbar (üblicherweise benötigen selbst diese 3 Befehle bereits mehrere Takte) sondern oft auch Division und Quadratwurzel (die dann noch mehr Takte benötigen, deswegen sind diese beiden auch beim Itanium nicht vorhanden (ebenso wie die noch komplexeren Operationen wie Logarithmus oder Sinus) sondern nur als Einzelschritte, es gibt beim Itanium also die passenden Rechenwerke aber die State-Machines die das üblicherweise ansteuern fehlen und da muss dann der Compiler nachhelfen).

Naja wenn ich bedenke, das ich nop ohnehin schon indirekt kodiert mit so befehlen wie add 0reg, 0reg, 0reg.
Okay, aber so ein Null-Register hab ich nicht und möchte ich eigentlich auch nicht, ich denke der Verlust eines Registers wiegt schwerer als der Verzicht auf ein 256tel des OpCode-Raums.

Wenn ich mal nur vom Lesezugriff ausgehe, baue ich einfach eine Schaltung ein, die die Verarbeitung die die Verarbeitung des Folgebefehls behindert. Führe ich alle Befehle nacheinander aus, weiß ich zwei Takte bevor ich den Befehl ausführe, ob dieser ausgeführt werden soll.
Aber was ist wenn Du die Befehl nicht hintereinander sondern gleichzeitig ausführen möchtest? Wäre ja möglich das die alle voneinander unabhängig sind und daher diese Parallelität durchaus erlaubt ist. Ich bleibe vorerst bei der Meinung das Du Dir mit diesem Konzept die nächst höhere Performance-Stufe verbaust oder zumindest erheblich komplizierter machst. IMHO ist es gerade einer der Vorteile wenn man große Befehle hat die komplette Immediates aufnehmen können das der Decoder alle Befehle unabhängig voneinander dekodieren und die Verarbeitungs-Logik diese auch unabhängig voneinander ausführen kann, natürlich soweit keine Datenabhängigkeiten o.ä. vorliegen aber das zu ermitteln ist schon komplex genug so das ich persönlich mir da nicht auch noch so ein NIR aufbürden würde.

sowie der evalFLAGS Befehl (setzt ein Register auf 0 oder -1, entsprechend der FLAGS).
Also für so einen Befehl sehe ich keine Verwendungsmöglichkeit. Wenn Du dann dieses Register mit einem folgenden bedingten Befehl prüfen möchtest so könntest Du auch gleich die Flags prüfen und würdest Dir einen Schritt sparen und wenn es Dir um das bedingte Laden von Immediates geht um diese dann einheitlich weiter zu verarbeiten dann benutze doch gleich einen bedingten Load-Immediate-Befehl der die Flags prüft.

Setzten der Flags (Arithmetische Befehle die als Rd das Nullregister verwenden.)
Heißt dass das Rechenbefehle die nicht aufs Null-Register schreiben keine Flags ablegen können? Das würde ich als sehr ungeschickt betrachten da es durchaus viele Fälle gibt wo man das Ergebnis haben will und auch die Flags interessieren.

Sprungbefehle fassen hierbei die Aktionen 2-4 oder 3-4 zusammen. Flagorientierte Konditionspräfixe fassen Aktion 2 und 3 zusammen. In beiden Fällen muss der Wahrheitswert dann nicht in notiert werden.
Im Instruction set, unterscheiden sich  evalFLAGS Befehl und Flagorientierte Konditionspräfixe dadurch, dass bei letzteren der Programm Counter als "Evaluationsziel angegeben wird."
Registerorientierte Conditionspräfixe gleichen den 3-4-Sprungbefehlen, nur das der PC als "Sprungziel" angegeben wird.
Beide Präfixe lassen sich deshalb leicht daran erkennen, das sie das PC adressieren.
Um ehrlich zu sein habe ich das überhaupt nicht verstanden, könntest Du noch mal anders beschreiben wie Du bedingte Befehlsausführung realisieren möchtest?


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

Sannaj

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #133 am: 17. January 2012, 21:13 »
Naja wenn ich bedenke, das ich nop ohnehin schon indirekt kodiert mit so befehlen wie add 0reg, 0reg, 0reg.
Okay, aber so ein Null-Register hab ich nicht und möchte ich eigentlich auch nicht, ich denke der Verlust eines Registers wiegt schwerer als der Verzicht auf ein 256tel des OpCode-Raums.
Naja, so schwer schätz ich den bei 32/64 Registern dann nicht ein. Dafür macht so ein Register viele Sachen einfach einfacher. Man braucht z.B. keine extra Compare Befehle und kann sich auch Sachen wie den mov Befehl sparen. Ohne Null Reg würde der Opcode dann halt einfach "mov anyGPReg1, anyGPReg1" heißen. Ich mein, ich hab mir ja nur ein paar Gedanken gemacht. Noch kein greifbares Design.

Wenn ich mal nur vom Lesezugriff ausgehe, baue ich einfach eine Schaltung ein, die die Verarbeitung die die Verarbeitung des Folgebefehls behindert. Führe ich alle Befehle nacheinander aus, weiß ich zwei Takte bevor ich den Befehl ausführe, ob dieser ausgeführt werden soll.
Aber was ist wenn Du die Befehl nicht hintereinander sondern gleichzeitig ausführen möchtest? Wäre ja möglich das die alle voneinander unabhängig sind und daher diese Parallelität durchaus erlaubt ist. Ich bleibe vorerst bei der Meinung das Du Dir mit diesem Konzept die nächst höhere Performance-Stufe verbaust oder zumindest erheblich komplizierter machst. IMHO ist es gerade einer der Vorteile wenn man große Befehle hat die komplette Immediates aufnehmen können das der Decoder alle Befehle unabhängig voneinander dekodieren und die Verarbeitungs-Logik diese auch unabhängig voneinander ausführen kann, natürlich soweit keine Datenabhängigkeiten o.ä. vorliegen aber das zu ermitteln ist schon komplex genug so das ich persönlich mir da nicht auch noch so ein NIR aufbürden würde.

Man könnte auch unsere beide Stategien kombinieren. Ein Opcodepaket besteht aus meheren Opcodes, die verschiedene Länge annehmen können. Beide Opcodelängen sind identisch, allerdings sind bei den kurzen Opcodes Teile derselbigen abgeschnitten. So enthalten kurze Opcodes zwar vollwertigen Befehl, aber kein Immediate Sektor (der impizit 0 enthält.) Lange Opcodes enthalten eine Immediate, die sich über ein Psydoregister (IR immidete Register, remake von NIR) ansprechen lässt.) Damit würde man variable Opcodelängen ermöglichen und den Decoder einfach halten.

Setzten der Flags (Arithmetische Befehle die als Rd das Nullregister verwenden.)
Heißt dass das Rechenbefehle die nicht aufs Null-Register schreiben keine Flags ablegen können? Das würde ich als sehr ungeschickt betrachten da es durchaus viele Fälle gibt wo man das Ergebnis haben will und auch die Flags interessieren.
Da hab ich mich falsch ausgedrückt. Natürlich kannst du auch mit allen anderen Registern Flags setzten.


Sprungbefehle fassen hierbei die Aktionen 2-4 oder 3-4 zusammen. Flagorientierte Konditionspräfixe fassen Aktion 2 und 3 zusammen. In beiden Fällen muss der Wahrheitswert dann nicht in notiert werden.
Im Instruction set, unterscheiden sich  evalFLAGS Befehl und Flagorientierte Konditionspräfixe dadurch, dass bei letzteren der Programm Counter als "Evaluationsziel angegeben wird."
Registerorientierte Conditionspräfixe gleichen den 3-4-Sprungbefehlen, nur das der PC als "Sprungziel" angegeben wird.
Beide Präfixe lassen sich deshalb leicht daran erkennen, das sie das PC adressieren.
Um ehrlich zu sein habe ich das überhaupt nicht verstanden, könntest Du noch mal anders beschreiben wie Du bedingte Befehlsausführung realisieren möchtest?
Naja, das war eh so ein spontaner Einfall, den ich vermutlich nicht umsetzten würde.

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #134 am: 18. January 2012, 10:07 »
Hallo,


... ich denke der Verlust eines Registers wiegt schwerer als der Verzicht auf ein 256tel des OpCode-Raums.
Naja, so schwer schätz ich den bei 32/64 Registern dann nicht ein. Dafür macht so ein Register viele Sachen einfach einfacher.
Naja, das fehlende Register kostet sicher etwas Performance wogegen die Art und Weise wie die Befehle codiert sind erst mal keine Performance kostet, solange diese Codierung nicht so ineffizient ist das die Befehle deutlich größer werden.

Einen CMP-Befehl habe ich auch nicht (ebenso wie ich keinen TEST-Befehl habe) sondern dafür wird ein ganz normaler SUB-Befehl (oder AND-Befehl) benutzt und das Ergebnis einfach nicht verwendet. Aus Sicht der CMP/TEST-Operation ist es egal ob das Ziel-Register grundsätzlich keine Werte speichern kann oder ob der Wert einfach nur ignoriert wird aber für andere Situationen ist ein Register weniger eben eine Register weniger und das kann manchmal etwas Performance kosten. Auf ein MOV würde ich auch grundsätzlich nicht verzichten, klar kann man das mit "ADD RD,RS,R0" ersetzen aber hier würde entweder eine sinnlose Addition passieren obwohl der Wert der in RD rein soll schon einen Takt eher bekannt ist oder Dein Decoder erkennt das und erzeugt einen simplen MOV-Befehl für die Pipeline die dann natürlich trotzdem einen dedizierten MOV-Befehl unterstützen muss und dann ist es IMHO auch nicht mehr schlimm wenn der MOV auch im normalen OpCode-Format enthalten ist. Ich persönlich halte nicht viel davon wenn die Befehle je nach Parameter sich unterschiedlich verhalten, beim klassischen ARM-Befehlssatz ist es ja so das Befehle die R15 modifizieren und die Flags setzen sich anders verhalten und einen Modus-Wechsel durchführen können. Mag sein dass das minimal kompakteren Code ergibt als wenn man diese Operationen mit eigenen Befehlen ermöglicht aber innerhalb der CPU (u.a. beim der internen Befehlsdarstellung) erspart man sich eher nichts da ja trotzdem alle Funktionalitäten unterstützt werden müssen, das macht IMHO nur den Decoder komplizierter.

Man könnte auch unsere beide Stategien kombinieren. Ein Opcodepaket besteht aus meheren Opcodes, die verschiedene Länge annehmen können. Beide Opcodelängen sind identisch, allerdings sind bei den kurzen Opcodes Teile derselbigen abgeschnitten. So enthalten kurze Opcodes zwar vollwertigen Befehl, aber kein Immediate Sektor (der impizit 0 enthält.) Lange Opcodes enthalten eine Immediate, die sich über ein Psydoregister (IR immidete Register, remake von NIR) ansprechen lässt.) Damit würde man variable Opcodelängen ermöglichen und den Decoder einfach halten.
Ja, das klingt interessant. Machen Sie es so! ;)

Da hab ich mich falsch ausgedrückt. Natürlich kannst du auch mit allen anderen Registern Flags setzten.
Dann hast Du aber bei vielen Befehlen ein extra Bit im OpCode das angibt ob die Flags geschrieben werden sollen oder?

das war eh so ein spontaner Einfall
Dafür ist dieser Thread ja da. Von dem was ich am Anfang dieses Threads (immerhin vor knapp 2 Jahren) geschrieben habe ist heute auch nicht mehr alles gültig, Konzepte entwickeln sich eben auch mal weiter.


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

Sannaj

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #135 am: 18. January 2012, 19:54 »
Einen CMP-Befehl habe ich auch nicht (ebenso wie ich keinen TEST-Befehl habe) sondern dafür wird ein ganz normaler SUB-Befehl (oder AND-Befehl) benutzt und das Ergebnis einfach nicht verwendet.
Ich hab mir überlegt, das 0reg doch abzuschaffen. Für die nicht vorhandenen TEST/COMP befehle, kann man ja die Daten in das IR schreiben, wo sie quasi weg sind. (Für den Executer ist das IR ein ganz normales Register. Der einzige Unterschied ist, das es extern durch den Pipe Shift geladen werden kann.)
Auf ein MOV würde ich auch grundsätzlich nicht verzichten, klar kann man das mit "ADD RD,RS,R0"
Da ich mit IR kein echtes 0-Register mehr habe, brauch ich natürlich auch einen echten MOV Befehl.

Generell bin ich auch der Meinung, das es bei Befehlen nicht zu viele Ausnahmen geben sollte. Auf der anderen Seite muss ein Schreibzugriff auf den PC natürlich registriert werden.
Ein Problem ist das Verhältnis von PC Addresse und Instruktion Fetch Addresse. Ich persönlich finde, dass man da einen Unterschied machen muss. Das der PC auf die Fetch-Addresse zeigt, halte ich für dumm, weil man so die Piplinelänge festlegt, es dem Programmierer schwieriger macht und zum anderen trotzdem umrechne muss (z.B. beim Sprung zu einem Unterprogramm, ist aber nicht so häufig wie andere Sprünge). Ich löse das deshalb so, das der PC auf den Befehl zeigt, der gerade ausgeführt werden soll. Der Fetcher besitzt dann eine Schaltung, die die Piplinelänge entsprechend addiert. Wichtig ist das ganze bei einem Pipline-Flush, bei dem dann der PC entsprechend dekrementiert wird. (Sodass er dann vor dem eigentlichen Sprungziel liegt. Für beides gibt es natürlich spezielle Schaltungen, die auf diese Funktion optimiert worden sind).

Meine Pipe sieht wie folgt aus:

Fetcher -(Packet)-> Puffer -> Unpacker -(Langer Befehl 60/124 bit) -┬-> Decoder --> Executer (--> Write Back)
                                                                alternativer Fetcher -┘

Eine weitere wichtige Funktion ist der sogenannte alternative Fetcher. Ebenso wie der normale Fetcher, kann auch diese Baugruppe Befehle in die Pipline einlesen, allerdings stehen diese nicht an irgendeiner RAM Adresse, sondern von einem externen oder auch interenen Bauelement. (In der Regel sind einige Funktionen intern vorprogrammiert. z.B. die Division.) Als Faustregel gilt. Negative Integer werden extern ausgeführt, positive Intern. Exteren Befehle werden über einen Port angesteuert. Wichtig beim alternativen Fetcher ist, das es keine Adressen gibt, und dass der PC auch (meist nicht) nicht hochgezählt wird. Schleifen und Sprünge erreicht man einfach durch rekursive Aufrufe oder durch interne Steuerung des alternativen Fetchers.

Man könnte auch unsere beide Stategien kombinieren. Ein Opcodepaket besteht aus meheren Opcodes, die verschiedene Länge annehmen können. Beide Opcodelängen sind identisch, allerdings sind bei den kurzen Opcodes Teile derselbigen abgeschnitten. So enthalten kurze Opcodes zwar vollwertigen Befehl, aber kein Immediate Sektor (der impizit 0 enthält.) Lange Opcodes enthalten eine Immediate, die sich über ein Psydoregister (IR immidete Register, remake von NIR) ansprechen lässt.) Damit würde man variable Opcodelängen ermöglichen und den Decoder einfach halten.
Ja, das klingt interessant. Machen Sie es so! ;)
Ich denke aber ich werde ehr nicht so viele Befehlslängen anbieten. (Es gibt einen 64 bit Doppelpaket, das entweder einen 60 Bit Befehl, 3 20 Bit Befehle oder nur 1 20 bit Befehl + 40 bit Zusatzinfos enthalten kann. (Die dann die Pipe abkürzen.)

Da hab ich mich falsch ausgedrückt. Natürlich kannst du auch mit allen anderen Registern Flags setzten.
Dann hast Du aber bei vielen Befehlen ein extra Bit im OpCode das angibt ob die Flags geschrieben werden sollen oder?
Ja so umgefähr.

Allerdings wollte ich doch eigentlich eine Programmiersprache und keine CPU bauen.
« Letzte Änderung: 18. January 2012, 20:14 von Sannaj »

Sannaj

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #136 am: 18. January 2012, 20:18 »
Vergiss das mit meinen Opcodelängen.

Jeder Befehlsblock besteht aus zwei Befehlspacketen.
Diese enthalten
4 bit Verwaltungsdaten+ 60bit Infos hierbei gilt:
Verwaltungsdaten:
0000b = 2. Befehlspaket einer Folge.
andere.
Kombination aus 20 bit, 40 bit und 80 bit Befehlen.
« Letzte Änderung: 18. January 2012, 20:28 von Sannaj »

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #137 am: 19. January 2012, 20:53 »
Hallo,


Auf der anderen Seite muss ein Schreibzugriff auf den PC natürlich registriert werden.
So wie ich mir das denke ist der PC (der bei mir einfach nur R63 ist und damit von jeden Befehl gelesen und beschrieben werden kann) zwar logisch ein normales Register aber nicht physisch. Bei Lesezugriffen auf dieses Register wird auch einfach immer das Offset des entsprechenden Befehls geliefert (es ist gerade bei positionsunabhängigen Code wichtig das der sich auf ein bestimmtes Verhalten beim Lesen des PC verlassen kann) und Schreibzugriffe auf R63 werden nicht vom normalen Register-File entgegengenommen sondern speziell abgefangen (aber außerhalb der ALUs) und dem Dispatcher zugeleitet damit der weiß von wo er als nächstes Befehle holen soll. Für die eigentlichen Ausführungseinheiten ist R63 ein ganz normales Register wie alle anderen auch. Es wird aber trotzdem einige Operationen geben die nicht mit R63 arbeiten können aber die lassen sich alle im Decoder abfangen und machen in der Pipeline keinen Stress.

Meine Pipe sieht wie folgt aus:
Also quasi der Klassiker. Aber die erlaubt Dir natürlich keine Parallelität zwischen den einzelnen Befehlen und auch keine Out-of-Order-Exection.
Wenn ich Dich richtig verstanden habe möchtest Du z.B. die Division "micro-codiert" erledigen (indem Du anstatt einem Befehl viele Befehle in die Pipeline lässt die diesen Job dann mit vielen Schritten erledigen)? Das macht zwar die Pipeline etwas einfacher aber dafür muss man eben diesen Micro-Code bauen. Hm, ist wohl Geschmackssache.

Dann hast Du aber bei vielen Befehlen ein extra Bit im OpCode das angibt ob die Flags geschrieben werden sollen oder?
Ja so umgefähr.
Ich hab da lieber gleich noch ein Bit mehr spendiert und habe dafür 4 unabhängige Flag-Sets, das dürfte gerade bei komplexen if-Abfragen oder auch verschachtelten if-Abfragen und Schleifen usw. einiges bringen.

Allerdings wollte ich doch eigentlich eine Programmiersprache und keine CPU bauen.
Ist doch hoffentlich kein Problem, oder? ;)


Dein OpCode-Format kannst Du ja, wenn es etwas näher an fertig ist, mal detaillierter vorstellen.


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

Sannaj

  • Beiträge: 103
    • Profil anzeigen
Gespeichert
« Antwort #138 am: 20. January 2012, 21:19 »
Naja, ich hab mir mein Instruktionsformat noch mal überarbeitet:
Ein Befehl ist 32 bit lang, kann aber Abhängigkeiten von folgenden Befehlen besitzen. Es werden aber immer zwei 64 bit gleichzeitig eingelesen und abgearbeitet (das entspricht bis zu zwei Befehlen, die sich nicht in die Quere kommen sollten.)

Zu den Abhängligkeiten:
Das most significant Bit bestimmt die Bedeutung des dwords:
eine "0" entspricht Daten und eine "1" Befehle. Datenwörter, die nicht benutzt werden, entsprechen in der Ausführung nop.

Im der zweiten Piplinestufe (Dekodierstufe 1) wird das Packetpaar entsprechend vordecodiert. Hierbei entsteht je ein 28 bit Befehl und ein 64 bit Datenwort. Jeder der beiden Einzelbefehle besitzt hierzu einen Controlnibble (4 bit), der folgenden Effekt hat.
(Die Bitnummer beginnt bei 1)
0xxxxb - Datenwort (wird in nop umgewandelt)
1000b - Keine externen Daten benötigt, setzte das Datenwort auf 0.
1001b - 31 bit Immideate, die aus dem folgenden Datenbefehl geladen wird. Das 32igste bit wird auf 1 gesetzt die Zahl mit Nullen auf 64 bit erweitert.
1010b - 31 bit Immideate, die aus dem folgenden Datenbefehl geladen und mit Nullen auf 64 Bit erweitert wird.
1011b - 31 bit Immideate, die aus dem folgenden Datenbefehl geladen und mit Einsen auf 64 Bit erweitert wird.
11xyb - 2x31 bit Immideate, die aus 2 folgenden Datenbefehlen geladen wird und deren 32igstes bit auf y und deren 64igstes bit auf x gesetzt wird.
Wird versucht einen gültigen Befehl (1...b) als Datenbefehl zu übergeben, gibt es eine Invalid-Opcode Exeption

Da der Decoder 1. nicht über ausreichend Informationen verfügt, um die Daten vollständig zu ergänzen (er hat ja nur die zwei Befehle zu Verfügung, ergänzt er einfach die ihm bekannten Daten, sowie einige Steuersignale für die nächste Pipliestufe.
Da der Decoder 1 somit auch nicht wirklich 64 bit Datenwörter produziert, sind einige Bits im Ausgangsbus zusammengefasst und zwar:
(Die Bitnummerirung beginnt bei 0)

1. Befehl des Befehlspaars
Abschnitt - Möglicher Werte               Länge im Ausgangsbus
bit[30:0] - individuelle Daten              31
bit[31]                                           1
bit[62:32] - immer alle gleich              1
bit[64]                                           1
Gesamt                                         34

2. Befehl des Befehlspaars
Abschnitt - Möglicher Werte               Länge im Ausgangsbus
bit[30:0] - immer null oder egal           0
bit[31]                                           1
bit[62:32] - immer alle gleich              1
bit[64]                                           1
Gesamt                                          3

In der 3. Piplinstufe werden die 28 Bit Befehle dekodiert. Paralel werden die Datenwörter mithilfe des jetzt in der 2. Pipliestufen liegenden Befehlspaares verfolständigt.
Diese sogenannte Nachladeeinheit erhält von der Dekodierstufe 1 abgesehen von den beiden "64 bit" Datenwörtern folgende Steuersignale.
1. Befehl des Befehlspaars
pldctrl0 - Läd das erste 31 bit Datenwort aus der Dekodierstufe 1 in das 64 bit Datenwort an Prosition [62:32].

2. Befehl des Befehlspaars
pldctrl1 - Läd das erste 31 bit Datenwort aus der Dekodierstufe 1 in das 64 bit Datenwort an Prosition [30:0].
pldctrl2 - Läd das zweite 31 bit Datenwort aus der Dekodierstufe 1 in das 64 bit Datenwort an Prosition [62:32].

Nach dem die 3. Piplinestufe abgeschossen ist, wird das nun vollständige 64 bit Datenwort in das IR geladen.

Somit gibt es bei mir folgende Spezialregister, die aber ganz normal wie andere Register auch adressiert werden können, die aber für die beiden Befehle des Befehlspaares unterschiedlich sind:
IR
PC (ist für den zweiten Befehl beim lesen 4 höher.)

Sprünge werden für beide Befehle danach ausgeführt, sodass wenn der erste Befehl ein Sprung ist, der zweite trotzdem ausgeführt wird.

Die Sache mit dem Mikrocode muss ich mal schauen, wo ich die am besten unterkriege. Ich vermute aber in Piplinestufe 1. Ich hab mir das überlegt. Außerdem könnt man, wenn man den Baustein extern einrichtet, auf die Weise auch so eine Art BIOS unterbringen.

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #139 am: 29. January 2012, 11:20 »
Hallo Sannaj,


ich hab noch mal etwas über Dein IR nachgedacht und mir sind da einige Probleme aufgefallen:
Wenn das Laden des IR und das Benutzen des IR mit unabhängigen Befehlen und in unterschiedlichen Pipeline-Stufen durchgeführt wird dann sehe ich ein Problem mit bedingten Sprüngen. Wenn nach so einem bedingtem Sprung ein IR-Lade-OpCode kommt und vom Decoder auch verarbeitet wird noch bevor für den bedingten Sprung feststeht ob dieser ausgeführt werden soll könnte es passieren dass das IR bereits mit einem neuen Wert geladen wird aber der Sprung trotzdem ausgeführt wird so das dann Befehle am Sprungziel im IR nicht den Wert vorfinden der als letztes vor dem bedingten Sprung geladen wurde sondern eventuell einen Wert der nach dem bedingtem Sprung geladen wurde. Ob das so passiert hängt von vielen Faktoren ab: vom Abstand (die Pipeline kann ja nur maximal eine gewisse Menge an Befehlen enthalten) aber auch davon ob der Speicher/Cache die nächsten Befehle schon an den Decoder geliefert hat. Damit würde die Situation entstehen das manche Befehle im OpCode-Stream die hinter dem bedingten Sprung kommen trotzdem ausgeführt werden und manche nicht und das auch noch ohne das der Compiler das immer eineindeutig ermitteln kann (eben weil das sicher auch von Umständen abhängt die erst zur Laufzeit bekannt sind und eventuell auch jedes mal anders ausfallen).
Ein weiteres Problem sind Exceptions und Interrupts. Du musst in der Lage sein das IR im Exception-Handler gezielt zu sichern und es am Ende des Exception-Handlers auch wieder herzustellen, ansonsten kannst Du nicht an beliebigen Stellen Exceptions/Interrupts zulassen.
In dieser Hinsicht gefällt mir das Konzept eines einfachen Load-Immediate-in-beliebiges-Register-Befehl am besten, entweder dieser Befehl wird in der Pipeline ausgeführt und ist damit für alle folgenden Befehle sichtbar oder er wird nicht ausgeführt und hat demzufolge auch keine sichtbaren Auswirkungen. Ich gebe zu das Dein IR durchaus seinen Reiz hat weil man damit mit jedem Befehl und für jeden Zweck ein Immediate benutzen kann aber wenn Du dafür eh ein Register opfern möchtest (also eine Register-Nummer) dann implementiere das als richtiges Register und mach einen Load-Immediate-Befehl der immer in dieses Register lädt und ganz normal von der Pipeline ausgeführt wird.

Nur 28 Bit für den eigentlichen Befehl würde ich persönlich als zu wenig betrachten, schau Dir mal an wie gedrängt es im klassischen ARM-Mode zugeht und dort wird die Bedingung (in den oberen 4 Bit) auch noch mitbenutzt um Befehle zu codieren. ARM hat auch nur 16 Register und das ist aus heutiger Sicht schon recht knapp bemessen.


Auf Micro-Code würde ich ganz verzichten, in einer RISC-CPU gibt es dafür IMHO keine Notwendigkeit. Ich glaube auch das Deine CPU dann die erste RISC-CPU wäre die Micro-Code benutzt und wie Du damit ein "BIOS" realisieren möchtest bzw. was Du damit meinst musst Du mal etwas genauer erläutern.


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

 

Einloggen