Bounds on Multithreaded Computations by Work Stealing

Blumofe and Leiserson [6] gave the first provably good work-stealing work scheduler for mul-tithreaded computations with dependencies. Their scheduler executes a fully strict (i.e., well-structured) computation on P processors in expected time T1/P + O(T∞), where T1 denotes the minimum serial execution time of the multithreaded computation, and T ∞ denotes the minimum execution time with an infinite number of processors. This thesis extends the existing literature in two directions. Firstly, we analyze the number of successful steals in multithreaded computations. The existing literature has dealt with the number of steal attempts without distinguishing between successful and unsuccessful steals. While that approach leads to a fruitful probabilistic analysis, it does not yield an interesting result for a worst-case analysis. We obtain tight upper bounds on the number of successful steals when the computation can be modeled by a computation tree. In particular, if the computation starts with a complete k-ary tree of height h, the maximum number of successful steals is ∑