Flop - Dauer

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
Flop - Dauer
Hallöchen,

wie lange braucht ein Rechner denn um einen flop durchzuführen. Würde gerne bei Laufzeiten O(n), O(n²) etc. mal ausrechen, wie lange das dann für bestimmtes n tatsächlich dauert.

Als Prozessor vielleicht die Pentium I - IV und dann was aktuelles (Dual Core ?)

Bei Dual Core auch die Frage, ob die im Vergleich zu den anderen "parallel" rechnen können.

Grüße Wink

P.S: Ja, ich hab von Hardware noch weniger Plan als von anderen Dingen. Augenzwinkern
AD Auf diesen Beitrag antworten »

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

Die angegebenen Werte sind aber sicher als Obergrenzen aufzufassen, denn sie beinhalten hochoptimierten Code sowie gleichmäßig hohe Auslastung aller Kerne (bei Mehrkernprozessoren). Also wenn du nur eine Single-Thread-Anwendung auf einem aktuellen Core2-System laufen hast, wirst du kaum über 6 GFLOPS kommen.
tigerbine Auf diesen Beitrag antworten »

Danke Arthur. Mir geht es grob gesprochen um eine Aussage darüber, ab welcher Größe von n eine Verbesserung der Laufzeit eines Algorithmus im "Laufe der Zeit" sich deutlich bemerkbar macht. Und aktuell eben, welche Verbesserungen einen wirklichen Zeitvorteil bringen oder ob es eher nur ein Sieg auf dem Papier ist.
tigerbine Auf diesen Beitrag antworten »

Könnte ich dann grob folgendes sagen:



Mit dem Standard von 09 könnte man ein Algorithmus mit , z.B. Gauss-Elimination, für in einer Sekunde durchführen. Dafür hätte man in den vorherigen Jahren 2.6sek, 10.6sek, ~1min, ~1h gebraucht.

Ich hab die Superrechner nun extra mal ausgelassen in der naiven Annahme, dass Programme für Probleme wie hier auch auf Standardmaschinen bearbeitet werden.

Wann würde man denn dann sagen, dass n groß ist? ?
AD Auf diesen Beitrag antworten »

Sofern du es mit massiv parallelisierbarem Code zu tun hast, solltest du auch die folgende seit einiger Zeit im PC-Bereich zu beobachtende Entwicklung beachten:

Die Nutzung der GPU (Prozessor auf Grafikkarte) für numerische Berechnungen.

Da sind schon jetzt mit den Spitzenmodellen von ATI und NVidia mehrere hundert GFLOPS drin, allerdings ist da die effiziente Programmierung noch viel komplizierter ... Stichworte: CUDA, Brook, DirectX 11 GPGPU
Airblader Auf diesen Beitrag antworten »

Edit: Quatsch hab ich geschrieben. Augenzwinkern

air
 
 
AD Auf diesen Beitrag antworten »

Bei genauerer Überlegung würde ich die obigen 0.008 GFLOPS = 8 MFLOPS für den 386DX33 ernsthaft anzweifeln: Diese CPU hatte überhaupt keine Floating-Point-Recheneinheit, das musste das also per Software emuliert werden, und da wurden bestimmt keine 8 Millionen pro Sekunde geschafft ... Ich schätze mal, in der Tabelle war das Gespann 386DX33/i387DX mit dem damals sündhaft teuren numerischen Coprozessor i387DX gemeint. Augenzwinkern
PrototypeX29A Auf diesen Beitrag antworten »

Zitat:

Mit dem Standard von 09 könnte man ein Algorithmus mit , z.B. Gauss-Elimination, für in einer Sekunde durchführen. Dafür hätte man in den vorherigen Jahren 2.6sek, 10.6sek, ~1min, ~1h gebraucht.


Aus der O-Notation kannst du keine Aussagen über die tatsächliche Geschwindigkeit ableiten.
Daß ein Algorithmus in liegt, bedeutet lediglich daß seine Laufzeit mit längerer Eingabe etwa kubisch wächst. Das könnten aber genausogut n^3 Sekunden oder n^3 Tage sein.

Die genaue Definition findet sich hier http://de.wikipedia.org/wiki/Landau-Symbole.

Proto
tigerbine Auf diesen Beitrag antworten »

Ich wollte eine grobe Überschlagsrechnung machen. Zähle ich die flops im Gaussalgorithmus, so ist der dominante Term n³. Daher habe ich dann eben die dritte Wurzel gezogen, um das n zu bestimmen. Wieso ist das nun falsch? verwirrt
PrototypeX29A Auf diesen Beitrag antworten »

Ich kenne jetzt den entsprechenden Algorithmus nicht, aber ein Typischer -Algorithmus sieht etwa so aus

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
x = 0
for a = 1 to n
  for b = 1 to n
    for c = 1 to n
       x+= a * b * c      // oder sonst irgendeine Berechnung mit konstanter Zeit
    next c
  next b
next a


Die innerste Schleife ist jetzt genau der Teil der n hoch 3 mal ausgeführt wird:
code:
1:
2:
3:
4:
5:
    for c = 1 to n
       x+= a * b * c      // oder sonst irgendeine Berechnung mit konstanter Zeit
    next c


Um die Tatsächlich Rechenzeit (der inneren Schleife) auszurechnen muß man mit der konstanten Abarbeitungszeit der inneren Schleife t multiplizieren.
Das werden je nach Komplexität der inneren Schleife einige Prozessorzyklen bis einige Bruchteile einer Sekunde sein. Und wenn in der inneren Schleife jetzt noch weiträumige Speicherzugriffe stattfinden kann das ganze noch deutlich länger dauern. Schließlich sind Speicherzugriffe oft der eigentlich Flaschenhals bei sowas.

Gruß,
Proto

PS: Du müsstest erst durch die Zahl der Flops pro (inneren) Schleifendurchlauf telien und anschliessend die dritte Wurzel nehmen um auf n zu kommen.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »