Parallel Computing Technology Group
Menu:
Software
This page provides a list of software that the group releases publicly.Disclaimer: We cannot guarantee that the software is bug-free,
so use it at your own risk. :-)
If you run into issues, please contact
PI I-Ting Angelina Lee.
Our group works closely with the Cilk Plus
concurrency platform, a C/C++ based parallel language.
Many modern compilers support Cilk Plus, including
GCC,
Intel C/C++ compiler, and
Clang/LLVM.
Most of our work is done primarily with the Clang/LLVM Cilk Plus compiler
and by extending the
Cilk Plus runtime
system released by Intel.
From time to time, our work results in tools built on top of Cilk Plus or
extends the compiler / runtime with features that can be of use to
the broader community — whether it's for research or educational purpose,
and we release these software via our
public GitHub account,
so check back often to see what we are up to!
F-Order
We have developed F-Order, a parallel determinacy race detector for detecting
races in Cilk programs that utilize futures. One of the important component
to race detecting task parallel code is reachability that, given two
instructions that access the same memory location in a conflicting way,
determines whether the two instructions are logically parallel or in series.
When a program utilizes futures, because the computation DAG generated can
contain arbitrary dependences, it is challenging to maintain and query for
reachability efficiently. Existing race detection algorithms cannot handle
the use of futures, or they must detect races while executing the program
sequentially. F-Order is the first known parallel determinacy race algorithm
that can handle the use of futures in a provably efficient manner.
To find out more about F-Order and its implementation and empirical evaluation,
please refer to our
PPoPP 2020 paper (to appear).
The code respository (including benchmarks) can be found in our public GitHub account, along with documentation for installation.
Cilk-L
To support the use of I/O operations in Cilk programs while maintainingin
provably efficient execution times, we have developed Cilk-L, a
variant of work stealing scheduler that supports blocking I/O operations,
and IO futures, a special type of futures that can be used to express
synchronous or asynchronous I/O operations in Cilk computations.
The Cilk-L runtime is based on ProWS that supports futures but additionally
schedules I/O operations that expressed as IO futures in a latency-hiding
manner. Upon encountering a blocking I/O operation, the worker encounters
the I/O operation will go find other work to do, thereby allowing the I/O
blocking time to overlap with computation time needed by other parts of
the application. To find out more about Cilk-L and the IO future library,
please refer to our
APoCS 2020 paper.
The code respository (including hand-compiled benchmarks) can be found in our public GitHub account, along with documentation for installation.
ProWS
To support Cilk programs that utilize futures, we have developed
Proactive Work Stealing, or ProWS, a variant of work stealing
algorithm. ProWS schedules computation with unstructured parallelism (such
as one that arises due to the use of futures) with provably efficient
execution time and bounded stack space.
To find out more about ProWS and the corresponding runtime implementation,
please refer to our
PPoPP 2019 paper.
The code respository (including hand-compiled benchmarks) can be found in our public GitHub account, along with documentation for installation.
FutureRd
We have developed sequential race detectors for Cilk programs that utilize
futures. Depending on how you use the future, the race detector utilizes
different algorithms --- MultiBag algorithm for "structured" use of futures
and MultiBag+ algorithm for general use of futures. The tool race
detects while executing the computation sequentially with small overhead.
Note that, since Cilk Plus does not actually support the use of futures,
the use of futures in the benchmarks are actually "hand-compiled" using
C macros.
To find out more about these algorithms and different types of futures, please refer to our PPoPP 2019 paper.
The code respository (including hand-compiled benchmarks) can be found in our public GitHub account, along with documentation for installation.
NUMA-WS
NUMA-WS is a Cilk Plus based task parallel platform that employs a
NUMA-aware work stealing runtime. NUMA-WS provides provably efficient
execuion time (same as the classic work stealing algorithm) but employs
additional heuristics to minimize remote memory accesses during parallel
executions.
The description of the algorithm and software can be found in our IISWC 2018 paper.
The code respository can be found in our public GitHub account, along with documentation for installation.
The platform itself comes with a set of API to allow the programmer to specify locality hints. To see how to use the API, check out the benchmarks that work with the runtime, also can be found under our public GitHub account.
P-RACER
P-RACER is a parallel race detector for Cilk-P, a variant of Cilk Plus that
supports pipeline parallelism. The tool can race detect while executing the
computation in parallel and provides provably efficient running time.
The description of the algorithm and software can be found in our PPoPP 2018 paper.
The code respository can be found in our public GitHub account, along with documentation for installation.
PORRidge
PORRidge is a process-oblivious record-replayer for Cilk computations
that employ locks.
The description of the software can be found in our PPoPP 2017 paper.
The code respository can be found in our public GitHub account, along with documentation for installation.
C-RACER
C-RACER is a parallel race detector for Cilk Plus computations; it can race detect while
executing the computation in parallel.
The description of the software can be found in our SPAA 2016 paper.
The code respository can be found in our public GitHub account, along with documentation for installation.
Clang/LLVM Cilk Plus Compiler
This version of Clang/LLVM Cilk Plus compiler implements two additional
funcationalities:- Instrumentation for building dynamic program analysis tools for Cilk Plus:
- Avoid inlining of calls to runtime:
Cilk Plus runtime that implements all non-inlined functions:
When supplied with -fcilktool compiler flag, this version of Cilk Plus compiler inserts instrumentation code at various code points to capture events that may be of interest to a dynamic program analysis tool, such as when entering a Cilk function, right before a spawn statement ... etc. The instrumentation inserted by this compiler closely resembles that documented in the open specification for "Intrinsics for Low Overhead Tool Annotations" released by Intel.
Acknowledgement: this code base was originally conceived when we built Cilkprof, and was largely done in collaboration with authors listed in the paper.
The Cilk Plus compiler generates code that interacts with the underlying runtime system (see the the Cilk Plus ABI for detail description of runtime calls). Often time, if you are a researcher modifying the underlying runtime system, the fact that the compiler inline certain calls becomes a real inconvenience. When supplied with -fcilk-no-inline compiler flag, this compiler avoids inlining of the runtime calls. Note that no inlining of runtime calls can incur performance penalty. This overhead can be largely avoided by turning on link-time optimization and use static linking to link with the runtime.
To setup this version of compiler, you can run this build script that will clone the code from our public repo and build it. Note that you need to also get our version of runtime that implements the non-inlined runtime functions if you intend to use the compiler with -fcilk-no-inline flag.
If you use our version of Clang/LLVM Cilk Plus compiler, and you intend to use the compiler with -fcilk-no-inline flag, you need a version of runtime that implements the non-inlined functions (by default they were not implemented). Here it is.