[LITMUS^RT] Binary heaps for Litmus

[Glenn Elliott]

On Mar 29, 2012, at 3:33 PM, Jonathan Herman wrote:

> It looks like I will be using this heap for my next project over the next three weeks. If there are bugs, I hope to find them. Once we're confident it is bug free, we could merge this.
> 
> On Thu, Mar 29, 2012 at 11:25 AM, Glenn Elliott <gelliott at cs.unc.edu> wrote:
> On Mar 29, 2012, at 10:32 AM, Björn Brandenburg wrote:
> 
> > On Mar 22, 2012, at 12:29 AM, Glenn Elliott wrote:
> >
> >> I realized that binheap_delete() was more complicated than necessary.  Cleaned that up and then added binheap_decrease().  Sorry for the explosion of patches.
> >>
> >> -Glenn
> >>
> >>
> >> On Mar 21, 2012, at 5:02 PM, Glenn Elliott wrote:
> >>
> >>> Hi All,
> >>>
> >>> GSN-EDF and C-EDF use a binomial heap to prioritize CPUs.  This seems to be a little bit overkill since binomial heaps are best at heap merges.  This patch series does the following:
> >>>
> >>> 1) Implements a binary heap in the style of Linux's linked lists.
> >>> 2) Updates GSN-EDF to use the binary heap instead of the binomial heap to order CPUs.
> >>> 3) Updates C-EDF to use the binary heap instead of the binomial heap to order CPUs.
> >>>
> >>> I need to use this binary heap data structure for other work (priority queues that don't need binomial's fast merges), but I thought it could be applied to other domains.
> >>>
> >>> I've attached the patches.
> >>>
> >>> For those with access to CGIT on rtsrv.cs.unc.edu, here are links (easier to read):
> >>> Binary Heap: http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=5b73afc4eb1b0303cb92eb29a2ecc59c1db69537
> >>> GSN-EDF w/ Binary Heap: http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=bdce67bc2babc2e5b3b2440964e9cf819ac814dc
> >>> C-EDF w/ Binary Heap: http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=ee525fe7ba4edf4da2d293629ffdff2caa9ad02b
> >>>
> >>> All of this work is in wip-binary-heap on rtsrv.cs.unc.edu.
> >>>
> >>> I've tested these patches out both in QEMU and Bonham.  Comments and suggestions are welcome.
> >
> > Hi Glenn,
> >
> > thanks for the patches! We were using binomial heaps at that point because that was already implemented… Just wondering, did you observe a noticeable impact on overheads by using binary heaps instead?
> >
> > Thanks,
> > Björn
> 
> I haven't made any efforts to compare the binheap performance against binomial heaps.  I would expect binheap to have only a small edge.  I actually suspect that a sorted linked list may outperform both heap-based solutions.  A linked list modification requires an update of at most 4 pointers.  For the binheap, one bubble-up operation updates 6 pointers (parent, child, left, right, reference pointer, reference double pointer).  There may be several bubble-up operations heap operation.
> 
> -Glenn
> _______________________________________________
> litmus-dev mailing list
> litmus-dev at lists.litmus-rt.org
> https://lists.litmus-rt.org/listinfo/litmus-dev
> 
> 
> 
> -- 
> Jonathan Herman
> Department of Computer Science at UNC Chapel Hill
> _______________________________________________
> litmus-dev mailing list
> litmus-dev at lists.litmus-rt.org
> https://lists.litmus-rt.org/listinfo/litmus-dev


Should we consider making heap operations atomic?  We would add a spinlock to the handle data structure and then have operations such as binheap_add() and __binheap_add(), would be thread-safe and non-thread-safe, respectively.  Any APIs that do not require a handle reference would need to be modified.

-Glenn
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20120329/487f121f/attachment.html>