  As Graphics Processing Units (GPUs) have gained in capability and GPU
development environments have matured, developers are increasingly turning to
the GPU to off-load the main host CPU of numerically-intensive, parallelizable
computations. Modern GPUs feature hundreds of cores, and offer programming
niceties such as double-precision floating point, and even limited recursion.
This shift from CPU to GPU, however, raises the question: how do we know that
these new GPU-based algorithms are correct?
  In order to explore this new verification frontier, we formalized a
parallelizable all-pairs shortest path (APSP) algorithm for weighted graphs,
originally coded in NVIDIA's CUDA language, in ACL2. The ACL2 specification is
written using a single-threaded object (stobj) and tail recursion, as the
stobj/tail recursion combination yields the most straightforward translation
from imperative programming languages, as well as efficient, scalable
executable specifications within ACL2 itself. The ACL2 version of the APSP
algorithm can process millions of vertices and edges with little to no garbage
generation, and executes at one-sixth the speed of a host-based version of APSP
coded in C- a very respectable result for a theorem prover.
  In addition to formalizing the APSP algorithm (which uses Dijkstra's shortest
path algorithm at its core), we have also provided capability that the original
APSP code lacked, namely shortest path recovery. Path recovery is accomplished
using a secondary ACL2 stobj implementing a LIFO stack, which is proven
correct. To conclude the experiment, we ported the ACL2 version of the APSP
kernels back to C, resulting in a less than 5% slowdown, and also performed a
partial back-port to CUDA, which, surprisingly, yielded a slight performance
increase.
