Suche nach Praktika und Diplomarbeiten

Suchbegriffe:

Gewünschte Betreuer:

Praktika und Diplomarbeiten

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

Architecture Description Languages (ADL) are used to describe processors and computer architectures. The task for this practical work is to develop a GUI for our XML based ADL, so that the user can create and manipulate a description. Components like registers, memories and functional units, as well as the interconnect should be displayed and manipulated in a graphical environment.

In addition a consistency checker should be developed that checks for invalid or meaningless constructs.

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

Embedded-C is a C language extension [1,2] that provides portability and access to common performance-increasing features of processors used in the domain of DSP and embedded processing. Extensions for fixed-point arithmetic, named address spaces and named registers allow the programmer to access those features of the target processor in a high level language, thereby significantly improving the performance of applications

The task in this practical work is to implement the Embedded-C extensions in the gcc [3] frontend.

[1] http://www.embedded-c.org
[2] http://www.open-std.org/jtc1/sc22/wg14/
[3] http://gcc.gnu.org

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

Im Rahmen dieses Praktikums soll mittels unserer Architekturbeschreibungssprache ein einfacher Mikroprozessor wie ein ARM beschrieben werden. Simulator und Compiler werden automatisch generiert.

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

An unserem Institut ist CACAO, ein 64 Bit JavaVM just-in-time Compiler für Alpha Prozessoren entwickelt worden. Der Codegenerator für den ALPHA Prozessor soll um weitere für MIPS, SPARC, POWERPC und HP-Precision Architecture Prozessoren erweitert werden. Kenntnisse einer dieser Prozessoren ist von Vorteil.

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

An unserem Institut ist CACAO, ein 64 Bit JavaVM just-in-time Compiler für Alpha Prozessoren entwickelt worden. Der Codegenerator für den Alpha Prozessor soll optimiert werden.

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

An unserem Institut ist CACAO, ein 64 Bit JavaVM just-in-time Compiler für Alpha Prozessoren entwickelt worden. CACAO unterstützt zur Zeit keine Debugging-Möglichkeiten wie BackTracing und Ausgabe von Zeilennummern. Diese Möglichkeiten sollen zu CACAO hinzugefügt werden.

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

An unserem Institut ist CACAO, ein 64 Bit JavaVM just-in-time Compiler für Alpha Prozessoren entwickelt worden. CACAO soll um Profiling erweitert werden. Die Profileergebnisse sollen dabei als HTML-Datei ausgegeben werden.

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

An unserem Institut ist CACAO, ein 64 Bit JavaVM just-in-time Compiler für Alpha Prozessoren entwickelt worden. Teile des das Java Runtime System sind noch unvollständig (z.B. die Net-Bibliothek) und müssen noch dem CACAO System hinzugefügt werden. Kenntnisse von Java sind von Vorteil.

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

Im Rahmen dieser Diplomarbeit soll ein Generator für zyklengenaue Architektur Emulatoren entwickelt werden. Die Architekturen werden in einer ADL beschrieben. Der Emulator soll Übersetzung und Interpretation unterstützen.

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

Im Rahmen dieser Diplomarbeit soll mittels unserer Architekturbeschreibungssprache ein einfacher Mikroprozessor wie ein ARM beschrieben werden. Simulator und Compiler werden automatisch generiert.

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

The CDLab (Christian Doppler Labor) 'Compilation Techniques for Embedded Processors' currently develops a compiler for the CHILI architecture by OnDemand Microelectronics.

The CHILI is a four-way VLIW DSP (Digital Signal Processor) designed for efficient processing of video/audio streams. The architecture offers an extensive general purpose register file, with 64 32 bit registers. A distinguishing feature of the CHILI is it's capability to execute most instructions conditionally and it's memory subsystem. The CHILI is able to execute up to four load and store instructions concurrently.

The compiler is based on the LLVM compiler infrastructure developed at the University of Illinois. LLVM is a C++ based framework for static compilers, dynamic compilers (Just-In-Time, JIT), (whole) program optimizations and (whole) program analysis.

The CHILI architecture offers a set of registers specifically reserved for global variables. A simple interprocedural optimization should be implemented that analyses the usage of global variables and allocates them to registers.

- Prerequisites:
* Good knowledge of C++
* Basic compiler courses

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

