Kremlin Logo
Kremlin Logo

Kremlin is a tool that, given a serial program, tells you which regions to parallelize.

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.

Sample Usage

	> 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

In the above example, the tool identified two loops (lines 19-23 in main, and lines 11-13 in main) that could be parallelized. The first loop would result in a 62 percent time reduction if parallelized on 4 cores, and 75 percent if parallelized on an infinite core zero-overhead machine. It has 82 percent of the execution time, and the inherent parallelism of the loop is 10.79X, and the loop is DOALL.

Downloading Kremlin

Kremlin is available as a Git reponsitory in Bitbucket. You can clone the repository with the following command:
git clone
Please see our official Bitbucket page for instructions on how to build and run Kremlin.

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.

If you have any questions, please contact Kremlin team members Sat Garcia or Michael Taylor at the following google group: kremlin-questions AT If you have any issues using Kremlin, we recommend that you report them on our official Bitbucket page.

The Kremlin Team

Prof. Sat Garcia    Donghwan Jeon    Chris Louie    Prof. Michael Taylor


  1. Parallel Speedup Estimates for Serial Programs
    PhD Dissertation, by Donghwan Jeon, 2012.

  2. A Practical Oracle for Sequential Code Parallelization
    PhD Dissertation, by Saturnino Garcia, 2012.

  3. Skadu: Efficient Vector Shadow Memories for Poly-Scopic Program Analysis
    Donghwan Jeon, Saturnino Garcia, and Michael B. Taylor.
    Code Generation and Optimization (CGO), February 2013. (Talk) (Paper)(bib)

  4. Kismet: Parallel Speedup Estimates for Serial Programs
    Donghwan Jeon, Saturnino Garcia, Chris Louie, and Michael Bedford Taylor.
    Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), October 2011. (pdf) (bib) (talk ppt, talk pdf)

  5. Kremlin: Rebooting and Rethinking gprof for the Multicore Age
    (aka Automatic Parallelism Planning and Discovery with Kremlin)
    Saturnino Garcia, Donghwan Jeon, Chris Louie, and Michael Bedford Taylor.
    Programming Language Design and Implementation (PLDI), June 2011. (pdf) (bib) (talk ppt, talk pdf)

  6. Parkour: Parallel Speedup Estimates for Serial Programs
    Donghwan Jeon, Saturnino Garcia, Chris Louie, Michael Bedford Taylor.
    HOTPAR, June 2011. (pdf) (bib)

  7. Kremlin: Like gprof, but for Parallelization
    Donghwan Jeon, Saturnino Garcia, Chris Louie, Sravanthi Kota Venkata and Michael Bedford Taylor.
    Principles and Practice of Parallel Programming (PPoPP), February 2011. (pdf, poster pdf) (bib)

  8. Bridging the Parallelization Gap: Automating Parallelism Discovery and Planning,
    Saturnino Garcia, Donghwan Jeon, Chris Louie, Sravanthi Kota Venkata, Michael Bedford Taylor.
    HOTPAR, June 2010. (pdf) (bib)


09/10/2015Kremlin is now officially available to the public! The official Kremlin repository is available on BitBucket.
4/14/2011       Sat and DJ are award best Computer Science and Engineering Poster at the 2011 Jacobs School Engineering Expo!

2/15/2011Sat and DJ win best poster award at PPoPP 2011!

(They were working on a grant proposal during the awards session
and another UCSD student had to receive it for them!)

11/30/2009Chris wins a 2010 CRA Outstanding Undergraduate Researcher Award honorable mention based on his research on the Kremlin project. Congrats, Chris!

This material is based upon work supported by the National Science Foundation under Grant No. 1018850 and 0725357.

Back to Michael Taylor's main page.