Topics for Student Theses

The Linux kernel contains the SCHED_DEADLINE CPU scheduler which is based on the Earliest Deadline First (EDF) and Constant Bandwidth Server (CBS) algorithms. SCHED_DEADLINE allows applications to reserve a budget Q every period P for computation, making this CPU-scheduler suitable for mixed hard and soft real-time work.

The goal of this task is to analyse and evaluate the efficacy, effectiveness, and overhead of SCHED_DEADLINE. To this end a selection of benchmarks from the PARSEC benchmark suite has to be ported to the SCHED_DEADLINE interface. The evaluation should include the latency/makespan of well-behaving tasks, as well as tasks overrunning their budget temporarily and permanently. Additionally, the throughput of best-effort scheduled in CFS can be set in relation to latencies achieved by real-time load to create a throughput-latency analysis.

Optionally, the same experiments can be conducted with the ATLAS scheduler1, developed at the operating systems group, to highlight differences in the behaviour of these approaches to schedule real-time work.

Supervisor: Michael Roitzsch, Hannes Weisbach

The ATLAS scheduler1 uses metrics to predict task execution time. However, it is conceivable to use the same or a similar predictor to derive other application- and workload-related measures such as cache behavior, memory accesses, or energy consumption.

The thesis should experiment with the ATLAS predictor to analyse its ability and accuracy in predicting these other measures.

[1] Michael Roitzsch, Stefan Wächtler, Hermann Härtig: ATLAS – Look-Ahead Scheduling Using Workload Metrics. RTAS 2013, https://os.inf.tu-dresden.de/papers_ps/rtas2013-mroi-atlas.pdf

Supervisor: Michael Roitzsch, Hannes Weisbach

Execution time prediction within ATLAS1 is based on metrics. A metric is a value from the application domain, which is required to correlate with the amount of work to be performed. Roitzsch proposed a set of 13 metrics to be used in the execution time prediction of decoding times of H.264-frames. These metrics were embedded as metadata in H.264-streams. An ATLAS-enabled media player would extract these metadata and pass the metrics to the ATLAS runtime. Since the original implementation, FFmpeg experienced a number of changes during its development, so that the original implementation cannot be easily re-used.

This programming-oriented thesis should implement the H.264 metrics handling in a recent version of FFmpeg and export them into an ATLAS-enabled media player (FFplay, for example). The written work should discuss tooling to analyse the FFmpeg code and how to extract the metrics.

Supervisor: Michael Roitzsch, Hannes Weisbach

The K2 I/O scheduler1 was developed at the operating systems group with the goal of isolating disk accesses of low-latency applications from interference by high-bandwidth applications, specifically on modern NVMe drives. Modern NVMe drives achieve their high bandwidth by having multiple disk accesses in flight concurrently. As a down side, any request may be delayed because the drive's firmware deems that request inopportune and postpones request fulfilment, thereby causing latency-spikes for some requests.

K2 mitigates this drive-internal scheduling by limiting the amount of concurrent requests that are issued to the drive. However, limiting the requests in flight impacts total bandwidth negatively. Currently the number of requests that can be in flight is a static, tunable parameter of the K2 I/O scheduler.

The goal of this task is to devise a mechanism that allows this parameter to be adapted at runtime. Additionally, at least one policy to update the queue length value should be devised.

Supervisor: Michael Roitzsch, Hannes Weisbach

The K2 I/O scheduler1 was developed at the operating systems group with the goal of isolating disk accesses of low-latency applications from interference by high-bandwidth applications, specifically on modern NVMe drives. To this end, K2 prioritises requests from real-time applications, with the consequence that currently real-time application(s) can starve background workload.

The goal of this task is to devise a mechanism to control fairness in K2. As a second step at least one policy should be implemented to control fairness.

Supervisor: Michael Roitzsch, Hannes Weisbach

The recently published K2 I/O scheduler1 was developed at our group to reduce access latency on NVMe storage devices for critical workloads. While the original work was published in a real-time context, we believe the benefits of K2 are also applicable to other areas of computing and processing where a critical but relatively low-bandwidth application has to contend with a non-critical, high-bandwidth application for data rate and access latency of local storage.

We imagine Burst Buffer access in HPC systems or workload co-location in Cloud settings to be such contexts. One use of Burst Buffers is the local caching of an application checkpoint before it is written to a parallel file system, while the application continues to run. Co-location of I/O-bound and CPU-intensive workloads on the same machine can be used to boost utilisation and hence increase cost-effectiveness.

Depending on the type of thesis (Bachelor, Master, Diploma) one or more scenarios should be selected, typical workloads chosen, implemented, and evaluated.

Supervisor: Michael Roitzsch, Hannes Weisbach

Applications in high-performance computing (HPC) usually comprise many processes distributed across a cluster of compute nodes. From previous research and experience in Cloud computing, we learn that concurrently running multiple such applications can improve not only overall performance but also system utilisation and, in turn, energy consumption.

We want to employ gang-scheduling1 , a concept well-known in real-time systems, as a distributed system-level scheduler to ensure performance and efficient resource sharing at the same time. Gang scheduling caters to the close interactions among the processes comprising an application by running all of them at the same time.
For scaling to large clusters, gang scheduling needs to utilise the precise clocks available each compute node2: All clocks are synchronised, and the central gang scheduler broadcasts a list of application processes and time slots when they are to run. Node-local schedulers then enforce this schedule based on their local clocks.

The goal of this task is to implement such a distributed gang scheduler. As HPC clusters usually employ predefined system software, the gang scheduler should run entirely in userspace. An important aspect of the task is to investigate different mechanisms for enacting a scheduling decision; e.g. signals3, process groups4, or Linux control groups5.

Supervisor: Jan Bierbaum

M³1 is a new hardware/operating system co-design that targets heterogeneous platforms and provides strong isolation between hardware tiles and software components. On the hardware side, M³ introduces a new hardware component into each tile called trusted communication unit (TCU) to isolate tiles from each other, while supporting cross-tile communication channels. On the software side, M³ uses a microkernel design that places components on different tiles by default.

To share a core among multiple applications, M³ uses a core-local multiplexer, called PEMux, that builds upon lightweight multiplexing features in the TCU. However, PEMux is built for general-purpose cores with virtual-memory support. This thesis should investigate how a multiplexer can be built for a RISC-V-based accelerator with a local scratchpad memory and without virtual-memory support to allow multiple applications to use such an accelerator simultaneously.

Supervisor: Nils Asmussen