2022/10/27 by Alex Reinking, Reinking, Alex, Gilbert Bernstein +3
Computer Science · #D.3.1 #Distributed and Parallel Computing Systems #Embedded Systems Design Techniques #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #Programming Languages (cs.PL)
paper · pdf · doi:10.48550/arxiv.2210.15740
openalex publication_date 2022/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present the first formalization and metatheory of language soundness for a user-schedulable language, the widely used array processing language Halide. User-schedulable languages strike a balance between abstraction and control in high-performance computing by separating the specification of what a program should compute from a schedule for how to compute it. In the process, they make a novel language soundness claim: the result of a program should always be the same, regardless of how it is scheduled. This soundness guarantee is tricky to provide in the presence of schedules that introduce redundant recomputation and computation on uninitialized data, rather than simply reordering statements. In addition, Halide ensures memory safety through a compile-time bounds inference engine that determines safe sizes for every buffer and loop in the generated code, presenting a novel challenge: formalizing and analyzing a language specification that depends on the results of unreliable program synthesis algorithms. Our formalization has revealed flaws and led to improvements in the practical Halide system, and we believe it provides a foundation for the design of new languages and tools that apply programmer-controlled scheduling to other domains.