The Cilk workstealing scheduler can be shown to be within a factor of 2 (worst case) of an ideal, greedy scheduler. I will try to find a link to the appropriate literature and post it here.

-Pablo

Please have a look at the following paper: Scheduling Multithreaded Computations by Work Stealing, Blumofe and Leiserson, 1994.

Intel Cilk Plus is based on the work done by Professor Leiserson and his colleagues. The paper listed is on the public MIT website.

- Barry

Thanks for the link, brunodefraine. Here is another link to the same paper, formatted a little better (actual text instead of a scanned image):

http://portal.acm.org/citation.cfm?doid=324133.324234

You might need an ACM membership to read it, though.

Almost immediately after I posted my last message, I realised that I miswrote the actual guarantees of the Cilk scheduler vs. greedy schedulers. Dr. Leiserson also spotted my error and was quick to correct me:

"Your comment about the Cilk scheduler and greedy is not quite correct. A greedy scheduler is within a factor of 2 of optimal. (See CLRS, 3rd ed., Ch. 27.) The Cilk work-stealing scheduler is within a constant factor of optimal with high probability. For applications with sufficiently high parallelism, both greedy and the Cilk scheduler are optimal (constant factor of 1) to within a low-order additive term. All of this assumes an ideal computer (no problems with memory bandwidth, etc.). The greedy bound ignores costs due to scheduling, however, but the Cilk work-stealing bound does account for scheduling overheads, including contention when stealing from the work deque."

- Pablo