Amos Robinson
ABSTRACT
The key to compiling functional, collection oriented array programs into efficient code is to minimise memory traffic. Simply fusing subsequent array operations into a single computation is not sufficient; we also need to cluster separate traversals of the same array into a single traversal. Previous work demonstrated how Integer Linear Programming (ILP) can be used to cluster the operators in a general data-flow graph into subgraphs, which can be individually fused. However, these approaches can only handle operations which preserve the size of the array, thereby missing out on some optimisation opportunities. This paper addresses this shortcoming by extending the ILP approach with support for size-changing operations, using an external ILP solver to find good clusterings.
- Thomas J. Ashby and Michael F. P. O'Boyle. Iterative collective loop fusion. In CC: Compiler Construction, 2006. Google Scholar
Digital Library
- Mohamed-Walid Benabderrahmane, Louis-Noël Pouchet, Albert Cohen, and Cédric Bastoul. The polyhedral model is more widely applicable than you think. In CC: Compiler Construction, 2010. Google ScholarDigital Library
- Siddhartha Chatterjee. Compiling nested data-parallel programs for shared-memory multiprocessors. TOPLAS: Transactions on Programming Languages and Systems, 15(3), 1993. Google ScholarDigital Library
- Siddhartha Chatterjee, Guy E. Blelloch, and Allan L. Fisher. Size and access inference for data-parallel programs. In PLDI: Programming Language Design and Implementation, 1991. Google ScholarDigital Library
- Duncan Coutts, Roman Leshchinskiy, and Don Stewart. Stream fusion: from lists to streams to nothing at all. In ICFP: International Conference on Functional Programming, 2007. Google ScholarDigital Library
- Alain Darte. On the complexity of loop fusion. In PACT: Parallel Architectures and Compilation Techniques, 1999. Google ScholarDigital Library
- Alain Darte and Guillaume Huard. New results on array contraction. In ASAP, 2002. Google ScholarDigital Library
- Guang R. Gao, R. Olsen, Vivek Sarkar, and Radhika Thekkath. Collective loop fusion for array contraction. In LCPC: Languages and Compilers for Parallel Computing, 1992. Google ScholarDigital Library
- Andrew Gill, John Launchbury, and Simon L Peyton Jones. A short cut to deforestation. In Proceedings of the conference on Functional programming languages and computer architecture. ACM, 1993. Google ScholarDigital Library
- Gabriele Keller, Manuel M. T. Chakravarty, Roman Leshchinskiy, Simon L. Peyton Jones, and Ben Lippmeier. Regular, shape-polymorphic, parallel arrays in Haskell. In ICFP: International Conference on Functional Programming, 2010. Google ScholarDigital Library
- Ken Kennedy. Fast greedy weighted fusion. International Journal of Parallel Programming, 29(5), 2001. Google ScholarDigital Library
- Ben Lippmeier, Manuel M. T. Chakravarty, Gabriele Keller, and Amos Robinson. Data flow fusion with series expressions in Haskell. In Haskell Symposium, 2013. Google ScholarDigital Library
- Nimrod Megiddo and Vivek Sarkar. Optimal weighted loop fusion for parallel programs. In SPAA: Symposium on Parallel Algorithms and Architectures, 1997. Google ScholarDigital Library
- Martin Odersky, Martin Sulzmann, and Martin Wehr. Type inference with constrained types. TAPOS, 5(1), 1999. Google ScholarDigital Library
- Louis-Noël Pouchet, Uday Bondhugula, Cédric Bastoul, Albert Cohen, J. Ramanujam, and P. Sadayappan. Combined iterative and model-driven optimization in an automatic parallelization framework. In SC: High Performance Computing, Networking, Storage and Analysis, 2010. Google ScholarDigital Library
- Louis-Noël Pouchet, Uday Bondhugula, Cédric Bastoul, Albert Cohen, J. Ramanujam, P. Sadayappan, and Nicolas Vasilache. Loop transformations: convexity, pruning and optimization. In POPL: Principles of Programming Languages, 2011. Google ScholarDigital Library
- Tiark Rompf, Arvind K Sujeeth, Nada Amin, Kevin J Brown, Vojin Jovanovic, HyoukJoong Lee, Manohar Jonnalagedda, Kunle Olukotun, and Martin Odersky. Optimizing data structures in high-level programs: new directions for extensible compilers based on staging. In ACM SIGPLAN Notices, volume 48, pages 497--510. ACM, 2013. Google ScholarDigital Library
- Yonghong Song, Rong Xu, Cheng Wang, and Zhiyuan Li. Improving data locality by array contraction. IEEE Transactions on Computers, 53(9), 2004. Google ScholarDigital Library
- Anand Venkat, Manu Shantharam, Mary W. Hall, and Michelle Mills Strout. Non-affine extensions to polyhedral code generation. In CGO: Code Generation and Optimization, 2014. Google ScholarDigital Library
Index Terms
- Fusing filters with integer linear programming
Recommendations
Mixed-integer quadratic programming
This paper considers mixed-integer quadratic programs in which the objective function is quadratic in the integer and in the continuous variables, and the constraints are linear in the variables of both types. The generalized Benders' decomposition is a ...
Safe bounds in linear and mixed-integer linear programming
Current mixed-integer linear programming solvers are based on linear programming routines that use floating-point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small ...
Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations
AbstractA standard quadratic program is an optimization problem that consists of minimizing a (nonconvex) quadratic form over the unit simplex. We focus on reformulating a standard quadratic program as a mixed integer linear programming problem. We ...
Comments