The Cilk tool suite

Cilk supports a suite of tools for analyzing Cilk programs.

  • The Cilksan determinacy-race detector can be used to regression-test Cilk programs for determinism.

  • The Cilkscale scalability analyzer quantitatively measures the parallelism of a Cilk program.

Both Cilksan and Cilkscale are packaged with the Tapir/LLVM compiler. The Tapir/LLVM compiler also supports CSI, a framework that allows programmers to write dynamic-analysis tools that use compiler instrumentation without modifying the compiler.

The Cilksan determinacy-race detector

Cilksan is a provably good determinacy-race detector packaged with the Tapir/LLVM compiler. Given a Cilk program and an input — i.e., a regression test — Cilksan will either certify that the program is deterministic or pinpoint the instructions that can cause lead to nondeterministic program behavior. In other words, Cilksan allows programmers to regression-test Cilk programs for deterministic behavior.

Cilksan is designed to be used in a similar fashion as Google’s Sanitizer tools. To use the Cilksan determinacy-race detector on your program, compile and link the program with the -fsanitize=cilk compiler flag.

You might receive an error about libclang_rt.cilksan-x86_64.so when running a program compiled with -fsanitize=cilk If the Cilksan dynamic library is not in your dynamic-library path, e.g., LD_LIBRARY_PATH on Linux. The Cilksan dynamic library is typically built or installed with Tapir/LLVM in a subdirectory named lib/clang/<VERSION>/lib/linux, where <VERSION> is the version of Clang and LLVM on which Tapir/LLVM is based. If you receive such an error, make sure this path is in your dynamic-library path.

Cilksan implements the SP-bags algorithm (Feng & Leiserson, 1997; Feng & Leiserson, 1999) to study a Cilk program execution to detect determinacy races, which occur when two logically parallel executed instructions access the same memory location and at least one of those instructions is a write. Conceptually, determinacy races are more primitive than data races, which occur when the instructions involved in a determinacy race hold no locks in common. The SP-bags algorithm executes a Cilk program serially and identifies logically parallel instructions based on the parallel control flow implemented by Cilk’s keywords for fork-join parallelism. The SP-bags algorithm detects determinacy races in time \(O(T_1\alpha(v,v))\) time, where \(T_1\) is the time to run the Cilk program on one processor, \(v\) is the number of shared-memory locations, and \(\alpha\) is Tarjan’s functional inverse of Ackermann’s function.

The Cilkscale scalability analyzer

Publications

  1. Feng, M., & Leiserson, C. E. (1997). Efficient Detection of Determinacy Races in Cilk Programs. SPAA, 1–11.
  2. Feng, M., & Leiserson, C. E. (1999). Efficient Detection of Determinacy Races in Cilk Programs. Theory of Computing Systems, 32(3), 301–326.
  3. He, Y., Leiserson, C. E., & Leiserson, W. M. (2010). The Cilkview Scalability Analyzer. SPAA, 145–156. https://doi.org/10.1145/1810479.1810509

Last updated: