In jenen Fällen, wo es nicht möglich ist, eine präzise Aufwandsermittlung durch "Abzählung" der zu erwartenden Operationen durchzuführen, besteht die Möglichkeit, während der Ausführung eines Programms die Anzahl der verschiedenen Operationen mitzuzählen und damit den Arbeitsaufwand eines bestimmten Programms bei der Lösung eines speziellen Problems auf einem konkreten Computersystem exakt festzustellen. Solche experimentellen Aufwandsermittlungen ermöglichen die sogenannten Software- und Hardwaremonitore (Jain).
In der Praxis der Numerischen Datenverarbeitung wird der Aufwand, den ein Programm für die Lösung eines Problems der Größe n benötigt, oft durch die Anzahl der erforderlichen Gleitpunktoperationen charakterisiert. Die Funktion K(n), die jeder Problemgröße n die Anzahl der Gleitpunktoperationen des Algorithmus zuordnet, wird als Rechen-Komplexität des Algorithmus bezeichnet. Es sind aber weder die verrichtete Arbeit noch die tatsächliche Zeitdauer der verschiedenen Gleitpunktoperationen gleich groß.
Außer dem Umstand, daß oft auch andere Operationen (z.B. Anzahl und Art der Speicherzugriffe) bezüglich ihres Zeitaufwandes eine Rolle spielen, muß berücksichtigt werden, daß auf verschiedenen Computersystemen Gleitpunktoperationen in unterschiedlicher Form vorhanden sind. Beispielsweise sind auf vielen Mikroprozessoren neben den Instruktionen für die arithmetischen Operationen + - . / eigene Instruktionen für die Berechnung der Quadratwurzel-, Sinus- und Kosinusfunktion etc. vorhanden. Solche Funktionsaufrufe stellen aber erheblich mehr Arbeit dar und benötigen auch deutlich mehr Zeit als die Ausführung einer Gleitpunktaddition oder -multiplikation.
Beispiele (Quadratwurzel, Multiply and Add)
Die im Instruktionssatz eines Prozessors verfügbaren arithmetischen Gleitpunktopertionen sind - im Gegensatz zu den vereinfachenden Annahmen z.B. des RAM-Modells - nicht homogen bezüglich ihres Zeitaufwandes; so benötigen z.B. Gleitpunktadditionen und -Multiplikationen meist deutlich weniger Taktzyklen als Gleitpunktdivisionen. Diese Tatsache darf sowohl bei der Aufwandsermittlung von Algorithmen als auch bei der empirischen Leistungsbewertung von Computersystemen nicht vernachlässigt werden (vgl. Abschnitt 2.5).
Für eine einfachere und einheitliche Aufwandsbeurteilung werden gelegentlich normalisierte Gleitpunktoperationen verwendet. Dabei wird jede Gleitpunktoperation gewichtet gezählt, z.B. mit der Anzahl an Taktzyklen, die sie benötigt.
Folgende Normalisierung des Aufwands ist gebräuchlich(Addison et al.):
| Gleitpunktoperation | Gewichtung |
|---|---|
| Addition, Subtraktion, Multiplikation | 1 flop |
| Division, Quadratwurzel | 4 flop |
| Exponentialfunktion, Winkelfunktionen | 8 flop |
Der auf diese Art ermittelte Wert für die Anzahl der Gleitpunktoperationen ist zwar unabhängig von der Art der auftretenden Gleitpunktoperationen, er ist allerdings nicht unabhängig von den Hardware-Besonderheiten des Prozessors. Falls z.B. der Instruktionssatz zusammengesetzte Instruktionen wie die bereits erwähnte Floating-Point-Multiply-and-Add-Instruktion enthält, muß das in der Normalisierung ebenfalls berücksichtig werden.
| Kadd(n) | = | n3/3 + n2/2 - 5n/6 | Additionen, |
| Kmult(n) | = | n3/3 + n2/2 - 5n/6 | Multiplikationen und |
| Kdiv(n) | = | n2/2 + n/2 | Divisionen. |
Beispiel (Multiply and Add) POWER- und POWER2-Prozessoren besitzen eine Instruktion, die eine Multiplikation und eine davon abhängige Addition - die Operation (a.b) + c - in derselben Zeit wie eine einzelne Gleitpunktaddition bzw. -Multiplikation ausführen kann ( Floating Point Multiply and Add). Ein weiterer Vorteil dieser zusammengesetzten Instruktion ist, daß das Zwischenergebnis nicht gerundet wird und daher insgesamt nur ein Rundungsfehler auftritt (White, Dhawan). zurück