The CDLab (Christian Doppler Labor) 'Compilation Techniques for Embedded Processors' currently develops a compiler for the CHILI architecture by OnDemand Microelectronics.

The CHILI is a four-way VLIW DSP (Digital Signal Processor) designed for efficient processing of video/audio streams. The architecture offers an extensive general purpose register file, with 64 32 bit registers. A distinguishing feature of the CHILI is it's capability to execute most instructions conditionally and it's memory subsystem. The CHILI is able to execute up to four load and store instructions concurrently.

The compiler is based on the LLVM compiler infrastructure developed at the University of Illinois. LLVM is a C++ based framework for static compilers, dynamic compilers (Just-In-Time, JIT), (whole) program optimizations and (whole) program analysis.

Branch and memory load instructions have a very large latency on the CHILI architecture. Branches take four cycles to take effect. In general it is hard to fill these four delay slots with usefull instructions - up to 19 instructions (4*4+3) may be executed in delay slots. Loads take at least 5 cycles to complete. Thus it is important to minimize the number of loads, stores and branches to get high quality code. Adaptive calling conventions may be used to reduce the number of memory accesses needed at function entry and exit. In addition the usage of the return address register (specifies where to resume after a function has completed its execution) may be optimized to minimize data dependencies and improve the filling of delay slots.

- Prerequisites:
* Good knowledge of C++
* Basic compiler courses

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

The CDLab (Christian Doppler Labor) 'Compilation Techniques for Embedded Processors' currently develops a compiler for the CHILI architecture by OnDemand Microelectronics.

The CHILI is a four-way VLIW DSP (Digital Signal Processor) designed for efficient processing of video/audio streams. The architecture offers an extensive general purpose register file, with 64 32 bit registers. A distinguishing feature of the CHILI is it's capability to execute most instructions conditionally and it's memory subsystem. The CHILI is able to execute up to four load and store instructions concurrently.

The compiler is based on the LLVM compiler infrastructure developed at the University of Illinois. LLVM is a C++ based framework for static compilers, dynamic compilers (Just-In-Time, JIT), (whole) program optimizations and (whole) program analysis.

The instruction selector of the LLVM infrastructure is based on a simple buttom-up DAG matcher. This work should implement a two-pass instruction selector based on dynamic programming, well known from systems like lburg[1]. Patterns for the tree grammer should be derived using the `tablegen` tool included in LLVM.

- Prerequisites:
* Good knowledge of C++
* Basic compiler courses
- [1] Christopher W. Fraser and David R. Hanson and Todd A. Proebsting, "Engineering a simple, efficient code-generator generator", 1992, p. 213-126, ACM Letters on Programming Languages and Systems

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

The CDLab (Christian Doppler Labor) 'Compilation Techniques for Embedded Processors' currently develops a compiler for the CHILI architecture by OnDemand Microelectronics.

The CHILI is a four-way VLIW DSP (Digital Signal Processor) designed for efficient processing of video/audio streams. The architecture offers an extensive general purpose register file, with 64 32 bit registers. A distinguishing feature of the CHILI is it's capability to execute most instructions conditionally and it's memory subsystem. The CHILI is able to execute up to four load and store instructions concurrently.

The compiler is based on the LLVM compiler infrastructure developed at the University of Illinois. LLVM is a C++ based framework for static compilers, dynamic compilers (Just-In-Time, JIT), (whole) program optimizations and (whole) program analysis.

The LLVM compiler infrastructure supports a C language extension, that allows to define vector types. These types can be used in regular C expressions (e.g., arithmetics, function calls, etc.). The Chili architecture, developed by OnDemand Microelectronics, supports vector operations natively. The existing LLVM-Chili backend should be extended to support all vector operations offered by the Chili using the extended C syntax.

- Prerequisites:
* Good knowledge of C++
* Basic compiler courses

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

The CDLab (Christian Doppler Labor) 'Compilation Techniques for Embedded Processors' currently develops a compiler for the CHILI architecture by OnDemand Microelectronics.

The CHILI is a four-way VLIW DSP (Digital Signal Processor) designed for efficient processing of video/audio streams. The architecture offers an extensive general purpose register file, with 64 32 bit registers. A distinguishing feature of the CHILI is it's capability to execute most instructions conditionally and it's memory subsystem. The CHILI is able to execute up to four load and store instructions concurrently.

