Themen

1

Offtopic / Instruction-Length Decoder und Alignment-Unit einer x86 CPU

« am: 17. February 2017, 16:33 »

Huhu, ich arbeite seit einiger Zeit an einem Entwurf einer neuen eigenen CPU( sozusagen Logisim-CPU 2.0  ). Um Fehler zu vermeiden die ich in früheren ähnlicheren Projekten gemacht habe, habe ich mir von Anfang an ein grobes Ziel und Spezifikation gesetzt:

• 2fach Superskalar mit Out-of-order Ausführung.
• Soll nacher einen durchschnittlichen IPC von 1.2 haben.
• Als Zielplattform soll eine Cyclone 4 FPGA mit einem Speedgrade C7 dienen.
• Die CPU soll nacher etwa 30k 4bit LUT-Tabellen und 70kByte Bram auf der FPGA benötigen.
• Als Takt-Fequenz peile ich etwa 100 Mhz an (also pro Pipeline-Stufe etwa ein Delay von 9 LUT-Tabellen).
• Der Ziel-Befehlssatz ist AMD64( zusätzlich soll SEE 1 bis 4.2 und VT-X implementiert werden).

Die Entwicklung ist bis jetzt recht weit Fortgeschritten, das Back-end (Also Integer-ALUs, Memory-Execution-Unit,  Out of order resource allocation und die FPU) hab ich schon grob fertig entworfen.
Die meisten noch ungelöste Fragen und Probleme meines Projektes befinden sich größtenteils im Frontend welches durch den CISC-Befehlssatzt wesentlich mehr Zeitauswand bei der Entwicklung erfordert wie die restlichen Teile des Entwurfs. Die größten Schwierigkeit davon ist der Instruction-Length Decoder (oder einfach ILD) zusammen mit der Alignment-Unit welche die Befehls-Bytes ausrichtet und an die beiden Decoder weiter gibt.

Ich hatte mir für den ILD und der Alignment-Unit ursprünglich als Ziel gesetzt maximal mit einer Pipeline-Sufe zusammen mit einem Predecode-Bit pro Befehlsbyte auszukommen.
Ich arbeite schon mehr als ein halbes Jahr an diesen beiden Komponenten meiner CPU und hab schon mehrere Entwürfe ausgearbeitet, welche aber allesamt mein selbst gesetztes Ziel verfehlt haben.
Die große Schwierigkeit ist die große Komplexität des x86-Befehlssatz. Zum einem kann ein Befehl 1 bis 15Byte lang sein zum anderen befindet sich das erste Opcodebyte nicht immer am ersten Befehlsbyte sondern bedingt durch die Prefix-Bytes an verschieden Stellen im Befehl.
Meine drei besten Entwürfe für den ILD und der Alignment-Unit sind folgende:

• Den Kompletten ILD und die Alignment-Unit direkt in der CPU-Pipeline implementieren. Der Entwurf basiert auf diesen beiden Patenten : https://www.google.com.au/patents/US6260134 https://www.google.com/patents/US7818542
  Es werden zunächst 16Bytes aus einem kleinem Buffer -welcher die I-Cache von dem Rest der CPU trennt- herraus geladen. Anschließend schiebt ein Shifter 8Byte der 16 Bytes entweder an die Startposition eines Befehls(z.b nach einem Sprungbefehl) oder an das Ende der letzten 8 Bytes. In diesen 8 Bytes gibt es 8 mögliche Startpositionen von maximal 8 möglichen Befehlen. Daher wird nach dem Shiften mit Hilfe 8 ILD für jedes Bytes die Längen 8 möglicher Befehle parallel Dekodiert. Im Anschluss werden diese 8 Befehlsbytes zusammen mit den ILD-Informationen in einem kleinen 24Byte Buffer zwischen gespeichert. Die 8 ILDs verwenden die letzten 8 Bytes aus diesem Buffer als zusätzliche Informationsquelle (falls ein Befehl die 8 Byte-Grenze überschritten hat). Die Alignment-Unit verwendet den 24Byte Buffer um die entsprechenden Instruction-Bytes zu laden  und anhand den ILD-Informationen in die richtige Position zu schieben.
  Dieser Entwurf hab ich nur grob ausgearbeitet. Insgesamt benötigt die Schaltung 3 Pipeline-Stufen um die geforderte Takt-Fequenz zu erreichen. Zusätzliche Predecode-Bits werden aber nicht benötigt.
