[LITMUS^RT] Binary heaps for Litmus

[Björn Brandenburg]

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