Wieviel Takte braucht eine Addition/Multiplikation/Division?

[PatkIllA]

Ich lerne grade für "Theorie des Logikentwurf" unter anderem auch Schaltkreise für grundlegende Funktionen, da ist aber alles entweder auf einen Fan-In von 2 oder unendlich ausgelegt.
Jetzt interessiert mich, wie viele Takte ein realer Prozessor für welche Anweisung braucht. Gibt es da noch große Unterschiede zwischen den verschiedenen Plattformen und Architekturen?

[Gast]

du meinst wieviele takte "standarddatentypen" in den ALUs verbrauchen?

normalerweise 1 takt.

[BlackBirdSR]

Klar gibt es noch Unterschiede.

Der K8/K7/P3/PM/Conroe braucht für simple Integeranweisungen z.B add genau 1 Takt.
imul braucht je nach Version 3 (x86) oder 5 (AMD64) Takte beim Conroe
3 (x86) oder 4 (AMD64) beim K8
3 (x86) beim K7

Der PP970 (G5) braucht auch für die add 2 takte.

Beim Pentium-4 sieht das schon wieder anders aus.
Simple Integeranweisungen in einer ganz gewissen Reihenfolge können in einem halben Takt ausgeführt werden (Willamette/Northwood)
IMul braucht auf diesen Modellen allerdings 14 Takte und wurde erst mit Prescott beschleunigt.

Am besten du vergnügst dich hiermit:

Conroe Instruction-Latency Dump (http://aceshardware.com/forums/read_post.jsp?id=120057200&forumid=1)

Pentium-M (Yonah) Instruction-Latency Dump (http://aceshardware.com/forums/read_post.jsp?id=120057234&forumid=1)

K8 Instruction-Latency Dump (http://aceshardware.com/forums/read_post.jsp?id=120057235&forumid=1)

Prescott Instruction-Latency Dump (http://aceshardware.com/forums/read_post.jsp?id=120057201&forumid=1)

[Stone2001]

PatkIllA[/POST]']Jetzt interessiert mich, wie viele Takte ein realer Prozessor für welche Anweisung braucht. Gibt es da noch große Unterschiede zwischen den verschiedenen Plattformen und Architekturen?
Ja, es gibt Unterschied zwischen den Architekture, auch wenn sie inzwischen recht gering ausfallen dürften.
Vom Prinzip her, sollten (RISC-)CPUs alles in einem Taktzyklus erledigen können. Für Integerbearbeitung ist das auch meistens der Fall, Fließkommazahlen nicht.
BSP.: Für einen PowerPC 405-Kern daueren die meisten Operationen 1 Takt (add, mov, Schiebeoperationen, ...), einige 2 Takte (Ladeoperationen oder Sprünge) und die Integerdivision ganze 35 Takte.
Für aktuelle x86 Prozessoren habe ich leider keine Zahlen im Kopf. Aber auch hier dauern die Standardoperationen einen Takt und komplexere Operationen benötigen mehere Takte. Was noch hinzukommt, ist Pipelinig, so dass ein Befehl vom Holen bis zum Zurückschreiben des Ergebnisses eigentlich immer meherere Takte benötigen. ;)

[PatkIllA]

@Stone2001
mich hatte jetzt das pure Rechnen interessiert.

Fangen wir doch mal mit dem einfachen an.
Wie kann man denn in ein Takt addieren? Im Script ist eine Schaltung mit unbegrenztem Fan-In, die das in Tiefe 3 schafft, aber selbst das reicht ja nicht.

[Stone2001]

PatkIllA[/POST]']Fangen wir doch mal mit dem einfachen an.
Wie kann man denn in ein Takt addieren? Im Script ist eine Schaltung mit unbegrenztem Fan-In, die das in Tiefe 3 schafft, aber selbst das reicht ja nicht.
Ich kenne jetzt deine Schaltung nicht... .
Normalerweise gibt es zwei Versionen eines Addierers die üblicherweise eingesetz werden, einmal den Carry Riple Addierer und einmal den Carry Look Ahead Addierer (es gibt auch Mischformen).
Carry Riple sind einfach aus Halb und Volladdierern aufgebaut und sind deshalb recht klein, aber dadurch, dass erst der Übertrag berechnet werden muß auch recht langsam.
Bei Carry Look Ahead Addierer werden die Überträge durch kombinatorische Schaltungen berechnet, so dass man im Prinzip in einem Taktschritt eine Addition durchführen kann. (O(1) gegen O( n) bei CR für eine Addition mit n Bits)
Da aber die Schaltung um die Übertrag vom 31 zum 32 Bit zu berechnen recht groß ist, wird häufig eine Mischung zwischen CR und CLA eingesetzt, bei denen man z.B. 8 Bits mit CR addiert, um dann einen Übertrag zu bekommen damit man die nächsten 8 Bits berechnen kann usw. (Man kann die Schaltung dann auch so bauen, dass nur einmal ein 8 Bit Addierer benötigt wird, was wieder Fläche spart)

[PatkIllA]

Es geht um den Carry Look Ahead Addierer und der hat hier um Skript eine tiefe von 3. Das ist dann zwar auch noch O(1), aber halt nicht.
Hatte nämlich irgendwo gelesen, dass viele Operationen (inkl Addition) in einem Takt abgearbeitet werden und mich gefragt, wie das gehen soll.
Ich denke doch mal, dass Transistoren sparen heute nicht mehr unbedingt so wichtig ist wie die Geschwindigkeit.

[Stone2001]

Oki, so wie es aussieht, gibt es doch ein paar mehr Methoden eine Addition durchzuführen. Siehe: http://www.scit.wlv.ac.uk/~jphb/cp4040/rolandonotes/CSNDSP2002/Papers/A2/A2.1.pdf (zwar schon etwas älter, die Ergebnisse sollten sich aber übertragen lassen)
Auch bei IEEE lassen sich ein paar Papers über das Design eines High-Performance Adders finden, ich habe hier aber leider kein Zugang dafür.

[PatkIllA]

Im Skript gibt es noch
Conditional Sum Adder (Zumindest bei B2-Schaltkreisen der schnellste, logarithmische Tiefe)
Noch zwei weitere ohne Namen.
Ladner Fisher (Mischform der zwei vorhgehenden als guter Kompromiss zwischen Größe und Tiefe, ebenfalls logarithmische Tiefe)
Direkte Umsetzung der Schulmethode (kleinste Größe, dafür aber lineare Tiefe)
Und anscheinend gibt es ja noch ein paar mehr.
Und dann gibt es ja noch das Problem, dass ein Schaltkreis bei 32Bit ja noch anwendbar ist, aber einem bei 64Bit alles sprengt.
Und was ich halt immer noch überhaupt nicht sehen kann ist wie das ganze in einem Takt gehen soll.

[Stone2001]

PatkIllA[/POST]']Und was ich halt immer noch überhaupt nicht sehen kann ist wie das ganze in einem Takt gehen soll.
Warum soll es nicht in einem Takt gehen? Die Verzögerung auf dem kritischen Pfad muß nur kürzer sein als deine Zykluszeit! ;)

[PatkIllA]

dann müssen die Transitoren ja nochmal um ein Vielfaches schneller schalten, als die Taktfrequenz des Prozessors.
Ist das denn prinzipiell möglich, dass man da mehrere Stufen ungetaktet hintereinander packt?

[Stone2001]

PatkIllA[/POST]']dann müssen die Transitoren ja nochmal um ein Vielfaches schneller schalten, als die Taktfrequenz des Prozessors.
Ist das denn prinzipiell möglich, dass man da mehrere Stufen ungetaktet hintereinander packt?
Die Schaltzeiten von Gattern bewegen sich in der Größenordnung von ca. 100 Picosekunden. (für heutige Technologien sind wahrscheinlich noch schneller) Es ist also Problemlos möglich meherere Gatter hintereinander zu schalten und trotzdem die Zeitbedingungen einzuhalten.

[Coda]

PatkIllA[/POST]']dann müssen die Transitoren ja nochmal um ein Vielfaches schneller schalten, als die Taktfrequenz des Prozessors.
Richtig ;)

[smoe82]

Stone2001[/POST]']Die Schaltzeiten von Gattern bewegen sich in der Größenordnung von ca. 100 Picosekunden. (für heutige Technologien sind wahrscheinlich noch schneller) Es ist also Problemlos möglich meherere Gatter hintereinander zu schalten und trotzdem die Zeitbedingungen einzuhalten.

Ack!

Sonst wären die heutigen Prozessoren ja auch garnich so schnell. Wenn eine Information den Weg durch den Prozzi nimmt, dabei sagen wir 1Mio Transistoren benötigt werden und immer ein Takt für eine Transistorschaltung gebraucht würde, dann käme heute kein Prozzi aus den Puschen...

Eine ADD-Instruktion, welche nur einen Takt braucht, läßt sich ja auch nicht mit einem Transistor realisieren.

[PatkIllA]

Das mit dem Takt war mein Gedankenfehler. Wobei ich immer noch nicht weiss welche Schaltung jetzt in den aktuellen Prozessoren zum Einsatz kommt.

[Trap]

Im Software Optimization Guide for AMD Athlon™ 64 and AMD Opteron™ Processors auf http://developer.amd.com/documentation.aspx gibts ein extra Kapitel für instruction latencies.

Zu Implementierungdetails der ALU weiß ich nix konkretes, man darf dabei aber nicht vergessen, dass der Herstellungsprozess großen Einfluss hat und man nur für die eigene jetzige Technologie sagen kann welche Variante die schnellste ist.