Bounded Model Checking. The key idea of BMC is to exercise the behavior of a system only up to a certain depth of computations [BCCZ99, CBRZ01, CKOS05]. BMC has been established as a valuable bug-hunting framework for hardware and soft- ware [CKL04], which is motivated by the observation that bugs can often be found after few computation steps if only the right inputs are chosen. How- ever, it has been observed that bounded model checking can also be applied for formal verification if the unrolling depth k of the transition relation is large enough. Precisely, the the unrolling depth k has to match the com- pleteness threshold c of the system, which can intuitively be described as: If no counterexample of length c or less is found, the specification holds for all (infinite) executions of the model. Hence, BMC with k ≥ c suffices for proving correctness of a system [BCCZ99, Thm. 27]. However, computing the completeness threshold is as least as hard as solving the model check- ing problem itself [CKOS04, KOS+11]. Consequently, BMC is often used for verification up to a certain bound, without giving an actual correctness guarantee for nonterminating executions of the system.
Bounded Model Checking. In bounded model checking, the loops in a program are unrolled to a certain bound. Next, a logical formula is constructed for the program and a property the program needs to satisfy, where the formula only considers the unrolled part of the loop. Finally, automated theorem proving is applied, as in the case of contract-based verification. Remark that this method is necessarily incomplete, as a counterexample to a property may only be found by unrolling the loop further than the chosen bound. A bounded model checking approach to GPGPU program verification is described by Li and Gopalakrishnan and their co-workers [89], i.e., the authors of PUG. As in the case of PUG, the focus is on data races and it is remarked that the method can be extended to arbitrary program properties by adding assertions to the programs being verified. However, unlike PUG and due to this work actually pre-dating PUG, no use is made of the observation that it suffices to consider only two threads when trying to detect data races. Instead, so-called partial order reduction is used to reduce the number of thread schedules that need to be considered, which, as reported in [88] is less effective than restricting attention to two threads. Symbolic Execution. In symbolic execution, a program is actually executed. However, part of the program is kept in symbolic form. For each path through the program that can be taken constraints on the symbolic data are generated. These constraints can be used to generate concrete test cases (ensuring high code coverage). Moreover, the constraints on two programs that are claimed to be equivalent can be generated and compared to actually prove equivalence. The route of proving equivalence of two programs is taken by Collingbourne et al. with their tool XXXX-CL [36]. XXXX-CL uses symbolic execution to establish the equivalence between a plain C or C++ version of a program and a OpenCL version of the same program. As reported in [36], the technique is very effective for finding differences between plain programs and GPGPU implementations of the same programs. Li and Gopalakrishnan and their co-workers [90] use their tool GKLEE to generate test cases with high code-coverage. In addition, during symbolic execution GKLEE attempts to detect memory races and bank conflicts (see above). Moreover, GKLEE also detects what is sometimes called barrier divergence, which means that some barrier synchronization points in GPGPU program are not hit by all threads; somethi...
