Modifying scheduling in gcc's libcilkrts

[Glenn_E_]

Hello.  I am interested in experimenting with modifications to the libcilkrts implementation in gcc for Linux.  Specifically, I would like to attach scheduling priorities to spawned work.  For the sake of simplification, we can assume that these are SCHED_FIFO priorities.  (In truth, priorities will be deadline-based in the LitmusRT Linux kernel.  LitmusRT is a real-time extension to Linux used in university research (www.litmus-rt.org).)

Suppose I wish to attach a SCHED_FIFO priority of 5 to some spawned work such that the worker thread that processes this work is scheduled with a priority of 5.  I could pass this as a regular argument in CilkPlus and let the worker thread call pthread_setschedprio() to set the proper priority (and restore its old priority upon completion).  However, there is a condition where the worker thread may never be able to wake up to call pthread_setschedprio():  Suppose our waiting worker thread has a default priority of 0 and we want to send priority-5 work to it. However, at the time this work is spawned, the CPUs are all occupied with threads running at priority 3.  The newly spawned work *should* preempt the priority-3 threads, but it can't since the worker thread's initial priority is 0---the thread is blocked from waking and cannot call pthread_setschedprio().

I can think of two possible workarounds:

1) After CilkPlus is initialized, set all worker thread priorities to 99 (maximum priority).  These threads won't consume any CPU time while they are waiting for work.  However, they will always be able to run when woken up to process new work.  They can then *downgrade* their priority as outlined above and restore their default 99 priority when work is completed.

2) Let the thread that spawns the work set the scheduling priority of the worker thread that will process the work.*

I am happy to use either technique, but I would prefer #2 if the notifications of new work to worker threads is broadcasted.  I don't want to trigger a flood of priority-99 threads to process one unit of work.  This would needlessly preempt other threads on the system.

Is there a design document that discusses the design of libcilkrts?  I have read the Cilk-5 paper from '98, but it appears to focus on work stealing.  If there is no such document, can someone walk me through the calls that are taken in libcilkrts when new work is spawned?  I've studied the libcilkrts code (including scheduler.c) and stepped through code in gdb, but I haven't yet identified the segment of code that says, "Here is some new work.  Wake up a worker to handle it."  I think scheduler.c::notify_children() might be what I want, but the context in which it is called doesn't quite match my expectations.

* Under either method, #1 or #2, I plan to set CILK_NWORKERS to be great enough to ensure that there is always an idle worker thread.  This will allow later-arriving higher-priority work to preempt lower-priority work already in-flight.  I know that this obviates the work stealing features of CilkPlus, but I want to put scheduling decisions exclusively in the domain of the operating system.

[Jim_S_Intel]

If I am understanding what you are trying to do correctly, you won't be able to get #2 to work exactly the way you are describing.  
Not every _Cilk_spawn statement will trigger a call into the runtime. 

In fact, in the common case, every _Cilk_spawn statement (roughly speaking) performs a "setjmp" to save some state, and pushes an element onto the deque.   Much of this code is generated by the compiler and inlined, which explains why you are probably not seeing what you expect in gdb.   The expected interactions between the compiled code and a runtime system are documented in the ABI document on our website:

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

In Cilk Plus, when a _Cilk_spawn of a function g() happens from a function f(), the worker executing the spawn immediately starts working on g(), and pushes the continuation of f() after the spawn of g() onto the deque.   I don't know if that information is useful for what you are trying to do or not?

More generally, my first impression is that I don't know if there will be any easy but generic solutions for what you are trying to do?   The work-stealing scheduler is integrated into the design of all the variants of Cilk, in large part because it enables many optimizations and has many good properties in theory and practice.    But that also means that you have to be careful when you try to change it, and changing the scheduling policy can be nontrivial.

Cheers,

Jim

[Glenn_E_]

Jim Sukha (Intel) wrote:

In Cilk Plus, when a _Cilk_spawn of a function g() happens from a function f(), the worker executing the spawn immediately starts working on g(), and pushes the continuation of f() after the spawn of g() onto the deque.

Ah, I think I understand what you are saying.  The spawning thread executes g() and passes the rest of f(), potentially, to another thread.  Am I understanding this correctly?  I might still be able to work with this.  Although, where in libcilkrts does the thread that was originally executing f() wake up a worker thread to execute the continuation of f()?

[Glenn_E_]

Glenn E. wrote:

Although, where in libcilkrts does the thread that was originally executing f() wake up a worker thread to execute the continuation of f()?

I figured it out.  No signal to wake is needed because worker threads spin on __cilkrts_yield(), waiting for work to arrive.  I believe that I was misreading the 'SCHEDULE_WAIT' case in __cilkrts_scheduler(): I thought workers were blocked here waiting for work.  Instead, workers continually spin on schedule_work() (which calls __cilkrts_yield()), looking for work to steal.

This breaks option #1 in my original post since spinners running with a SCHED_FIFO policy would effectively block the execution of any other regular programs.  This isn't what I was hoping to find, but I certianly understand why it works well for Cilk!

[Jim_S_Intel]

Yes,  the SCHEDULE_WAIT that you were seeing is part of a mechanism that is used for starting up / suspending worker threads when a program first enters / leaves the outermost parallel region in a program.    As you observed, worker threads in Cilk that do not have work to do usually go around in a steal loop, trying to steal, and calling a __cilkrts_yield()  if they fail.   Thus, a thread does not need to get woken up to resume a continuation.    The main loop for worker threads is in __cilkrts_scheduler in scheduler.c.

In terms of mechanism, it seems like you might be able to raise and lower thread priorities on worker threads at appropriate times, either in the runtime code directly, or by making the user insert calls into the runtime in their code at every spawn or sync, for example.  (I don't know what the overheads might be though.)    But I'm not quite sure I understand what the expected behavior of priorities is for programs that have nested cilk_spawns.     For example, if I write a function with recursive nested parallelism such as fib, is it possible to set priorities in this program, and what are they supposed to mean?

Just in case you haven't seen "fib" before:
http://www.cilkplus.org/sites/default/files/code_samples/cilk-fib.tgz

In any case, it seems like an intriguing but potentially difficult problem.  If you come up with some good solutions, do let us know!
Cheers,

Jim