Verifying Array Properties in Pure Data-Parallel Programs
This program is tentative and subject to change.
In functional data-parallel programs, index array computations are separated into sequences of bulk-parallel operators—map, prefix sum, scatter—and used to gather or scatter data array elements, thus determining data array properties. This programming style is problematic for general-purpose verification frameworks (e.g., Dafny, F*, Liquid Haskell), which are flexible and powerful, but require verbose annotations and non-trivial user proofs, making them inaccessible to non-experts. We present a \emph{compiler approach} to verifying array properties with high automation, aimed at making verification of data-parallel programs more accessible to users without verification expertise. We support a small but powerful predefined set of properties—equivalence, range, injectivity, bijectivity, monotonicity, filtering, partitioning—that enable the compiler to (automatically) reason at a higher level of abstraction. We evaluate our approach on challenging applications with non-linear indexing, including graph algorithms, Cooley-Tukey FFT, filtering, multi-way partitioning, and flattened irregular nested parallel programs that are difficult to verify, such as batch operations on arrays of different sizes.
This program is tentative and subject to change.
Fri 19 JunDisplayed time zone: Mountain Time (US & Canada) change
10:30 - 12:10 | |||
10:30 20mTalk | Verifying Array Properties in Pure Data-Parallel Programs PLDI Research Papers Nikolaj Hey Hinnerskov University of Copenhagen, Robert Schenck Northeastern University, Cosmin E. Oancea University of Copenhagen DOI | ||
10:50 20mTalk | Soteria: Efficient Symbolic Execution as a Functional Library PLDI Research Papers Sacha-Élie Ayoun Imperial College London; Soteria Tools, Opale Sjöstedt Imperial College London; Soteria Tools, Azalea Raad Imperial College London; Soteria Tools DOI | ||
11:10 20mTalk | A Categorical Basis for Robust Program Analysis PLDI Research Papers DOI | ||
11:30 20mTalk | Restart and Refine: Scalable IFDS Taint Analysis across Memory Budgets PLDI Research Papers DOI | ||
11:50 20mTalk | Synthesizing Backward Error Bounds, Backward PLDI Research Papers DOI Pre-print | ||