Hide menu

OPEN MASTER THESIS PROJECTS

Research Group on Compiler Technology and Parallel Computing at PELAB

Prof. Christoph Kessler

Internal Thesis Projects

Note:

Most projects in this list require a solid background in either compiler construction or parallel programming (some both); at least one major course (preferably at master level including programming labs) in these areas should be passed successfully. Specific prerequisites are listed below.

Note to non-LIU students (FAQ): If you want to do a thesis project with us, you must be registered on a master (or bachelor) program at Linköping University. It is generally not possible to do such projects remotely.

  • Prediction of Task Runtimes and Power Consumption for SkePU Skeleton-Based Parallel Streaming Applications (30hp)

    Many static scheduling approaches, e.g., Crown Scheduling (Melot et al. 2015), require information on the runtime behavior of tasks and the power consumption their execution causes for certain degrees of parallelism and processor core operating frequencies. Accurate data can be obtained via microbenchmarking in individual cases (Litzinger and Keller 2022). Unfortunately, it necessitates a large resource investment due to the myriad of combinatorial possibilities, which can generally only be justified for long-running or widely deployed applications. Thus, there is a desire for abstraction, allowing one to describe a task-based application in terms of, e.g., the SkePU skeletons it makes use of as well as the inputs it processes. This information could then be leveraged to predict the aforementioned quantities on a particular system. Evidently, the underlying data will still have to be gathered via microbenchmarking and subsequently refined by means of adequate performance/power modeling, but it will serve to cover a broad range of applications instead of just a single one, significantly easing the deployment of SkePU-based applications when it comes to scheduling and resource management.

    Task: This project aims at generating accurate runtime and power consumption estimations for parallel tasks in SkePU-based streaming applications. Predictions shall be based on high-level task descriptions and a suitable set of microbenchmarks. It will be necessary to identify relevant task properties and to develop a reliable prediction method. Furthermore, the microbenchmarks serving as an empirical basis will have to be curated and carried out on a distributed test system. Ultimately, the estimator could be inserted into the system's resource manager to improve prediction quality.

    Prerequisites: TDDD56 Multicore and GPU Programming (highly recommended), TDDE65 Programming of parallel computers (recommended), familiarity with C/C++, operating systems (especially Linux), Unix shell (e.g., Bash), ideally experience with SkePU or skeleton-based frameworks in general.

    Contact: Sebastian Litzinger, Christoph Kessler (\verb+first.last@liu.se+)

    Description also available as PDF.


  • Dynamic Task Migration in Generalized Stream Processing Pipelines for Heterogeneous Distributed Systems (30hp)

    Background: We consider distributed soft real-time applications that process continuous data streams such as sensor data or video contents. Such applications can be computationally expensive, and are often organized for parallel processing by pipelining. In heterogeneous parallel and distributed systems, such as the IoT device / edge / cloud continuum, the different pipeline tasks can be internally parallel again and be more or less suitable for running on accelerators such as GPUs. In general, we have for each task multiple equivalent implementations to choose from. These could, for example, be provided by the programmer or generated from a high-level specification, such as SkePU code. SkePU is a C++ based framework for portable high-level programming for heterogeneous parallel systems, developed in our group as an open-source effort.

    Task: In a previous master thesis project, a prototype framework for specifying and deploying pipelines of SkePU-defined tasks has been designed and implemented. The purpose of this thesis project is to make this framework dynamic, i.e., to allow for changing deployment options at runtime while the application pipeline is processing data, without corrupting data or having to restart the computation from the beginning.

    Prerequisites: TDDD56 Multicore and GPU Programming and/or TDDE65 Programming of parallel computers, TDDD25 Distributed systems, Advanced C++ (template metaprogramming), Linux. Also useful: TDDE31 Big data analytics.

    Contact and more information: Christoph Kessler.

    Description also available as PDF


  • Skeleton programming with SkePU and MLIR (30hp)

    Background: High-level parallel programming aims to abstract challenging aspects of parallel and heterogeneous systems for non-expert programmers. Algorithmic skeletons is an interface approach based on computational patterns, such as map, reduce, and stencil operations. These patterns can be instantiated by providing a custom operator ("user-function"), which is then applied to a supplied dataset in parallel according to the particular pattern semantics. Skeleton programming framworks and libraries such as SkePU implement skeletons as C++ constructs and provides "backends" for parallelism in multi-core CPUs, GPU accelerators, and multi-node clusters. The skeletons are typically provided as libraries, or in the case of SkePU, as a framework with both library and a custom pre-compiler toolchain. The pre-compiler is a source-to-source compiler based on LLVM clang. It performs a rather light-weight source code transformation; in particular, generates platform-specific code variants from the user-functions that can be used with the different SkePU back-ends. SkePU is a long-term open-source effort at PELAB, Linköping University.

    MLIR is a rather new, customizable, multi-level intermediate representation (IR) within the LLVM open-source compiler infrastructure. It has become very popular in both academic and industry research and development in recent years. MLIR allows to develop custom, domain-specific as well as device-specific, IR dialects at various levels of abstraction, which are translated into other IR dialects at higher or lower level of abstraction by raising and lowering passes, respectively, eventually lowering down to the LLVM IR from which target code can be generated. Directly controlling the compiler's lowering process for SkePU-specific code constructs is expected to enable new optimization opportunities and provide more independence from the vendor-specific compilers employed in the existing SkePU backends.

    Task: Use the sequential SkePU interface (and header-only implementation) to generate MLIR of existing dialects (e.g., "linalg", "affine", "gpu", "acc") in order to generate optimized and/or parallelized IR. This is then evaluated against the current, textual-replacement-based SkePU backend with regards to performance and portability. A comparison of the two with regards to future extensibility and maintainability should also be conducted.

    Remark: This is an exploratory, research-oriented thesis project. It provides a perfect preparation for compiler-related work in academia or industry.

    Prerequisites: A completed course in compiler construction with labs, such as TDDE66. TDDD56 Multicore and GPU Programming; Advanced Programming in C++; some familiarity with Linux and Cmake.

    Contact: August Ernstsson, Christoph Kessler

    Description also available as PDF


  • Nested Parallelism in Algorithmic Skeleton Programming Frameworks (30hp or 2x30hp)

    Background: High-level parallel programming aims to abstract challening aspects of parallel and heterogeneous systems for non-expert programmers. Algorithmic skeletons is an interface approach based on computational patterns, such as map, reduce, and stencil operations. These patterns can be instantiated by providing a custom operator ("user-function"), which is then applied to a supplied dataset in parallel according to the particular pattern semantics. Skeleton programming framworks and libraries such as SkePU and Muesli implement skeletons as C++ constructs and provides "backends" for parallelism in multi-core CPUs, GPU accelerators, and multi-node clus- ters. This can result in a very high degree of available parallelism in the target system. For simple programs, the skeleton abstraction works well and can utilize the parallelism expressedciently with very few lines of code. However, with more complex applications the choice of the right skeleton patterns to use can be differentcult, and sometimes there are no suitable patterns available in the provided skeleton set.

    Task: This project aims to extend the skeleton abstraction in SkePU and/or Muesli with multi-level or "nested" parallelism. The goal is to investigate whether the option to invoke new skeleton patterns from within a user-function can improve parallelization efficiency, programmer productivity, or both, and in which type(s) of applications this feature is advantageous. The execution context outside and within a skeleton/user-function dif- fer greatly in the implementation of SkePU, which makes the addition of nested parallelism nontrivial. There are open questions regarding the syntax of nested skeleton calls, whether the set of available skeleton calls should be restricted for nested calls (likely to be the case), and how allocation of resources is acted by the introduction of nested parallelism.
    The aim is to incur no overhead from this feature when it is not used, and minimal overhead also for programs using nested parallelism. (It is therefore not advised to dynamically allocate resources during execution of a nested skeleton. Heuristics, static analysis, or other tools could be used to predict a sufficient amount of resources beforehand.)

    Prerequisites:
    Mandatory: Advanced C/C++ programming; Good understanding of parallel programming concepts; Basic GPU programming with CUDA and/or OpenCL.
    Useful: Prior experience with SkePU, e.g. through the TDDD56 lab series.

    Contact August Ernstsson or Christoph Kessler for further information on this project.


  • [taken]Software Testing Methodology and Framework for High-Level Parallel Programs (30hp, 2x30hp, or 16hp)
    SkePU is an open-source programming framework for portable, high-level, single-source programming of heterogeneous parallel computer systems, such as systems with GPU-accelerated multicore CPUs. In SkePU programs, parallelism is expressed using so-called (algorithmic) skeletons, which are generic, high-level programming constructs derived from higher-order functions such as map, reduce, scan, stencil etc., that can be instantiated by customization in problem-specific sequential code, and for which efficient parallel and accelerator-specific implementations are provided. SkePU programs look like well-structured sequential C++ code; instantiated skeletons can be invoked like any manually written C++ function, but inherit all parallel implementations from the different generic parallel implementations (also known as back-ends) of the skeleton.
    Different from most other high-level parallel programming frameworks, the SkePU skeletons are variadic (can take any number of data-container operands) and polymorphic in both operand shape (accepting data-container operands of any shape, i.e., vectors, matrices, tensors) and element type. In addition, many skeletons can also be configured to specialize their behavior. Hence, many possible such combinations may occur in practice. However, only a few of these combinations are currently actually tested for. For SkePU development, it is nevertheless desirable to automatically check that after changes made to a specific data-container shape or a specific skeleton type, SkePU still works consistently across all/many possible combinations. A possible approach to automatizing this is fuzz-testing.
    This thesis project will develop a methodology for systematically generating test cases for SkePU programs and, depending on scope, also realize distributed parallel testing on GPU clusters.
    The project scope and depth can be configured to match a 16hp, 30hp or 2x30hp project.
    This is a research-oriented project. If the result looks publishable, we will encourage you to jointly write and submit a research paper to a conference and support your presentation.
    Prerequisites: Multithreaded (OpenMP) and GPU (CUDA, OpenCL) programming (e.g. TDDD56), advanced C++ programming skills; good background in software engineering, esp. software testing. Linux.
    Contact: Christoph Kessler.


  • Skeleton computing as a service (30hp)

    Background: High-level parallel programming aims to abstract challenging aspects of parallel and heterogeneous systems for non-expert programmers. Algorithmic skeletons is an interface approach based on computational patterns, such as map, reduce, and stencil operations. These patterns can be instantiated by providing a custom operator ("user-function"), which is then applied to a supplied dataset in parallel according to the particular pattern semantics. Skeleton programming frameworks and libraries such as SkePU implement skeletons as C++ constructs and provide "backends" for parallelism in multi-core CPUs, GPU accelerators, and multi-node clusters. The skeletons are typically provided as libraries, or in the case of SkePU, as a framework with both library and a custom compiler toolchain. The SkePU library is implemented in modern C++ and involves template metaprogramming. SkePU is a long-term open-source effort at PELAB, Linköping University.

    Task: This thesis project will develop a method for setting up SkePU skeleton instantiations and computations as microservices on heterogeneous parallel computing resources in the cloud or in edge computing resources for portable remote execution. This includes the specification and generation of efficient interfaces and efficient operand data transfer, the remote deployment of a SkePU microservice with skeleton instantiation and invocation mechanisms, and the evaluation of the implementation for performance, portability, ease of use, and for security weaknesses. The project should also elaborate on suitable (remotely verifiable) restrictions on user functions to be used with such services to avoid security loopholes, and implement a simple rule-based source code checker for user functions to statically verify absence of "dangerous" constructs, or at least avoid known attack patterns with high probability.
    Inspiration for the service implementation can be taken from CORBA and subsequent component-based frameworks, from MapReduce and Spark, and from a recent master thesis project that extended SkePU for execution of stream-parallel applications in distributed systems. An experimental testbed with a number of Raspberry Pi units and GPU-accelerated servers is available for the evaluation.

    Prerequisites: TDDD56 Multicore and GPU Programming (mandatory), a course on Distributed Systems such as TDDD25 (mandatory), Advanced Programming in C++ (mandatory), Linux, operating systems, network programming.

    Contact: Christoph Kessler, August Ernstsson.

    Description also available as PDF.


  • Parallel I/O for skeleton programs in SkePU (30hp or 16hp)
    The C++ based portable skeleton programming framework SkePU for heterogeneous multicore systems and clusters is designed to work on data types usually residing in main memory, so-called data-containers.
    This thesis project will investigate how SkePU data-containers can efficiently interface with the Hadoop Distributed File System HDFS in order to provide distributed parallel I/O on large distributed files. The solution will be prototypically implemented in the open-source SkePU framework and evaluated with several simple big-data analytics computations.
    The project can be configured for Master or Bachelor thesis level.
    Prerequisites: Advanced C++ (esp., template metaprogramming), Big-Data Analytics and/or parallel programming courses, some familiarity with Linux, git, cmake, HDFS.
    Contact: Christoph Kessler.


Further thesis projects for LiU-based students with interest in compiler technology and/or parallel programming are available on request, please contact me.


External Thesis Projects

in cooperation with partners in industry or research institutes


Back to my master thesis students page

More thesis projects at PELAB


Responsible for this page: Christoph Kessler, IDA

Page responsible: Webmaster
Last updated: 2025-09-19