Oliver's pages

I am more than happy to supervise PhD and Master thesis projects as well as undergraduate and graduate projects in my areas of research.

In the following you find a list of suggested projects. This list is by no means complete and the topics can be adapted to your needs. If you cannot find anything which interests you, but your are in general interested in my areas of research, do not hesitate to contact me and we devise a topic appropriate for you.

(For information on admission, enrolment, scholarships etc. please look at my students page).

One important aspect in the parallelisation of a program is the scheduling of its tasks onto the processors of the parallel system. In the area of task scheduling, the program is represented by a directed acyclic graph called the task graph. The nodes of the graph represent the tasks and the edges between the nodes the dependences, i.e. communications, among the tasks. Weights assigned to the nodes and edges represent their computation and communication costs (time), respectively. The objective of task scheduling is to find a schedule that executes the tasks of the program in minimal time. This is a difficult problem, in fact it is NP-hard, which means that no algorithm has been found yet that can solve it in polynomial time (and it is improbable that such an algorithm can be found). As a consequence, usually heuristics are employed to find near optimal solutions. The research area of task scheduling tries to find better scheduling heuristics and realistic, but simple, models of the program and the target parallel system.
Projects:

The most important parts to parallelise in a program are usually the loops, as they commonly carry the lion's share of the computational load. For the process of parallelisation, a loop can be represented by a directed cyclic graph G=(V,E), where the nodes V represent the tasks of the loop and the edges E the dependences, i.e. communications, between the tasks. Given G, a crucial step of loop parallelisation is the scheduling of G on the processors P, i.e. the mapping of the tasks to the processors and their ordering for execution. Unfortunately, loop scheduling is also a very difficult problem, in fact the general problem is NP-hard. It is a trade-off between maximising the concurrency of the program and minimising the communication costs among tasks. One of the difficulties is that remote communication, i.e. communication between processors, is usually an order of magnitude slower than local communication, i.e. communication between tasks executed on the same processor. As a consequence, the current parallelisation of loops is based on idealised models that are mostly suitable for loops with negligible communication costs or with regular structure.
Projects:

In the area of parallel computing, clusters have gained high popularity during the last decade or so. A cluster is a set of more or less standard computers, which are connected via a Local Area Network (LAN). One of the advantages of such a cluster is the relatively low cost in comparison to more conventional parallel systems. Usually each computer of the cluster has its own operating system and message passing is employed for interprocessor communication.
On the other hand, there is the trend to have dedicated computation hardware for special application areas like signal processing, multimedia, bioengineering, scientific computing etc.. Such hardware can incarnate as vector processors (as in, for example, the EarthSimulator), GPUs (Graphic Processing Units), acceleration boards (e.g. ClearSpeed) etc. A more flexible approach is to use reconfigurable hardware based on FPGAs that can be adapted to the need of the application to be executed.
With the incorporation of FPGAs into workstations these two trends can now be combined. This retains the cost advantage of clusters and the high performance potentials of dedicated hardware.
Unfortunately, there are two major problems that have to be overcome. First, developing a hardware design for a given application is much more complex, time consuming and error prone than programming general purpose processors. Second, it is all but trivial to combine the general purpose processors in such a cluster with the reconfigurable computing capacity of the FPGAs.
This research project intends to study these two problems and therefore has to address several issues:

• Integration of the two different approaches:
  How can the configured FPGA be integrated into the program logic of a typical parallel program, written for example in MPI (Message Passing Interface)?
• Hardware/Software co-design:
  Given an application specification, which parts should be performed in hardware, which in software? Integrated approaches must be investigated (this is current research in our group).
• Dynamic reconfiguration:
  Can and should the hardware be dynamically reconfigured? There will be a trade-off between performance gain and increased development effort.
• Local vs. remote communication:
  Communication between workstations is more expensive than local communication, i.e. between the units within a workstation. How does this circumstance extend to communication between FPGAs in different workstations? In other words, how can the FPGAs of different systems collaborate?

The department recently received two XtremeData XD 1000 development systems (of which one was donated through the University Program award). In these system, an FPGA sits together with a dual-core AMD Opteron processor on a two socket motherboards. Since the FPGA communicates via HyperTransport, the communication interface used by the Opteron processors, it is much better integrated into the system than extension card solutions. As a consequence this opens great opportunities for application areas which were not feasible before.

Writing a program to be executed on a parallel system is complicated. The programmer has to take care of the division of the program into sub-tasks and the correct execution order of these tasks on the parallel system. OpenMP is a standard Application Program Interface (API) that allows for a relatively simple, portable and scalable programming of shared-memory parallel systems. With OpenMP, the source code of the (sequential) program is augmented with directives that advice the compiler on how to generate code for a parallel system.
While OpenMP is powerful, it has no mechanism for dependent tasks, i.e. tasks which must be executed in a certain order. All the data transfer (communication) and synchronisation between the tasks must be hand-coded by the programmer. This is not only complicated and error prone, but it is also not scalable and inflexible. This problem can be overcome with a simple extension to OpenMP for dependent tasks. This extension consists of directives that specify the task and their mutual dependences.
In this project it is intended to implement a source-to-source compiler that transforms an OpenMP program with the above described dependent task extension into a pure OpenMP program.
The compiler shall be written in Java using JavaCC, a compiler generator. The language to be compiled is C/C++ with (extended) OpenMP directives.