Search papers, labs, and topics across Lattice.
This paper introduces Wavelet, the first formally verified compiler for asynchronous dataflow architectures, addressing the challenges of maintaining determinacy while enabling pipelining. By employing a novel capability type system with synchronization mechanisms, the authors ensure that the compiled dataflow programs are both deterministic and optimized for parallel execution. Evaluation results indicate that the dataflow graphs generated by Wavelet are comparable in size to those produced by an unverified optimizing compiler, highlighting its practical viability.
Formal verification of a compiler for asynchronous dataflow could redefine the reliability and efficiency of parallel computing architectures.
Dataflow architectures have gained renewed interest due to their balance between power efficiency and performance. In (spatial) dataflow architectures, a program is represented as a set of entirely distributed and dynamically scheduled dataflow operators that communicate through asynchronous channels, which greatly improves data locality and parallelism. However, compiling to dataflow architectures remains an error-prone process, in order to maintain determinacy while enabling pipelining. Determinacy means that the result of a dataflow program is deterministic and independent of the schedule of operator execution, and pipelining is an important optimization in spatial dataflow that enables parallelism across loop iterations. In this work, we present Wavelet, the first effort to formally verify a compiler for asynchronous dataflow. We use a mix of techniques to achieve this goal. Our frontend uses a novel capability type system with fences to synchronize conflicting memory accesses and enable pipelining. We then verify a Lean formalization of two core passes of our compiler that translates elaborated programs from the type checker to dataflow graphs, proving important properties of forward simulation and determinacy. Notably, our formalization semantically propagates the soundness guarantees of the frontend type system, ensuring modularity between simulation and determinacy proofs. In evaluation, we show that dataflow graphs compiled by Wavelet have comparable sizes to those produced by an unverified optimizing compiler for the RipTide spatial dataflow architecture.
CMU ML