Write a Blog >>
Mon 19 Jun 2017 11:40 - 12:05 at Aula Master - Compiler Optimizations Chair(s): Uday Bondhugula

Triangular Inequality (TI) has been used in many manual algorithm designs to achieve good efficiency in solving some distance calculation-based problems. This paper presents our generalization of the idea into a compiler optimization technique, named TI-based strength reduction. The generalization consists of three parts. The first is the establishment of the theoretic foundation of this new optimization via the development of a new form of TI named Angular Triangular Inequality, along with several fundamental theorems. The second is the revealing of the properties of the new forms of TI and the proposal of guided TI adaptation, a systematic method to address the difficulties in effective deployments of TI optimizations. The third is an integration of the new optimization technique in an open-source compiler. Experiments on a set of data mining and machine learning algorithms show that the new technique can speed up the standard implementations by as much as 134X and 46X on average for distance-related problems, outperforming previous TI-based optimizations by 2.35X on average. It also extends the applicability of TI-based optimizations to vector related problems, producing tens of times of speedup.

Mon 19 Jun

Displayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

10:50 - 12:30
Compiler OptimizationsPLDI Research Papers at Aula Master
Chair(s): Uday Bondhugula Indian Institute of Science
10:50
25m
Talk
Cache Locality Optimization for Recursive Programs
PLDI Research Papers
Jonathan Lifflander , Sriram Krishnamoorthy Pacific Northwest National Laboratories
11:15
25m
Talk
Fusing Effectful Comprehensions
PLDI Research Papers
Olli Saarikivi , Margus Veanes Microsoft Research, Todd Mytkowicz , Madan Musuvathi Microsoft Research
11:40
25m
Talk
Generalizations of the Theory and Deployment of Triangular Inequality for Compiler-Based Strength Reduction
PLDI Research Papers
Yufei Ding North Carolina State University, Lin Ning North Carolina State University, Hui Guan North Carolina State University, Xipeng Shen North Carolina State University
Media Attached
12:05
25m
Talk
ALIVE-INFER: Data-Driven Precondition Inference for Peephole Optimizations in LLVM
PLDI Research Papers
David Menendez Rutgers University, Santosh Nagarakatte Rutgers University, USA
Media Attached