Zufallsgenerator basierend auf Wolfram Rule 30

Martok · Verfasst: So 14.07.13 22:14

Hallo!

Diese Unit stellt einen Zufallszahlengenerator zur Verfügung, der auf dem zellulären Automaten der "Rule 30" basiert [MW], [WA], [NKS].

Dieser einfache Automat hat ein stark chaotisches Verhalten unabhängig von seinen initialen Bedingungen und eignet sich deswegen gut als schneller Zufallszahlengenerator. Aus seinem Zustand kann man einfach Bits extrahieren und daraus Ausgabedaten generieren. Genaueres im Kommentarblock in den Units.

Der generator ist Seedbar und nicht im klassischen Sinne ein kryptografisch sicherer Generator (CSPRNG) (auch wenn er die Kriterien tatsächlich formal erfüllt bzw. einfach modifiziert werden kann). Durch die hohe Sensitivität generiert jeder beliebige Ausgangszustand eine andere Sequenz, was durch das verwendete Sampling-Verfahren nochmal verstärkt wird. In der Standardkonfiguration existieren 2^4097 * 5 ~ 1E1234 mögliche Ketten, von denen durch die Art des Seedens allerding nur 2^64 ~ 1.8E19 zugänglich sind. Die Periodendauer ist dabei schon beim relativ kleinen Zustandsraum in Mathematica (~200 Zellen) länger als das Alter des Universums (schreibt Wolfram...), ich hab da etwas übertrieben (~4k Zellen), dürfte also besser sein ;-)

Mit einfachen statistische Analysen (Byte-Verteilung, FFT, mehrdimensionale Darstellungen) haben keine Regularität ergeben. Jedes Byte kommt im Mittel mit einer Wahrscheinlichkeit von 1/256+/-0.006% vor. Falls jemand Autokorrelationstests zwecks Perioden implementieren will: bitte, tut es, ich habe davon keine Ahnung ;-)

Mit im Paket ist ein einfaches Testprogramm, welches die Verwendung zeigt. Normalerweise wird man die Zustandsbreite nicht mit angeben, sondern nur den Seed (wenn überhaupt).

markieren

Beispiel

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

var
  rng: TRule30Random;
begin
  //rng:= TRule30Random.Create(); //Standard Seed, Standard Breite
  //rng:= TRule30Random.Create(MeinSeedWert); //Standard Breite
  rng:= TRule30Random.Create(MeinSeedWert, 2047);
  try
    ShowMessageFmt('Float (0..1): %f', [rng.NextSingle]);
    ShowMessageFmt('Ganzzahl: %d', [rng.NextCardinal]);
  finally
    FreeAndNil(rng);
  end;

Der Generator liefert bei mir ca. 8MB/s zuällige Daten.
Optimierungsbedarf wäre noch in uCellularAutomaton.TRule30Automaton.Step. Offensichtlich ist ja erstmal die Verwendung eines Bitvektors und SIMD (das geht sogar recht gut, hab das hier auf Papier), aber an der Implementation bin ich erstmal gescheitert.

Lizenz: MPL 1.1/GPL 2.0/LGPL 2.1

Historie
R1: Initial
R2: FPC-Anpassungen, Optimierungen von & mit Horst_H

Einloggen, um Attachments anzusehen!

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Horst_H · Verfasst: Mo 15.07.13 13:46

Hallo,

wenn schon 4 Byte auf einmal verarbeitet werden, dann bitte auch so speichern und um 4 Byte weiter schreiten.Dabei begehe ich eine Grenzüberschreitung, aber das angelegte Feld ist ja 16 kB groß.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:

procedure TRule30Automaton.Step;
//....
asm  // nur wegen Einfärbung/ highlightning
    @loop:
      {$IFDEF ASM_1}
      mov ebx, dword ptr [ecx + $01]
      or ebx, dword ptr [ecx + $02]
      xor ebx, dword ptr [ecx]
      {$ELSE}
      mov edx, dword ptr [ecx]

      mov ebx, edx
      shr ebx, 8
      or bl, bh

      xor ebx, edx
      {$ENDIF}
      {$IFDEF ASM_1}
      mov Dword ptr [eax], ebx
      ADD eax,4
      ADD ecx,4
      {$ELSE}
      mov byte ptr [eax], bl
      inc eax
      inc ecx
      {$ENDIF}      
      cmp eax,esi
    jbe @loop

