high performance computing on graphics processing units: hgpu.org

Monte Carlo methods are various techniques aimed at obtaining numerical results through simulations with random samples: the base idea of Monte Carlo methods is to generate a sequence of random numbers and execute the same algorithm on each one of them or in groups, then the resulting outputs are combined to obtain the final result. One of the applications of Monte Carlo methods is rendering images from a 3D scene through ray tracing. Monte Carlo methods are usually "parallel-friendly": for example, computing a definite integral can be done by making each work-item generate random numbers and computing function values based on them; after each work-item has computed the needed values, the values need to be put together. This can be done with atomic operations, that give each work-item exclusive access to a shared variable or a reduction kernel to sum all values contained in a GPU buffer. The rendering case is strictly connected to integration, since the fundamental rendering equation involves a definite integral corresponding to each light source’s contribution from every direction. A rendering engine aims to approximate this integral in order to obtain the ideal luminance values for each pixel of the output image. Before analysing GPU implementations, a simple CPU ray tracer in C++ will be covered. For GPU versions, OpenCL 1.2 was used. OpenCL has a host-device structure which, combined with a dedicated graphics card, allows executing the same code in numerous units. The algorithms presented here heavily benefit from this structure and sequential CPU implementations are much slower.