-
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document -
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document -
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.
Description
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.