Benchmark Algorythmus

[theomega]

Hallo Leute,
ich suche eine Berechnung die extrem CPU lastig ist, aber nicht stark auf den RAM geht. Je simpler der Algorythmus desto besser, es soll nacher ein Benchmark für bestimmte Prozessoren werden, also fertige Programme bringen mir nichts. Ob delphi oder anderes ist mir egal, wird nacher eher nicht in Delphi gemacht werden können.
Also, wer kann was bieten? Was ist mit Primzahlentests? Sieb des Archimedes z.b. geht extrem auf den Ram, also nichts für mich!

Danke für ein Paar hilfen!
TO

[Dax]

Das hier müsste extrem auf die CPU, aber kaum aufs RAM gehen:

Delphi-Quellcode:

var i: Integer;
begin
  i := 10;
  Randomize;
  while SomeCondition do
    i := (i + Random(i) * Random(i)) mod High(Integer);
end;

[theomega]

oki, ich muß noch folgendes sagen: es sollten auf Zeit reproduzierbare ergebnisse sein, so dass ich sagen kann, CPU 1 bekommt das in x sekunden hin und CPU 2 in y sekunden. Ich geh doch recht in der Annahme, dass sobald Zufall ins Spiel kommt die Sache und damit auch die Ergebnisse recht zufällig werden und meinen Anforderungen nicht entsprechen?

[Dax]

Der Zufallsanteil darin ist nur gut, um die CPU auszulasten, sie braucht trotzdem ungefähr gleich lange für N Iterationen dieser Schleife. Für Benchmarks, die Zeit messen, nimmst du eben eine for-Schleife mit z.B. 10.000.000 Iterationen und misst die Zeit- ;-)

[MisterNiceGuy]

Damm probiers mal mit Fibonacci ;) Müsste irgendwo inner Math.pas drinstehen, das geht auch ganzschön auf die CPU!

[theomega]

fibonacci ist nicht geeignet, weil die zahlen zu schnell zu groß werden, mir stehen auf den zu verwendeten Prozessoren nur max. 32bit Interger zur verfügung. Trotzdem danke, aber hat noch jemand noch gute Vorschläge?

[theomega]

*Push* niemand ne Idee, also eine ohne Random und wo man mit 32 bit auskommt?

[Alexander]

Was mir gerade so einfällt ist der BubbleSort. Aber so Rechenlastig ist der nun auch wieder nicht...

[tommie-lie]

Was hast du denn gegen Dax' Vorschlag?
Wenn auf der Zielplattform ein Zufallsgenerator zur Verfügung steht, der die Zufallszahlen synchron erzeugen kann (also für jede Zahl die gleiche Zeit braucht, z.B. einen Takt, weil er sie aus einem Pool holt), dann ist gegen sowas eigentlich nichts einzuwenden. Du rechnest ja nur mit den Random-Werten, und eine Integer-Berechnung benötigt immer gleich viele Taktzyklen, egal ob von den 32bit nun sieben oder siebzehn auf 1 gesetzt sind.

Wo wir aber auch schon bei der nächsten Frage sind: Was für eine Architektur isses denn? Du fragst uns nach einem Rechenlastigen Benchmark für eine spezialisierte Architektur, verrätst aber nicht, welche es ist. Wenn die Architektur z.B. massiv viele Pipelines einsetzt, sollte man versuchen alle Pipelines um jeden Preis auszulasten und viele Sprünge zu vermeiden, damit nicht jedesmal die Pipelines neu befüttert werden müssen. Hat der Prozessor nur eine Pipeline, spielt das natürlich keine Rolle und man kann sich auch auf Schleifen konzentrieren, sofern die Architektur keine geisteskranke Sprungvorhersage hat. Hat sie eine, muss man sich nach ihr richten. Und wie schnell ist das Speicherinterface im Vergleich zum Prozessor? Darf man den Speicher ruhig für Daten benutzen, oder ist man auf die zahl der Register beschränkt? Wie sieht's mit synchronem Cache aus? Wie groß ist er? Gibt's überhaupt welchen, oder gibt's nur langsamer getakteten Cache? Wieviel langsamer getaktet ist der?

U.u. müsste man direkt Assembler-Beispiele nehmen, denn man weiß sonst nie, welche Variablen der Compiler auf den Stack legt, und wie groß der Stack sein darf, damit er in den schnelleren Cache ausgelagert werden kann.

[ibp]

Zitat:

Zitat von theomega

*Push* niemand ne Idee, also eine ohne Random und wo man mit 32 bit auskommt?

