Path Regeneration for Random Walks

Jan Novák, Vlastimil Havran, and Carsten Dachsbacher

GPU Computing Gems - Emerald Edition

abstract

We present a method for efficiently generating random walks on the GPU. We analyze the main drawback of naive random walk generators resulting in a low GPU utilization over time, and propose an intuitive scheme for keeping all the processing units busy during the entire computation. The algorithm does not require interthread communication, collective operations, or intricate handling of work queues. Instead, the improved utilization is achieved by intelligently regenerating terminated walks. We discuss our optimization in the context of rendering global illumination images where random walks are used to compute the propagation of energy between light sources and cameras. Algorithms such as (bidirectional) path tracing, photon mapping, and irradiance caching directly benefit from the higher throughput; however, our technique is also applicable to nongraphical problems that explore the domain of interest by random walks.

downloads

bibtex

@incollection{Novak2011PathReg,
    title       = {Path Regeneration for Random Walks},
    author      = {Jan Nov\'{a}k and Vlastimil Havran and Carsten Daschbacher},
    booktitle   = {GPU Computing Gems Emerald Edition},
    editor      = {Hwu, Wen-mei W.},
    pages       = {401--412},
    publisher   = {Morgan Kaufmann Publishers Inc.},
    address     = {San Francisco, CA, USA},
    year        = {2011},
}