Thema: binäre Division

[Dimension]

Zur Evaluierung und Ausarbeitung verschieder Ansätze für parallele Architekturen habe ich letztens ein paar Schaltungen für Addierer und Multiplizierer konstruiert. Kurz: Addierer mit n Chipfläche und in log(n) Zeit, sowie Multiplizierer mit 2n Fläche und 2log(n)+x Zeit für Bitbreite n=128 und kleinem x. Packed integer werden unterstützt.

Einen Multiplizierer mit log(n) Zeit und n^2 Platz habe ich verworfen.

Pro Instruktion sind mehrere Schaltungen parallel vorgesehen. Die Kosten berechne ich näherungsweise mit Taktzyklen * Transistoren(d.h. Chipfläche), würde aber kürzere Taktzyklen bevorzugen (Serialisierung).

Nun bin ich auf der Suche nach Ideen für die Division, welche über die schriftliche Division hinausgehen. In der englischen Wikipedia gibt es dazu den Artikel: Division algorithm, der sich mir jedoch nicht ganz erschließt.

Kennt jemand die Schaltungen in aktuellen Prozessoren von Intel/ARM/GraKas etc?

Ich habe bisher noch keinen guten EDA-Designer gefunden, die freien sind etwas unhandlich, oder es fehlt etwas, bspw Logikbausteine, Timing-Simulation oder Export in ein standardisiertes Format.

SORRY NOCH NICHT FERTIG... bis gleich : )

[chris12]

http://www.informatik.uni-ulm.de/ni/Lehre/SS01/TI/folien/arithC2.pdf

da hst du sogar ein blockschaltbild

[Dimension]

http://www.informatik.uni-ulm.de/ni/Lehre/SS01/TI/folien/arithC2.pdf

da hst du sogar ein blockschaltbild

Danke für den Link.

Mein Problem ist halt, dass die Subtraktionen voneinander abhängen und ich sie nicht parallelisieren kann. Um alle Fälle abzudecken bräuchte man jede Menge Register und Addierer.

Dieses SRT interessiert mich, da die Operanden zuvor analysiert werden.

Alles in allem scheint die Division eine teure Angelegenheit zu werden.

[erik.vikinger]

Hallo Dimension,


eine Frage vorweg: Integer oder Floating-Point?
Die Newton-Raphson Division ist eher für Floating-Point ausgelegt da das Reziprok des Divisors ja kleiner als 1.0 ist falls der Divisor größer 1.0 ist ansonsten natürlich umgedreht (Newton-Raphson kommt mit beidem gleich gut zurecht).

Falls Du Integer meinst lässt sich die schriftliche Division eigentlich ziemlich effizient (was Flächenbedarf pro Performance angeht) in Hardware implementieren.
Wichtig ist das Du im ersten Schritt alle Sonderfälle wegschaffst: Divisor==0 und Dividend<Divisor*2.
Außerdem musst Du zur Vorbereitung noch ermitteln um wie viele Bits der Divisor für den ersten Schritt tatsächlich nach links geshiftet werden muss (also wo wahrscheinlich das höchste Bit im Quotient steht).

Bei einer Hardwareumsetzung würde ich aber nicht den Divisor shiften sondern den Dividend.
Beschleunigen lässt sich das Ganze indem pro Takt nicht nur ein Bit vom Quotienten sondern z.B. 2 Bits ermittelt werden, dazu wird der Inhalt des aktuellen Fensters vom Dividend nicht nur mit dem Divisor verglichen sondern parallel auch mit Divisor*2 und Divisor*3 (das kostet nur 2 zusätzliche Vergleicher dafür musst Du alle anderen Shift-Operationen und auch die Vorbereitungsopertionen auf vielfache von 2 ausrichten). Wenn als zusätzliche Abbruchbedingung noch Dividend==0 (also den aktuellen bearbeiteten Dividend) vorhanden ist gehen auch Divisionen wie 100'000'000/10'000'000 in wenigen Takten durch.


Grüße
Erik

[erik.vikinger]

Hallo,

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.


Grüße
Erik

[Dimension]

Welches EDA-Tool ist am Besten geeignet für die Entwicklung von CMOS-ICs? Ich habe die Lite-Versionen von CircuitLogix und OrCAD probiert und zuvor KTechLab. KiCad und gEDA habe ich nicht zum Laufen gebracht.

Was mir gefehlt hat:
- Konstruktion in CMOS, also kein TTL
- Simulation mit analogen Signalen und Timing
- Setzen und Lesen von Buswerten, in hex, nicht binär
- Export nach EDIF

