Liste der Diplomarbeiten

Diplomarbeiten

Im Rahmen einer Diplomarbeit wurde LLFS entwickelt, ein Dateisystem für Linux. Dieses Dateisystem soll nun weiterentwickelt werden; einige Ideen dazu.

Es ist mit realer Hardware schwierig und langwierig, zu Testen, ob und wie gut ein Dateisystem einen Absturz übersteht, insbesondere ob die Daten dabei konsistent sind. Im Rahmen dieser Arbeit soll ein Testframework auf Basis einer virtuellen Maschine entwickelt werden, das auf verschiedene Dateisysteme angewendet werden kann. Einige Ideen dazu: Die virtuelle Maschine stellt eine virtuelle Platte zur Verfügung, die für jeden Sektor mitführt, ob er sicher geschrieben wurde, oder nur vielleicht (oder eventuell, in welchem logischen Zeitbereich der Sektor geschrieben wurde). Nach einem simulierten Stromausfall darf das Filesystem nicht von Sektoren lesen, die vielleicht geschrieben wurden. Man müßte sich allerdings noch etwas für Dateisysteme überlegen, die mit Checksums arbeiten. Weiters müssen noch Testprogramme geschrieben und/oder gesammelt werden, bei denen die Dateisysteme eher zu Inkonsistenzen neigen.

Es gibt viele Techniken, um Interpreter schneller zu machen: schnellerer Dispatch z.B. durch threaded code, stack caching, statische und dynamische Superinstructions. Im Rahmen dieser Arbeit soll evaluiert werden, welche dieser Techniken auf den existierenden Python oder Ruby-Interpreter angewandt werden können, wieviel sie bringen können, und eventuell soll eine dieser Techniken angewendet werden.

Interpreter werden oft mit einem switch in einer Schleife implementiert, und das führt auf Prozessoren wie dem Pentium 4 und dem Athlon 64 zu schlechter Sprungvorhersage, die den Grossteil der Zeit in Anspruch nehmen kann. Das kann optimiert werden, indem das Ende der Schleife und der Anfang der naechsten Iteration an die einzelnen Zweige angehängt wird. Im Rahmen dieser Arbeit soll so eine Optimierung im gcc implementiert und die Auswirkungen auf Interpreter und andere Programme untersucht werden.

Die Version 2.95 von gcc hat gewisse Vorteile gegenüber jüngeren Versionen, aber leider noch keine Codeerzeugung für den AMD64. Im Rahmen dieser Arbeit soll ein port für den AMD64 erstellt werden.

tcc ist ein schneller C-compiler, der aber realtiv schlechten Code erzeugt. Im Rahmen dieser Diplomarbeit soll ein globaler Registerallokator (Graph Colouring oder Linear Scan) in tcc eingebaut werden.

Codegenerator-Libraries wie Vcode und GNU Lightning leiden darunter, dass sie nur wenige Zielmaschinen unterstützen, und dass die Unterstuetzung zusätzlicher Zielmaschinen viel Arbeit kostet. Im Rahmen dieser Diplomarbeit soll die Unterstützung für zusätzliche Zielmaschinen automatisch erzeugt werden, indem ein bestimmtes C-Programm mit einem C-Compiler fuer die Zielmaschine compiliert wird, und dann aus dem erzeugten Code Maschinencodefragmente extrahiert werden, die dann in der Codegenerator-Library verwendet werden. Alternativ zum Einbauen in eine Codegenerator-Library kann auch ein Compiler wie z.B. tcc so mit neuen Zielmaschinen erweitert werden.

Labels-as-values ist ein Feature von GNU C, das besonders bei der effizienten Implementierung von Interpretern mittels threaded code oder dynamischen Superbefehlen wichtig ist. LLVM unterstuetzt dieses Feature zwar, aber in einer extrem ineffizienten Form. Im Rahmen dieser Arbeit soll eine effiziente Implementierung dieses Features in LLVM eingebaut werden.

Mit der zunehmenden Verbreitung von Multi-Core CPUs wird die Parallelisierung allgemeiner Anwendungen immer interessanter; eine sinnvolle Möglichkeit dazu scheinen Channels (Ein-Richtungs-Kommunikationskanäle zwischen zwei Threads, ähnlich der üblichen Verwendung von Pipes) zu sein: sie erlauben die Parallelisierung bei gleichzeitiger Modularisierung. Im Rahmen dieser Arbeit soll eine Anwendung auf diese Weise parallelisiert werden; mögliche Anwendungen wären Compiler wie lcc, tcc, oder gcc; Sie können aber nach Absprache auch eine beliebige andere Anwendung parallelisieren.

Beim Debugging hat man oft das Problem, dass das Programm in einem unerwünschten Zustand gelandet ist, und man sich fragt, wie es dahin gekommen ist. Dazu wäre es günstig, wenn man das Programm rückwärts ausführen könnte, und insbesondere den letzten Schreibzugriff auf eine Speicherstelle auffinden könnte. Im Rahmen dieser Diplomarbeit sollen Techniken zum Emulieren der Rückwärtsausführung in einen Debugger eingebaut werden: Wiederlaufenlassen mit Wiederabspielen der Eingaben, Laufenlassen mit abgezähltem Vorkommen bestimmter Ereignisse, Snapshots vom Programmzustand (um nicht zu lange wieder vorwärts laufen zu müssen).