end;

Als Testprogramm habe ich dies hier.
Ich zähle einfach mal die gesetzten Bits, um einen schnellen Vergleich zwischen purepascal und Asm1 zu haben.
deshalb ein konstanter randseed, zumal ich unter Linux kein QueryPerformanceCounter habe und ich wine hier noch nicht installiert habe/werde.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

constructor TRule30Random.Create;
var
  pc: Int64;
begin
  //QueryPerformanceCounter(pc);
  pc := $471108150007AA55;
  Create(pc);
end;

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:

program Rng30Test;
{$IFDEF FPC}
  {$Mode Delphi}
  {$ASMMODE Intel}
  {$OPTIMIZATION ON}
  {$OPTIMIZATION REGVAR}
  {$OPTIMIZATION PEEPHOLE}
  {$OPTIMIZATION CSE}
  {$OPTIMIZATION ASMCSE}
{$ENDIF}
uses
  sysutils,uCellularAutomaton,uRule30Random;
function popcount(v :integer) :integer; assembler;
asm
      mov  edx, eax          ;// v
      shr  eax, 1            ;// v >> 1
      and  eax, 055555555h   ;// (v >> 1) & 0x55555555
      sub  edx, eax          ;// w = v - ((v >> 1) & 0x55555555)
      mov  eax, edx          ;// w
      shr  edx, 2            ;// w >> 2
      and  eax, 033333333h   ;// w & 0x33333333
      and  edx, 033333333h   ;// (w >> 2)  & 0x33333333
      add  eax, edx          ;// x = (w & 0x33333333) + ((w >> 2) &
                             ;//  0x33333333)
      mov  edx, eax          ;// x
      shr  eax, 4            ;// x >> 4
      add  eax, edx          ;// x + (x >> 4)
      and  eax, 00F0F0F0Fh   ;// y = (x + (x >> 4) & 0x0F0F0F0F)
      imul eax, 001010101h   ;// y * 0x01010101 //Hier ist Pentium IV langsam
      shr  eax, 24           ;// population count = (y *
                              //  0x01010101) >> 24
      mov result,EAX
end;


function RandomSpeedtest(m : integer):LongWord;
var
  rng: TRule30Random;
  i: integer;
  T1,T0 : TDateTime;
begin
  result := 0;
  rng:= TRule30Random.Create(123456789, 8192);// 8192 teilerfremd zu 5 = FCursorSkip
  try
    T0 := time;
    //QueryPerformanceCounter(c1);
    IF m < 0 then
      m:= 1000;
    for i:= 1 to m do
      inc(result,PopCount(rng.NextCardinal));
    T1 := time;
    //QueryPerformanceCounter(c2);
    Write(Format('%d iterations took',[m]));
    writeln(Format('%d ms',[round((T1-t0)*86400.0*1000)]));
  finally
    FreeAndNil(rng);
  end;
end;
begin
  writeln(RandomSpeedtest(10*1000*1000),' Bits gesetzt');
end.
//Laufzeiten AMD Phenom II X4 955 auf 800 Mhz eingefroren  
28423 ms //purePascal
12246 ms //ASM_1 alt 
 7897 ms //ASM_1 neu ca. 5 MioB/s

Angeblich sollen AMD solche verschobenen Zugriffe +0 +1 +2 nicht so mögen, es könnte also auf Intel-Chips schneller sein.

Gruß Horst

Martok · Verfasst: Mo 15.07.13 15:00

Ähm, ASM_1 ist der alte ("erste") Versuch. Da wird nur dword gelesen, weil das auf meinem AMD Windsor (jup, die gibts noch) schneller ist als byte ptr, vermutlich wegen dem rausmaskieren des untersten bytes. War aber alles nix. Aktuell ist der Code ohne alle defines, also dword lesen und im Register verarbeiten. Spart die Addition ein.

Horst_H hat folgendes geschrieben :

Dabei begehe ich eine Grenzüberschreitung, aber das angelegte Feld ist ja 16 kB groß.

Genau deswegen rummsts bei mir dann auch direkt... der Typ ist nur so deklariert, damit man einfacher debuggen kann (siehe auch in der RTL), es wird nicht mehr reserviert als gebraucht wird.

Horst_H hat folgendes geschrieben :

