I would image stealing work from queues would only happen once for each continuation token to minimize inter-thread communications. How are dependencies kept track of for tasks that are stolen? I ask this question because there is a sync point at the end of else clause so there are dependencies among tasks between recursive caller and callee. Are they kept track of using dependency graph that are shared among threads? Would this approach be efficient with many threads?

I dont think there are dependencies among tasks. The reason we are able to parallelize this quick sort is that each 'loop' is independent of the other.

The cilk abstraction fits tree branching very well: siblings are independent amongst themselves but dependent on their parent.

@woo. I'm not sure I agree; There are dependencies among the different levels of tasks. The "Second level"-calls to part() are depended by the first call to part. In other words, the first call to part can't finish until the second levels finish.

The reason this isn't an issue is that cilk guarantees that if there is no cilk_sync at the end of a function that calls cilk_spawn, there's an implicit cilk_spawn at the end of the function. In other words, @gohan2021, there is a sync point at the end of the else clause (it's inserted at the end of a function)

From the documentation (here: https://cilk.mit.edu/docs/OpenCilkLanguageExtensionSpecification.htm#keywd.sync )

• There is an implicit sync at the end of every task block. If a spawning statement appears within a try block, a sync is implicitly executed on exit from that try block, as if the body of the try were a task block