En af de løsningsmetoder som jeg skitserede under mit indlæg Thread-safe Random Numbers var at oprette en tråd som stod for genereringen af de tilfældige tal. Den metode skulle sikre at resultat var reproducerbart og at man stadig kunne bruge sin favorit talgenerator (Mersenne Twister er et godt bud på en favoritgenerator). Selvom det er en relativt simpel løsning, betyder det jo ikke at man ikke skal tænke sig om. Min første indskydelse var at generere en masse uniform variable i en pool og så transformere dem til f.eks. normalfordelte i løbet af selve simuleringen. Det minimerer tidsforbruget i generatortråden og overlader det til simuleringstrådene.
Det giver dog et lille problem.

Den bedste måde at generere normalfordelte tilfældige tal er at benytte polar Box-Müller som er givet ved

do 
{ 
  x = 2.0 * Random() - 1.0; 
  y = 2.0 * Random() - 1.0; 
  w = x * x + y * y; 
} 
while (w >= 1.0 || w == 0.0) 
w = Math.Sqrt(-2.0 * Math.Log(w) / w); 
x *= w; 
y *= w; 

Ovenstående kode giver os to normaltfordelte tal, men bruger MINDST to ligefordelte tal. Vi ved altså ikke på forhånd hvor mange ligefordelte tal vi skal bruge, hvilket forkaster min udmiddelbare indskydelse. I stedet vil jeg nu skabe en række streams som er generede med den ønskede fordeling. Generator tråden får altså mere arbejde, men alternativet er ikke et reelt alternativ, da det er svært at vide om man er på den sikre side hvis man vil generere rigeligt med ligefordelt tal.

Man kunne indvende at jeg kunne vælge en anden form af Box-Müller, som bruger præcis to ligefordelte tal til at generere to normal fordelte. Hvis vi ser bort fra at denne metode er langsommere og mindre numerisk stabil, så er der jo andre fordelinger som har samme problem, f.eks. Poissonfordelingen. Det antyder at vi bare skal løse problemet med det samme.

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.