CPU 3. Custom Schedulers

As of v1.6.0, DotMP allows you to implement custom schedulers via the IScheduler interface. While implementing a custom scheduler can be very difficult, DotMP tries to make it as easy as possible.

DotMP exposes the DotMP.IScheduler interface for implementing custom schedulers. There are only two methods that must be overloaded: LoopInit, called by the master thread to initialize the data structure, and LoopNext, called to fetch the next chunk to execute. In this section, we're going to look at how the dynamic scheduler is implemented internally.

Implementing the Dynamic Scheduler

Here's how the dynamic scheduler is implemented in DotMP:

sealed class DynamicScheduler : IScheduler
{
    private int chunk_size;
    private int start;
    private int end;

    public void LoopInit(int start, int end, uint num_threads, uint chunk_size)
    {
        this.chunk_size = (int)chunk_size;
        this.start = start;
        this.end = end;
    }

    public void LoopNext(int thread_id, out int start, out int end)
    {
        start = Interlocked.Add(ref this.start, chunk_size) - chunk_size;
        end = Math.Min(start + chunk_size, this.end);
    }
}

Here you can see the necessary type signatures for LoopInit and LoopNext.

• LoopInit takes integers representing the start (inclusive) and end (exclusive) of the loop, and unsigned integers representing the number of threads in the team and the loop's chunk size.
• LoopNext takes the calling thread ID, and has out parameters for the start of the current chunk (inclusive) and the end of the current chunk (exclusive).

LoopInit is the first method to be called, and is only called by the master thread, since a single instance of DynamicScheduler is shared among all threads. Then, LoopNext is called repeatedly to get the next chunk a thread should execute. You'll notice that there are no flags to specify to the runtime that a loop has concluded. The DotMP runtime deduces that a thread is out of work if start >= end. Therefore, as long as start is less than end, threads will continue to call LoopNext.

The actual implementation is pretty simple. Dynamic scheduling doesn't care about the number of threads in a team (unlike static or work-stealing scheduling) so that parameter in LoopInit is unused. However, the rest of the parameters are assigned to member variables.

To get a chunk, the chunk size is atomically added to this.start to pop a chunk from the queue. Since Interlocked.Add returns the new value of this.start, we then subtract the chunk size to get the initial value of this.start. It's done this way so that we don't have to use any locks when accessing the queue, making scheduling much more efficient. Then, we want to check that we're not executing beyond the end of the loop, so we set the out end parameter to the minimum of start + chunk_size and this.end. That way we ensure that out end is either a full chunk or the remainder of the iterations in the queue.

And that's all we have to do! If the queue is out of work, then the returned value of start is greater than or equal to the returned value of end, the DotMP runtime detects this, and threads are retired.

Using Custom Schedulers

To actually use a custom scheduler with DotMP is trivial. Assuming you have something like:

sealed class CustomScheduler : IScheduler
{
    // implementation
}

You would use this with DotMP as follows:

var customScheduler = new CustomScheduler();

DotMP.Parallel.ParallelFor(0, M, schedule: customScheduler, chunk_size: cs, action: i =>
{
    // do work
});

Note that for custom schedulers, you must specify the chunk size. This is because DotMP cannot infer a chunk size for custom schedulers. It's further worth noting that a chunk size of 0 throws an InvalidArgumentException, so if a chunk size is unnecessary for your scheduler, you can just pass 1 or any other non-zero unsigned integer.