[LITMUS^RT] prop/cpu-sbinheap (based on 2014.2)

[Glenn Elliott]

Hi Everyone,

A while back there was some discussion of replacing GSN-EDF's and C-EDF’s use of bheap (the binomial heap data structure) for ordering CPUs.  These schedulers use bheap to organize CPUs into a min-heap, ordered by priority of the currently scheduled task.  This lets the scheduler quickly determine which CPU to preempt (i.e., the lowest-priority CPU).  bheap is a powerful data structure, but it is heavier-weight than is needed to just order CPUs—we don’t need bheap's quick merging.

Some time ago, I proposed replacing bheap with the binheap data structure (include/litmus/binheap.h).  However, binheap was thought to be also too heavyweight since it supports arbitrarily large heaps.  We don’t need this flexibility to order CPUs since the maximum size of the heap is known at compile-time (i.e., NR_CPUS).

To make some of my GPUSync locking protocols more efficient, I developed an “sbinheap” (static binary heap) data structure.  With exception of initialization routines, sbinheap uses the same API as the binheap data structure.  sbinheap builds the binary heap on a supplied contiguous array of heap nodes (either statically allocated or kmalloc’ed at runtime) using basic binary-tree-in-an-array indexing.  I’ve used sbinheap to: track the top M highest-priority released jobs, track the top M blocked tasks in a locking protocol, etc.  I’ve also used it to order CPUs the GSN-EDF and C-EDF schedulers.

I thought sbinheap might be useful for others, so I’ve proposed a set of changes in the “prop/cpu-sbinheap” patch set.  This branch includes patches to add the sbinheap data structure and update GSN-EDF and C-EDF to use sbinheap instead of bheap to order CPUs.

It might be hard measure performance benefits of sbinheap vs bheap when heaps are small.  Would someone at MPI be willing to quickly measure GSN-EDF scheduling overheads on their 64-core system under Litmus 2014.2 with and without my patch?  Locking protocol overheads may also be reduced.  I will do the same on one of our UNC systems.

Thanks,
Glenn