next up previous

1 Monte Carlo Algorithms and ``Random'' Numbers     continued...

Moreover, some impediments to effective vectorization have been identified and analyzed. Zhong and Kalos [61] analyzed the ``straggler'' problem, where few particles persist for many event steps, inhibiting performance due to the overhead incurred where vectors are ``short.'' Pryor and Burns [51,10] reported, for one Monte Carlo problem where particles interact, speedups on the order of half of those observed where the particles do not interact, albeit with a vectorized algorithm of greatly increased complexity. The same problem has been attacked with different physics [42,16] in a more efficient algorithm.

Good general references on Monte Carlo abound [4,24,56,31,55,5,22]

in the literature. Most have a distinct bent - usually either statistics or physics. Unfortunately, there is a dearth involving large-scale engineering applications.

No tutorial on large-scale Monte Carlo simulation can be complete without a discussion of pseudo-random number generators. Where billions of random numbers are required, it is essential that the generator be of long period, have good statistical properties and be vectorizable. On 64-bit machines, these criteria are usually satisfied with a multiplicative generator if the constants are carefully chosen [30]. Indeed, we have come a long way from the early days of random number generators [32]. For example, Cray's FORTRAN callable generator ranf has a cycle length of , and is very efficient (vectorized with low overhead).

We summarize this introduction with our impression of the present status of Monte Carlo surface to surface simulation. ``All the pieces of the puzzle'' have just come into confluence for large-scale Monte Carlo analysis. First, supercomputers are now sufficiently powerful to enable the simulation of very large engineering and physics systems, involving thousands of surfaces and billions of particle emissions. Secondly, a comprehensive formulation for material properties exists in the aggregate of several models. Thirdly, an estimate of the number of trials required to achieve a specified level of accuracy is now obtainable prior to execution. This makes possible a formulation which allows the number of emissions to evolve dynamically as the simulation proceeds. Finally, a number of investigators have effectively vectorized diverse Monte Carlo transport algorithms, with a sufficient base to establish a synthesized approach. We now even have a quantitative model which allows the assessment of the degree of parallelism and the amount of overhead required. Moreover, with the emergence of lagged Fibonacci generators, parallelization at any granularity appears to be easily implemented, and robust. With this as a point of departure, we now embark upon a discussion of random number generators, upon which all Monte Carlo methods rely.