Write a Blog >>
ICFP 2019
Sun 18 - Fri 23 August 2019 Berlin, Germany
Mon 19 Aug 2019 11:15 - 11:37 at Aurora Borealis - Compilation & Parallelism Chair(s): Michael D. Adams

Parallel reduction is a major component of parallel programming and widely used for summarization and/or aggregation. However, it is not well understood what sorts of nontrivial summarizations can be implemented as parallel reductions. This paper develops a calculus named \lambda^{as}, a simply-typed lambda calculus with algebraic simplification. The calculus provides a foundation for studying parallelization of complex reductions by equational reasoning. Its key feature is \delta abstraction. A \delta abstraction is observationally equivalent to the standard \lambda abstraction, but its body is simplified before the arrival of its arguments by using algebraic properties such as associativity and commutativity. In addition, the type system of \lambda^{as} guarantees that simplifications caused by \delta abstractions do not lead to serious overheads. The usefulness of \lambda^{as} is demonstrated on examples of developing complex parallel reductions, including those containing more than one reduction operator, loops with jumps, prefix-sum patterns, and even tree manipulations.

Mon 19 Aug
Times are displayed in time zone: (GMT+02:00) Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

10:30 - 12:00: Research Papers - Compilation & Parallelism at Aurora Borealis
Chair(s): Michael D. AdamsUniversity of Michigan
icfp-2019-papers10:30 - 10:52
Matthew FlattUniversity of Utah, Caner DericiIndiana University, R. Kent DybvigCisco Systems, Inc, Andy KeepCisco Systems, Inc, Gustavo E. MassaccesiUniversidad de Buenos Aires, Sarah SpallIndiana University, Sam Tobin-HochstadtIndiana University, Jon Zeppieri
Link to publication DOI
icfp-2019-papers10:52 - 11:15
Youyou CongTokyo Institute of Technology, Leo OsvaldPurdue University, USA, Gregory EssertelPurdue University, Tiark RompfPurdue University
icfp-2019-papers11:15 - 11:37
Akimasa MorihataUniversity of Tokyo
icfp-2019-papers11:37 - 12:00
Stefan K. MullerCarnegie Mellon University, Sam WestrickCarnegie Mellon University, Umut A. AcarCarnegie Mellon University