Thallo – Scheduling for High-Performance Large-scale Non-linear Least-Squares Solvers

Large-scale optimization problems at the core of many graphics, vision, and imaging applications are often implemented by hand in tedious and error-prone processes in order to achieve high performance (in particular on GPUs), despite recent developments in libraries and DSLs. At the same time, these hand-crafted solver implementations reveal that the key for high performance is a problem-specific schedule that enables efficient usage of the underlying hardware. We propose Thallo, a domain-specific language for large-scale non-linear least squares optimization problems. Thallo takes as input a compact, shader-like representation of an energy function and a (potentially auto-generated) schedule, translating the combination into high performance
GPU solvers. Thallo can generate solvers from a large scheduling space, and thus able to handle a large set of large-scale non-linear and non-smooth problems with various degrees of non-locality and compute-tomemory ratios, including diverse applications such as bundle adjustment, face blendshape fitting, and spatially-varying Poisson deconvolution. Abstracting schedules from the optimization, we outperform state-of-the-art GPU-based optimization DSLs by an average of 16× across all applications introduced in this work, and even some published hand-written GPU solvers by 30%+.