Gibt es dafür evtl etwas von den bekannten Anbietern von EDA-Software? Ich bin auch in der Lage mir eine Testversion zu laden.

[erik.vikinger]

Hallo,


ich schätze mal das Deine speziellen Fragen hier etwas ungünstig platziert sein könnten. Ich selber habe noch keine Designs für echte CMOS-ICs gemacht und kenne da auch kaum Leute, ich weiß aber aus zuverlässiger Quelle das die großen Firmen (wie AMD/Intel/NVidia/....) alle VHDL oder Verilog benutzen. Wenn Du bei ARM eine richtige Core-Lizenz kaufst (was sicher mindestens einen 7-stelligen Euro-Betrag erfordert) bekommst Du auch "nur" Verilog-Quell-Code geliefert (zusammen mit ein paar Scripten und etwas nicht synthesefähigen Verilog-Code (der eine fiktive Umgebung für den CPU-Core bildet) für eine Simulation in ModelSim). Hardware noch auf Basis von Gattern oder gar Transistoren zu designen ist seit mehr als 30 Jahren old-fashioned.

Falls Du keine eigene IC-Fertigung betreiben möchtest wird das ganze darauf hinauslaufen das Du Deinen Quell-Code (VHDL oder Verilog) mit den Tools des Auftragsfertigers (also einer Foundry wie TSMC) "synthetisierst" und dieses Ergebnis dann bei der Foundry selber noch auf das Silizium Layoutet (Placing und Routing) wird. Die Tools für FPGAs machen das ähnlich: die synthetisieren erst den Quell-Code indem die gewünschte Funktionalität auf die Logik-Elemente des FPGAs abgebildet wird (das Ergebnis ist hier manchmal eine Netzliste im EDIF-Format) und im zweiten Schritt werden diese Logik-Elemente dann im FPGA platziert und dazu die Verbindungen durch die im FPGA fest vorhandene aber flexible Verbindungsmatrix gerouted. Die Tools der Foundrys sind auch alle ganz speziell auf den konkreten Herstellungsprozess den diese Foundry benutzt optimiert, da gibt es keinerlei Kompatibilität und mWn auch nichts generisches. Die Portabilität entsteht durch passend geschriebenen VHDL/Verilog-Quell-Code (ich behaupte mal das man große Teile des VHDL-Codes den ich in den letzten 10 Jahren geschrieben hab auf allen FPGAs und auch auf echten CMOS-ICs mit verschiedenen Herstellungstechnologien umsetzen könnte, mit einer maximalen Taktrate die dem jeweiligen FPGA bzw. Herstellungsprozess entspricht).

Simuliert wird digitale Logik auch üblicherweise nicht auf analogem Niveau (wo jedes Signal echte Anstiegszeiten usw. hat) sondern einfach mit passenden Laufzeiten wo der neue Pegel einfach erst nach einer gewissen Zeit (inklusive Reserve für schwankende Temperaturen, Versorgungsspannungen und Fertigungstoleranzen) ankommt und vorher noch der alte Pegel anliegt. Falls Du wirklich vor hast mal etwas im Umfeld der IC-Entwicklung zu machen solltest Du Dir zuvor mal das Entwickeln mit FPGAs genauer anschauen, wenn Du möchtest kann ich dazu gerne noch ein paar Dinge schreiben.

Das man mit gEDA auch ICs designen kann ist mir neu, ich habe damit bisher nur normale Schaltungen und passende Leiterplatten gemacht, OrCAD fällt wimre in die selbe Kategorie, von allen anderen von Dir genannten Tools habe ich noch nie gehört (trotz fast 15 Jahren Berufserfahrung in der Industrie).


Was genau ist Dein eigentliches Ziel?


Grüße
Erik

[Dimension]

Mit welchem Programm kann man Logik-Gatter mit Timing simulieren? Ich will das design parallel zu VHDL per Schaltbild machen, da die Verdrahtung einen bedeutenden Anteil an der Gesamtfläche hat.

[erik.vikinger]

Hallo Dimension,

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 machen

Das 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 hat

Auf einem echten CMOS-IC belegt die Verdrahtung keine zusätzliche Fläche da diese über dem Silizium in mehreren Kupfer-Ebenen gemacht wird.
das Bild ist aus http://de.wikipedia.org/wiki/Integrierter_Schaltkreis#Front-End
Das eigentliche Silizium ist nur die untere Hälfte von FEOL und die Verdrahtung ist in BEOL.


