Reducers and Other Cilk++ Hyperobjects

by Matteo Frigo, Pablo Halpern, Charles E. Leiserson, and Stephen Lewin-Berlin.

To appear in SPAA 2009.
SPAA 2009 Best Paper Award.
[Full text]


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.

This page maintained by: Matteo Frigo. Last updated: Sun Jun 21 09:29:38 2009