Software Lab: Parallel Graph Algorithms

We run through the main stages of a typical software development process inspired by practically relevant graph algorithms.

General Information

... on the administrative structure of the lab can be found here.

Topics

Algorithmic Differentiation [2,3,4] is the process of automatically calculating derivatives of computer programs. The derivatives represent sensitivities of the program outputs with respect to its inputs. In the setting of this seminar, we imagine that we want to calculate the entire Jacobian matrix, i.e., all partial derivatives. In order to speed up the computation of a Jacobian matrix of a program, we can split the program into subprograms, calculate the Jacobians of the subprograms, and multiply them together -- this is known as Jacobian chaining. In a recent publication [1], we explored the possibility of running the Jacobian chaining in parallel and the challenges that this brings to the combinatorial optimization of the Jacobian Chaining problem. Two main challenges we want to investigate in seminar:

  1. Given the computational graph of a program, what is the best way to cut it into subprograms? Ideally, we want to cut it where we have as few intermediate variables as possible. Since the vertices in the computational graph represent the intermediate variables, this means we want a vertex min-cut algorithm. 
  2. The combinatorial optimization of the Scheduled Jacobian Chaining problem is done via a dynamic programming heuristic as well as a branch and bound algorithm. The latter produces the matrix bracketing that results in the overall lowest computational cost. This branch & bound algorithm gets very expensive very quickly when we increase the number of subprograms we cut our program into. In order to improve performance, we want to port the branch & bound algorithm to the GPU.

Details on the topics are below.

References

  1. S. Martens and U. Naumann, ‘Scheduled Jacobian Chaining’, in 2025 Proceedings of the Conference on Applied and Computational Discrete Algorithms (ACDA), in Proceedings. , Society for Industrial and Applied Mathematics, 2025, pp. 90–100. doi: 10.1137/1.9781611978759.7.
  2. A. Griewank and A. Walther, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Second. in Other Titles in Applied Mathematics. SIAM, 2008. doi: 10.1137/1.9780898717761.
  3. U. Naumann: The Art of Differentiating Computer Programs. An Introduction to Algorithmic Differentiation. 2012. doi: 10.1137/1.9781611972078.
  4. www.autodiff.org
  5. https://ad-elimination-playground-accadf.pages.stce.rwth-aachen.de

User Requirements

Topic 1. (Vertex/Edge Cuts in Computational DAGs)

Develop a min-cut algorithm that finds the minimal vertex cut in a computational graph. There are the following requirements and constraints:

  • The software must run on the RWTH Compute Cluster as well as on a normal PC.
  • The software must be written in or callable from C++.
  • When the vertex cut cuts through an edge, count that edge towards the size of the cut as well. That means that the algorithm is, in fact, a vertex + edge min-cut algorithm.
  • The algorithm has to be able to find a certain (user-provided) number of minimal cuts at the same time.
  • The algorithm should run in parallel. 
  • The user should be able to set a minimum distance between cuts, which the algorithm has to uphold.

Topic 2. (Scheduled Jacobian Chaining on GPUs)

Develop a Branch & Bound algorithm that solves the Scheduled Jacobian Chaining Problem on an accelerator / GPU. A parallel reference implementation using OpenMP on the CPU exists here: https://github.com/STCE-at-RWTH/Jacobian-Chaining

  • The software must run on the RWTH Compute Cluster as well as on a normal PC that has an accelerator card.
  • The software must be written in or callable from C++.
  • The software must be compatible with NVidia GPUs.

Agenda

  • Kick-off meeting on Oct 17, 2025, 11am in Seminarraum 231, IT Center, Seffenter Weg 23
  • Proposal (PDF slides to info@stce.rwth-aachen.de) by Oct 30, 2025. Presentation on Oct 31, 2025, 1pm in Seminarraum 231
  • Requirements and Design (slides) by Dec 4, 2025. Presentation on Dec 5, 2025, 1pm in Seminarraum 231.
  • Implementation and Final Presentation (slides; access to source repository on git.rwth-aachen.de) by Jan 22, 2026. Presentation on Jan 23, 2026, 1pm in Seminarraum 231 .
  • Publication (PDF report) by Feb 6, 2026.