Automatic parallelization friendly programming practices

From this paper: Avoid unnecessarily serializing algorithms: Algorithms such as random number generators that must pass a seed to the next generator call serialize the algorithm unnecessarily if the number of times the generator will be called within a thread cannot be accurately predicted. These algorithms should be replaced with more distributed versions, instead.

Q: Can anyone please explain "serialize the algorithm unnecessarily if the number of times the generator wi开发者_如何学Cll be called within a thread cannot be accurately predicted." As for random number generation we have to pass a seed. Thus how can serialization be avoided.

If you have a RNG that depends on its previous value (most) and you write it like this:

r = Random.new();
for(int i=0; i<100*usersInput; i++) 
    r.rand();
}

It cannot be automatically parallelized even by a smart compiler. However, if you write it like this:

for(int i=0; i<usersInput; i++) {
    r = Random.new();
    [for(int j=0; j<100; j++) {
        r.rand();
    }] fork
}

A very smart compiler can make the program run in usersInput-number-of-threads, each will only have to run 100 iterations instead of usersInput*100.