Ich zähle einfach mal die gesetzten Bits, um einen schnellen Vergleich zwischen purepascal und Asm1 zu haben.

Ist bei einem halbwegs guten Random ja eher wenig hilfreich...
Ich war auch schonmal soweit, dass ich 4 byte lese und 2 byte schreibe, aber dafür gehen mir aktuell etwas die Register aus. Man könnte noch esp verleiern und den linearen Speicherzugriff per pop machen... :nut:

Horst_H hat folgendes geschrieben :

deshalb ein konstanter randseed, zumal ich unter Linux kein QueryPerformanceCounter habe und ich wine hier noch nicht installiert habe/werde.

Stimmt, die Version mit fpgettimeofday müsste auch mal jemand einbauen.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Horst_H · Verfasst: Mo 15.07.13 15:52

Hallo,

Damit es nicht "rummst" eben 4 byte extra belegen ;-)

Die Bits zählte ich, um eben zu kontrollieren ob PurePascal und ASM_1 auch die gleichen Ergebnisse liefern.

was noch enorm bremst ist die Erstellen eines Cardinal in rule30random.pas deshalb mal hier eine Variante,
die es recht schnell macht, wenn man StateSize ausreichend groß wählt.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:

function NextCardNoLoop(pB:pByte;delta:integer): cardinal;
// Wenn man auf nichts achten muss dann stumpf 33 Werte verknüpfen
// eine Schleife 32 downto 0 do .. dauerte 21% länger
begin
{# [153] result:= 0;
  movl  $0,%eax
# [154] result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  shll  $1,%eax
  movzbl  (%ecx),%ebx
  orl  %ebx,%eax
  addl  %edx,%ecx }

  result:= 0;
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);

  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);

  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);

  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);
  result:= (result shl 1 ) OR (pB^); inc(pB,delta);

  result:= (result shl 1 ) OR (pB^);
end;

function TRule30Random.NextCardinal: Cardinal;
var
  pB : pByte;
// wegen Freepascal was sonst immer auf das Original zugreift, 
// also aufwendig die Adressen bestimmt
  delta,i,Fc,OG: DWORD;
begin
  // generate 1 additional value to loose track
  OG := FAutomaton.StateSize;
  Fc := FCursor;
  pB := @FAutomaton.State[Fc];
  delta := FCursorSkip;
  IF (Fc + 33*delta) < OG then
  begin
    //sorgt dafür, das pB,delta in Registern sind 
    result := NextCardNoLoop(pB,delta);
    FCursor := FCursor+ 33*delta;
  end
  else
  Begin
    result:= 0;
    for i:= 32 downto 0 do begin
      result:= (result shl 1 ) OR pB^;
      inc(pB,delta);
      inc(Fc, delta);
      if Fc >= OG then begin
        dec(Fc, OG);
        dec(pB,OG);
        FAutomaton.Step;
      end;
    end;
    FCursor := Fc;
  end;
end;

Jetzt sind es 3879 ms statt 7897 ms, das ist doch ein kleiner Gewinn ;-)

Gruß Horst

Edit:
RandomW30

Ich habe es mal mit TurboDelphi kompiliert und dazu FastMM4 auskommentiert.
Diesmal mit 3.2 Ghz.

Einloggen, um Attachments anzusehen!

Martok · Verfasst: Mo 15.07.13 20:03

Einige der hier besprochenen Optimierungen habe ich jetzt eingebaut und damit eine Beschleunigung ungefähr auf 2.5-fache Datenrate erreicht. Einige der aggresiveren haben noch subtile Änderungen im Verhalten zur Folge, das ist nicht so ganz toll ;-)

Download im ersten Beitrag.
EDIT: da fehlten ein paar Dateien. Fixed.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Horst_H · Verfasst: Di 16.07.13 00:30

Hallo,

eine kleine Änderung in uRule30Random.pas:
EDIT: Änderung verworfen, aber eine neue gemacht:
Die Felder werden jetzt in einem Getmem erstellt und "aligned".
Die AssemblerVariante von Step, macht jetzt genauso, wie die PascalVariante.
Dazu wird Feld 0 an die Stelle FeldGroesse kopiert und die TSelle Feldgroesse-1 zu Feld[-1].
Anschliessend wird in einem Rutsch durchgerechnet.
// Ohne {$OPTIMIZATION REGVAR} wird Freepascal elend langsam

Zu Testzwecken habe ich Step in die zwei Varianten StepPurePascal und StepASM aufgeteilt.
Jetzt arbeiten sie scheinbar identisch.
Aber NextCardinalASM liefert ab und an falsche Werte gegenüber NextCardinalPurePascal.
Und zwar ist immer das niederwertigste BIT. Völlig absurd, wieso dieses. Ich sehe es nicht.... MäuseMelk...

Gruß Horst

Einloggen, um Attachments anzusehen!

Horst_H · Verfasst: Di 16.07.13 21:57

Hallo,

passend zum Thema:
www.clevercaboose.com/rich/ca/index.htm
dort ein Test der Periodizität von Rule 30 bei kleinen Weiten, bei der wrap around geradezu übel zu sein scheint.[ OK, die Enden fest auf 0/1 zu setzen ist wohl noch schlechter )
Exemplarisch :

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

In other words, a random number generator based on this approach will initially
generate a non-repeating succession of count values, then it will start repeating every period
values.
Weite  Start der    Perioden-
       Periode      länge
..
35    18,636,338   18,480,630
36       197,368        2,844

www.clevercaboose.co...xpts_with_rule30.pdf

Ist Rule30 dann nicht nur eine Spielerei, wenn dort solche Sprünge in der Periodenlänge sind?

Gruß Horst

Horst_H · Verfasst: Fr 19.07.13 13:22

Hallo,

Martok hätte es gerne mal schneller in Assembler.
Ich hatte einen Knoten im Gehirn, es tauchten Bits an falschen Stellen auf, ist wohl zu kalt...
Eigentlich sollte es Richtung MMX/SSE gehen, aber erst wollte ich nur testen ob auch rauskommt, was man erwartet.
Ich bin erstaunt über die Geschwindigkeit. 15 Befehle, 5 Takte -> IPC = 3
Wie man schnell an die passende Bits kommt, wenn man mit einem Versatz arbeitet, kann ja user profile icon

Martok mal recherchieren, wenn er wieder Zeit hat.

EDIT: nach Martok's Veto geändert:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:

Program Rule30;
//http://en.wikipedia.org/wiki/Rule_30;
//http://mathworld.wolfram.com/Rule30.html
{$IFDEF FPC}
  {$Mode Delphi}
{$ELSE}
  {$OPTIMIZATION ON}
  {$APPTYPE CONSOLE}
{$ENDIF}
uses
  SysUtils;
const
  Limit    = 8192;
  LimitArr = Limit div 32-1;
var
  TestArray : Array[0..LimitArr+1] OF Cardinal;

function Rule_30(a:pCardinal):cardinal;assembler;
const
  SizeOfRegister = 4;
//EBX TestArray[0]
//ESI der Index 0..LimitArr-1

//EAX der Wert
//ECX der Wert um ein Bit rechts davon
//EDX der Wert um ein Bit links  davon
//EDI hält den Nachfolger
asm
  push EBX;
  push ESI;
  push EDI

  MOV  EBX,EAX
  MOV  ESI,LimitArr
  //MUL  ESI,SizeOfRegister
  SHL ESI,2
  ADD  ESI,EBX
  //MSB
  MOV  ECX,Dword Ptr [ESI];  // Den obersten Wert laden POS-1 vorgaenger
  MOV  EAX,Dword Ptr [EBX];                // den aktuellen
  MOV  Dword Ptr [ESI+SizeOfRegister],EAX; // ganz nach oben hin kopieren

@Loop:
  MOV   EDI,Dword Ptr [EBX+SizeOfRegister]; // den nachfolger

  BT    ECX,31      // das MSB von Pos-1
  MOV   ECX,EAX
  RCL   ECX,1       // MSB ins LSB schieben

  BT    EDI,0       // das LSB  von Pos+1
  MOV   EDX,EAX
  RCR   EDX,1       // LSB ins MSB schieben

  OR    EDX,EAX     // POS[i] OR POS[i+1]
  ADD   EBX,SizeOfRegister       // Zur Pos+1 wechseln
  XOR   ECX,EDX     // POS[i] XOR (POS[i] OR POS[i+1])

  MOV   Dword Ptr [EBX-SizeOfRegister],ECX;  // Speichern
  MOV   ECX,EAX     // Der aktueller wird vorheriger
  cmp   EBX,ESI
  MOV   EAX,EDI     // Der nachfolger wird aktueller
  JBE   @Loop

  POP EDI
  POP ESI
  POP EBX
