Invited talk by Dr. Ramakrishna Upadrasta on Sub-Polyhedral Compilation using (Unit-)Two-Variables-Per-Inequality Polyhedra

Title Of the Talk: Sub-Polyhedral Compilation using (Unit-)Two-Variables-Per-Inequality Polyhedra
Speaker: Dr. Ramakrishna Upadrasta
Date&Time: Monday, 30th Dec 2013 14:30-15:30
Venue: Room No-120

Abstract:

The goal of my work is to design algorithms that run with better complexity when compiling or parallelizing loop programs. The framework within which our algorithms operate is the polyhedral model of compilation which has been successful in the design and implementation of complex loop nest optimizers and parallelizing compilers. The algorithmic complexity and scalability limitations of the above framework remain one important weakness. We address it by introducing sub-polyhedral compilation by using (Unit-)Two-Variable-Per-Inequality or (U)TVPI Polyhedra, namely polyhedra with restricted constraints of the type axi+bxj ≤c (±xi±xj≤c). A major focus of our sub-polyhedral compilation is the introduction ofsub-polyhedral scheduling, where we propose a technique for scheduling using (U)TVPI polyhedra. As part of this, we introduce algorithms that can be used to construct under-aproximations of the systems of constraints resulting from affine scheduling problems. This technique relies on simple polynomial time algorithms to under-approximate a general polyhedron into (U) TVPI polyhedra. The above under-approximation algorithms are generic enough that they can be used for many kinds of loop parallelization scheduling problems, reducing each of their complexities to asymptotically polynomial time. We also introduce sub-polyhedral code-generation where we propose algorithms to use the improved complexities of (U)TVPI sub-polyhedra in polyhedral code generation. In this problem, we show that the exponentialities associated with the widely used polyhedral code generators could be reduced to polynomial time using the improved complexities of (U)TVPI subpolyhedra. The above presented sub-polyhedral scheduling techniques are evaluatedin an experimental framework. For this, we modify the state-of-the-artPLuTo compiler which can parallelize for multi-core architectures using permutation and tiling transformations. We show that using our scheduling technique, the above under-approximations yield polyhedral that are non-empty for 10 out of 16 benchmarks from the Polybench (2.0) kernels. Solving the underapproximated system leads to asymptotic gains in complexity, and shows practically significant improvements when compared to a traditional LP solver. We also verify that code generated by our sub-polyhedral parallelization prototype matches the performance of PLuTo-optimized code when the under-approximation preserves feasibility.

Speaker Profile:

Ramakrishna Upadrasta works as a postdoctoral researcher in Indian Institute of Science, Bangalore. He works in parallelizing compilers using a well understood mathematical abstraction of loop-programs called as Polyhedral Model of Compilation which uses linear and integer linear programming (and related tools) so that for-loop programs can be transformed to run efficiently on modern architectures like multi-core or GPU. Specifically, his recent work has been to propose “sub-polyhedral compilation” so as to reduce the complexity of algorithms used in polyhedral compilation using approximations of polyhedra, namely ones that can be represented using (Unit-) Two-Variables-Per- Inequality constraints. The contributions of his thesis were to reduce the complexity of scheduling in polyhedral compilation from quintic time to cubic time, and to reduce the complexity of codegeneration from exponential complexity to polynomial complexity. He obtained his Ph.D from University of Paris-Sud (11) and INRIA, Paris, France in March- 2013. Earlier, he worked for INRIA, Paris as research engineer, Lawrence Livermore National Laboratories, USA as research scholar and Hewlett Packard Compiler Optimization Group as software engineer. He has a Masters of Science from Colorado State University, USA, a Masters of Engineering in Computer Science from Indian Institute of Science, in 2000, and a Bachelors in Electrical Engineering from Andhra University in 1998. He has research interests in Programming languages, compiler optimizations, parallelizing compilers, program optimizations, static analysis, verification, algorithms, combinatorial optimization, theory of algorithms.

Dates:
Monday, December 30, 2013 - 14:30 to 15:30