This is a finger exercise for experimenting with different approaches to parallelising code. The file alias.c contains an implementation of Vose's alias method for sampling from a finite probability distribution and some timing code. We loop 100 times, performing the following steps:
- Generate 1,000,000 random numbers, corresponding to weights of a 1,000,000-sided loaded die.
- Normalise these numbers so that their mean is 1.
- Construct "dartboard" and "alias" tables allowing us to sample from this distribution in constant time.
- Roll the die 1,000,000 times.
Steps 1 and 4 are embarrassingly parallel; step 2 is a parallelisable reduction followed by an embarrassingly parallel division; step 3 is easy to parallelise with a work-stealing approach but hard to make data-parallel.