end;

function dummy(a:pCardinal):cardinal;assembler;
asm

end;

function BinStr(Zahl: cardinal): String;
var
  i : integer;

begin
  setlength(result,33);
  result[1] :='_';
  For i := 0 to 31 do
  begin
    result[i+2] := chr(Zahl AND 1+Ord('0'));
    Zahl := Zahl shr 1;
  end;
end;

procedure Ausgabe;
var
  i : integer;
begin
  For i := LOW(TestArray) To High(TestArray)-1 do
    write(BinStr(TestArray[i]));
  write('D',BinStr(TestArray[High(TestArray)]));
  writeln;
end;

const
  Runden :Int64 = 10*1000*1000;
  CpuF = 3.2e9; // AMD Ph XII 955 3.2 Ghz
var
  k: integer;
  T1,T0 : TDateTime;
Begin
  TestArray[Limit DIV 32 DIV 2]:=256*256;
  // Ausgabe;
  T0 := time;
  For  k := 1 to Runden do
  begin
  dummy(@TestArray[0]);
  //Ausgabe
  end;
  T1 := time;
  writeln('Dummy Aufrufe ',FormatDateTime('HH:NN:SS.zzz',T1-T0));
  // Takte pro Durchlauf
  writeln('Takte pro Aufruf: ',((T1-t0)*86400*CpuF)/(Runden):0:1);


  T0 := time;
  For  k := 1 to Runden do
  begin
  Rule_30(@TestArray[0]);
  //Ausgabe
  end;
  T1 := time;
  writeln('Echte Aufrufe ',FormatDateTime('HH:NN:SS.zzz',T1-T0));
  writeln('Takte pro Aufruf: ',((T1-t0)*86400*CpuF)/Runden:0:0);
  writeln('Takte pro 32-Bit: ',((T1-t0)*86400*CpuF)/(Runden*(LimitArr+1)):0:1);

  //Ausgabe;
  readln
end.

Gruß Horst

Martok · Verfasst: Fr 19.07.13 18:15

Horst_H hat folgendes geschrieben :

Eigentlich sollte es Richtung MMX/SSE gehen, aber erst wollte ich nur testen ob auch rauskommt, was man erwartet.

markieren

Delphi-Quelltext

1:
2:

  XOR   EDX,EAX      // POS[i] XOR POS[i+1]
   OR   ECX,EDX      // POS[i] OR (POS[i] XOR POS[i+1])

Andersrum. Erst OR, dann XOR. Passt akkurat dann.

Horst_H hat folgendes geschrieben :

Ich bin erstaunt über die Geschwindigkeit. 15 Befehle, 5 Takte -> IPC = 3

Sieht bei mir geringfügig schlechter aus:

Zitat:

CpuF = 1.4e9; // AMD FX 6300 per PowerMgmt auf 1.4 Ghz
Dummy Aufrufe 00:00:00.063
Takte pro Aufruf: 8.8
Echte Aufrufe 00:00:13.171
Takte pro Aufruf: 1844
Takte pro 32-Bit: 7.2

Horst_H hat folgendes geschrieben :

Wie man schnell an die passende Bits kommt, wenn man mit einem Versatz arbeitet, kann ja user profile icon

Martok mal recherchieren, wenn er wieder Zeit hat.

Hrrm. Ich hab keine Zeit, aber das ist so viel interessanter :lol:

Die Idee mit BT und RCL ist gar nicht doof. Im Prinzip kann man ja sogar sehr einfach vorhersagen, wie viele Bereiche man braucht: Um 32bit in N-Bit-schritten zu generieren braucht man N DWORDs... damit braucht man nur einen Index für den ersten und von dort aus Bits mod 32 zählen. Das mit dem einen Überspringen kann man (vermutlich) lassen.

Als nächstes sollte man dann wohl mal die Periode untersuchen, immerhin haben wir ja jetzt 8mal weniger RAM-Verbrauch als der naive Ansatz. 100Mio 128Bit-Zustände sind nur 1.6GByte, das kann man sogar mit 32bit-OS problemlos machen. Zeit für viele viele CompareMem ist ja nicht so das Problem (zumal es ja die FastCode gibt).

