Towards a Linear-Algebraic Hypervisor
It addresses the underutilization of GPUs for parallel rollouts in program synthesis and superoptimization, offering a practical solution for accelerating these workloads.
The paper introduces a pleasingly parallel virtual machine for executing general-purpose programs on GPUs, achieving speedups up to 147x over serial evaluation for millions of concurrent array programs.
Many techniques in program synthesis, superoptimization, and array programming require parallel rollouts of general-purpose programs. GPUs, while capable targets for domain-specific parallelism, are traditionally underutilized by such workloads. Motivated by this opportunity, we introduce a pleasingly parallel virtual machine and benchmark its performance by evaluating millions of concurrent array programs, observing speedups up to $147\times$ relative to serial evaluation.