The compiler is based on the LLVM compiler infrastructure developed at the University of Illinois. LLVM is a C++ based framework for static compilers, dynamic compilers (Just-In-Time, JIT), (whole) program optimizations and (whole) program analysis.

During this practical work debug support should be added to the existing LLVM backend for the Chili architecture. LLVM already offers a library for the DWARF debugging format, that has to be adopted for the Chili.

- Prerequisites:
* Good knowledge of C++
* Basic compiler courses

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

The CDLab (Christian Doppler Labor) 'Compilation Techniques for Embedded Processors' currently develops a compiler for the CHILI architecture by OnDemand Microelectronics.

The CHILI is a four-way VLIW DSP (Digital Signal Processor) designed for efficient processing of video/audio streams. The architecture offers an extensive general purpose register file, with 64 32 bit registers. A distinguishing feature of the CHILI is it's capability to execute most instructions conditionally and it's memory subsystem. The CHILI is able to execute up to four load and store instructions concurrently.

The compiler is based on the LLVM compiler infrastructure developed at the University of Illinois. LLVM is a C++ based framework for static compilers, dynamic compilers (Just-In-Time, JIT), (whole) program optimizations and (whole) program analysis.

For this practical work profiling support should be added to the existing LLVM-Chili compiler. LLVM already offers a library for basic block, function and edge profiling, which should be used during this work.

- Prerequisites:
* Good knowledge of C++
* Basic compiler courses

Andreas Krall (andi@complang.tuwien.ac.at, Tel. 58801/18511)

