Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We give an O(n + minfn; mg log m) work algorithm for scheduling n tasks with ?exible amount of parallelism on m processors, provided the speedup functions of the tasks are concave. We give ef?cient parallelizations of the algorithm that run in polylogarithmic time. Previous algorithms were sequential and required quadratic work. This is in some sense a best-possible result since the problem is NP-hard for more general speedup functions.

Questions and Answers

You need to be logged in to be able to post here.