Reducers and Other Cilk++ Hyperobjects: Peeking Under the Hood
Posted by Ilya Mirman on Wed, Jun 17, 2009
We have written extensively about the challenges global variables pose for multithreaded applications - inhibiting parallelism by inducing data races.
One way to deal with this challenge is by employing Cilk++ hyperobjects. Cilk++ hyperobjects mitigate data races on non-local variables without the need for locks or code restructuring. Cilk hyperobjects are straightforward to use: Simply by declaring a global variable to be a hyperobject of the appropriate type, data races on the global variable are automatically resolved.
What's Under the Hood?
To date, we have shared WHAT hyperobjects do, but not HOW they work. With the patent filings behind us, we have authored a paper for the 2009 Symposium on Parallelism in Algorithms and Architectures.
Here's the abstract:
This paper introduces hyperobjects, a linguistic mechanism that allows different branches of a multithreaded program to maintain coordinated local views of the same nonlocal variable. We have identified three kinds of hyperobjects that seem to be useful - reducers, holders, and splitters - and we have implemented reducers and holders in Cilk++, a set of extensions to the C++ programming language that enables multicore programming in the style of MIT Cilk. We analyze a randomized locking methodology for reducers and show that a work-stealing scheduler can support reducers without incurring significant overhead.
The paper can be downloaded here.
Comments / Questions? We'd love to hear from you!