Context YesControl is a DCS-System, consisting of a SCADA (Supervisory Control and Data Acquisition) system and a PLC (programmable logic control) based on IEC 61131-3. Its concept of combining these two worlds with one engineering tool based on standard hardware for SCADA and PLC is unique, and the integration is much better than competitive products on the market. Task Description YesControl has an integrated compiler, which compiles Structured-Text- Source to Intel X86 assembler code, which then runs on the PLC. The Compiler first generates intermediate code, and then the intermediate code is compiled by the backend to the assembler code of the corresponding processor, with the help of The New Jersey Machine-Code Toolkit (see http://www.eecs.harvard.edu/~nr/toolkit/) The task of this diploma thesis is to port the PLC runtime system of YesControl (which is easily portable plain C) to an arm-processor-based hardware, and then to make an arm-backend for the compiler, including a Dissassembler for the ARM built with the help of the New Jersey machine- Code Toolkit Requirements
. Good knowledge in C
. Interest in building compilers
. knowledge of the arm-processor would be helpful, but is not necessary

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

Der Inhalt des RAMs ueberlebt meistens Betriebssystemabstuerze und (eventuell mit Fehlern auch kurze Stromausfälle). Wie kann man diese Eigenschaften für Dateisysteme nutzen? Beim Lesen: Blöcke, die im RAM liegen (und ueber eine Checksumme validiert werden können), können einfach wiederverwendet werden, man spart sich das Lesen von der Platte (schnelleres Booten). Beim Schreiben: Die beabsichtigten Schreiboperationen können in ein Log im RAM (abgesichert mit Fehlerkorrektur) geschrieben werden, von dort auf das log auf der Platte migrieren, und dann endgültig auf der Platte umgesetzt werden. Im Rahmen dieser Diplomarbeit sollen einige dieser Ideen in einem Filesystem (z.B. für Linux) umgesetzt werden.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

Das C-Interface von Gforth benötigt Deklarationen von C-Funktionen und C-Strukturen in einer Forth-freundlichen Syntax. SWIG ist ein Werkzeug, um Interfaces zwischen C und anderen Programmiersprachen zu erstellen. In dieser Arbeit sollen mit Hilfe von SWIG C-Header-Files in Forth-Deklarationen der C-Funktionen und -Strukturen übersetzt werden.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

Auf der AMD64-Architektur wird bei Speicherzugriffen das Alignment normalerweise nicht überprüft. Man kann so eine Überprüfung aber einschalten, sodass ggf. eine Exception erzeugt wird. Das kann hilfreich sein, um Programmierfehler zu finden. Leider ist es nicht ganz einfach, das zu tun, weil einige Library-Funktionen, insbesondere Stringfunktionen, absichtlich nicht ausgerichtete Zugriffe durchführen. In diesem Praktikum sollen Ersatzfunktionen geschrieben und mit einem Programm gelinkt werden, und das Programm dann mit eingeschaltetem Alignment-Checking ausgeführt werden. Als Programm schwebt mir in diesem Zusammenhang gforth vor, aber es kann auch ein beliebiges anderes Programm entsprechend angepasst werden.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

Der perfctr patch erlaubt es, die Performance-Counter von Intel-kompatiblem Prozessoren zu benutzen. In diesem Praktikum soll dieser Patch auf einen Alpha-Prozessor oder PPC-Prozessor erweitert werden.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

(je ein Praktikum pro Architektur). Der Assembler soll sehr einfach gehalten werden, die komplizierteren Teile (Parsing, Symbolverwaltung) werden vom zugrundeliegenden Forth-System übernommen.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

M. Anton Ertl (anton@mips.complang.tuwien.ac.at, Tel. 58801/18515)

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.

eva Kühn (eva@complang.tuwien.ac.at, Tel. 58801/18512)

Franz Puntigam (franz@complang.tuwien.ac.at, Tel. 58801/18514)

Programmiersprachen unterscheiden sich in vielen Details, die manchmal große Auswirkungen auf die Ausdrucksstärke haben. In einer Reihe von Praktika sollen jeweils zwei objektorientierte Programmiersprachen hinsichtlich ihrer Fähigkeit, für je eine Klasse von Problemstellungen einfache, effiziente und wiederverwendbare Lösungen zu ermöglichen, verglichen werden. Als Problemstellungen bieten sich unter anderem Sammlungen heterogener Daten (Listen, Stacks, etc.) und Operationen auf Paaren gleichartiger Objekte; es ist bekannt, dass diese Aufgaben in einigen Sprachen viel besser zu lösen sind als in anderen. Es werden z.B. Vergleiche zwischen allen Paaren von Java, Smalltalk, C++, Eiffel und Ada'95 vorgeschlagen, aber interessierte Praktikanten können auch Vergleiche zwischen weniger bekannten Sprachen durchführen. Diese Praktika richten sich auch an Gruppen beliebig vieler Personen, die solche Aufgaben im Team lösen wollen.

Voraussetzungen: grundlegende Programmierkenntnisse

Franz Puntigam (franz@complang.tuwien.ac.at, Tel. 58801/18514)

Programmiersprachen bieten dem Programmierer viele verschiedene Konzepte zur Lösung unterschiedlichster Aufgaben und sind dadurch oft sehr komplex. In der Lehre wie in der Praxis ist diese Komplexität unerwünscht. Andererseits sollen alle wichtigen Konzepte wie Subtyping, Generizität, Überladen, Dynamic Binding, Reflection, strenge Typisierung, getrennte Typ- und Vererbungshierarchien, Kapselung und Data Hiding, etc. in einer objektorientierten Sprache vorhanden sein. Es soll in einer Diplomarbeit untersucht werden, wie gut die Sprachen Java, Smalltalk, C++, Eiffel und Ada'95 diese Konzepte unterstützen und wie verständlich und leicht verwendbar diese sind. Dabei muss natürlich der Charakter einer Sprache (d.h. deren Ziele sowie Zusammenhänge zwischen deren Konzepten) berücksichtigt werden.

Voraussetzungen: Grundkenntnisse der objektorientierten Programmierung

Franz Puntigam (franz@complang.tuwien.ac.at, Tel. 58801/18514)

Obwohl Java als Programmiersprache für das Internet angepriesen wird, gibt es nur minimale Unterstützung für die nebenläufige Programmierung. Daher empfiehlt es sich, Java um aktive Objekte (= nebenläufige Prozesse) zu erweitern. In einer Diplomarbeit sollen aktive Objekte und deren Klassen zu Java dazugefügt werden, so dass jedes aktive (wie auch jedes passive) Objekt einen Typ hat. Auch auf Klassen aktiver Objekte soll eine Art von Vererbung realisiert werden.

Voraussetzungen: Java, Compilerbau

Franz Puntigam (franz@complang.tuwien.ac.at, Tel. 58801/18514)

Als Vorteil der objektorientierten Programmierung wird meist die Unterstützung der Wiederverwendung von Code und Spezifikationen genannt. In der Praxis treten dabei jedoch häufig Probleme auf. Es sollen die Ursachen für diese Probleme untersucht werden. Dabei sollen Zusammenhänge zwischen den Problemen und verschiedenen Unterparadigmen des objektorientierten Paradigmas bzw. den Konzepten der entsprechenden Programmiersprachen hergestellt werden.

Voraussetzungen: Erfahrungen mit objektorientierter Programmierung

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Gegenwärtig optimiert gcc (bzw. egcs) nur direkt rekursive tail-calls. Diese Optimierung soll möglichst allgemein für tail-calls erweitert werden.

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Neuere Prozessoren führen Statistiken über viele Vorgänge wie das genaue Verhalten des Cache. In diesem Praktikum sollen diese Daten über eine möglichst allgemein gehaltene Schnittstelle unter Linux für intel x86 und dec alpha zur Verfügung gestellt werden.

Voraussetzungen: Linux-Kernel

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Viele Prozessoren erlauben es, während der Laufzeit die Betriebsfrequenz des Prozessors herunterzusetzen. Dadurch laufen Programme natürlich langsamer. Der Stromverbrauch geht jedoch effektiv meist stärker als nur proportional zurück. Wenn also keine hohen Anforderungen an die Antwortzeit eines Prozesses bestehen, kann es energiesparender sein, diesen Prozess bei niedriger Taktfrequenz auszuführen, statt ihn bei höchster Frequenz auszuführen und entsprechend früher in die Idle-Loop zu gehen.

• BIOS-Schnittstellen
• Scheduler
• Traces

Literatur: Mark Weiser, Alan Demers, Brent Welch, Scott Shenker. "Scheduling for Reduced CPU Energy", Operating System Design and Implementation (OSDI) Conference, Monterey, CA. November, 1994.

Voraussetzungen: Linux-Kernel

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Programm slicing ist eine Programmanalysetechnik, um jene Programmteile herauszufinden, die für gewisse Eigenschaften verantwortlich sind. Im folgenden Programm ist etwa nur ein sehr kleiner Teil für die Nichttermination der Anfrage verantwortlich. Die in der Laborübung logikorientierte Programmiersprachen verwendeten Lesarten sollen nun mittels Slicing-Techniken implementiert werden. Eine Technik zur Generierung von Slices, die die Terminationseigenschaft eines Programms erklärt, wurde bereits entwickelt. Siehe dazu den Artikel Termination slicing in logic programs.

:- phrase(rnaloop, "AAAGCGTTT").
rnaloop -->
   {Bs = [_,_,_|_]},
   complseq(Bs), {false},
   list([_,_,_|_]),
   list(Bs).
%
list([]) --> {false},
   [].
list([E|Es]) --> {false},
   [E],
   list(Es).
%
complseq([]) --> {false},
   [].
complseq([B|Bs]) -->
   complseq(Bs), {false},
   [C],
   {base_compl(C,B)}.
%
base_compl(0'A,0'T) :- false.
base_compl(0'T,0'A) :- false.
base_compl(0'C,0'G) :- false.
base_compl(0'G,0'C) :- false.

Voraussetzungen: Prologübung

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Constraints erlauben die flexible Analyse von Programmanhängigkeiten. In dieser Diplomarbeit sollen constraints zur Implementierung einer Datenflußanalyse eingesetzt werden

Voraussetzungen: Prologübung

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Seiteneffekte, wie sie in herkömmlichen Programmiersprachen üblich sind, passen nicht direkt zu deklarativen Programmiersprachen. Wie Entwicklungen vor allem in puren funktionalen Programmiersprachen gezeigt haben, ist es aber dennoch möglich Seitenffekte mit einer deklarativen Programmiersprache zu verbinden. Es sollen die bisherigen Ansätze zusammengefaßt werden, und auf Logik-Programmiersprachen angewandt werden.

Voraussetzungen: Prologübung

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Die Wahl der richtigen Methode zum Labeling eines Constraintsystems entscheidet oft über seine praktische Einsetzbarkeit. Vergleich anhand konkreter Probleme.

Voraussetzungen: Prologübung

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Die meisten praktischen Implementierungen von Parsern in Prolog verwenden Seiteneffekte zum Lesen einer Datei. Durch neuere Implementierungstechniken ist es möglich geworden, daß eine Datei direkt auf eine Liste von Zeichen effizient abgebildet werden kann. Dadurch erübrigt sich die Verwendung von Seiteneffekten innerhalb eines Parsers. Es soll ein Parser für Prolog entwickelt werden, der eine Liste von Zeichen auf den entsprechenden Prologterm abbildet. Dieser Parser soll mit existierenden Parsern verglichen werden.

Voraussetzungen: Prologübung

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

In diesem Werk beschreibt Raymondus Lullus (1232-1316) eine Art Grammatik zur Darstellung von Argumentationsweisen (Ars compediosa inveniendi veritatem), die sich zur Umsetzung in Prolog geradezu anbietet.

Eine interessante Persönlichkeit ist Raimundus Lullus, der um 1300 mittels mehrerer konzentrischer Scheiben, die mit verschiedenen Wörtern beschriftet waren, durch Drehen der Scheiben immer neue »Wahrheiten« hervorbrachte (»ars inveniendi«). Die Fortsetzung findet solche »automatische Wissensverarbeitung und -erzeugung« in den Kalkülen von Leibniz, de Morgan und Boole und schließlich in den regelbasierten Expertensystemen, wie man sie im Bereich der sogenannten Künstlichen Intelligenz hat. (Aus: Uni Ulm intern, Juni 1995:

• Die Ars des Raimundus Lullus. Eine mediterrane Kommunikationslogik, Berlin 1989, text machines text
• Texte der österreichischen Nationalbibliothek.
• Kommt in vielen Romanen vor: Umberto Eco, Die Insel des vorigen Tages als aristotelisches Fernrohr. Jonathan Swift, Gullivers Reisen. Christoph Martin Wieland, Der neue Amadis, 10. Gesang.
• Artistic Websites

Voraussetzungen: Prologübung

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Zur Schonung der Batterie auf einem Laptop sollen die Plattenzugriffsstrategien von Linux adaptiert werden. üblicherweise wird durch den update-Dämon immer wieder auf die Platte zugegriffen. Dadurch ist es nicht möglich, die Platte zur Einsparung der Batterie abzuschalten. (Eine einfache, aber nicht optimale und zufriedenstellende Lösung ist es, den update-Dämon erst gar nicht zu starten und manuell zu sync-en.) Es soll eine für Laptops geeignetere Strategie implementiert werden, die die Zeit zu der die Platte abgeschaltet sein kann, maximiert.

Gegenwärtig gibt es eine relativ einfache, aber nicht optimale Lösung: mobile-update. Es fehlen vor allem Adaptierungen für Power-Managements etc.

Voraussetzungen: Linux-Kernel

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Zur Darstellung gerichteter Graphen soll die Lösungsannotation graphs_marks(Graphs,Marks) realisiert werden. Dabei ist Graphs eine Liste von Prädikatsindikatoren. Jedes Prädikat beschreibt einen gerichteten Graphen, dessen Knoten Atome (Konstanten) sind. Marks ist eine Liste der Knoten, die gesondert hervorgehoben werden sollen (In diesem Falle Joseph II). Die erste Relation wird durch einfache möglichst senkrechte Striche dargestellt, die zweite durch doppelte möglichst horizontale Striche. Genauere Beschreibung im WWW.

kind_von(joseph_I, leopold_I).
kind_von(karl_VI, leopold_I).
kind_von(maria_theresia, karl_VI).
kind_von(joseph_II, maria_theresia).
kind_von(joseph_II, franz_I).
kind_von(leopold_II, maria_theresia).
kind_von(leopold_II, franz_I).
kind_von(marie_antoinette, maria_theresia).
kind_von(franz_II, leopold_II).

gatte_gattin(franz_I, maria_theresia).

:- graphs_marks([kind_von/2,gatte_gattin/2], [P]) <<< P = joseph_II.

Voraussetzungen: Prologübung

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Zur besseren Darstellung einer Lösung (Antwortsubstitution) soll diese graphisch (z.B. mittels postscript) dargestellt werden. Die Treiber sollen als DCGs beschrieben werden, die einen Postscript-Text beschreiben. Ein Treiber ist also nichts anderes als eine Relation zwischen einem Term und einem Postscripttext. Hier ein kleines Beispiel. Die Zeile besagt, daß die Variable Cs als Postscripttext dargestellt werden soll. Die Variable Cs wird durch das Nichtterminal box1//0 beschrieben. Fragt man nach den Antworsubstitutionen, so wird der Postscripttext in einem eigenen Fenster dargestellt.

:- postscript(Cs) <<< phrase(box1, Cs).

:- europastadt(Stadt) <<< stadt(Stadt).

Literatur zu Postscript:

• PostScript-Minikurs, ziemlich gut
• Postscripttutorial (Dies ist eine lokale Kopie des Originals).
• Internet Postscript Resources
• Zürcher Postscriptcorner
• Cs4Ce
• Imation Postscript Pages

Voraussetzungen: Prologübung

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Prozesse teilen gewisse Hauptspeicherbereiche miteinander. Etwa die nicht modifizierbaren Teile unabhängiger Prozessinstanzen, Bibliotheken und die nicht modifizierten Teile zwischen Vater- und Kindprozeß. Daten, die vom Prozeß selbst initialisiert wurden, werden jedoch nicht mit identischen Daten eines anderen Prozesses zusammengelegt. Durch das Zusammenlegen solcher Daten wird der Hauptspeicherbedarf und damit auch das Swapping (paging) in Linux weiter reduziert. Es soll a) gemessen werden, welche Speichereinsparungen dadurch erzielt werden könnten und b) der Linux-Kernel daraufhin adaptiert werden.

