next up previous

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

Uses of Monte Carlo methods have been many and varied since that time. However, due to computer limitations, the method has not yet fully lived up to its potential as discussed by Metropolis [44]. Indeed, this is reflected in the stages the method has undergone in the fields of engineering. In the late 1950's and 1960's, the method was tested in a variety of engineering fields [46,18,48,23,12].

At that time, even simple problems were compute-bound. The method has since been extended to more complex problems [26,45,35,36,37,38,14].

Since then, attention was focused upon much-needed convergence enhancement procedures [28,19,8,33,58,62,34].

Many complex problems remained intractable through the seventies.

With the advent of high-speed supercomputers, the field has received increased attention, particularly with parallel algorithms which have much higher execution rates. In his Ph.D. dissertation, Brown introduced the concept of the ``event step'' [7], enabling efficient vectorization of Monte Carlo algorithms where the particles do not interact. This approach was later successfully exploited by several investigators. Martin et al. [40] reported speedups of a factor of five on an IBM 3090 with vector units. Nearly linear speedup was reported [57] on a parallel architecture for photon tracing. Bobrowicz et al.\ [Bobrowicz et al., 1984a and 1984b]

obtained speedup factors of from five to eight in an algorithm where particles are accumulated in queues until efficient vector lengths are obtained, allowing physics algorithms such as the Los Alamos benchmark GAMTEB to be effectively vectorized [9]. Such advanced coding techniques have enabled much bigger problems to be attacked, with improved accuracy. However, there are still a host of problems which remain intractable, even with an effectively vectorized algorithm.