Will I get a different reducer view after cilk_sync?

Will I get a different reducer view after cilk_sync?

Hello again,

I'm looking for clarification of something I found a bit ambiguous in the docs.

My code is using the usual recursive structure, and I have a reducer at each (parallel) level. Then,
* at the beginning of each spawned function 'A' I read some values from that worker's view of the reducer
* 'A' calls another function that recursively spawns some more calls to 'A'.
* then I update the values in the worker's view of the reducer.

Does the reducer have the same view in the read & write in the first & last op?

I had assumed it did, but the "Mapping Strands to Workers" section in the Cilk Plus docs says:
"After a
cilk_sync, execution may proceed on any worker that executed a
strand that entered the sync."

And cilkscreen is reporting a race between the first & last ops (though it reports other things that seem invalid), so maybe someone could steal the initial worker & be reading values from it while I'm writing them in the final worker? [Edit: I was actually saving the pointer to the initial view, and then updating that pointer, instead of getting the pointer from the current view; hence my concern about races. But avoiding this (i.e. using the view every time) actually isn't removing the race as far as cilkscreen is concerned]

I say I found this a bit ambiguous because e.g. a bit earlier on that page it says "there are one of two ways that this
program may execute" and doesn't consider this particular option. Not that this is incorrect, but it doesn't correct any prior assumptions I may have had :).

[Edit: also, if this is the case, is there any way to avoid this - i.e. to use the same reducer view after the sync?]

Thanks again for your help.

Daniel

P.S. On a related note, how would TBB behave in this scenario, where instead of cilk_spawn/sync one uses tbb::task_group::run() and ::wait()? Can the post-wait() continuation be stolen? Wrong forum I know, but should my mental model be different?

5 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

Daniel,

I don't quite understand what you mean by a "reducer at each (parallel) level". Nevertheless, let me try to answer your questions.

A reducer's view is predictable under certain specific circumstances: The first spawned child of a function will have the same view as the parent function (we sometimes say that the view follows the "leftmost" branch of the spawn tree). In addition, the parent will have the same view after a sync as it did before the first spawn. Thus, if I undederstand your situation, you should have the same view in the read and write steps ONLY IF you execute a _Cilk_sync between the second and third steps.

The documentation is correct that the worker executing the code after a sync is not predictable. This is unrelated to the reducer. It is very important to note that a reducer view is not tied to a specific worker or thread -- it can and does migrate among them. A reducer is not thread-local storage, although it can sometimes be used as a substitute for thread-local storage. So, even though the tread after the sync is not predictable, the reducer view is predictable.

I think you have tripped across a known bug in the current implementation of cilkscreen. If I am correct, you can work around the problem by setting the environment variable CILK_FORCE_REDUCE to 1 before running cilkscreen. (Do not run with this variable except in cilkscreen or you will severely slow down your program, and possibly crash it.) This should solve your false races problem.

-Pablo

Oh, and regarding your question about TBB. No, TBB never steals continuations. Your mental model should be different only if you rely on thread/worker identity. In general, relying on thread/worker identity is an indication that you are writing manually-threaded code using the wrong tool. Cilk Plus and TBB are for writing parallel code at a higher level of abstraction. When you begin to worry about the actual worker threads, you are hindering the tool's ability to find the best mechanism for parallelizing your program.

- Pablo

Pablo,

Thanks for your reply.

OK, thats great that the reducer view follows the parent thread of the sync. I had not appreciated that it was separate from the threads. I had in fact thought the same *thread* was used for the first spawned child, and so the view was maintained, but obviously I was confused. But this is in the docs..

I tried setting CILK_FORCE_REDUCE to 1, and now cilkscreen doesn't report *any* races, even innocuous expected races. So I tried removing almost all my mutex-locks and it still doesn't report any!

Of course, if I run it without cilkscreen it crashes immediately ("tried to pass an SEH exception through a spawn") because the threads are stepping on each other.

Any other suggestions?

thanks again,
Daniel

Pablo,

Forgot to say -
By "reducer at each (parallel) level" I just mean that at every level in my recursive computation, I have a reducer instance there, on the stack, if it is calling cilk_spawn. When there is only one child computation needed (it varies) I don't use cilk_spawn or a reducer.

Daniel

Leave a Comment

Please sign in to add a comment. Not a member? Join today