Siehe dazu auch das Mergemem-Projekt

Gegenwärtig sind vor allem effiziente Strategien zum Auffinden identischer Seiten von Interesse.

Voraussetzungen: Linux-Kernel

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Binäres Prolog ist eine stark vereinfachte Prologvariante, die verhältnismäßig einfach zu implementieren ist. Es soll ein Compiler entwickelt werden, der BinWAM-Code erzeugt.

Voraussetzungen: Prologübung

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Die Ablaufmechanismen von Prologmaschinen sollen visualisiert werden. Beispiel 2-dimensionale Darstellung von WAM und VAM.

1. Graphischer Entwurf. Z.B. Wie stellt man Terme, Stacks, Bindungen etc. graphisch dar?
2. Animation. Für den Ablauf einer Prologmaschine beim Beweis eines konkreten Prologziels soll eine Folge von Bildbesschreibungen generiert werden.

Voraussetzungen: Prologübung

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Es soll eine Schnittstelle entworfen werden, um Programmtransformationen in der Programmierumgebung GUPU interaktiv durchführen zu können.

Voraussetzungen: Prologübung

Ulrich Neumerkel (ulrich@complang.tuwien.ac.at, Tel. 58801/18513)

Für die Programmierumgebung GUPU wurde ein spezieller Emacs-Mode entwickelt, der das Entwickeln und Testen von Prologprogrammen unterstützt. Es soll ein allgemeiner einsetzbarer Mode zum Entwickeln und Testen von Prologprogrammen entwickelt werden.

Voraussetzungen: Emacs und Emacs-Lisp

Folgende Personen befassen sich mit diesen Themen:

• Objektorientierte Programmiersprachen
• Programmanalyse
• Source-To-Source Transformation
• ROSE
• PAG

• Codegenerierung
• Forth
• Constraint Logic Programming
• Linux

• Abstrakte Maschinen
• Algorithmen
• Animation
• Anwendungsprogrammierung
• Constraint Logic Programming
• Implementierung logischer Programmiersprachen
• Linux
• Postscript
• Programmanalyse
• Programmtransformationen
• Prolog
• Systemprogrammierung

• Verteilte Systeme
• Coordination Languages
• Parallelverarbeitung
• Datenbanksysteme
• GUI
• Groupware, CSCW
• Internet
• Java
• Netzwerke
• Programmiersprachen
• Security
• Systemprogrammierung

• Objektorientierte Programmiersprachen
• Java
• Compiler
• Interpreter
• Codegenerierung
• Run-Time Code Generation (RTCG)
• Implementierung logischer Programmiersprachen
• Abstrakte Maschinen
• Systemprogrammierung

• Objektorientierte Programmiersprachen
• Typsysteme
• Concurrent Languages
• Coordination Languages