Thesis Proposal in Computer Science/Engineering:
Optimization of Decompositions Based on Space Filling Curves
- Author: tbd
- Examiner: Prof. Dr. Miriam Mehl (IPVS), Dr. Colin Glass (HLRS)
- Advisor: Michael Lahnert (IPVS), Marius Poke (HLRS)
- Start: tbd, End: tbd
Space filling curves linearize multi-dimensional arrays. Such arrays can, for example, represent mesh nodes used for numerical calculation of PDEs. Given a mesh, the space filling curve will create a one-dimensional ordering of the mesh nodes. The ordering preserves, to some degree, the spatial cohesion of the mesh nodes. Therefore, a sequence of nodes in the space filling curve is expected to cluster in space. Moreover, a mesh should be decomposed for parallel execution with two goals in mind: (1) the resulting subdomains should have the same computational load (i.e., load balancing); and (2) the communication effort should be minimal.
Thus the decomposition consist of solving a multi-objective optimization problem, where a solution is simply represented as a selection of points along the curve at which to cut.
The meshes regarded in this Thesis are hierarchically refined – they can have different mesh densities in different areas. Such meshes can still be represented by a space-filling curve, however, the load per mesh point can vary and the communication can depend on the level of refinement of the two neighbouring mesh points. This renders the problem more complex.
The goal of this Thesis is to investigate appropriate models for both load balance and communication and to design an optimization method which can identify an optimal decomposition. To match different problems, the models should be parametrizable. Also, the optimization method must be validated on the basis of simple test cases.
Existing approaches can be found in , , , and .
 P. M. Campbell, K. D. Devine, J. E. Flaherty, L. G. Gervasio, and J. D. Teresco, "Dynamic octree load balancing using space-filling curves", Williams College Department of Computer Science, Technical Report, pp. 1–26, 2003.
 H. Sundar, R. S. Sampath, and G. Biros, "Bottom-up construction and 2:1 balance refinement of linear octrees in parallel", SIAM Journal on Scientific Computing, vol. 30, no. 5, pp. 2675–2708, 2008.
 T. Weinzierl, "A framework for parallel PDE solvers on multiscale adaptive Cartesian grids", PhD thesis, Technische Universität München, 2009.
 C. Burstedde, L. C. Wilcox, and O. Ghattas, "p4est: Scalable algorithms for parallel adaptive mesh refinement on forests of octrees", SIAM Journal on Scientific Computing, vol. 33, pp. 1103–1133, Jan. 2011.
Wissenschaftliche Hilfskraft (HiWi)
Reference: RDMA programming
We are looking for a student with advanced knowledge of C programming and basic understanding of networking (e.g., linux sockets); the position consist of programming on RDMA networks (i.e., InfiniBand).
Modern networks, such as InfiniBand, offer support for Remote Direct Memory Access (RDMA). RDMA allows servers to access memory in the user-space of other servers. The mechanism is based on the concept of Queue Pairs (QPs); each QP is a logical endpoint for a communication channel. Contrary to traditional message-passing mechanisms, the remote access is fully performed by the hardware without any interaction with the OS at the origin or target of the access.
DARE is a replicated state machine protocol that uses RDMA features to ensure highest performance . DARE is implemented in C and relies on two libraries: libibverbs, an implementation of the RDMA verbs for InfiniBand; and libev, a high-performance event loop. Currently, DARE is a proof-of-concept implementation. Therefore, your main tasks are as follows:
increasing DARE's portability (e.g., use the RDMA communication manager for setting up the connection);
testing & debugging;
implementing known mechanisms to increase performance.
enrolled as student
strong background in Linux or Unix
proficiency with C programming
understanding of networking programming
Please direct applications including a short CV which addresses the requirements stated above to marius.poke[at]hlrs.de. Please quote the reference "RDMA programming".
 M. Poke and T. Hoefler. DARE: High-Performance State Machine Replication on RDMA Networks, HPDC, 2015