Kremlin
Authors:
Open Access
- 4 June 2011
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 46 (6) , 458-469
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 ? This paper examines 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.Keywords
This publication has 39 references indexed in Scilit:
- Modeling optimistic concurrency using quantitative dependence analysis2008
- Compiler-Driven Dependence Profiling to Guide Program Parallelization2008
- Valgrind2007
- POSH2006
- A microbenchmark suite for OpenMP 2.0ACM SIGARCH Computer Architecture News, 2001
- SUIF Explorer1999
- Parallel programming with PolarisComputer, 1996
- Loop-level parallelism in numeric and symbolic programsIEEE Transactions on Parallel and Distributed Systems, 1993
- Interactive parallel programming using the ParaScope EditorIEEE Transactions on Parallel and Distributed Systems, 1991
- Measuring parallelism in computation-intensive scientific/engineering applicationsIEEE Transactions on Computers, 1988