I was a PhD student at UNC from Fall 2006 until Fall 2011. I have since moved on to MPI-SWS.
My dissertation work was recognized by the Graduate School with the 2012 UNC Dean's Distinguished Dissertation Award in the area of Mathematics, Physical Sciences and Engineering (details) and nationally by the Council of Graduate Schools with the 2012 CGS/ProQuest Distinguished Dissertation Award in the area of Mathematics, Physical Sciences and Engineering (details, UNC perspective). At DATE 2013, my dissertation was honored with the EDAA Outstanding Dissertations Award 2012 in the category “New directions in embedded system design and embedded software” (press release).
At UNC, I worked with my advisor Jim Anderson on practical multiprocessor real-time scheduling and real-time synchronization issues. In particular, I built large parts of the LITMUSRT system and designed several new multiprocessor real-time locking protocols.
My time at UNC was funded in part by the Fulbright Program and by a UNC Dissertation Completion Research Fellowship. (Thanks!)
While at UNC, I wrote a lot of code, both for fun and for work. Some of it is made available here.
Binomial heaps are a nice solution if you need a fast means of merging priority queues with logarithmic complexity (that is predictable in the worst case, that is, not relying on amortized analysis, see Wikipedia). We use binomial heaps in the LITMUSRT kernel to implement release and ready queues.
Here are three implementations of binomial heaps, two written in C and one written in Python. They come with examples and some documentation. In contrast to some other implementations available online, these versions support decreasing the keys of already-queued items (= increasing their priority) and deleting queued items.
bh.py — Binomial Heaps in Python
This implementation mostly implements the container interface. You can use any comparable object as a key. The cool part of this implementation is that you can delete items (through references) without having to know in which heap an item currently resides,
i.e., merging is supported transparently. Tested with Python 2.5.
The module is fully documented and contains an example of how to use it. Here's a short example:
>>> import bh >>> h1 = bh.heap([(40, "cool."), (10, "Binomial")]) >>> h2 = bh.heap([(20, "Heaps")]) >>> ref1 = h2.insert(123, "trash") >>> ref2 = h2.insert(400, "are") >>> h1 += h2 >>> ref2.decrease(30) >>> h2[35] = "quite" >>> ref1.delete() >>> for x in h1: ... print x, ... Binomial Heaps are quite cool.
heap.h — generic binomial heaps in C
This heap implementation (realized as C99 inline functions in a header file) is somewhat generic because it does not assume anything about the keys in use — the user provides a priority function to compare items. This allows for items with priorities that cannot (efficiently or conveniently) be reduced to a single integer value (examples include PFAIR priorities).
There are two cool twists to this version. First, repeated calls to peek() are cached, so that a take() operation (=dequeue) after a peek() operation completes in O(1). Second, the implementation does not make any assumptions about memory management (the availability of malloc() and friends is not assumed). This makes it possible to use it in OS kernels and systems with “unusual” memory management (e.g., embedded systems).
A test program illustrates how to use the library.
iheap.h — binomial heaps with integer keys in C
This heap implementation is very similar to the previous one, except for the fact that it requires all priorities to be integers. Requiring all keys to be integers is a performance improvement since the priority comparison can be hard coded, which eliminates the need for (and overhead of) a user-provided callback function.
As with the generic heap library, the integer heap library is agnostic towards memory management and caches peek() results.
A test program illustrates its use.
The binomial heaps repository (released under the BSD license) resides on Github now.
An implementation of
bin packing heuristics in Haskell
. The module implements the
first fit decreasing,
modified first fit decreasing,
last fit decreasing,
best fit decreasing,
worst fit decreasing, and
almost last fit decreasing heuristics. The module further offers all of the above heuristics with
increasing and
unmodified item orders. As of August 2009, the module is a properly cabalized package and available on HackageDB. I no longer maintain this code because I have mostly lost interest in Haskell.
download module Data.BinPack on Hackage (released under a BSD license)
The show_asm script is a little debugging helper that displays the assembly code of all symbols matching a given pattern in a given set of files. It is a quick&dirty wrapper around the nm(1) and objdump(1) tools. I use the script when debugging Linux kernel panics.
Its main advantage is that it automates finding out the addresses of a given set of symbols. Also, on slow systems, it is considerably faster than just disassembling the whole Linux kernel.
show_asm is written in Python and released under the BSD license.
download script
The Simple Grep Shell (gsh) is a thin layer around GNU grep. Use it to save time when you search through a given set of files a lot. It comes with its own query history. Have a look at the screen shot to get a better idea.
I use grep a lot. It is a great tool for navigating large software packages such as the Linux kernel. However, using grep directly from the shell can become tedious if you repeatedly execute many queries on the same set of files. Also, relying on the shell's history for recalling common or similar searches is somewhat cumbersome.
The Simple Grep Shell solves both problems by offering a simple, specialized shell for invoking grep. Once started for a set of files, the user can repeatedly enter search queries, and even recall prior searches (thanks to libreadline). You can pass any command line options that GNU grep understands to gsh — they will be transparently passed to grep.
gsh is written in Python and released under the BSD license.
screen shot-
download script
