Calculating 'pie' on the GPU using a pseudo probability function (estimating Pi using Monte Carlo method). This approach for estimating the value of pi using random numbers can illustrate the relationship between the sample size, the estimate of pi, and the error in the estimate. The Monte Carlo method generates random points inside a square and counts the number of points that fall inside a circle inscribed in the square to estimate pi.
First, let's start by understanding what pie actually is, the definition for pie is:
The number π is a mathematical constant that is the ratio of a circle's circumference to its diameter, approximately equal to 3.14159...
We're going to do a calculation using a unit circle. Instead of a whole circle which has a range of -1 to 1, we'll only do the calculation with a quarter (i.e., 0 to 1). A circle is the same - so any calculation on this small quadrant can be multipled by 4 to get the final answer.
Now we can generate lots of random numbers in the range 0 to 1 for the corner. Take a random point P at coordinate X, Y such that 0 <= x <= 1 and 0 <= y <= 1. If x2 + y2 <= 1, then the point is inside the quarter disk of radius 1, otherwise the point is outside.
Random points for the x and y (0 to 1) - how the points are distributed inside and outside the circle quarter.
Before implementing the calculation on the compute shader - we can do a small proof of concept in JavaScript to see that the number returned is in the ball-park (close to 3.14).
The result returned from the JavaScript code is actually very good, it returned ["approximateValueOfPi:",3.1484]. It still has an error - but the value is close.
Random Numbers on Compute Shader
For the compute shader we'll create 128 threads - each thread will perform the same calculation - then we'll take the average of the final result (which should be more accurate as it's over a larger number of iterations).
However, one aspect of the calculation is how to generate a random number? For this example, we'll use a simple pseudo random number generator - for the seed we'll use the globalId. This is so each compute shader generates it own cluster of unique numbers.
While it's not really a very robust random number generator - it's good enough for testing here - provide a proof of concept. Later on you could try modifying the random number generator with other more complex ones to see if it improves the result.
The complete code for the compute pie calculation using a Monte-carlo random approximation is given below. The code includes all of the setup code and the buffers for the result. The result is written to an output buffer which is summed on the JavaScript side.
let div = document.createElement('div'); document.body.appendChild( div ); div.style['font-size'] = '20pt'; function log( s ) { console.log( s ); let args = [...arguments].join(' '); div.innerHTML += args + '<br>'; }
log('WebGPU Compute Example (PIE)');
if (!navigator.gpu) { log("WebGPU is not supported (or is it disabled? flags/settings)"); return; }
// Note this buffer is not linked to the 'STORAAGE' compute (used to bring the data back to the CPU) const buffer3 = new Float32Array( Array.from({length: arraySize}, () => 0) ); const gbuffer3 = device.createBuffer({ size: buffer3.byteLength, usage: GPUBufferUsage.COPY_DST | GPUBufferUsage.MAP_READ}); device.queue.writeBuffer(gbuffer3, 0, buffer3);
// Bind group layout and bind group const bindGroupLayout = device.createBindGroupLayout({ entries: [ {binding: 0, visibility: GPUShaderStage.COMPUTE, buffer: {type: "storage"} } ] });
// Computation loop for (var i = 0; i < iterations; i++) { var x = random( vec2<f32>( f32(i), f32(index)*10.0 ) ); // Random x position in [0,1] var y = random( vec2<f32>( f32(i*10), f32(index)*999.0 ) ); // Random y position in [0,1]
