Using Answer Set Programming for HPC Dependency Solving

Abstract

Modern scientific software stacks have become extremely complex, using many programming models and libraries to exploit a growing variety of GPUs and accelerators. Package managers can mitigate this complexity using dependency solvers, but they are reaching their limits. Finding compatible dependency versions is NP-complete, and modeling the semantics of package compatibility modulo build-time options, GPU runtimes, flags, and other parameters is extremely difficult. Within this enormous configuration space, defining a "good" configuration is daunting. We tackle this problem using Answer Set Programming (ASP), a declarative model for combinatorial search problems. We show, using the Spack package manager, that ASP programs can concisely express the compatibility rules of HPC software stacks and provide strong quality-of-solution guarantees. Using ASP, we can mix new builds with preinstalled binaries, and solver performance is acceptable even when considering tens of thousands of packages.