Lightweight and Locality-Aware Composition of Black-Box Subroutines
summary
A system called Fern enriches black-box subroutine interfaces with producer-consumer annotations that describe how small data blocks are produced and consumed, then auto-generates lightweight glue that tile-and-chunk across calls to restore cache locality. Experiments show fused compositions beat naive composition (a 30% regression example) and reach library-level speed, with microbenchmarks showing up to 5× over unfused code and prior hand-fused libraries sometimes 600× faster than naive implementations; limits: no register-level fusion and GPUs remain hard.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:06Hand-optimized libraries vs naive code
- 3:13Black-box subroutine composition
- 6:05Cache misses in naive composition
- 9:34Monolithic compilers limitations
- 10:36Fern’s locality-aware composition
- 12:44Fern’s extended function interface
- 14:07Experimental results with Fern
- 16:58Fern vs DSLs like ISPC
- 17:40Future work challenges
- 19:24Q&A
related talks
40mSuperfusion: Eliminating Intermediate Data Structures via Inductive Synthesis
55mDeforestation and Program Fusion
18mBlame-aware Recomposition for Formally Secure Low-level Compiler Backends
11mEnabling Composition of Kernels and Compilers
24mMapping Sparse Applications to Accelerated Computing Systems
23mDeep Fusion for Efficient Nested Recursive Computations
01h 05mControl Flow Obfuscation for Featherweight Java + Efficient Fair Conjunction
18mLoop Fusion in Matrix Multiplications with Sparse Dependence