• Predecoder vor der I-Cache. Dieses Konzept basiert auf drei Intel-Patente und sieht dem ILD und Alignment-Unit der Silvermont Architektur nicht unähnlich : https://www.google.com/patents/US6539469 https://www.google.ch/patents/US20130290678 https://www.google.com/patents/US5586276 . Als Predecoder war das oben genannte Patent angedacht: https://www.google.com.au/patents/US6260134
  Ein Predecoder dekodiert Befehle, die in die Instruction-Cache geladen werden, vor und markiert mit einem zusätzlichen Bit pro Befehls-Byte das Ende jedes Befehls. ByteBlöcke (16Byte) die aus der I-Cache geladen werden, werden in einen 12x8Byte umfassenden Prefetch-Buffer geladen oder über einen Bypass an die Alignment-Unit weitergereicht.
  Der Prefetchbuffer ist mit 3 Speicherblöcken a 4x8 Byte organisiert. In jedem Takt werden 3x8Byte (also pro Speicherblock 8Byte) aus dem Prefetchbuffer geladen und anschließend über drei 5:1 Multiplexer in die richtige Reihenfolge gebracht (es wird halt anhand des PC welcher die Alignment-Unit verarbeiten möchte ausgewählt welcher der drei 8Byte-Blöcke der erste, der zweite und der Dritte Block ist). Zusätzlich werden diese drei Multiplexer verwendet um den Bypass von der Cache an die Alignment-Unit zu organisieren.
  Die Alignment-Unit besteht in diesem Konzept aus zwei unabhängige Teile. Der erste Teil schiebt zunächt anhand der vorgegebenen Startposition( dem zu verarbeitenem PC) mit Hilfe eines 128Bit breiten 8:1 Multiplexers ein 16Byte Block an die Startposition des ersten Befehls. Daneben wird über einen zweiten 16Bit Breiten 8:1 Multiplexer die EndBits in die selbe Position gebracht und diese anschließend mit Hilfe eines Prioritizer das Ende des ersten Befehls gescannt. Falls der erste Befehl kürzer wie 9 Byte ist (Ansonsten bräuchte man für den zweiten Befehl einen 16:1 Mux) werden 8 Befehlsbytes des zweite Befehl mithilfe eines zweiten 64Bit 8:1 Multiplexer, welcher die gerichteten 128Bit des ersten Befehls verwendet, in ihre richtige Position gebracht.
  In Anschluss werden sowohl die 16 Befehls-Byte des ersten Befehls und die 8 Befehls-Byte des zweiten Befehls auf Prefix-Byte gescannt und ein weiteres mal geschoben, bevor sie an die Decode-Unit weitergereicht werden.
  Der Zweite Teil der Alignment-Unit scannt alle 24 EndBits parallel und bestimmt den PC, der im nächsten Takt-Zyklus verarbeitet wird.
  Dieses Konzept ist am besten ausgearbeitet. Es existiert schon ein Verilog-Code und ist schon im großen und ganzen fertig validiert. Bin aber irgendwie nicht richtig Zufrieden mit dem Konzept, es benötigt zwar nur ein Predecode-Bit pro Befehlsbyte, verbraucht aber zwei Pipeline-Stufen in der CPU. Auserdem werden die Befehlsbytes Unnötig oft geschoben.
• Der Dritte Entwurf ist ein kompletter Eigenentwurf.
  Wie beim zweiten Entwurf werden werden die Befehlsbyte bevor sie in die I-Cache geladen werden vordekodiert. Diesmal wird aber der Start jedes Befehls markiert. Auserdem werden die Befehlbytes umsortiert. Prefix-Bytes welche immer am Anfang jedes Befehls stehen, werden nach hinten geschoben und als Suffixe an die vorherigen Befehlsbytes -welche vorgeschoben wurden- drangehängt. Die Suffixe werden mit einem zweiten Predecode-Bit markiert.
  Die I-Cache ist mit einem Way-Prediction Mechanismus ausgestattet und ladet die 16 Befehls-Byte direkt in einem 8x16Byte umfassenden PrefetchBuffer.
  Der Prefetchbuffer besteht aus 4 Teilblöcken mit je 8x4BefehlsByte. In jedem Taktzyklus ladet jeder Teilblock 4Byte und gibt sie an die nachfolgende Alignment-Unit weiter. Der Prefetchbuffer ist also in etwa so aufgebaut wie im Zweiten Konzept. In einer der 4Byte der vier Teilblöcke befindet sich der Startbyte des ersten Befehls. Die vier 4Byte werden jetzt aber nicht mit Multiplexer in die Richtige Position gebracht sondern direkt an einen Scanner weitergereicht welcher die Startbyte des ersten und zweiten Befehls erkennt. Mit zwei 16:1 Rotierer werden die beiden Befehle ausgewählt und zwei 8Byte Blöcke( jeder Befehl kann maximal 8Byte lang sein. Falls ein Befehl länger ist, wird nur ein Befehl pro Zyklus verarbeitet) und die nachfolgende Decoder weitergeschickt.
  Der Scanner sucht auch nach einem dritten Startbit welches den Start des nächsten Befehls markiert. Falls der Scanner kein drittes Startbit findet wird in diesem Zyklus nur ein Befehl verarbeitet.
  Für denn Fall das nur ein Startbit gefunden wurde, ist eine Speziallogik nötig. Die hab ich aber nocht nicht ganz zuende entworfen.
  Das Konzept benötigt nur eine einzige Pipeline-Stufe. Daher besitzt die CPU mit diesem Konzept eine extrem Kurze Pipeline, die Branch mispredict loop beträgt 7 Zyklen. Es werden aber 2 Predecode Bits pro Byte benötigt. Die I-Cache wird dadurch um 25% größer. Auserdem stellen sich Probleme mit der Branch-Prediction Unit ein, da diese jetzt nurnoch 1 Taktzyklus zeit hat um eine Vorhersage zumachen (Bzw. eine Branch-Byte-Mask zu generieren, welche die Scan-Unit benötigt). 

Ich bin derzeit ziemlich Unschlüssig welcher meiner Drei Konzepte (welche alle meine Spezifikation nicht ganz erfüllen) die geeigneteste für mein Projekt ist. Hat jemand Erfahrung mit diesem Komplexen Thema? Was haltet ihr von diesen drei Konzepten? Und habt ihr eventuell Anregungen und Verbesserungs-Vorschläge?

Mfg Tufel

PS: Ich hatte mir Vorgenommen in diesem Beitrag alles Unterzubringen was wichtig ist, Irgendwie ist Beitrag aber dadurch etwas länger geworden. 

2

Offtopic / Logisim CPU

« am: 31. October 2012, 09:46 »

Huhu, hab mir eine CPU in logisim gebaut und möchte jetzt für die CPU ein OS programmieren. Nun hab mir schon einige Gedanken für das dateisystem gemacht:

die ganzen dateien werden im Ram gespeichert.

es gibt 2 große listen, die Dateiliste und die Verzeichniss liste.In denen werden die ganzen ID's gespeichert

/a/programm/Hirn.OS
 0        1      1024,1

nun jedes verzeichniss hat einen bestimmten pfad ID.Wird nach ner datei gesucht wird zunächst die Pfad's in ihre ID'n übersetzt und dann die ID'S zusammen addiert.

0+1 = 1 PfadID

dannach wird die datei Übersetzt:

DateiID = 1024
DateiPfadID = 1

Nun jetzt wird überprüft ob die PfadID mit der DateiPfadID übereinstimmt wenn das nicht der fall ist wird ne fehlermeldung angezeigt.Die DateiID für zur adresse im ram.

So, gibt ne Effektivere Möglichkeit für das Dateiensystem? Auserdem will ich für das projekt einen Compiler programmieren, hat wer ne Idee wie man das am besten macht ?

MfG Tufelix