topic Cilk worker size deque in Software Archive

Cilk worker size deque

Haris_R_1 — Wed, 20 Mar 2013 00:56:16 GMT

I understand that each worker in Cilk has its own deque from which it pops frames to work on and to which it pushes frames. Is there any way I could somehow display/print/get/obtain the number of frames in a worker’s deque at any point i.e. the size of a worker’s deque? I have dug into Cilk runtime code (scheduler.c, global_state.cpp, stacks.c, local_state.h … just to name few) and could not recognize anything that would give me such information. Push and pop functions only work on next_frame that is just a pointer to a struct of full_frame type. Thank you.

The number of frames in the

Jim_S_Intel — Wed, 20 Mar 2013 02:39:00 GMT

The number of frames in the deque of a worker w should roughly be w->tail - w->head. That value might be off slightly, depending on whether you want to count a worker's currently executing __cilkrts_stack_frame as being on the deque or not, and what exactly tail points to (i.e., does it point to an empty slot or the currently executing frame).

I don't remember off the top of my head which way the tail is currently maintained, but I would look at the comments in scheduler.c, in the section labeled "THE protocol" for more information. Section 10.6 of the ABI also describes what happens on a spawn, where the tail pointer is incremented in __cilkrts_detach.

http://www.cilkplus.org/sites/default/files/open_specifications/CilkPlusABI_1.1.pdf

The push and pop of full frames you are seeing in the runtime code have nothing to do with the worker's deques.
Cheers,

Jim

A word of caution.

Barry_T_Intel — Wed, 20 Mar 2013 13:24:27 GMT

A word of caution.

Additions to the deque happen when a cilk_spawn is executed. The __cilkrts_stack_frame of the function doing the spawn is pushed onto the tail of the deque. See the __cilkrts_detach logic in the ABI document Jim referenced for the details.

Frames are removed from the deque from *both* ends:

Code executing on the worker will remove entries from the tail when a spawned function who's parent has not been stolen returns. See __cilkrts_undo_detach in cilk-abi.c for the code.
Other workers may steal frames from the head of the deque at any time, assuming that there are frames to steal. That's the code involving the THE protocol that Jim mentioned.

So the number you get by calculating w->tail - w->head is only correct at that instance, since w->head may change at any time as a result of a successful steal.

- Barry

Hello,

Haris_R_1 — Wed, 20 Mar 2013 18:27:13 GMT

Hello, first and foremost, thank you for the prompt answer I could not find the function you mentioned in 10.6 “void __cilkrts_detach(struct __cilkrts_stack_frame *sf);”. These are 2 functions with “detach” in header name that could I find: cilk-abi.c /* Return true if undo-detach failed. */ static int __cilkrts_undo_detach(__cilkrts_stack_frame *sf) scheduler.c /* detach the top of the deque frame from the VICTIM and install a new CHILD frame in its place */ static void detach(__cilkrts_worker *w, __cilkrts_worker *victim, __cilkrts_stack *sd) The idea of taking “w->tail - w->head” sounded great and I tried it in a number of places in scheduler.c and the only number I get back is either 8 or 0. I used the method from “static int can_steal_from(__cilkrts_worker *victim)” (unsigned long)(victim->tail) - (unsigned long)victim->head In addition to the above, I tried casting to other types without any success.

> I could not find the

Barry_T_Intel — Wed, 20 Mar 2013 19:05:12 GMT

> I could not find the function you mentioned in 10.6
> “void __cilkrts_detach(struct __cilkrts_stack_frame *sf);”.

There is no implementation of __cilkrts_detach in the runtime. It's always inlined by the compiler when it builds the spawn helper. The only implementation is in section 10.6 of the ABI document.

To test this, I'd run with a single worker so you're sure there are no steals going on to confuse you.

- Barry

Hello, thank you for the

Haris_R_1 — Thu, 21 Mar 2013 17:33:35 GMT

Hello, thank you for the previous responses. So “__cilkrts_undo_detach()” is the function that pops from the tail of a worker’s deque while “__cilkrts_detach” is the one that pushes onto the deque. Could you briefly explain the purpose of the push and pop of full frame structures in scheduler.c? I fail to make connection here. When calling “static void detach()” from scheduler.c, it points victim’s full frame as a worker’s next frame and why not push __cilkrts_stack_frame onto the worker’s deque

The short answer is that

Jim_S_Intel — Thu, 21 Mar 2013 18:24:02 GMT

The short answer is that there is not an obvious connection between full_frame and __cilkrts_stack_frame objects. If all you care about is figuring out what is currenly on the deque, you don't need to worry about those methods.

The "push" and "pop" functions you are seeing in scheduler.c are related to the one-element "queue" of full frames that a worker maintains. The runtime uses this push and pop to guarantee that the worker that enters the topmost Cilk region in a program is the same one that leaves the region.

Stack frames (__cilkrts_stack_frame) and full frames (full_frame) are described in the following paper:
http://dl.acm.org/citation.cfm?id=1584017

Most of this paper is about reducers, but there is a description of the runtime at the beginning of Section 4 of stack frames and full frames. The paper is talking about the implementation of Cilk++, but since Cilk Plus is derived from Cilk++, most of the ideas still apply.

Roughly speaking, a full frame object only gets created on every steal, while a __cilkrts_stack_frame object is created for every spawning function and every time a function is spawned. In principle, one could have created a runtime that uses full frames for everything, but that is more expensive than necessary.

Cheers,

Jim

Hello,

Haris_R_1 — Tue, 26 Mar 2013 10:55:35 GMT

Hello, I understand that there is no implementation of “__cilkrts_detach” in the runtime. It is inlined by the compiler when it builds the spawn helper and the only implementation is in section 10.6 of the ABI document. Also, “__cilkrts_undo_detach()” is the function that pops from the tail of a worker’s deque while “__cilkrts_detach” is the one that pushes onto the deque. Is there any place in runtime code that would allow me to get notified (in any way possible) when a worker pushes an item onto its deque? Basically, I would like to know when a worker pushes something onto its deque. Thank you again.

For better or for worse, the

Barry_T_Intel — Tue, 26 Mar 2013 13:48:49 GMT

For better or for worse, the answer is no. Since __cilkrts_detach() is inlined, there is no call into the runtime in a spawn helper until the call to __cilkrts_leave_frame(), at least with code generated by the Intel compiler.

GCC may be generating calls to __cilkrts_enter_frame(), but those are subject to inlining too.

- Barry