Parallel Computing - rFronteddu/general_wiki GitHub Wiki
-
Cilk implements a randomized "work-stealing" job scheduling algorithm to balance workloads efficiently across multiple processors.
-
Per-Processor Deques: Each worker thread maintains a double-ended queue (deque) of ready-to-execute tasks.
-
Work-First Principle: When a Cilk program encounters a spawned task, the worker treats the child like a normal function call (executing it immediately) and pushes the continuation (the parent task) onto the bottom of its own deque. Workers push and pop local tasks from the bottom, operating in a LIFO (Last-In-First-Out), stack-like manner.
-
Randomized Stealing: When a processor runs out of local work, it becomes a "thief" and randomly picks another processor ("victim").
-
Stealing from the Top: The thief steals work from the top of the victim's deque (FIFO). This ensures the largest possible chunks of computation are stolen, reducing the total number of steals and respecting sequential caching advantages.