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

[Felipe Cerqueira]

Hi Glenn,

I got some overhead graphs from our 64-core machine, running up to 640
tasks.

"noheap" is the master branch and sbinheap is the "prop/sbinheap" branch.
The difference between the two was not significant.
The results are almost equal. sbinheap was slightly worse, but just because
of measurement noise/small number of samples.

In general, the queue implementation doesn't seem to affect much the
overheads. Otherwise we would also see more differences in the results
of the RTSS'09 paper for the different heap implementations. Even though
SCHED and RELEASE operations make heavy use of the task queue,
I think the costs are mostly due to lock and cache contention on the global
state, because it is accessed by all the processors simultaneously.
And our machine has 32 + 32 CPUs connected by an interconnect, which makes
cache coherence more costly.

Perhaps for larger task counts, the new heap would make a difference. But
contention would also increase, so I think it would still dominate.
Still, replacing the heavy binomial heap with this binary heap makes sense.
And it's working fine :)

Thanks,
Felipe


2014-06-12 10:51 GMT+02:00 Björn Brandenburg <bbb at mpi-sws.org>:

>
> On 10 Jun 2014, at 20:16, Glenn Elliott <gelliott at cs.unc.edu> wrote:
>
> > 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.
>
> Thanks a lot for the patches. On first glance, they look great.
>
> > 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?
>
> The machine is currently in use for another project, but we'll try to give
> it a run in the coming days.
>
> > Locking protocol overheads may also be reduced.  I will do the same on
> one of our UNC systems.
>
> Sounds good. Let's compare notes once the tests have completed.
>
> Thanks,
> Björn
>
>
> _______________________________________________
> litmus-dev mailing list
> litmus-dev at lists.litmus-rt.org
> https://lists.litmus-rt.org/listinfo/litmus-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20140617/bfb532a4/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: RELEASE_noheap.pdf
Type: application/pdf
Size: 18469 bytes
Desc: not available
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20140617/bfb532a4/attachment.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: RELEASE_sbinheap.pdf
Type: application/pdf
Size: 18447 bytes
Desc: not available
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20140617/bfb532a4/attachment-0001.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: SCHED_noheap.pdf
Type: application/pdf
Size: 18466 bytes
Desc: not available
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20140617/bfb532a4/attachment-0002.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: SCHED_sbinheap.pdf
Type: application/pdf
Size: 18461 bytes
Desc: not available
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20140617/bfb532a4/attachment-0003.pdf>