Lambda Calculus with Algebraic Simplification for Reduction Parallelization by Equational Reasoning
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 AugDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
10:30 - 12:00 | Compilation & ParallelismResearch Papers at Aurora Borealis Chair(s): Michael D. Adams University of Michigan | ||
10:30 22mTalk | Rebuilding Racket on Chez Scheme (Experience Report) Research Papers Matthew Flatt University of Utah, Caner Derici Indiana University, R. Kent Dybvig Cisco Systems, Inc, Andy Keep Cisco Systems, Inc, Gustavo E. Massaccesi Universidad de Buenos Aires, Sarah Spall Indiana University, Sam Tobin-Hochstadt Indiana University, Jon Zeppieri Link to publication DOI | ||
10:52 22mTalk | Compiling with Continuations, or without? Whatever. Research Papers Youyou Cong Tokyo Institute of Technology, Leo Osvald Purdue University, USA, Gregory Essertel Purdue University, Tiark Rompf Purdue University | ||
11:15 22mTalk | Lambda Calculus with Algebraic Simplification for Reduction Parallelization by Equational Reasoning Research Papers Akimasa Morihata University of Tokyo | ||
11:37 22mTalk | Fairness in Responsive Parallelism Research Papers Stefan K. Muller Carnegie Mellon University, Sam Westrick Carnegie Mellon University, Umut A. Acar Carnegie Mellon University |