Når man sidder og kigger på en Monte Carlo simulering okser derudaf med 50 % af processorkraften, så begynder man at overveje om man ikke skulle ha' nogle tråde i spil. Microsoft's Parallel Programming team har skrevet et indlæg på deres blog om Getting random numbers in a thread-safe way. Hvis vi lige et kort øjeblik ser bort fra at Random er en håbløs generator til Monte Carlo simulering og se på de problemer indlægget beskriver.

Random er IKKE thread-safe. Det er de implementeringer af Mersenne Twister jeg har set heller ikke. Hvis vi antager, at vi er i besiddelse af en generator som er thread-safe. Er vi så nået meget videre?

Indlægget behandler det faktum at Random initialiseres med TickCount hvis man ikke angiver et seed og at TickCount har en omløsning på omkring 15ms. Derfor vil mange af de tilfældige tal være ens, specielt når man benytte flere tråde. Det gives der så flere løsninger på, men hvis man kører Monte Carlo simulering på lidt mere end hyggeniveau så bruger man ikke et tilfældigt seed. I hvert fald ikke mere tilfældigt end at det stadig ligger på din personlige top-10 favorit seed liste.

Problemet er reproducerbarhed (godt dansk ord). Hvis jeg kører simulering igen med samme seed, får jeg så samme resultat? Sandsynligvis ikke, hvis jeg bruger flere tråde. Selvom jeg sikrer mig at kun en enkelt har adgang til min generator på et givet tidspunkt, så kender jeg ikke rækkefølgen.

En løsning kunne være at give hver tråd sin egen generator som så er initialiseret på en deterministisk måde. Det er implementeret i RandomGen2 eksemplet, hvis bare den globale generator initialiseres med et kendt seed. Problemet er bare om man introducerer noget afhængighed.

Hvis jeg trækker en række tal tilfældigt, så er de genereret så de er indbyrdes stokastiske uafhængige. Men hvad sker der hvis man trækker to rækker med tilfældige tal fra hver sin generator (samme type, men forskellige seed)? Kan de så antages at være uafhængige? Sandsynligvis ikke. Vi skal ikke glemme at tilfældige tal genereret af en computer er mindre tilfældige end dagligdags begivenheder som vi tilskriver højere magter. Det er ren matematik det hele. Det overlades til en øvelse, men ser man på Linear Congruential Generators, så er det relativt simpelt at finde to seeds så man får to forskudte processor - altså det der med LaTeX notation er x_i = y_{i+1}.

Man kunne antage at når jeg nu har påpeget et problem som er relevant for mig, så har jeg også fundet løsningen. Men I må nøjes med nogle indspark, for det er endnu ikke implementeret (gammel C++/COM kode har ikke en Parallel.For). Mit mål er at hver sti i Monte Carlo simuleringen skal behandles af en enkelt tråd. Generelt er der for lidt optimering i at bruge Parallel.For (eller lign. via OpenMP) på enkelte loops inden for hver sti og det forhindrer reproducerbare stier. Men en sti per tråd kan hver tråd få sin egen generator.

Problemet er nu, som beskrevet ovenfor, at undgå at introducere afhængigheder mellem de enkelte stier. Der er flere løsninger på det

  1. Hvis beregningerne er den tunge del kan man vælge at generere alle tilfældige tal up-front. Hver tråd får så tildelt en pool af tilfældige til. Den første tråd kan sættes i gang så en pool er genereret færdig.
  2. Til ovenstående skal man kende antallet at tilfældige tal som skal benyttes i hver pool. Som alternativ til at generere alle tallene up-front  kan man evt. spole frem i generatoren for hver sti. For Random og Mersenne Twister betyder det dog at man generer en masse tal og så smider dem væk.
  3. Der findes generatorer hvor det at spole frem i rækken af tilfældige tal er en simpel operation. Hvis perioden er tilstrækkelig stor kan man spole 2^n tal frem, hvor n er stor nok til at man ikke overlapper med næste sti. Hvis n er stor nok behøver man ikke kende det præcise antal tilfældige tal i hver sti.

Jeg arbejder videre med den sidste ide, men forslag er velkomne.

Kommentarer

Mac Switzerland siger:

21. februar 2009 17:50

Stærk artikel - (3) lyder som en god ide (der er ikke oplagt for mig at du kan finde en god generator hvor dette kan lade sig gøre) - najs! Smile

Det må være muligt at bikse noget med (1), men ikke generere _alle_ up-front... men tage dem i etaper. Jeg tænker noget á la at du har tråd 1 til at generere tallene og tråd 2 til pool beregningerne - tråd 1 kører så lystigt derudaf og ind i mellem kan den så også tage et nap med en pool.
Hvis du f.eks. begynder med at tage tid på tråd 2 hvor lang tid det tager at regne den første pool, så burde du kunne bruge det til at sync'e hvordan tråd 1 kører uden at få for meget idle tid på trådene og uden at bruge for meget hukommelse.

ne0san Denmark siger:

21. februar 2009 17:59

Jeg må finde et link til (3). Har set på nogle generatorer hvor man springer 2^54 tal frem med en simpel matrix multiplikation.

Mht (1) så er tiden der bruges på at generere tilfældige tal er forsvindende i forhold til tiden der bruges på at diskontere lange aktuar cash flows. Det er bestemt noget jeg har overvejet at gøre, desværre passer det ikke ind i den nuværende program struktur.

Torben Denmark siger:

23. februar 2009 00:17

Interessant problem. 3 lyder som en god løsning, men stiller jo visse krav til generatoren. En reference ville være lækkert.

Det du vil opnå med 3 er vel a) at kun have en generator og b) at finde 2 ikke-overlappende, uafhængige del-sekvenser i den generator. Det kunne du også ved at give de to tråde hver sin generator med samme seed (altså samme generator), men lade de to tråde benytte kun hver anden tilfældige tal (den første tråd de ulige, den anden de lige). Ved at have to generatorer behøver de ikke vente på hinanden, hvis den ene tråd er mere sulten end den anden.

Det stiller dog kravet at disse to del-sekvenser ikke er afhængige, hvilket de vel heller ikke bør være i en ordentlig generator. Jeg kan i hvert fald ikke se at forskudte sekvenser vil opstå - end ikke for LCG.

Et problem er dog at man forhånd skal fordele opgaverne mellem de to tråde for at sikre at de kan reproduceres. Hvis man har mange relativt ens pakker er problemet måske ikke så stort i praksis.

ne0san Denmark siger:

23. februar 2009 08:40

Det vil være naturligt at dele en Monte Carlo simulering op per sti og så give hver sti sin egen delmængde af tilfældige tal. Denne delmængde kaldes en stream og indeholder enormt mange tal (f.eks. 2^32 tal). Generatoren kan så nemt springe frem til næste stream med en enkelt operation. En gut ved navn Pierre L'Ecuyer, University of Montreal har arbejdet med det, men kan ikke finde links til hans artikler. Men ellers kan du se på http://sprng.cs.fsu.edu/ som indeholder en parallel random number generator. Jeg vil gerne høre hvad du finder mht. SPRNG, som jeg ikke selv har kigget på.

Kommentarerne er lukkede