http://www.informatik.uni-ulm.de/ni/Lehre/SS01/TI/folien/arithC2.pdfDanke für den Link.
da hst du sogar ein blockschaltbild :D
Mein Problem ist halt, dass die Subtraktionen voneinander abhängen und ich sie nicht parallelisieren kann.Das ist nun mal der Kern einer jeden Division, deswegen baut man das ganze ja als getaktete State-Maschine in dem pro Takt immer nur eine (oder wenige) Bit vom Quotienten ermittelt werden und somit pro Takt auch nur eine (oder wenige aber parallele) Subtraktion erforderlich ist. Man kann natürlich auch alle diese Stufen jeweils in Hardware realisieren und ohne Zwischenregister hintereinander schalten was aber den maximalen Takt auf ein n-tel begrenzt (weil diese riesige Logik-Schaltung eine enorm lange Durchlaufzeit hat).
Dieses SRT interessiert mich, da die Operanden zuvor analysiert werden.Falls Du nicht wirklich vor hast einen ASIC zu designen würde ich von SRT eher die Finger lassen. Der Kern von SRT geht davon aus das Du z.B. bei einer Radix-4-Division nicht immer den kompletten Divisor mit dem kompletten aktuellem Fenster des Dividenden vergleichst sondern von beidem z.B. nur die obersten 5 Bit nimmst (was auch bedeutet das man auch beim Divisor genau wissen muss wo das höchste Bit ist) und damit für die 2 Bit des Quotienten nicht nur die Werte +0...+3 sondern -1...+4 erhalten kannst da so eine Schätzung ja auch mal daneben gehen kann und dann in der nächsten Stelle korrigiert werden muss. Der Hintergedanke dazu ist das man sich gerade bei großen Bittiefen der beteiligten Zahlen versucht die doch recht lange Durchlaufzeit einer vollständigen Subtraktion zu ersparen. In Takten gerechnet würde ich vermuten (nicht wissen) das eine SRT-Division eher ein oder zwei Takte mehr benötigt (wegen komplexerer Vorbereitungen und Nachbereitungen) aber dafür z.B. 20% höheren Takt ermöglicht weil die Subtraktionen in der eigentlichen Kernschleife abgekürzt werden, bei 128Bit : 64Bit und Radix-4 lohnt sich das durchaus (in absoluter Zeit gerechnet) da die 2 Zusatztakte nicht mal 10% von den 32 Takten für die Kernschleife ausmachen. Dafür dürfte der Transistorbedarf deutlich höher liegen (ich schätze mal mindestens das doppelte) und auch das Design ist enorm komplexer (und fehleranfälliger wie Intel vorgemacht hat) da Du überlegen musst wie viele Stellen des Quotienten Du pro Takt korrigieren kannst und diese Schätzfunktion (anstelle eines korrekten Vergleichs) ist sicher auch nicht ganz ohne. Auch wenn Du Deine Logik einmal in einem FPGA realisieren möchtest würde ich von SRT abraten da FPGAs üblicherweise über Carry-Chains verfügen mit denen sich auch breite Subtraktionen/Additionen/Vergleiche relativ performant umsetzen lassen, in einer Soft-CPU in einem FPGA ist eine Subtraktionen mit voller Bitbreite sicher nicht der kritische Pfad der den maximalen Takt limitiert. SRT lohnt sich IMHO nur bei echten CPUs wo man vermeiden möchte das die Division den maximalen Takt zu stark limitiert und man deswegen gerne ein paar Transistoren mehr auf das Silizium verteilt wenn man dafür die Konkurrenz wieder mal überholen kann.
Alles in allem scheint die Division eine teure Angelegenheit zu werden.Ja, das hast Du absolut korrekt erkannt. ;)
Mit welchem Programm kann man Logik-Gatter mit Timing simulieren?Das geht ganz sicher auch mit ModelSim, man kann in VHDL schließlich auch Gatter beschreiben und auch die Durchlaufzeiten durch ein Gatter mit angeben und auch die Durchlaufzeiten von Leitungen kann man in VHDL abbilden. Alles was Du dazu bräuchtest wäre ein Synthese-Tool das Deinen normalen VHDL-Code nimmt und daraus eben Schaltungen nur mit AND/OR/NAND/NOR/NOT/XOR-Gattern baut und alle Laufzeiten passend einbaut, ob es sowas gibt weiß ich aber nicht. Der Macher von MyCPU.eu hat wimre geschrieben das er seine CPU auf Gatter-Ebene mit Laufzeiten simuliert hat, vielleicht kann er ja sagen womit (ist immerhin ein Deutscher).
Ich will das design parallel zu VHDL per Schaltbild machenDas klingt für mich so als würdest Du ein Programm zusätzlich zu C++ auch noch mal parallel in Assembler umsetzen wollen (inklusive Optimierungen), diesen erheblichen zusätzlichen Aufwand würde ich nur Treiben wenn es dafür auch wirklich einen triftigen Grund gibt.
da die Verdrahtung einen bedeutenden Anteil an der Gesamtfläche hatAuf einem echten CMOS-IC belegt die Verdrahtung keine zusätzliche Fläche da diese über dem Silizium in mehreren Kupfer-Ebenen gemacht wird.
Die Funktionen werden iterativ auf das Register angewendet. log2(128)=7, also muss 7-Fach verschaltet werden.da die Verdrahtung einen bedeutenden Anteil an der Gesamtfläche hatAuf einem echten CMOS-IC belegt die Verdrahtung keine zusätzliche Fläche da diese über dem Silizium in mehreren Kupfer-Ebenen gemacht wird.
Die Funktionen werden iterativ auf das Register angewendet. log2(128)=7, also muss 7-Fach verschaltet werden.Hä? Was tust Du da meinen?
Im Schaltbild setze ich nur die (platz&zeit-)kritischen Instruktionen um.Gerade das dürfte ein automatisches Synthesetool deutlich besser als Du schaffen, hier passt der Vergleich zwischen Assembler und einer Hochsprache mit gutem Compiler durchaus. Wenn es auf möglichst kurze Durchlaufzeit ankommt werden binäre Addition/Subtraktion (und auch Multiplikation) schon lange nicht mehr aus einfachen 1Bit-Addierern zusammengesetzt, da gibt es deutlich effizientere Methoden.
/ Adresse 1
S <- Adress-Pipeline <- Multiplexer - ...
R \ Adresse n
A
M -> Daten-Pipeline -> packed mask and shift
Was genau hast du denn nicht verstanden?Alles.
Ich will viele Kerne auf wenig Chipfläche bringen.Okay, so weit so gut.
Diese sollen selbst parallel auf einem Branch rechnen können.Branch von was? Und was meinst Du mit rechnen? Also was genau ist der gewünschte Funktionsumfang eines Kerns? Sollen das normale General-Purpose-CPU-Kerne werden?
Jeder Kern soll mit 50-80% der Chipfläche aus cache bestehenDas ergibt sich von allein wenn die Caches groß genug sind. Man sagt nicht umsonst das Intel der größte SRAM-Hersteller auf diesem Planeten ist.
und diesen unabhängig von anderen Kernen mit dem DRAM synchronisieren können.Das erfordert ein wirklich sehr gutes Kohärenz-Protokoll und sowas ist wahrlich keine einfache Aufgabe. Du kannst ja mal probieren die große Version der HyperTransport-Spezifikation (also die Version die Kohärenz beinhaltet und leider nicht frei verfügbar ist) zu bekommen, falls Du das schaffst hast Du auf jeden Fall guten Lesestoff (HyperTransport soll in diesem Bereich recht gut sein, vor allem die High-Node-Count-Version (http://www.hypertransport.org/default.cfm?page=HighNodeCountSpecification)), für eine Kopie wäre ich sehr dankbar. Ich selber möchte auch SMP (ccNUMA) erreichen und das dürfte eine der härtesten Nüssen sein die ich für mein Projekt knacken muss.
Es geht mir erstmal nur um die reine MachbarkeitMachbar ist das bestimmt, die Frage ist ob Du es schaffst alle Detail-Probleme auf dem Weg dahin zu lösen.
Kann man SRAM-Cache mit der doppelten Schaltgeschindigkeit eines Transistors takten?Eher nicht. Eine Taktperiode sollte mindestens 5 bis 10 Transistor-Schaltzeiten + die zugehörigen Signallaufzeiten zwischen den Transistoren umfassen damit die Logik auch wenigstens ein klein wenig sinnvolle Arbeit pro Takt verrichten kann. Der L1-Cache in aktuellen Intel-CPUs hat etwa 3 bis 4 Takte Latenz (was etwa 1.5 bis 2.0 ns entspricht) und die ergibt sich wimre im wesentlichen aus den Signallaufzeiten (da selbst der kleine L1-Cache in Relation zur Ausbreitungsgeschwindigkeit bereits eine recht große Fläche belegt) und weniger aus der Schaltgeschwindigkeit der Transistoren. Aktuelle L2-Caches (bei AMD und Intel) liegen so im Bereich von 20 bis 30 Takten. Dazu kommt das man bei jedem Zugriff auf eine Cache-Line auch den zugehörigen Tag aktualisieren muss (falls man eine bessere Ersetzungsstrategie als Round-Robin verwenden will).
mit der doppelten Schaltgeschindigkeit eines Transistors takten?Was glaubst Du mit was für Elementen das Taktsignal auf einem CMOS-IC verteilt/verstärkt wird? Selbst eine halbe Taktperiode muss mindestens ein vielfaches der normalen Transistor-Schaltzeit betragen, pro Takt muss ein Transistor zum Takt-Transport ja immer genau zwei mal schalten.
Wieviel Transistoren wird ein SRT-Dividierer mit 128 bit in etwa verbrauchen?Ich vermute mal das es kaum mehr als 100 Menschen auf diesem Planeten gibt die dazu wirklich echte Zahlen nennen können. Auf was beziehen sich die 128 Bit, auf den Dividend oder den Divisor?
Ich will mit einem Kern insgesamt unter 1m Transistoren kommen, zzgl. Cache.Dann dürfte nicht sehr viel mehr als ein besserer 486 bei raus kommen (wobei ich jetzt nicht weiß wie viele von dessen gut 1M-Transistoren auf den Cache entfallen), falls Du ein schlankes RISC-Design nimmst sollte aber zumindest eine gewisse Menge an Instruction-Level-Parallelism und eventuell sogar Superscalar-Execution möglich sein. Der 486 hatte übrigens keinen SRT-Dividierer.
Der L1-Cache in aktuellen Intel-CPUs hat etwa 3 bis 4 Takte Latenz (was etwa 1.5 bis 2.0 ns entspricht) und die ergibt sich wimre im wesentlichen aus den Signallaufzeiten (da selbst der kleine L1-Cache in Relation zur Ausbreitungsgeschwindigkeit bereits eine recht große Fläche belegt) und weniger aus der Schaltgeschwindigkeit der Transistoren.
Die Frage ist eher, wie Groß die Toleranzen der Signallaufzeiten sind.Uns wurde in der Vorlesung gesagt, dass die Toleranzen ne Größenordnung mehr sind als die eigentlichen Signallaufzeiten, je nachdem, wie das Synthese-Tool das grad aufbaut.
Ist das der Turbo bei x86-CPUs?Der Turbo-Modus bei Intel-CPUs (ob AMD etwas ähnliches hat, weiß ich nicht) hält alle Kerne bis auf einen an, der dann dafür höher getaktet wird. Könnte man theoretisch mit allen Kernen machen, aber dann ist die Verlustleistung so hoch, dass man die Wärme nicht mehr wegkühlen kann.
Und ja, ich lese alle Beiträge sehr sorgfältig, im Rahmen der Möglickeiten auf dem kleinen Android-Display.Sicher? Dann vermute ich mal das Android keine Fragezeichen darstellen kann, Du hast genau 12 Stück davon in meinen Beiträgen komplett übersehen und nur dieses eine beachtet.
Dann vermute ich mal das Android keine Fragezeichen darstellen kannEines letzten Dinge, die noch funktionieren.
Soso, da bin ich aber froh das ich keines dieser smarten Phönchen habe.Dann vermute ich mal das Android keine Fragezeichen darstellen kannEines letzten Dinge, die noch funktionieren.
128 bit Dividend, Divisor gerne weniger.Aber die Größe des Divisors gibt vor wie viel Logik die Divisions-HW kostet, der Divisor bestimmt die Breite der Subtraktionen/Vergleiche und der Dividend gibt nur vor wie breit das Shift-Register ist von dem immer ein kleiner Teil (der so groß ist wie der Divisor) bearbeitet wird. Für meine CPU hab ich mir überlegt das ich zwei leicht unterschiedliche Divisionseinheiten haben will (wenn im FPGA noch Platz ist): eine mit voller Breite 128:64 = 64,64 (Dividend:Divisior = Quotient,Rest) die immer nur ein Bit pro Takt errechnet und eine mit reduziertem Divisor 128:24 = 64,24 die immer 4 Bit pro Takt errechnet. Da ich in der Slow-ALU eh mindestens einen Takt zum Vorbereiten der Parameter und selektieren der zuständigen Logik benötige kann ich dabei auch prüfen wie viele Bits im Divisor tatsächlich benutzt werden und damit sicher einen Großteil der Divisionen erheblich beschleunigen.
Ein Branch des Ausführungs-Graphen. Also alles zwischen Bedingungen und Schleifen.Aha, Dir geht es also um Loop-Unrolling in Hardware. Das schätze ich mal als relativ Aufwendig ein da dabei die HW selbstständig ermitteln muss welche Variablen (Register) bei jeder Iteration neu benutzt werden (also parallelisiert werden können) und welche Variablen den Schleifenzähler darstellen (das muss nicht nur eine Variable sein und die muss auch nicht simpel Inkrementiert/Dekrementiert werden) und welche Variablen für alle Iterationen immer Konstant sind. Dazu kommt das die Hardware zuverlässig erkennen können muss welche Schleifen nicht parallelisierbar sind (selbst wenn die Abhängigkeit zwischen den Iterationen nicht linear ist und nur über den Speicher geht), schau Dir dazu mal den RC4-Verschlüsselungsalgorithmus an (das ist ein tolles Beispiel für sehr simplen Code bei dem man trotzdem nicht erkennen kann welche Iteration von welcher abhängt). Ich vermute mal das es einfacher ist sowas dem Compiler zu überlassen und dafür ein bisschen mehr Code-Cache zu haben (damit die Schleifen auch größer sein dürfen). Beim Pentium 4 war Loop-Unrolling extrem effektiv weil diese CPU relativ viele Befehle aktiv haben kann und der L1-Code-Cache hinter dem Decoder sitzt (die damaligen Intel-Compiler haben das Loop-Unrolling auch bis ins extrem getrieben und damit auch einen echten Vorteil gegenüber dem gcc raus geholt).
Jeder Kern ist für allgemeine Zwecke vorgesehen. Es sollen nur wenige Instruktionen angeboten werden, darunter Integer-Arithmetik, Bit-Manipulation und Vergleiche (alles gepackt in 8, 16, 32, 64 oder 128 bit), dazu Bedingungen und SchleifenAlso RISC mit SIMD.
anstelle von Sprungbefehlen.Um allgemeine Sprungbefehle wirst Du nicht umhin kommen, überlege mal wie Du ein switch-Konstrukt umsetzen möchtest.
Vergleiche werden im Register gespeichert. Es gibt überhaupt keine Flags.Also sowas wie Alpha, der hat auch keine Flags und prüft bei bedingten Befehlen direkt den Inhalt eines beliebigen Registers ob dies bestimmten Kriterien entspricht. Hast Du Dir schon mal überlegt was für Nachteile dieses Konzept haben kann? Meiner persönlichen Meinung nach ist es effektiver den Vergleich und den bedingten Sprung in einen Befehl zu vereinen also einen bedingten Sprung bauen der das Verhältnis zwischen 2 beliebigen Registern prüft (das geht sogar für Floating-Point ganz einfach), solange Du genug Bits in den Befehlen hast sollte das kein Problem sein (das Sprungziel muss auch nicht allzu viele Bits haben da bedingte Sprünge üblicherweise nur kurze Strecken springen).
Bedingungen und Schleifen stellen nicht parallelisierbare Befehle dar.Das ist aber doof, Sprünge stellen ein interessantes Betätigungsfeld für spekulative Ausführung dar.