79. KREMLIN: LIKE GPROF, BUT FOR PARALLELIZATION

Department: Computer Science & Engineering
Faculty Advisor(s): Michael Taylor
Award(s): Department Best Poster

Primary Student
Name: Donghwan Jeon
Email: djeon@ucsd.edu
Phone: 858-822-8240
Grad Year: 2012

Student Collaborators
Saturnino Garcia, sat@cs.ucsd.edu

Abstract
Many recent parallelization tools lower the barrier for parallelizing a program, but overlook one of the first questions that a programmer needs to answer: which parts of the program should I spend time parallelizing?

We introduce Kremlin, an automatic tool that, given a serial version of a program, will make recommendations to the user as to what regions (e.g. loops or functions) of the program to attack first. Kremlin introduces a novel hierarchical critical path analysis and develops a new metric for estimating the potential of parallelizing a region: self-parallelism. We further introduce the concept of a parallelism planner, which provides a ranked order of specific regions to the programmer that are likely to have the largest performance impact when parallelized. Kremlin supports multiple planner personalities, which allow the planner to more effectively target a particular programming environment or class of machine.

We demonstrate the effectiveness of one such personality, an OpenMP planner, by comparing versions of programs that are parallelized according to Kremlin's plan against third-party manually parallelized versions. The results show that Kremlin's OpenMP planner is highly effective, producing plans whose performance is typically comparable to, and sometimes much better than, manual parallelization. At the same time, these plans would require that the user parallelize significantly fewer regions of the program.

« Back to Posters or Search Results