Was genau ist Dein eigentliches Ziel?


Grüße
Erik

[Dimension]

da die Verdrahtung einen bedeutenden Anteil an der Gesamtfläche hat

Auf 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.

Im Schaltbild setze ich nur die (platz&zeit-)kritischen Instruktionen um. Das Prinzip an sich tut jedenfalls schon mal was es soll.

[erik.vikinger]

Hallo Dimension,

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.


Bitte beschriebe doch erst mal was Du eigentlich konkret erreichen willst.
Hast Du wirklich vor einen echten eigenen CMOS-IC zu entwickeln?


Grüße
Erik

[Dimension]

was mir gerade aufgefallen ist: die iterative funktion bringt nur eine transistorerparnis von etwa 25% (ich hatte mit min. 80% gerechnet) ohne da viel herumoptimieren zu wollen werde ich die schaltung für den addierer nun in ungetakteter logik machen.

und wens interessiert: die parallele architektur ist fürs loop unrolling und die spekulative ausführung gedacht. bei 8 128-bit addierern etwa 32 ausführungspfade mit 32 bit werten. oder halt 8 128 bit werte parallel. die compare- und bit-instruktionen können auch alle gepackt werden, fallen aber gegenüber multiplikation (2 einheiten) und division (1 einheit) sowieso nicht ins gewicht.

die parallelen kerne sind als ausweich-cache und für paralellisierbare ausführungspfade gedacht, sowie für unabhängige prozesse. jeweils eine kleine gruppe von kernen hat eine eigene anbindung an den hauptspeicher. die kommunikation zwischen prozessen geschieht über routing im speichercontroller, links zu benachbarten kernen und einen hochgetakteten message-bus.

[erik.vikinger]

sorry, aber ich habe kein einziges Wort verstanden,
Bitte erkläre doch erst mal in ein paar Sätzen was Du eigentlich willst (im Groben und dann auch im Feinen für Dein aktuelles Problem)

[Dimension]

Was genau hast du denn nicht verstanden?

Ich will viele Kerne auf wenig Chipfläche bringen. Diese sollen selbst parallel auf einem Branch rechnen können. Jeder Kern soll mit 50-80% der Chipfläche aus cache bestehen und diesen unabhängig von anderen Kernen mit dem DRAM synchronisieren können.

Es geht mir erstmal nur um die reine Machbarkeit, ob daraus mal ein CMOS gebastelt wird, oder ich mir selbst einen abgespeckten FPGA baue ist mir wurscht.

[Dimension]

Kann man SRAM-Cache mit der doppelten Schaltgeschindigkeit eines Transistors takten?

                                    / Adresse 1
S  <- Adress-Pipeline <- Multiplexer - ...
R                                   \ Adresse n
A
M  -> Daten-Pipeline -> packed mask and shift

[erik.vikinger]

Hallo,

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 bestehen

Das 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), 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 Machbarkeit

Machbar 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.


Grüße
Erik

[Dimension]

Aktualisierte Zahlen:

Für die Addiererstufen in 128 bit brauche ich, neben etwa 32 x128 Transistoren für die erste Stufe
bei ungetakteter Logik: 7 Stufen x 64 Funktionen x 4 Auswahl x 14 Transistoren = 25088 Transistoren
bei iterativer Auswahl: 128 Funktionen x 4 Register x 36 Transistoren = 18432 Transistoren

Wieviel Transistoren wird ein SRT-Dividierer mit 128 bit in etwa verbrauchen?

Ich will mit einem Kern insgesamt unter 1m Transistoren kommen, zzgl. Cache.

[erik.vikinger]

Hallo,


hast Du meine Beiträge eigentlich vollständig gelesen?

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.


Grüße
Erik

[Dimension]

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.

Sollte die Ausbreitungsgeschwindigkeit nicht bei grob 10 cm pro Takt bei 1 GHz sein?

Wenn
c ~ 3E8 m/s
vel ~ 0.3c = 1E8 m/s = 0.1 m/ns

Ich dachte natürlich an die doppelte Schaltdauer, also die halbe Schaltgeschwindigkeit! Eine Pipeline ohne Latches quasi, mit dem richtigen Align am Demultiplexer. Die Frage ist eher, wie Groß die Toleranzen der Signallaufzeiten sind.

Ist das der Turbo bei x86-CPUs?

Und ja, ich lese alle Beiträge sehr sorgfältig, im Rahmen der Möglickeiten auf dem kleinen Android-Display.

[Svenska]

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.

Gruß,
Svenska