schreib dir doch eine eigene berechnungsmethode!

oder

ping doch mal hagen [negaH] an vielleicht hat der eine Idee!

[tommie-lie]

Zitat:

Zitat von ibp

schreib dir doch eine eigene berechnungsmethode!

Sein Problem ist ja anscheinend der Mangel an Kreativität, genau das zu tun ;-)

Zitat:

Zitat von ibp

ping doch mal hagen [negaH] an vielleicht hat der eine Idee!

Zitat:

C:\>ping hagen [negaH]
Ping-Anforderung konnte Host "hagen" nicht finden. Überprüfen Sie den Namen, und versuchen Sie es erneut.

Hmm... also irgendwas stimmt da nicht, er wird doch nicht etwa tot sein? :gruebel:


Edit, die 19823.: Aaaargh, ich hasse meinen Browser-Cache! :wall:

[Binärbaum]

Du hattest doch schon sowas wie Primzahlentest vorgeschlagen. Warum nimmst du das dann nicht auch?

Delphi-Quellcode:

function Ist_Prim(n: LongWord): Boolean;
//LongWord ist ein vorzeichenloser 32bit-Integertyp
var i: Longword;
begin
  if n>=2 then Result:= True
    else Result:= False;
  i:= 2;
  while (Result and (i<=n-1)) do begin
    Result:= ((n mod i)<>0);
    i:= i+1;
  end;//while
end;

(ja, ich weiß, die Funktion könnte man noch deutlich optimieren, aber da es hier ja darum geht, eine gewisse Auslastung zu erreichen, erspare ich mir das mal.)

Diese Funktion kann man dann in einer for-Schleife laufen lassen und mit GetTickCount die Zeit nehmen:

Delphi-Quellcode:

var x, t: LongWord;
begin
  t:= GetTickCount;//Zeit nehmen
  for x:= 2 to 1000000 do Ist_Prim(x);
  t:= GetTickCount -t;
  ShowMessage('Dauer: '+IntToStr(t)+' ms');
end;

MfG
Binärbaum

[3_of_8]

Man kann auch einfach Integeradditionen/divisionen/potenzen/wurzeln bzw. das gleiche mit Float.

Einfach, aber es funktioniert.

[Binärbaum]

Zitat:

Zitat von 3_of_8

Man kann auch einfach Integeradditionen/divisionen/potenzen/wurzeln bzw. das gleiche mit Float.

Einfach, aber es funktioniert.

Ja, aber laut Threadersteller sollten es nur 32bit-Integer sein. Und Float-Typen (z.B. Real (48bit)) gehören leider nicht dazu. :wink:
Und Wurzeln sind in den seltensten Fällen auch wieder Integer-Werte (z.B. bei sqrt(2)= 1.41....).
Wer lesen kann ist halt klar im Vorteil.

[3_of_8]

Ich kann ja nicht wissen, dass Floats 48-Bit Variablen sind, ich bin schließlich doch ein Newbie und habe keine Ahnung von den Hintergründen.

[tommie-lie]

Zitat:

Zitat von Binärbaum

Ja, aber laut Threadersteller sollten es nur 32bit-Integer sein. Und Float-Typen (z.B. Real (48bit)) gehören leider nicht dazu. :wink:

Er sagte, es stehen im vom Range her nur 32bit für Integer zur Verfügung, weswegen er nicht mit großen Zahlen arbeiten kann. Außerdem, man soll es nicht für möglich halten, gibt es auch 32bit Floats, und wenn man die FPU in Software emuliert :zwinker:
Solange der OP nichts über die Architektur verrät, können wir hier weiter im Dunkeln tappen und irgendwelche Berechnungen in die Luft werfen, Benchmarks sind und bleiben ziemlich oft Architekturspezifisch. Wenn ich 3GB Cache habe, kann mir der Speicherzugriff egal sein, da ich praktisch nie auf den langsamen RAM zugreife. In einem solchen Fall kann ich auch schonmal 10000x10000 Matrizen durch den Rechner jagen. Wenn ich hingegen mehrere Dutzend Pipelines habe, muss ich dafür sorgen, daß der Code so aussieht, daß auch jede Pipeline sinnvoll benutzt werden kann.
Aber das schrob ich ja alles schon...

[Binärbaum]

Zitat:

Zitat von 3_of_8

Ich kann ja nicht wissen, dass Floats 48-Bit Variablen sind, ich bin schließlich doch ein Newbie und habe keine Ahnung von den Hintergründen.

