For clarification, by putting bar on the work queue are you referring to putting the continuation on the work queue? I'm a bit confused on how the scheduler would know that the bar() function is coming up since it has not run that part of the code yet.

@mark. Yes. I'm being a little loose in the visualization. Thread 0 has put the continuation for the spawn of foo() on the work queue. And I am denoting the continuation by the next thing the continuation does, which is to invoke the function bar().

How does the thread work queue differentiate between dependent and independent work? For instance, if bar() was dependent on foo(), how can thread 1 know not to steal it?

bar() is not dependent on foo() because foo() was spawned. The act of writing a program that spawns foo() is the programmer telling the system that foo() (or the continuation bar()' can be run asynchronously with other work in the system... up to the nextcilk_sync`.

Sorry, I was talking in general terms and not related to cilk. So if bar was not created via spawn, but is dependent on foo. Isn't the work queue used for work outside of those created by cilk (and hence could have dependent items)?

Well, this slide is specifically about Cilk's implementation. And in Cilk's implementation, there's no way to enqueue work that is dependent on other outstanding queued work in the system. The only dependency is when a running thread hits a sync, which creates a dependency on stolen work that other threads might be working on.

But if you're not talking about Cilk, you could imagine some other parallel runtime library that allows work to be enqueued with a dependency on other prior work. One example is what we have you implement in part 2 of your programming assignment 2.