kremlin: like gprof but for parallelization
Kremlin is a tool that, given a serial program, tells you which regions to
parallelize. It was developed by researchers at the University of San Diego and
the University of California, San Diego.
To create Kremlin we developed a novel dynamic analysis, hierarchical critical
path analysis, to detect parallelism across nested regions of the program,
which connects to a parallelism planner which evaluates many potential
parallelizations to figure out the best way for the user to parallelize the
The following shows you the basic flow of using Kremlin to create a
parallelization plan for your program.
make CC=kremlin-gcc ./demo data.large.txt kremlin --planner=openmp PlannerType = OpenMP Target : NumCore = 4, Overhead = 0, Cache = 0 MB, BW= 0 MB/s Speedup: 4.00 Serial : 182 Parallel: 45 [ 0] TimeRed(4)=62.23%, TimeRed(Ideal)=75.27%, Cov=82.97%, SelfP=10.79, DOALL LOOP main.c [ 19 - 23]: main [ 1] TimeRed(4)=12.77%, TimeRed(Ideal)=15.93%, Cov=17.03%, SelfP=15.50, DOALL LOOP main.c [ 11 - 13]: main ...
The output of the planner lists the regions of the program that you should
parallelize, in the order that they should be parallelized.
It also gives some basic information about each suggestion, including the
reduction in time if parallelized and the type of parallelism present.
Before you get started, you will need the following software installed:
- A modern C and C++ compiler (GCC 4.7+ or Clang 3.1+, per LLVM's requirements)
- Java JDK (1.6 or above)
- python with argparse (2.7 or above highly recommended)
- CMake (2.8.8 or above)
- The C++ Boost Library (1.42 or above)
Kremlin has been tested on Mac OS X (10.9 and 10.10) and RHEL 7 but should work well
on any modern Linux distribution, assuming you have the required software listed above.
To get started clone the kremlin repository and simply run
make inside the
This will take some time as it has to compile LLVM.
After compilation is complete, update your shell's
PATH to point to Kremlin's
The exact directory to use will have been printed after successfully
To ensure you have the proper setup, run the Kremlin test suite by going into
kremlin/test directory and running the
This will take a few minutes the first time you run it; subsequent runs should
be significantly faster.
kremlin will print out a message if any of the tests failed; if you don't see
this message then kremlin has been successfully installed.
Parallelization Planning with Kremlin
The basic flow for using Kremlin requires three steps:
- Compile your program with
kremlin-g++. These programs are
drop-in replacements for
- Run your program as you normally would.
- Run the parallelism planner by invoking the
kremlinprogram within the
same directory that you build/ran your program.
By default, Kremlin gives you basic parallelization information based on a 4 core
Kremlin provides various planners to guide you towards parallelizing with a specific
platform (e.g. OpenMP 2.0).
kremlin --help for a list of options that Kremlin's parallelism planner
Target parallelization platforms include:
- OpenMP (
--planner=openmp): Based on OpenMP 2.0
- Profiler (
--planner=profiler): No plan, just parallelism statistics for
your program's regions.
- GPU (
--planner=gpu): Based on OpenCL. This planner is experimental.
- Cilk (
--planner=cilk): Based on Cilk++. This planner is experimental.
More Details and Getting Help
For more details about using Kremlin and how it works, head to Kremlin's Bitbucket wiki.
If you are running into problems, please use our issue tracker here on Bitbucket.