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//lib/linux`, where `` 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.

Publications

1. Feng, M., & Leiserson, C. E. (1997). Efficient Detection of Determinacy Races in Cilk Programs. In SPAA (pp. 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. In SPAA (pp. 145–156). ACM. https://doi.org/10.1145/1810479.1810509

Last updated: