Betragsbildung, Multiplikation, Addition -> Dauer

[joe1234]

ja, für int Zahlen.

@HighLigerBiMBam
Wenn ich wüsste wie, hätte ich es gemacht!

[Paul Müller]

Bei der Betragsbildung benötigst du genau ein Takt. Dabei wird einfach nur das Vorzeichenbehaftete Bit entfernt.
Die Addition ist auch eine Grundoperation der CPU und benötigt deswegen auch nur ein Takt.
Bei der Multiplikation sieht es schon etwas komplizierter aus. Dafür gibt es verschiedene Ansätze und Umsetzungen. Prinzipiell ist eine Multiplikation aber aufwendiger.
Das ganze auszuprobieren ist übrigens völliger Unsinn. Du könntest maximal für ein bestimmtes Rechenwerk die Zyklen angeben. Die auch in der technischen Dokumentation stehen. Technisch gesehen kommst du aber nur bis zur Maschinenbefehl-Ebene runter. Dort kannst du die einzelnen Befehle adressieren. Wie viele Takte sie benötigen kannst du daraus aber nicht entnehmen. Bei modernen CPUs spielt das ganze auch nur eine Untergeordnete Rolle, weil dort verschiedene Stufen parallel abgearbeitet werden. Das heißt die effektive Ausführungszeit kann schwanken.

http://de.wikipedia.org/wiki/Zweierkomplement

[D-U-D-E]

Betrag läuft wahrscheinlich in konstanter Zeit.
Addition sollte linear in der Eingabelänge sein.
Multiplikation wohl quadratisch.
Genaue Anzahl der Schritte interessiert doch eh nicht :p

[HighLigerBiMBam]

