high performance computing on graphics processing units: hgpu.org

A program is deterministic if it always produces the same output for a given input. Although sequential programs are often deterministic by default, parallel programs are more susceptible to behaving nondeterministically because instructions from different threads can be interleaved unpredictably. Non-determinism complicates the task of developing and maintaining software because it makes reasoning about program behavior more difficult, and it frustrates attempts to test and debug due to the unrepeatability of results. To combat this difficulty, researchers have followed various approaches at the operating system, user runtime, and language design level to verify, test, and enforce deterministic execution of parallel programs. This paper presents a survey these approaches, then concludes with a discussion of original research by the author towards verification of determinism in GPU kernels.