Cilk work-stealing scheduler
E679890
load-balancing algorithm
parallel runtime scheduling algorithm
task scheduler
work-stealing scheduler
The Cilk work-stealing scheduler is a parallel runtime scheduling algorithm that efficiently balances dynamic multithreaded workloads by having idle processors "steal" tasks from busy ones, enabling scalable performance on multicore systems.
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
load-balancing algorithm
ⓘ
parallel runtime scheduling algorithm ⓘ task scheduler ⓘ work-stealing scheduler ⓘ |
| analyzes | work and span of computation ⓘ |
| assignsTo | each worker a deque of tasks ⓘ |
| associatedWith |
Charles E. Leiserson
NERFINISHED
ⓘ
MIT Laboratory for Computer Science NERFINISHED ⓘ Robert D. Blumofe NERFINISHED ⓘ Yuli Zhou NERFINISHED ⓘ |
| basedOn | work-stealing ⓘ |
| behavior | idle processors steal tasks from busy processors ⓘ |
| designedFor |
multicore systems
ⓘ
shared-memory multiprocessors ⓘ |
| executionModel | each worker runs a deque-driven loop of executing or stealing tasks ⓘ |
| formalizedIn | Cilk-5 multithreaded language papers ⓘ |
| goal |
load balancing
ⓘ
minimize parallel execution time ⓘ minimize scheduling overhead ⓘ |
| guarantees |
expected running time within constant factor of optimal
ⓘ
expected space usage within constant factor of serial execution ⓘ |
| handles |
irregular parallelism
ⓘ
nested parallelism ⓘ |
| hasProperty |
distributed scheduling
ⓘ
good cache locality ⓘ low scheduling overhead ⓘ noncentralized scheduling ⓘ provably efficient ⓘ scalable ⓘ space-efficient ⓘ |
| implementsConcept |
continuation stealing
ⓘ
lazy task creation ⓘ work-first principle ⓘ |
| influenced |
.NET Task Parallel Library work-stealing queues
NERFINISHED
ⓘ
Java ForkJoinPool NERFINISHED ⓘ many modern task-based runtime systems ⓘ |
| inspired | work-stealing schedulers in other task-parallel runtimes ⓘ |
| localPolicy | workers execute tasks in LIFO order from bottom of deque ⓘ |
| operatesOn | ready deque ⓘ |
| schedules |
DAG of tasks
ⓘ
fork-join parallelism ⓘ spawnable tasks ⓘ |
| stealPolicy | thieves steal tasks in FIFO order from top of victim deque ⓘ |
| supports | dynamic multithreaded workloads ⓘ |
| usedIn |
Cilk
NERFINISHED
ⓘ
Cilk++ NERFINISHED ⓘ Cilk-5 NERFINISHED ⓘ Intel Cilk Plus NERFINISHED ⓘ |
| usesDataStructure | double-ended queue ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.