EDIT: die Ergebnisse aus dem Link oben für die Periode von 32bit konnte ich reproduzieren. Weitere Vielfache von 32 sind mit meinen Mitteln nicht mehr festzustellen. Ich weiß nur, dass die Periode angefangen von einer schwarzen Zelle größer 242483200 ist, ausgehend von zufälligen Werten (Stichprobe von 100 Läufen) ist mit 2GB auch nichts zu finden.
Oh und: meine Güte, ist das Ding schnell :shock:

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Horst_H · Verfasst: Sa 20.07.13 07:38

Hallo,

das der "Bulldozer" mehr im doze-mode ist wundert mich ;-)

Das IPC ist ja knapp über 2 .
Ich gebe zu, IPC =3 habe ich auch bisher noch nicht erlebt ( 2,3 in www.entwickler-ecke....der=asc&start=37 ) .
Mit Freepascal 2.6.2, CPUF= 3.2e9

markieren

Quelltext

1:
2:
3:
4:
5:
6:

sh-4.1# ./Rule30
Dummy Aufrufe 00:00:00.031
Takte pro Aufruf: 9.9
Echte Aufrufe 00:00:04.079
Takte pro Aufruf: 1305
Takte pro 32-Bit: 5.1

Scheinbar kann man sehr viel outoforder oder noch verarbeiten während andere Dinge laufen, da sie unabhängig von einander sind.
Sicher geht es noch schneller, aber für wen oder was ;-)

Gruß Horst

Martok · Verfasst: Sa 20.07.13 15:21

Horst_H hat folgendes geschrieben :

Wie man schnell an die passende Bits kommt, wenn man mit einem Versatz arbeitet, kann ja user profile icon

Martok mal recherchieren, wenn er wieder Zeit hat.

BTS/BTR/BT laufen über :shock:

, und Delphi kennt eine TBits-Klasse (Classes.pas). :shock:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

function TRule30Automaton.GetBit(Index: integer): boolean;
asm
  MOV     EAX,[EAX].FState[0]
  BT      [EAX],Index
  SBB     EAX,EAX
  AND     EAX,1
end;

Wenn man mehr als das 32. Bit will, fasst das einfach mal in das nächste DWORD.

Also jetzt einfach nur noch durchzählen:

markieren

Pseudoassembler, nach Geschmack mit Registern würzen

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

asm
  mov ptr, FState[0]
  xor result, result
@@0
  bt ptr, index
  rcl result, 1
  add index, StepSize
  cmp index, bitcount
  jl @@1
  call Automaton.Step
  dec index, bitcount
@@1
  jmp @@0
end

EDIT:
323 Clocks/Call für 32bit. 67% der Zeit in asm BT [esi], edi end, obwohl das komplett Data Cache Hits sind. :gruebel:

Einloggen, um Attachments anzusehen!

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Horst_H · Verfasst: Mo 22.07.13 12:04

Hallo,

Da übergibt der Assembler stepsize und ersetzt dann durch ein Register das ich gerade benutzte. Was für ein falscher Fehler von mir.
Anbei ein Version, die zumindest nicht abstürzt ;-)

Ich übergebe bei Testcard nicht mehr die Startposition innerhalb des Bitfeldes und nutzte das wieder eingeführte FCursor.
Bei einer Schrittweite von 5 und einer minimalen teilerfremden ( sonst kommen immer die gleichen Bitpositionen zum Zuge ) Feldgröße von (5+1) *32 Bit brauche ich jetzt 220 Takte pro Cardinalzahl, bei 256*32 Bit sind es um die 150.
Eigentlich wollte ich berechnete Sprünge machen.Vielleicht später.

Gruß Horst
P.S.
Endlich habe ich den Fehler gefunden.
Rule30.step erwartet die Anzahl der Cardinal und ich habe in GetBis32 aber die Anzahl der Bits übergeben.
Dass das nicht immer "knallte" wundert mich.

Einloggen, um Attachments anzusehen!

Horst_H · Verfasst: Do 01.08.19 21:55

Hallo,

es geht auch ohne Assembler als 64-Bit Kompilat schnell.Wenn auch hier jedes Byte Bit für Bit erzeugt wird.
Freepascal kennt ja ROR und ROL.
Rule30, dort kann man es auch mit TryItOnline aufrufen,

Gruß Horst

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme