Fusing Filters with Integer Linear Programming

Amos Robinson
University of New South Wales

The key to compiling functional, collection oriented array programs into
efficient code is to minimise memory traffic.  Fusing array operations
together reduces memory traffic, but finding the best fusion clustering with
the least memory traffic turns out to be NP-hard. Integer linear programming
(ILP) is a well known technique for solving NP-hard problems, with adequate
solvers being freely available.  Previous work has used ILP to find the “best”
fusion clusterings for imperative programs, but these approaches cannot handle
vertical fusion or array contraction for size-changing operations such as
filter. By using combinators instead of imperative loops, we have more higher-
level information available to guide optimisations. In this talk, I will show
how we are able to use this high-level information to extend previous ILP-
based approaches to support size-changing operations such as filter.