Back To Schedule
Thursday, March 5 • 15:15 - 17:15
Poster: 'Efficient implementation of cactus stack in work-stealing runtimes,' Chaoran Yang, Rice University

Sign up or log in to save this to your schedule, view media, leave feedback and see who's attending!

Multithreaded concurrency platforms that employ a work-stealing scheduler often requires to support a “cactus stack”, wherein multiple child functions of a common calling ancestry can exist and operate in parallel. Unfortunately, such existing concurrency platforms failed to support a cactus stack without making at least one of the following sacrifice:

- unable to interoperate with legacy or third-party serial binaries that have been compiled to use an ordinary linear stack,
- a weak time bound that cannot provide near-perfect linear speedup on some application even with sufficient parallelism,
- unbounded or extravagant use of memory for the cactus stack, or
- requires special support from the operation system kernel.

We have addressed this cactus-stack problem by carefully manage the memory used for cactus stacks, while maintaining the near-perfect linear speedup time bound. Even though our work-stealing runtime may consume up to DPS virtual-address space, the physical memory it uses is bounded by P(S + D), where D is the depth of stack, P is the number of processors, and S is the stack size. Benchmark results show that our implementation incurs very low overhead comparing to previous approaches and achieves up to 2x speedup over the state of the art CilkPlus runtime library.


Thursday March 5, 2015 15:15 - 17:15 CST
BioScience Research Collaborative 6500 Main Street, Houston, Tx 77005