Topics for Student Theses
All topics in this list are available for Bachelor, Diploma, and Master theses. You own topic proposals are welcome as well!
Scheduling
Analysis of Real-Time Scheduling Characteristics in Current Linux Versions
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 [1] scheduler, 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
Using ATLAS to Predict Measures Other Than Execution Time
The ATLAS [1] scheduler 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.
Supervisor: Michael Roitzsch, Hannes Weisbach
ATLAS Integration for Recent FFmpeg
Execution time prediction within ATLAS [1] 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 [2] 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
Dynamic Queue-Length Adaptation on K2
The K2 I/O scheduler [1] 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
Fairness in K2
The K2 I/O scheduler [1] 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
Does I/O Scheduling have a place in Cloud and HPC centres in the age of fast NVMe storage?
The recently published K2 I/O scheduler [1] 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
Virtualization
Multiplexer support for a RISC-V-based accelerator
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