by Graham on March 16, 2009.
Tagged as: Lunches.
Peter talked about work-stealing and implementation of runtime systems. We started with briefly discussing a simple implementation of a runtime system, and the scalability problems that you get [3]. There was a brief passage about the optimality of work stealing [1], to get straight into the new paper about the runtime support for multicore Haskell [2]. At the end we concluded with questioning the premises that seems common: each task is executed exactly once. There is a nice new paper called “Idempotent Work Stealing” [4] which changes the premise to “each task is executed at least once” and show by microbenchmarks that puts and takes executed on this queue only costs 60% of the Chase-Lev algorithm [5].
[1] Scheduling multithreaded computations by work stealing
[2] Runtime Support for Multicore Haskell
[3] Erlang Multicore
[4] Idempotent Work Stealing
[5] Dynamic Circular Work-stealing deque