It is very easy to implement, with the main hurdle being the generation of random numbers.It is very easy to understand how the method works, which is often not the case with the algorithm for the corresponding exact solution (assuming one exists).
However, it does demonstrate three reasons why Monte Carlo methods are so popular: As the number of points increases, the accuracy improves, giving estimates of 3.1492 for n = 2 x 10 4 and 3.1435 for n = 2 x 10 5.įigure 37-1 Random Points Within a Square to Calculate PiĬlearly this is an inefficient way to calculate : the rate of increase in accuracy is low (accuracy is usually proportional to the square root of the number of trials) and is much less efficient than standard iterative methods. Figure 37-1 shows random points placed within a circle, with n = 20, 200, and 2,000, shown as blue circles, red crosses, and green points, respectively, providing estimates of as 3.4, 3.18, and 3.158. Some fraction k of the points will lie within the circle, thus we have p k/ n, leading to p 4 k/ n. We can calculate the ratio p using Monte Carlo methods by generating n independent random points that are uniformly distributed within the square. If we can calculate the ratio, p, of the circle area to the square area, then we can calculate :
We know that if the radius of the circle is r, then the area of the circle is r 2, and the area of the square is 4 r 2. Take a square and inscribe within it a circle that touches each edge of the square. A simple example of a Monte Carlo solution to a problem is for calculating. Monte Carlo approaches were introduced by Ulam and von Neumann in the 1940s with the aim of simulating nuclear reactions (Metropolis 1987). Overall, we find that a single GeForce 8 GPU generates Gaussian random numbers 26 times faster than a Quad Opteron 2.2 GHz CPU, and we find corresponding speedups of 59x and 23x in the two financial examples. We then demonstrate how these random number generators can be used in real simulations, using two examples of valuing exotic options using CUDA. We describe two methods for generating Gaussian random numbers, one of which works by transforming uniformly distributed numbers using the Box-Muller method, and another that generates Gaussian distributed random numbers directly using the Wallace method. In this chapter, we discuss methods for generating random numbers using CUDA, with particular regard to generation of Gaussian random numbers, a key component of many financial simulations. 2006 has investigated random number generation in older generations of GPUs, but the latest generation of completely programmable GPUs has different characteristics, requiring a new approach. There is an extensive body of literature devoted to random number generation in CPUs, but the most efficient of these make fundamental assumptions about processor architecture and performance: they are often not appropriate for use in GPUs. These generators must meet the conflicting goals of being extremely fast while also providing random number streams that are indistinguishable from a true random number source. However, a key component within Monte Carlo simulations is the random number generators (RNGs) that provide the independent stochastic input to each trial. The independent trials are inherently parallelizable, and they typically consist of dense numeric operations, so GPUs provide an almost ideal platform for Monte Carlo simulations. The results of the independent trials are then combined to extract the average answer, relying on the Law of Large Numbers, which states that as more trials are combined, the average answer will converge on the true answer. The defining characteristic of Monte Carlo simulations is the use of multiple independent trials, each driven by some stochastic (random) process. Monte Carlo methods provide approximate numerical solutions to problems that would be difficult or impossible to solve exactly. Efficient Random Number Generation and Application Using CUDA You can also subscribe to our Developer News Feed to get notifications of new material on the site.Ĭhapter 37. The CD content, including demos and content, is available on the web and for download.
#Permute high quality vs. keep quality for free
GPU Gems 3 GPU Gems 3 is now available for free online!
0 kommentar(er)