Kann ja passieren, dass man nicht weiß, wie groß ein Typ ist (ich behaupte, dass es selbst den erfahrenen Programmierern manchmal so geht :wink: ). Doch das ist auch nicht unbedingt das, was ich meinte.
Man könnte auch statt Real den Typ Single verwenden. Der wäre dann 32 bit groß. Allerdings ist ein Float-/ Real-Typ doch auch was anderes als ein Ganzzahl-/Integer-Typ. Schleißlich kann man mit einem Integer keine Werte wie 1234.56789 darstellen. Und das könnte bzw. sollte man doch wissen (auch wenn man sich noch als Newbie einstuft).

MfG
Binärbaum

[3_of_8]

Natürlich weiß ich, was ein Float ist. Ich habe ja auch gesagt, man kann die Berechnung sowohl mit Integern als auch mit Floats machen, was dann natürlich auch unterschiedliche Ergebnisse bringt, denn Floats sind natürlich deutlich langsamer. Ich habe nie behauptet, dass es das gleiche ist, was man nimmt.

[yankee]

WARUM nicht einfach sowas:

Delphi-Quellcode:

function benchmark:integer; //gibt die dauer in ms zurück
var i,temp:integer;
begin
result :=getTickCount();
for i:=0 to 30000 do
begin
    temp :=round(i+sqr(i)-sqrt(i)*i+3/i);
end;
result :=result -getTickCount();
end;

Oder irgend so einen Schwaschsinn. Du kannst wahrscheinlich auch einfach konstante Werte nehmen... Ich weiß nur nicht, ob der Compiler dann irgendwelche Optimierungen vornimmt, die ganz überl sind...

[3_of_8]

Die Compileroptimierungen kann man doch ausschalten, oder? :gruebel:

Und @Binärbaum: Vielleicht sollten wir aufhören mit diesem *Streit*. Sonst kommt noch ein Mod und schließt den Thread oder sowas in der Art.

[Binärbaum]

Zitat:

Zitat von yankee

...
Oder irgend so einen Schwaschsinn. Du kannst wahrscheinlich auch einfach konstante Werte nehmen... Ich weiß nur nicht, ob der Compiler dann irgendwelche Optimierungen vornimmt, die ganz überl sind...

Auch eine Möglichkeit. Aber wenn man sowas macht, wird der Compiler IMHO erkennen, dass nur das letzte Ergebnis, welches in temp gespeichert wird, auch relevant ist. Ich denk mal, das dort die Compileroptimierung greift.
Oder irre ich mich da? (Bin mir auch nicht so sicher :| )

[yankee]

ich gaube {$OPTIMAZIATION OFF} oder so... ich weiß es aber nicht so genau. In jedem Fall wäre das Problem damit gelöst...

[tommie-lie]

Zitat:

Zitat von yankee

WARUM nicht einfach sowas:

Weil auch dabei Fließkommazahlen benötigt werden, die vielleicht nicht zur Verfügung stehen.
Und ohne Compileroptimierung weiß man auch nicht, was der Compiler unoptimiert draus macht, wenn man den Assemblercode nicht selber schreibt, sodaß ein derartiges Benachmark auch wieder nicht repräsentativ für optimierte Programme ist.
Dax' Beispiel wäre an sich schon nicht schlecht, wenn der Zufallsgenerator schnell und gleichmäßig genug ist.

Den Hinweis, daß man in allen anderen Fällen mehr über das System kennen muss, spare ich mir hier. Hoppala :mrgreen:

[theomega]

das thema ist recht alt und ich hatte die hoffnung schon aufgegeben einen ordentlichen Algorithmus zu finden. Es geht bei den Benchmarks um sehr verschiedene Prozessoren, angefangen von standart i386 über xscales bis hin zu kleinen microcontrollern. Deshalb sollen auch möglichst einfache Zahlen verwendet werden damit die grundbedingungen für alle cpus möglichst gleich ist.

Danke
TO

[Binärbaum]

Zitat:

Zitat von theomega

Es geht bei den Benchmarks um sehr verschiedene Prozessoren, angefangen von standart i386 über xscales bis hin zu kleinen microcontrollern. Deshalb sollen auch möglichst einfache Zahlen verwendet werden damit die grundbedingungen für alle cpus möglichst gleich ist.

Danke
TO

Wie schon gesagt: versuchs mit einem Primzahlentest für ein vorher festgelegte Anzahl von Zahlen. Dazu braucht man nur Ganzzahlen, und die sollten doch auf jedem Prozessor darstellbar sein.