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)

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)

Thema ist der Entwurf und die Umsetzung eines verteilten Spiels fürs Internet. Die Implementierung soll mit Corso, einem Virtual Shared Memory Layer, erfolgen. Dabei ist zu beachten, daß die Spieler im regelmäßigen Abständen miteinander kommunizieren müssen (kooperativ und/oder Kampf um gemeinsame Ressourcen) und daß der "scale-up" beliebig sein soll, d.h., beliebig viele Spieler sollen dynamisch hinzukommen respektive aufgeben können. Ein Netzwerk- oder Systemfehler soll den Spielverlauf nicht beeinträchtigen.

Die Regeln und das Layout des Spiels können selbst erfunden werden. Eine einfache, graphische Oberfläche soll implementiert werden, bevorzugterweise mit Java. Die anderen Teile des verteilten Systems können wahlweise in C/C++ implementiert werden.

Anmerkung: bevorzugterweise ist dieses Praktikum im Team durchzuführen (2-4 StudentInnen).

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

Zu Corso (Virtual Shared Memory für verteilte Systeme) soll ein WEB Interface (graphisches Monitoringtool) geschrieben werden. Zur Zeit gibt es ein Interface, das über eine graphische Console erfolgt, die auf Linux und Windows NT Plattformen läuft. Die Funktionalität der bestehenden Console ist in Form einer Java-Console umzusetzen. Das aktuelle graphische Design kann beibehalten werden.

Voraussetzungen: Java

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

Corso (Virtual Shared Memory für verteilte Systeme) soll um ein graphisches Debug-Tools erweitert werden. Dieses ist in Java zu erstellen. Es besteht bereits ein simples Debug-API, das aber noch keine graphische Oberfläche besitzt. Die Funktionalität dieses APIs soll noch erweitert werden, wobei zu analysieren ist, welche Information über Corso für den Programmierer hilfreich ist.

Voraussetzungen: Java

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

Für Corso (Virtual Shared Memory für verteilte Systeme) sollen Tests entworfen und implementiert werden, die die Belastungsgrenzen dieses Systems ausloten hinsichtlich Performance, benötigte Ressourcen, Skalierbarkeit, etc.

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

Die meisten verteilten Architekturen bestehen aus einem zentralen Server und vielen (fat) Clients, die auf diesen Server zugreifen. Dies führt sehr oft zu einem Bottleneck hinsichtlich Performance, Verügbarkeit und Zuverlässigkeit der verteilten Anwendung. Um dieses Problem zu vermeiden, versucht man, sogenannte thin Clients zu bauen, die Business-Logic in mittlere Schichten zu ziehen und durch Caching den Server zu entlasten und auch damit bessere Performance / Verfügbarkeit zu erreichen.

Es sollen Business-Cases für solche Multi-Tier Architekturen entworfen, implementiert und gebenchmarkt werden. Dabei sind die Vorteile von Shared Objects im Vergleich zu Distributed Objects auszuloten.

Implementierungssprachen: C/C++ und/oder Java.

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

Werkzeuge für verteilte Verarbeitung (sogenannte Middleware Tools wie Corba, DCOM, Corso, etc.) sind zu evaluieren. Konkret sollen mit selbstimplementierten Business-Cases Benchmarks erstellt werden.

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

Die Möglichkeiten zwischen Datenbanken (gleicher, verschiedener) Hersteller Daten auszutauschen sollen analysiert werden. Es sollen selber Lösungsansätze für Gateways erarbeitet werden.

Voraussetzungen: Datenbanksysteme

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

Es wurde tragbare Hardware mit Spracherkennung entwickelt, die inbesondere in Szenarien zum Einsatz kommen soll, wo der mobile Mitarbeiter die Möglichkeit hat, sich mit den anderen MitarbeiterInnen zu synchronieren, Information (zB Videos mit Montage-Informationen) von der Zentrale zu holen, etc.

Es sollen weitere Einsatzgebiete für diese tragbaren Geräte analysiert und die dabei auftretenden Interaktions/Kommunikationsmuster analysiert werden, die 1:1 und 1:n Kommunikation übersteigen.

Die Umsetzung dieser Kommunikationsmuster soll mit Hilfe von Corso (Virtual Shared Memory für verteilte Systeme) realisiert werden.

Es besteht die Möglichkeit einer Industriekooperation.

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

Im Rahmen dieser Arbeit sollen verteilte / mobile Filesysteme (zB. Coda) analysiert werden. Basierend auf diese Erkenntnisse ist ein solches Filesystem zu entwerfen und mit Hilfe von Corso zu implementieren.

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

Im Rahmen dieser Arbeit ist zu überlegen, wie mehrere Benutzer gleichzeitig an einem Spreadsheet arbeiten können (semantische Probleme, gemeinsamer Nutzen, technische Realisierbarkeit, etc.). Der Entwurf ist mit Hilfe von Corso (Virtual Shared Memory für verteilte Systeme), das die Umsetzung diverser Interaktionsmuster von Benutzern gut unterstützt, zu implementieren. Ein Vergleich mit der neuesten Excel Version ist durchzuführen.

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

Das gemeinsame Bearbeiten von Texten in einem Netzwerk erfordert ein passendes kooperatives Tool ("Teameditor"), das einerseits eine wohldefinierte Semantik bei gleichzeitigem Zugriff auf dieselbe Textstelle(n) aufweist. Ein bestehendes Textsystem (WYSIWYG oder auch LaTeX) ist um Kooperation zu erweitern. Die Implementierung soll mit Corso (Virtual Shared Memory für verteilte Systeme) erfolgen, das die Umsetzung diverser Interaktionsmuster von Benutzern gut unterstützt.

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

Corso (Virtual Shared Memory für verteilte Systeme) unterstützt das Persistieren von Daten und Berechnungen. Nach einem Wiederanstart werden automatisch diese Daten und Berechnungen wiederhergestellt resp. angestartet. Dazu ist es notwendig, im laufenden Betrieb in Daten- und Logfiles zu speichern. Der von Corso intern unterstützte Speichermechanismus soll alternativ durch das Speichern in ein bestehendes Datenbanksystem ersetzt werden. ZB. ODBC, SQL Server 7, Oracle 8.

Die dafür notwendigen Anpassungen sind zu analysieren und die Umsetzung ist durchzuführen. Das Ergebnis soll im Rahmen von Benchmarks evaluiert werden.

Voraussetzungen: Datenbanksysteme

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

Corso (Virtual Shared Memory für verteilte Systeme) ist Systemsoftware für missionskritische Anwendungen. System- und/oder Netzwerkfehler werden von Corso maskiert. Im Rahmen dieser Arbeit sollen Teststrategien festgelegt und implementiert werden, die diese Eigenschaft von Corso unter Beweis stellen. Insbesondere ist der Aspekt, daß Teile der Applikation verteilt laufen und daher auch verteilt gesichert werden, zu berücksichtigen.

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

Virtual Shared Memory (VSM) ist ein alternatives und innovatives Paradigma zu Message Passing auf den Gebieten Parallelverarbeitung und verteilte Systeme. Traditionellerweise werden heute Client/Server Technologien eingesetzt und im Rahmen dieser Arbeit sollen von einem technologischen als auch praktischen Standpunkt die typischen Business-Cases für VSM analysiert werden.

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

Im Bereich der Parallelverarbeitung und im Bereich der verteilten Systeme gewinnt Virtual Shared Memory (VSM) zunehmend an Beliebtheit. Es gibt eine Reihen von Prototypsystemen, die im Rahmen dieser Arbeit zu analysieren sind. Wenn möglich (von einigen Systemen sind auch free-ware Prototypimplementierungen verfügbar), sollen diese Systeme auch praktisch erprobt werden.

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

Für das Decodieren von geheimen Schlüsseln sind Algorithmen zu analysieren und die geeignetsten sollen so implementiert werden, daß durch Ausnutzung von Parallelität in einem Netz mehrerer Rechner hohe Performance erreicht wird.

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

Es ist zu analysieren, wie mögliche Einbruchszenarien für Corso (Virtual Shared Memory für verteilte Systeme) aussehen könnten. Corso ist Systemsoftware, die verteiltes Arbeiten im Netz unterstützt. Die Nachrichten, die die einzelnen Corso Server austauschen, werden auf IP Ebene geschickt.

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

Die meistverbreitete Architektur sind Rechner, die durch LAN/WAN Netzwerke miteinander verbunden sind. Obwohl diese Netze keine extrem hohe Performance bieten, ist es möglich, bei geeigneter Zerlegung eines Problems, durch Parallelisierung und Verteilung eine Effizienzsteigerung zu erreichen. Es sind Problemstellungen zu finden und deren Eignung zur Parallelisierung auf Rechnern im Netz zu untersuchen.

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

Die Integration heterogener Datenbanken, sogenannter Legacy Systems die bereits existieren und die in der Organisation beibehalten werden müssen, ist eines der zentralen Themen in der Industrie. Selbst wenn die Datenbanken ein sauberes Two-Phase-Commitment unterstützen, ist dies keine einfache Sache. Im Rahmen dieser Arbeit soll einerseits die Problematik globaler Transaktionskontrolle analysiert werden. Andererseits sollen praktische Datenbankinterfaces implementiert werden (inkludiert die Analyse geeigneter Object-Wrapper für relationale Datenbanken), die eine Integration von Daten aus Datenbanken unterschiedlicher Hersteller erlaubt, möglich machen. Als Basistechnologie für die Integration soll Corso (Virtual Shared Memory für verteilte Systeme) verwendet werden.

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

Im Rahmen dieser Arbeit soll eine neue Koordinationssprache entworfen und implementiert werden, die auf dem Koordinationsparadigma von Corso (Virtual Shared Memory für verteilte Systeme) basiert. Heute gibt es bereits Sprachanbindungen zu C/C++, VisualBasic, Java und Developer2000. Als mögliche Basissprache kann zB. Prolog, PL/I, Fortran, Tcl/Tk, oder Smalltalk gewählt werden. Dabei ist zu beachten, daß das Paradigma des Virtual Shared Memory möglichst gut in die Basissprache integriert wird.

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

Viele Firmen verwenden heute das Internet, um Information über ihre Produkte zu publizieren und um Services dort anzubieten. Dabei tritt das Problem auf, die lokalen Firmen-Daten mit den auf der beim Internet Provider gelagerten Web-Site konsistent zu halten. Die Übertragungszeiten sind teuer und sollen minimal gehalten werden. Wir nehmen an, daß die Daten entweder direkt in (HTML) Files oder in Datenbanken gehalten werden.

Es soll ein geeigneter Mechanismus gefunden und implementiert werden, der ein qualifiziertes Upload/Download zum/vom Internet Provider implementiert. Dafür sollen die von Corso (Virtual Shared Memory für verteilte Systeme) unterstützten Notifikations- und Synchronisationsmechanismen verwendet werden.

Es besteht die Möglichkeit einer Industriekooperation.

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

Im Rahmen dieser Arbeit ist ein Prototyp für ein Call Center zu entwerfen, wobei Internet-Clients zu unterstützen sind. Die Thematik von Call Centers ist zu analysieren sowie bestehende Produkte und Produktideen. Die Erkenntnisse sollen in das Design des zu entwickelnden Prototyps einfliessen.

Es besteht die Möglichkeit einer Industriekooperation.

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

Sicherheit in Netzen ist ein wichtiges Thema. Im Rahmen dieser Arbeit ist zu analysieren, welcher Sicherheitsmechanismus für das von Corso (Virtual Shared Memory für verteilte Systeme) verwendete Kommunikationsprotokoll im Internet am geeignetsten ist. Es soll eine Implementierung durchgeführt und mit Corso integriert werden, wobei wahlweise die Codierung ein/ausgestellt werden kann. Die notwendigen organisatorischen Rahmenbedingungen (woher bekomme ich public Keys, etc.) sollen auch ausdiskutiert werden.

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

Im Rahmen dieser Arbeit sollen Transaktionssysteme und -modelle analysiert werden wie zB Microsoft Transaction Server, XA Standard, Corso Transaction Server, Corba Transactions, etc.

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

Es ist eine verteilte Applikation im Internet zu implementieren, wobei als Basistechnologie Corso (Virtual Shared Memory für verteilte Systeme) verwendet werden soll. Die Implementierung kann in einer der verfügbaren Sprachanbindungen (C/C++, Java, VisualBasic, 4thGL) erfolgen. Die Themenstellung wird gemeinsam diskutiert und sollte in einem Prototypen eines Produkts, das im Internet eingesetzt werden kann und ein praktisches Marktpotential hat, resultieren. Neue Anwendungsgebiete, die durch die Möglichkeiten des Internets eröffnet werden, sind zu beachten.

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

Im Rahmen dieser Arbeit sind Replikationstechniken zu analysieren. Als konkrete Vorgabe ist auch das von Corso (Virtual Shared Memory für verteilte Systeme) verwendetet Replikationsprotokoll zu untersuchen und zu bewerten hinsichtlich Anzahl der Nachrichten, Paketgrößen, Ausfallsicherheit, etc.

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

Das Internet eröffnet eine Reihe neuer Einsatzgebiete. Dazu gehört auch das Kommunizieren zwischen Internet-Benutzern. Im Rahmen dieser Arbeit soll analysiert werden, welche Kommunikations- und Interaktionsformen sinnvoll sind. Praktische Anwendungen wie zB. das gemeinsame Lernen, Arbeiten, etc. sind zu diskutieren.

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

Computer können abstürzen. Auf einem einzelnen Rechner bedeutet das das Ende aller Berechnungen. Auf Rechnern, die über Netzwerke verbunden sind, sollte der Ausfall eines Rechners nicht die gesamte verteilte Berechnung stillegen. Weiters ist zu überlegen, welche Daten Systemabstürze zu überleben haben.

Im Rahmen dieser Arbeit sind diese Anforderungen an Hand von ein paar klassischen verteilten Programmen zu untersuchen. Wir stellen einen Werkzeugkasten zur Verfügung, der bereits Datenpersistenz garantiert sowie die Möglichkeit, Wiederaufsetzpunkte für Berechnungen zu spezifizieren und es somit leicht macht, robuste, verteilte Programme zu schreiben. Focus ist der praktische Erfahrungsgewinn: was bedeutet "Recoverability" für die einzelnen Problemstellungen? Eines unserer DEMO-Beispiele ist etwa ein "recoverable" Primzahlenberechner, bei dem nach Abstürzen jeder Arbeiter wieder seinen alten Job weiterführt. Das Testen soll nicht nur durch SIGNAL schicken, X-Terminal-Ausschalten, sondern auch durch systematische "Fehlerinjektion" erfolgen.

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

Zum Management unserer (so knappen) Zeitressourcen verwenden wir heute ca. A5-große Time Planner und zur Kommunikation von Terminen elektronische Mail. Es soll im Rahmen dieser Diplomarbeit ein Modell entwickelt werden, das das gesamte "Time Planning" elektronisch unterstützt. Memos und Termine sowie über E-Mail empfangene Informationen und Daten sollen integrierbar werden. Ein paar Ideen: Eine Mail kann sofort erledigt werden, oder triggert eine Terminvereinbarung, oder triggert mehrere Folgeaktionen. Eine wichtige Nachricht, ein wichtiger Termin soll nicht übersehen werden können. Der private "Time Planner" soll im Netzwerk als Server agieren, sodaß Kunden automatisch Termine reservieren können. Durch geeignete Regeln kann sich der Besitzer vor unangenehmen Terminen schützen. Wie kann zuätzlich ein "off-line Management" des Time Planners unterstützt werden?

Die Implementierung ist mit Hilfe unseres neuen Werkzeugkastens Corso (Virtual Shared Memory für verteilte Systeme) für verteiltes Programmieren zu realisieren.

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