Provably Efficient

Provably Efficient

In several publications on Cilk++ and Intel CIlk the writers use the term provably efficient scheduling algorithm. I am paraphrasing here.

Being an operations research professional I have done my fair share of mathematical proofs, but, frankly,I have never had a formal education in scheduling.

I do know that scheduling is an amazing complicated field of operations research and that there are few rigorousproofs in it. Each scheduling situation is unique and there are few proofs that can be applied to it; as compared to resource allocation in which we have a simplex algorithm which has beenrigorously proved.

If there is a formal proof please give me a reference or link, if there is a paper a reference or link will also work. I just want someone to expand on that phrase.

The people that I work for will surely want to know more about this.


6 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

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.


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

Please understand that I am not requesting anything that is not in the public domain. I do not want trade secrets, just a convincing argument.

Thanx in advance.


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):

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

Leave a Comment

Please sign in to add a comment. Not a member? Join today