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
target program.

Example Usage

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.

Getting Started

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)
  • ant
  • python with argparse (2.7 or above highly recommended)
  • scons
  • 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
kremlin directory.
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
bin directory.
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
the kremlin/test directory and running the scons command.
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:

  1. Compile your program with kremlin-gcc or kremlin-g++. These programs are
    drop-in replacements for gcc and g++, respectively.
  2. Run your program as you normally would.
  3. Run the parallelism planner by invoking the kremlin program 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).
Run 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.