Fusing Gathers with Integer Linear Programming
summary
Extends an existing Integer Linear Programming formulation to fuse combinator programs that include the gather combinator, encoding fusion choices with binary X variables, Pi ordering, M manifest flags and new D order variables. Implements it in Accelerate and runs benchmarks on programs of about 50–150 combinators, finding the commercial ILP solver solves problems in <0.01s while open‑source solvers time out for some cost functions. Cost models are provisional and code generation is working but not production ready.
AI-written summary · about
chapters (16)
- 0:00Fusion with ILP introduction
- 2:29Fusion basics in array languages
- 5:21Formalizing array fusion
- 11:53Fusing maps and gathers
- 17:15Integer linear programming for fusion
- 23:30Cost functions and benchmarks
- 26:47Limitations and future work
- 29:20Gather/scatter combinators design
- 31:08Scheduling in Halide comparison
- 33:17Accelerate fusion engine improvements
- 35:04Work duplication and cost models
- 36:31CPU/GPU cost functions
- 37:40Automatic fusion in XLA
- 38:23Judgment rules and binary fusion
- 40:11ILP binary fusion limits
- 40:55Q&A
related talks
40mSuperfusion: Eliminating Intermediate Data Structures via Inductive Synthesis
16mA Compiler for Fused Relational Operations on Multisets
15mMetaprogramming with Combinators
25mAUTOMAP: Inferring Rank-Polymorphic Function Applications with Integer Linear Programming
01h 02mLogic, Optimization, and Constraint Programming: A Fruitful Collaboration
01h 01mFunction Composition in Programming Languages
18mLoop Fusion in Matrix Multiplications with Sparse Dependence
19mCompile-Time Java Stream Fusion via mapMulti