Moderne CPU`s haben etwas, welches sich ALU tauft (arithmetic logical unit). Diese können tatsächlich jede Arithmetische oder Logische Funktion in einem Takt durchführen. Messen kannst du den Unterschied natürlich nicht, da das System die Rechenleistung auf alle laufenden Prozesse verteilt. Für Dezimalzahlen gibt es die FPU (floating point unit). Ältere CPU's (sehr alte!!!) ohne diese speziellen Rechenwerke benötigen durchaus mehrere Takte.

[SeppJ]

Paul Müller schrieb:

Die auch in der technischen Dokumentation stehen.

Genau. In diesem Sinne ein Beispiel:
support.amd.com/us/Processor_TechDocs/25112.PDF
Anahang C.

Und was sehen wir?
Fast nichts, da die Sache nicht so einfach ist, wie Paul Müller schon erläutert hat und wie das Dokument selbst beschreibt. Aber wenn man die Nebenbemerkungen und Sonderfälle ignoriert hat man ADD/SUB mit 1 Takt, MUL 3 und DIV 16 Takte. Für Integer. Und wie gesagt, nicht ganz so einfach, weil dies die Zeit ist, bis das Ergebnis feststeht, der Prozessor kann nebenher durchaus noch andere Sachen machen.

Bei anderen modernen Prozessoren dürfte dies nicht großartig anders sein.

[Paul Müller]

Hier kann man sich bei Intel ein wenig austoben:
http://www.intel.com/products/processor/manuals/index.htm

Genaue Anzahl der Schritte interessiert doch eh nicht :p

Bei einem Desktop-System nicht, nein. Es gibt aber noch andere Einsatzfälle, wo man genau wissen muss, wie lange etwas dauert.

Diese können tatsächlich jede Arithmetische oder Logische Funktion in einem Takt durchführen.

Das ist Unsinn. Operationen die aus mehren Teilergebnissen bestehen, brauchen immer mehrere Takte. Da kann man auch die Physik nicht austricksen.

Messen kannst du den Unterschied natürlich nicht, da das System die Rechenleistung auf alle laufenden Prozesse verteilt.

Hier widersprichst du dir. Auf der einen Seite behauptest du, die Operationen laufen in einem Zyklus. Und auf der anderen Seite willst du diesen Zyklus auf verschiedene Prozesse verteilen. Das hat aber mit BS-Prozessen überhaupt nichts zu tun. Auf der CPU läuft nur ein einziger Prozess und dass ist das BS. Die Verteilung der Ressourcen und welcher Befehl zu welchen Prozess des BS gehört, wird vom BS verwaltet. Damit hat die CPU nichts zu tun. Moderne CPUs bieten aber zusätzliche Funktionen um dem BS ein wenig Arbeit abnehmen zu können. Hier greift das Prinzip, welches du wahrscheinlich eigentlich meintest. Jede Operation der ALU ist Atomar. Hier hört der Einfluss auf, den du durch Software auf die CPU hast. Alternativ gibt es auch Prozessoren, auf denen man Befehle per Software programmieren kann. Diese haben aber auch eine gewisse Grundfunktionalität, aus der sich dann weitere Funktionen zusammen setzen lassen.

[HighLigerBiMBam]

Ich meinte, dass du beim Messen der Durchführungsdauer keinen Einfluss darauf hast, ob nun deine 10 additionen in 10 Takten durchgeführt werden, oder ob der Zeitschlitz gerade von einem anderen Prozess verwendet wird und deine Messung über 10 Takte benötigt. Ich habe mich definitiv nicht wiedersprochen, du wolltest nur irgendwas in meinen Satz hineininterpretieren.

Messen kannst du den Unterschied natürlich nicht, da das System die Rechenleistung auf alle laufenden Prozesse verteilt.

[Paul Müller]

Und das ist Quatsch. Um eine sinnvolle Messung durchführen zu können, braucht man einen deterministisch definierten Fall und keinen zufälligen Programmcode. Die Messungen kannst du dir aber trotzdem sparen, weil eine moderne CPU wie schon von mir geschrieben, mehrere parallele Verarbeitungsstufen hat. Und das hat nicht die Bohne etwas mit Prozessen zu tun.

[SeppJ]

@HighLigerBiMBam: Es gibt da den feinen, aber wichtigen, Unterschied zwischen Echtzeit und Prozesszeit. Theoretisch kannst du solche Benchmarks auch auf einem voll ausgelasteten System durchführen und bekommst trotzdem ein brauchbares Ergebnis.

Brauchbar mit der Einschränkung, dass man nicht wirklich auf die Taktzahl schließen kann, wegen der Parallelverarbeitung, aber es ist wirklich die Zeit die dein Programm gerechnet hat.

[Paul Müller]

Nicht nur das. Ein Betriebssystem mit seinen Unterprozessen ist in Wirklichkeit auch ein ganz anderes Programm, für die CPU, als wenn du nur eine simple Addition ausführen willst.
Nichtsdestotrotz, sind Addition und Betragsbildung bei Integern Befehle, die mit einem Takt auskommen. Weil das eine triviale Bitweise-Verknüpfung ist. Eine Multiplikation bedarf mehr Schritte. Für den Betrag gilt das selbe auch bei Float. Addition mit Float läuft bei ungleichen Exponenten auf eine zusätzliche Integer-Multiplikation hinaus. Die dadurch abgekürzt werden kann, indem die Basis zwei genutzt wird.
Optimierungen durch die Substitution von Befehlen, beispielsweise die Multiplikation mit 2, werden vom Compiler ausgeführt. Das sollte man nicht vergessen, da die Frage sich auf die Operationen in C bezog. Vorbereitende Schritte gehören in C bei den Anweisungen auch dazu. Deswegen bietet dir der Befehlssatz, auch mehrere ADD, etc. Befehle. Diese unterscheiden sich in ihrer Größe (Bitbreite) und in den Orten, wo die Werte hinterlegt sind. Für eine optimale Ausführung müssen die Werte in den Registern der CPU hinterlegt sein.

[Bashar]

Paul Müller schrieb:

Nichtsdestotrotz, sind Addition und Betragsbildung bei Integern Befehle, die mit einem Takt auskommen. Weil das eine triviale Bitweise-Verknüpfung ist.

Das ist mir neu. Wie soll diese Verknüpfung denn beim Betrag aussehen? Du schreibst weiter vorne was davon, das Vorzeichenbit einfach zu entfernen. Das funktioniert aber in der Zweierkomplementardarstellung nicht. Soweit ich sehe kommt man nicht drumherum, das Vorzeichen zu testen und dann bedingt zu negieren.

[Paul Müller]

Bashar schrieb:

Das funktioniert aber in der Zweierkomplementardarstellung nicht.

Doch gerade mit dieser funktioniert das. Schaue dir den verlinkten Wikipedia-Artikel an, wie das Zweierkomplement gebildet wird.

Beispiel:
-4 (4Bit)
1100 => -8 + 4
0100 =>      4

Bei Float gibt es für das Vorzeichen ein spezielles Bit.

[DirkB]

Addition, Betrag, Shift ist trivial. Das ist doch alles in Hardware 'gegossen'.

Die Takte die da nötig wären, sind die zum laden und speichern der Werte.
Da musste man sich zu Zeiten von Z80 und 6502 und kurz danach noch Gedanken machen. Der 486 hatte schon den Barrel Shifter, der auch 1 .. 31 Bit in einem Takt verschiebt.

[Bashar]

Paul Müller schrieb:

Bashar schrieb:

Das funktioniert aber in der Zweierkomplementardarstellung nicht.

Beispiel:
-4 (4Bit)
1100 => -8 + 4
0100 =>      4

Und -3 ist 1101, aber +3 ist 0011 und nicht 0101.

[Paul Müller]

Du hast Recht. Der Inhalt wird bitweise negiert und anschließend inkrementiert. Das wären im schlimmsten Fall also zwei Takte.

[DirkB]

Dazu kann man auch den Negierer und Addierer in Reihe schalten und hat gleich das richtige Ergebnis.

Das ist Hardware.

Denn die Gatter um so etwas zu machen hat man mittlerweile mehr als genug.

[SeppJ]

DirkB schrieb:

Dazu kann man auch den Negierer und Addierer in Reihe schalten und hat gleich das richtige Ergebnis.

Das ist Hardware.

Denn die Gatter um so etwas zu machen hat man mittlerweile mehr als genug.

Es gibt aber (bei x86) keinen Befehl zum Betrag nehmen, daher wird es wohl bei den 2 Takten bleiben. Wobei Wikipedia aber von 3 Takten spricht. Sicher, dass die vorgeschlagene Methode wasserdicht ist?

[Paul Müller]

Man wird wohl noch prüfen, ob die Zahl wirklich negativ ist. Letztendlich müsste der Compiler aber erkennen, dass du den Betrag haben willst, um die richtige Befehlsfolge zu bilden. Es sollte aber auch nicht so schwierig den C-Code zu evaluieren. Der Test auf kleiner Null sollte identisch sein. Es ist also nur wichtig den Faktor richtig zu interpretieren. Und da hab ich bei modernen Compilern eigentlich keine Zweifel.

[pointercrash**]

Paul Müller schrieb:

Man wird wohl noch prüfen, ob die Zahl wirklich negativ ist. Letztendlich müsste der Compiler aber erkennen, dass du den Betrag haben willst, um die richtige Befehlsfolge zu bilden. Es sollte aber auch nicht so schwierig den C-Code zu evaluieren. Der Test auf kleiner Null sollte identisch sein. Es ist also nur wichtig den Faktor richtig zu interpretieren. Und da hab ich bei modernen Compilern eigentlich keine Zweifel.

Klar erkennt der das. Ich hab' jetzt nur M16C angeguckt, da sind's nur zwei Befehle:

jpz    over  ;jump on plus or zero
        neg.w  R0    ;2s complement
over:
                     ; continue with sth. else

Ganz so deterministisch kann man das trotzdem nicht sehen, weil ich nicht weiß, ob für den Compiler R0 jetzt wirklich das wichtigste ist, vllt. mag er da lieber einen Schleifenzähler unterbringen, auf jeden Fall ist vorher ein move nötig, Umladen kostet unglaublich Zeit. Im Kern sind's aber nur zwei Befehle.
Weitere Unwägbarkeiten sind momentaner Stand der Pipes und was evtl. eine Branch Prediction machen würde. Das Odd/Even- Alignment spielt ggf. auch eine große Rolle.
Die Handreichung von Renesas für's branchen lautet:

2 cycles. If branched to label, the number of cycles above is increased by 2

Für das Komplement braucht die Registeradressierung nur 1 Cycle, bei indirekt- indiziert sind's 3 Cycles.
Aber was der Compiler hernimmt, ist schwer zu sagen, i.A. ist jedoch Optimierung von Hand nicht nötig.