Festplattenzugriffe sind vergleichsweise langsam. Die Wartezeit auf die Festplatte kann verringert oder eliminiert werden, wenn die Zugriffe vorauseilend und in einer optimierten Reihenfolge (moeglichst sequentiell) durchgeführt werden. In dieser Diplomarbeit soll eine geschichtsbasierte Vorhersage von Festplattenzugriffen im Linux-Kernel implementiert werden: Wenn Zugriff auf einen Block (oder eine kurze Sequenz) meistens von Zugriffen auf eine Menge von anderen Blocks gefolgt wird, sollten diese Zugriffe in Gang gesetzt werden, sobald auf den ersten Block bzw. die Anfangssequenz zugegriffen wurde. Eine mögliche weitere Optimierung ist das Umordnen der Blöcke, um die Zugriffe zu beschleunigen.

Stackmaschinen haben einen Stack statt des Registersatzes konventioneller Prozessoren. Analog zur Registerbelegung bei Registermaschinen ergibt sich das Problem, Variablen auf den Stack abzubilden, um Hauptspeicherzugriffe zu minimieren. Im Rahmen dieser Diplomarbeit sind Methoden für die globale Stackallokation für die JavaVM zu entwickeln.

Diese beiden Compilerphasen machen einander das Leben schwer: Diejenige, die zuerst kommt, behindert die andere. In der Literatur wurden mehrere Methoden vorgeschlagen, diese Phasen aufeinander abzustimmen. Die Methoden sind im Rahmen des GNU C Compilers zu implementieren und miteinander zu vergleichen.

Baumgrammatiken beschreiben die Befehlsauswahl in Compilern. Allerdings wird in solchen Baumgrammatiken jeder Maschinenbefehl oft auf mehrere Arten beschrieben, um besseren Code zu erzeugen. Die zusätzlichen Regeln entsprechen dabei gewissen Mustern, die bei allen Maschinenbeschreibungen vorkommen, und vor allem auf Eigenschaften des Zwischencodes zurückzuführen sind (z.B. die Kommutativität eines Operators). In dieser Arbeit soll ein System entwickelt werden, das aus einer einfachen Maschinenbeschreibung und einer Beschreibung von Optimierungen des Zwischencodes eine Baumgrammatik für eine gute Befehlsauswahl erzeugt.

Bei der Codeerzeugung zur Laufzeit kommt es besonders auf kurze Übersetzungszeiten an. In dieser Arbeit soll am Beispiel eines Forth-Compilers untersucht werden, wie schnell stack-basierter Code in effizienten Maschinencode für eine Registerarchitektur (Intel oder RISC) übersetzt werden kann.

Der Hauptvorteil von Attributierten Grammatiken ist, dass die Attribute automatisch in der richtigen Reihenfolge ausgewertet werden. Ein solcher Attributevaluator ist nicht nur für die bei Grammatiken vorkommenden Syntaxbäume interessant, sondern auch für allgemeine Graphen. In dieser Diplomarbeit sollen Sie so einen Attributevaluator implementieren.

lex und flex haben zwei Nachteile: 1) Sie erzeugen langsame Scanner. 2) Der Scanner liefert nur den erkannten String, und welche Regel er matcht; er liefert keine Information über die innere Struktur des Strings (z.B. bei einer Gleitkommazahl die Ziffern der Mantisse vor und nach dem Komma, und den Exponenten), sodass in vielen Fällen der String noch einmal von einer handgeschriebenen Scanner-ähnlichen Routine bearbeitet werden muß. In dieser Diplomarbeit sollen Sie einen Scanner-Generator implementieren, der diese Nachteile nicht hat.

Programme, die auf große Mengen von Speicher in einer nicht-lokalen Weise zugreifen, werden oft stark von TLB-misses gebremst (der Translation Lookaside Buffer (TLB) ist ein sehr kleiner Cache in der MMU). Moderne Prozessoren können Speicherseiten verschiedener Größe verwalten. Dieses Feature kann dazu benutzt werden, um einen größeren Teil des Speichers im TLB abzubilden und damit die Anzahl der TLB-Misses zu reduzieren. In diesem Praktikum bzw. dieser Diplomarbeit soll das Betriebssystem (Linux) folgendermaßen verändert werden: es soll mit einer Seitengröße anfangen, die die Abbildung des gesamten Speichers im TLB erlaubt, und Seiten aufteilen, wenn der Speicher ausgeht. Im Rahmen der Diplomarbeit sollen Seiten auch wieder zusammengelegt (und zu einer Seite verbunden) werden, sobald es geht. Eine ähnliche Idee wird in einem LWN-Artikel diskutiert.

Die Berechnungsregeln von Spreadsheets können als Sammlung von Constraints aufgefasst werden, die nur in eine Richtung ausgewertet werden. Oft wollen die Benutzer auch die andere Richtung verwenden (z.B.: vorgegebene Gesamtsumme, wobei einige Posten noch variiert werden können), was zu einer zeitraubenden Versuch-und-Irrtum-Arbeitsweise oder zur Eingabe redundanter (und möglicherweise falscher) Berechnungsregeln führt. Im Rahmen dieser Diplomarbeit soll ein Spreadsheet erstellt werden, das die Berechnungsregeln in alle Richtungen verwendet bzw. allgemein ein Constraint-basiertes Arbeiten ermöglicht.

Weitere mögliche Themenbereiche:

• Codegenerierung
• Forth
• Constraint Logic Programming
• Linux