Superfusion: Eliminating Intermediate Data Structures via Inductive Synthesis
summary
Superfusion uses inductive program synthesis to remove intermediate collections by synthesizing a small compression function that maps packed structures to scalars, generating per-hole input/output examples and delegating hole filling to program‑by‑example solvers. The implementation, SuFu, synthesizes compression functions by enumeration, rewrites sketches into scalar code, and runs on a 290‑task benchmark, solving 264 out of 290 tasks, outperforming rewrite‑based fusion and matching many specialized restructuring tools; artifacts and evaluation data are available with the paper.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 1:07Divide and conquer synthesis
- 4:59Synthesis problem definition
- 7:07AutoLifter decomposition
- 10:59AutoLifter generalizations
- 13:50Summary and Q&A
- 19:12Superfusion goals
- 24:07Eliminating intermediate structures
- 27:40Compression function example
- 31:30Divide and conquer via Sufu
- 33:37Native interpreter synthesis
- 35:24Sufu evaluation summary
related talks
23mDeep Fusion for Efficient Nested Recursive Computations
14mDataflow-Based Pruning for Speeding up Superoptimization
55mDeforestation and Program Fusion
22mLightweight and Locality-Aware Composition of Black-Box Subroutines
23mInductive Program Synthesis by Meta-Analysis-Guided Hole Filling
15mHieraSynth: A Parallel Framework for Complete Super-Optimization with Hierarchical(…)
41mFusing Gathers with Integer Linear Programming
29mStaging Automatic Differentiation with Fusion