Hello World, nice to meet you! Let me introduce myself.

I am a 3 ^rdyear Ph.D. student and part of the Real-Time Systems Group.

Originally, I'm from Berlin, Germany, where I attended Technische Universität Berlin. I came to UNC in Fall 2006 as a Fulbright Fellow and graduated with a M.S. in computer science in May 2008. Now I pursue a Ph.D. under the supervision of my adviser Professor Dr. James H. Anderson.

My research interests include Multiprocessor Real-Time Systems, Real-Time Operating Systems, and Operating Systems in general. As part of my research, I contribute to LITMUS ^RT, a real-time extension for the Linux kernel. To obtain trace data from real-world systems, I developed Feather-Trace, a very low-overhead tracing toolkit for Intel x86 compatible CPUs.

In December 2006, Hennadiy Leontyev and I participated in the international CiberMouse@RTSS2006 programming contest. The challenge was to program a (simulated) robot that would find a beacon in an unknown (and unstructured) maze and return to the start position in the face of real-time constraints, sensor noise, and competing agents. Our agent, “Ramses the Rat”, won the competition!

I'd be very happy to hear from you if you have comments or questions. Just send an email to bbb >>AT<< cs.unc.edu.

Spring 2008

• COMP 915 Technical Communication in Computer Science
• COMP 737 Real-Time Systems

Fall 2007

• COMP 633 High Performance Computing.
• COMP 790-95 Introduction to Computer Security.
• COMP 991-062 Reading and Research (with Dr. Anderson).

Spring 2007

• COMP 735 Distributed Algorithms.
• COMP 790-042 Advanced OS Implementation.
  In this class, we studied and hacked on the FreeBSD operating system. That was a fun class!
• COMP 790-078 Multiprocessor Real-Time Systems.
• COMP 991-062 Reading and Research (with Dr. Anderson).
  Feather-Trace was designed and implemented in this class.

Fall 2006

• COMP 750 Algorithm Analysis.
• COMP 790-062 Real-Time Operating Systems.
• COMP 665 Images, Graphics & Vision.

I take great interest in Free and Open Source Software (FOSS), the FOSS community, and support its ideals. Projects that I contribute to and code that I write (that I consider to be potentially of use or interest to others) is made available here.

Projects

• The LITMUS^RT project develops and maintains a patch on top of Linux that enhances the vanilla kernel with multiprocessor real-time scheduling and synchronization algorithms. It is our group's main development and evaluation platform for applied research multiprocessor real-time research. The code is licensed under the GPL 2.
  Project homepage
• Feather-Trace is a very low-overhead static tracing toolkit for the Intel x86 platform. The core part is distributed under a BSD license. The included Linux kernel patch is licensed under the GPL 2.
  Project homepage

Data Structures

I love programming; I like data structures. Thus – once in a while – I happen to implement some data structures. I try to keep the implementations as dependency-free, cleanly implemented, and documented as possible, so that they may serve as a drop-in solution. Maybe you can make use of them in your next project?

• Binomial Heaps

  Binomial Heaps are a wonderful solution if you need a fast and deterministic means of merging priority queues. In fact, we use Binomial Heaps in the LITMUS ^RTkernel to implement per-quantum release queues. Here are three implementations of Binomial Heaps, two in C and one in Python. They come complete 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.
    

    download module bh.py (released under the BSD license)

  • 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. Both the header and test program compile with gcc -Wall -ansi -std=c99.

    download heap library - download test program (released under the BSD license)

  • 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. Both the integer heap library and the test program follow the C99 standard.

    download integer heap library - download test program (released under the BSD license)

Misc. Scripts

These are some minor scripts that I happen to find useful. Maybe you do, too.

• show_asm

  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 oopses.

  Its main advantage is that it automates finding out the addresses of a given set of symbols manually. Also, it's considerably faster than just disassembling the whole Linux kernel on slow systems.

  show_asm is written in Python and released under the BSD license.
  download script

• Simple Grep Shell

  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

• GRUB Boot Kernel Selector

  Simple shell script to update the default choice in GRUB's menu.lst file. Use it to avoid human error when updating remote machines late at night.

  If you happen to be switching the default choice in the GRUB bootloader menu.lst file a lot (for example, if you frequently update the kernel on a remote machine), then you might appreciate this little script. It provides a shell-based dialog to select a new default entry based on the ones already present in the config. It is even so nice to leave a backup of your original config, just in case anything goes wrong. ;-)

  Released under the BSD license.
  screen shot - download script

Once I get around to cleaning up some of the stuff I have sitting around I will post some more.